計算機存儲管理.ppt

1、存儲管理,本章內容提要,引言 分區(qū)法 分頁技術 分段技術 段頁式技術 虛擬存儲器 請求分頁技術 頁面置換算法 內存塊的分配和抖動問題 請求分段技術 Linux系統(tǒng)的存儲管理,5.1 引 言,內存（Main Memory或Primary Memory或Real Memory）也稱主存，是指CPU能直接存取指令和數(shù)據(jù)的存儲器。,內存在計算機系統(tǒng)中的地位,5.1.1 用戶程序的地址空間,用戶程序的主要處理階段,主要處理階段 編輯 編譯 連接 裝入 運行 有關概念 裝入程序 相對地址或邏輯地址 絕對地址或物理地址 程序裝入內存的方式 絕對裝入方式 可重定位裝入方式 動態(tài)運行時裝入方式,5.1.2 重定

2、位,邏輯地址空間（簡稱地址空間） 由程序中邏輯地址組成的地址范圍 內存空間（也稱物理空間或絕對空間） 由內存中一系列存儲單元所限定的地址范圍 重定位 程序和數(shù)據(jù)裝入內存時，需對目標程序中的地址進行修改。這種把邏輯地址轉變?yōu)閮却嫖锢淼刂返倪^程稱作重定位 重定位方式 靜態(tài)重定位 動態(tài)重定位,1靜態(tài)重定位 目標程序裝入內存時進行地址變換,程序裝入內存時的情況,靜態(tài)重定位示意圖,優(yōu)點 :無需增加硬件地址轉換機構 主要缺點 :位置“釘死”；不便共享,2動態(tài)重定位 程序執(zhí)行期間進行重定位,動態(tài)重定位示意圖,主要優(yōu)點：位置可變，不必連續(xù) ；易于共享 主要缺點 ：需要附加硬件支持 ；軟件算法比較復雜,5.1.

3、3 對換技術,對換兩個進程示意圖,多道程序對換技術示例,5.2 分區(qū)法,分區(qū)分配是為支持多道程序運行而設計的一種最簡單的存儲管理方式。 5.2.1 固定分區(qū)法 分區(qū)個數(shù)固定不變，大小固定不變 劃分分區(qū)方式： 等分方式 差分方式,固定分區(qū)法,固定分區(qū)管理示意圖,分區(qū)說明表,優(yōu)點：管理方式簡單，所需操作系統(tǒng)軟件和處理開銷都小 缺點 ：內存空間利用率不高，碎片嚴重； 活動進程數(shù)目受限； 無法預知所需內存大小,5.2.2 動態(tài)分區(qū)法,1分區(qū)的分配,MVT的內存分配和進程調度情況,操作系統(tǒng)內部設置一個 內存登記表,動態(tài)分區(qū)法,2數(shù)據(jù)結構 常用的數(shù)據(jù)結構形式： （1）空閑分區(qū)表 （2）空閑分區(qū)鏈 使用鏈指

4、針把所有的空閑分區(qū)鏈接成一條鏈,3分配算法,（1）最先適應算法 空閑表是按地址排列的（即空閑塊地址小的，在表中的序號也?。?。 （2）最佳適應算法 空閑表是以空閑分區(qū)的大小為序、按增量形式排列的，即小塊在前，大塊在后。 （3）循環(huán)適應算法 最先適應算法的變種。它不從空閑表的開頭查找，而從上次找到的可用分區(qū)的下一個空閑分區(qū)開始查找，從中選擇滿足大小要求的第一個空閑分區(qū)。,分配算法,三種算法分配16KB空閑分區(qū)之前和之后的內存配置情況,4. 碎片問題 “碎片”或“零頭”： 內存中這種容量太小、無法利用的小分區(qū) 內部碎片： 在一個分區(qū)內部出現(xiàn)的碎片（即被浪費的空間），如固定分區(qū)法會產生內部碎片。 外部

5、碎片： 在所有分區(qū)之外新增的碎片,5.2.3 可重定位分區(qū)分配,1緊縮 緊縮（或拼湊） 可重定位分區(qū)法 緊縮時機 釋放所占分區(qū)時 分配進程分區(qū)時,可重定位分區(qū)的緊縮示意圖,2動態(tài)重定位的實現(xiàn)過程 動態(tài)重定位經常用硬件實現(xiàn) 硬件支持 基址寄存器 限長寄存器,動態(tài)重定位的實現(xiàn)過程,3. 可重定位分區(qū)法的優(yōu)缺點,優(yōu)點： 可以消除碎片，能夠分配更多的分區(qū)，有助于多道程序設計，提高內存的利用率。 缺點： 緊縮花費了大量CPU時間 當進程大于整個空閑區(qū)時，仍要浪費一定的內存 進程的存儲區(qū)內可能放有從未使用的信息 進程之間無法對信息共享,5.3 分頁技術,5.3.1 分頁存儲管理的基本概念 （1）邏輯空間分

6、頁 （2）內存空間分塊 內存塊或頁框 （3）邏輯地址表示,分頁技術的地址結構示意圖,給定的邏輯地址是A，頁面的大小為L，則頁號p和頁內地址d可按下式求得 p = INT(A/L) , d = A MOD L 式中，INT是向下整除的函數(shù)，MOD是取余函數(shù)。,分頁存儲管理的基本概念,（4）內存分配原則 以塊為單位 每個頁面對應一個內存塊 內存塊可不連續(xù),分頁存儲管理系統(tǒng)示意圖,（5）頁表,實現(xiàn)從頁號到物理塊號的地址映射,分頁存儲管理的基本概念,（6）內存塊表 整個系統(tǒng)有一個內存塊表。每個內存塊在內存塊表中占一項，表明該塊當前空閑還是已分出去了。,分頁存儲管理的基本概念,5.3.2 分頁系統(tǒng)中的地

7、址映射,分頁系統(tǒng)的地址轉換機構,每個進程平均有半個頁面的內部碎片,5.3.3 頁面尺寸,折中方案 設進程的平均大小為s字節(jié)，頁面尺寸為p字節(jié)，每個頁表項占e字節(jié)。那么，每個進程需要的頁數(shù)大約為s/p， 占用 s . e /p 字節(jié)的頁表空間。 每個進程的內部碎片平均為p/2。 因此，由頁表和內部碎片帶來的總開銷是：,總開銷=,5.3.4 硬件支持,由硬件實現(xiàn)頁表的方式有多種，最簡單的方式是由一組專門的寄存器來實現(xiàn)。 通常將頁表保存在內存中，由一個頁表基址寄存器PTBR指向該頁表。整個系統(tǒng)只有一個PTBR。 帶來存取速度下降的矛盾 聯(lián)想存儲器，也稱快表（或Translation Lookasid

8、e Buffer, TLB）。快表每項包括鍵號和值兩部分，鍵號是當前進程正在使用的某個頁面號，值是該頁面所對應的物理塊號。,利用快表實現(xiàn)地址轉換示例,硬件支持,命中率 在快表中成功找到指定頁號的次數(shù)占總搜索次數(shù)的百分比,5.3.5 保護方式,（1）利用頁表本身進行保護 （2）設置存取控制位 （3）設置合法標志,5.3.6 頁表的構造,1多級頁表 大多數(shù)現(xiàn)代計算機系統(tǒng)都支持非常大的邏輯地址空間，如232 264。在這種情況下，只用一級頁表會使頁表變得非常大。 一種方法是利用兩級頁表，即把頁表本身也分頁。,兩級頁表地址結構示意圖,兩級頁表結構示意圖,多級頁表,兩級頁表結構的地址轉換,多級頁表,三級

9、頁表地址結構示意圖,多級頁表,2散列頁表（Hashed Page Table） 以頁號作為參數(shù)形成散列值。散列表中每一項有一個鏈表，它把有相同散列值的元素鏈接起來。每個鏈表元素由三部分組成： 頁號 對應的內存塊號 指向鏈表中下一個元素的指針,散列頁表,散列頁表構成及地址轉換過程,3倒置頁表,它是按內存塊號排序的，每個內存塊占有一個表項。每個表項包括存放在該內存塊中頁面的虛擬頁號和擁有該頁面的進程標識符。,倒置頁表構成及地址轉換過程,5.3.7 頁面共享,可再入代碼（或純碼）：在其執(zhí)行過程中本身不做任何修改的代碼，通常由指令和常數(shù)組成,三個進程共享大小為三個頁面的編輯器的情況，每個進程都有自己的

10、私有數(shù)據(jù)頁。,頁面共享示例,5.4 分段技術,5.4.1 分段存儲管理的基本概念,分段地址空間,1分段 段是一組邏輯信息的集合。 每段都有自己的名字、長度。 段號,2程序的地址結構,邏輯地址要用兩個成分來表示： 段號s和段內地址d 進程的邏輯地址空間是二維的,分段技術地址結構示意圖,3內存分配,內存以段為單位進行分配，每段單獨占用一塊連續(xù)的內存分區(qū)。各分區(qū)的大小由對應段的大小決定。 4段表和段表地址寄存器 系統(tǒng)為每個進程建立一個段映射表，簡稱“段表”。每個段在段表中占有一項，段表項中包含段號、段長和段起始地址（又稱“基址”）等。 系統(tǒng)還要建立一個段表地址寄存器。它有兩部分： 該段表在內存的起始

11、地址 該段表的長度。,5分頁和分段的主要區(qū)別, 頁是信息的物理單位 段是信息的邏輯單位 頁的大小是由系統(tǒng)確定的 段的長度因段而異 分頁的進程地址空間是一維的 分段的進程地址空間是二維的 分頁系統(tǒng)很難實現(xiàn)過程和數(shù)據(jù)的分離 分段系統(tǒng)卻可以很容易實現(xiàn)這些功能,5.4.2 地址轉換,分段地址轉換過程,5.4.3 段的共享和保護,1段的共享 共享是在段一級實現(xiàn)的，任何共享信息可以單獨成為一段。 也可以只共享部分程序。,分段系統(tǒng)中段的共享,2段的保護,段的保護措施包括以下三種： 存取控制 段表本身可起保護作用 表項中設置該段的長度限制 段長 段表地址寄存器中有段表長度的信息 保護環(huán),5.5 段頁式技術,5

12、.5.1 段頁式存儲管理的基本原理 等分內存 地址空間分段 段內分頁 邏輯地址結構 內存分配 段表、頁表和 段表地址寄存器,段頁式存儲邏輯地址結構示意圖,5.5.2 地址轉換過程,段頁式系統(tǒng)的地址轉換機構,5.6 虛擬存儲器,5.6.1 虛擬存儲器的概念 進程在執(zhí)行之前要全部裝入內存，這種限制是不合理的。 程序中往往含有不會被執(zhí)行的代碼 分配的內存空間會大于它們的實際需要 一個程序的某些選項和特性可能很少使用 程序的執(zhí)行過程也顯示出局部性 按需分別調入內存會帶來兩點好處： 用戶編制程序時不必考慮內存容量的限制 在一定容量的內存中就可同時裝入更多的進程,虛擬存儲器（Virtual Memory）

13、 用戶能作為可編址內存對待的虛擬存儲空間，它使用戶邏輯存儲器 與物理存儲器分離，是操作系統(tǒng)給用戶提供的一個比真實內存空間大得多的地址空間。 實現(xiàn)虛擬存儲技術的物質基礎 二級存儲器結構 動態(tài)地址轉換機構（DAT） 虛擬存儲器實質上是把用戶地址空間和實際的存儲空間區(qū)分開來。 它主要受到兩方面的限制： 指令中表示地址的字長 外存的容量,虛擬存儲器的概念,5.6.2 虛擬存儲器的特征 虛擬擴充 部分裝入 離散分配 多次對換,5.7 請求分頁技術,5.7.1 請求分頁存儲管理的基本思想 是在單純分頁技術基礎上發(fā)展起來的 二者的根本區(qū)別在于請求分頁提供虛擬存儲器。 基本思想是： 當一個進程的部分頁面在內存

14、時就可調度它運行；在運行過程中若用到的頁面尚未在內存，則把它們動態(tài)換入內存。 為了標示進程的頁面是否已在內存，在每個頁表項中增加一個標志位。,5.7.2 硬件支持及缺頁處理,1頁表機制 頁表項通常包含下列5種信息：,典型的頁表表項示意圖,2缺頁中斷機構,指令執(zhí)行步驟與 缺頁中斷處理過程,5.7.3 請求分頁技術的性能,缺頁率p：表示缺頁中斷的概率（0p1） 等于缺頁次數(shù)與全部訪問內存次數(shù)之比 有效存取時間可表示為： 有效存取時間= (1-p)ma + p缺頁處理時間,缺頁導致以下一系列動作（設當前進程為A）： 捕俘進入操作系統(tǒng) 保存進程A的各個寄存器和進程狀態(tài)信息 確定該中斷是缺頁引起的 檢查

15、對該頁的訪問是合法的，并確定該頁在磁盤上的地址 把該頁從盤上讀到空閑內存塊中，其中包括在設備隊列中等待，直至該請求得到服務；等待盤尋道以及潛在時間；把該頁傳送到空閑內存塊。 在等待盤I/O完成時，把CPU分給其他進程（如進程B） 盤I/O完成，發(fā)出盤中斷 保存進程B的用戶寄存器和進程狀態(tài) 確定該中斷來自磁盤 調整頁表和其他表格，標明所需頁已放入內存 進程A就緒，等待分配CPU 調度到進程A，則恢復它的各寄存器、進程狀態(tài)和新的頁表，然后重新執(zhí)行前面被中斷的指令。,請求分頁技術的性能,缺頁中斷處理所花費的時間主要有以下三部分： 處理缺頁中斷的時間 調入該頁的時間 重新啟動該進程的時間 將頁面從盤上

16、讀到內存所花費的時間包括： 磁盤尋道時間（即磁頭從當前磁道移至指定磁道所用的時間） 旋轉延遲時間（即磁頭從當前位置落到指定扇區(qū)開頭所用的時間） 數(shù)據(jù)傳輸時間 典型磁盤的旋轉延遲時間約為8 ms，尋道時間約為15 ms，傳輸時間是1 ms。,請求分頁技術的性能,5.8 頁面置換算法,5.8.1 頁面置換 1頁面置換過程,頁面置換過程,2頁面走向,抖動 頻繁地更換頁面,以致系統(tǒng)的大部分時間花費在頁面的調度和傳輸上。 盡量避免系統(tǒng)“抖動” 存儲訪問序列也叫頁面走向 對于給定的頁面大小，僅考慮其頁號，不關心完整的地址。 如果當前對頁面p進行了訪問，那么，馬上又對該頁訪問就不會缺頁。這樣連續(xù)出現(xiàn)的同一頁

17、號就簡化為一個頁號。 如下地址序列（用十進制數(shù)表示）： 0100，0432，0101，0612，0102，0103，0104，0101，0611，0102， 0103，0104，0101，0610，0102，0103，0104，0101，0609，0102，0105 若每頁100個字節(jié)，則頁面走向簡化為： 1，4，1，6，1，6，1，6，1，6，1,一般來說，隨著可用塊數(shù)的增加，缺頁數(shù)將減少。,缺頁量與內存塊數(shù)關系圖,統(tǒng)一采用下述頁面走向： 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 并且假定每個作業(yè)只有三個內存塊可供使用。,頁面走向,5.8.2 先進先出法

18、（FIFO）,總是淘汰在內存中停留時間最長（年齡最老）的一頁，即先進入內存的頁，先被換出。,FIFO頁面置換序列,總共有15次缺頁,優(yōu)點：容易理解，方便程序設計。 缺點： 性能并不很好，效率不高 存在Belady異常現(xiàn)象，即缺頁率隨內存塊增加而增加,關于一個頁面走向的FIFO淘汰算法的缺頁曲線,先進先出（FIFO）法,5.8.3 最佳置換法（OPT）,最佳置換算法（Optimal Replacement, OPT）其實質是：為調入新頁面而必須預先淘汰某個老頁面時，所選擇的老頁面應在將來不被使用，或者是在最遠的將來才被訪問。,保證有最小缺頁率 OPT算法在實現(xiàn)上有困難,最佳頁面置換序列 僅出現(xiàn)9

19、次缺頁中斷,5.8.4 最近最少使用置換法（LRU）,以“最近的過去”作為“不久將來”的近似 實質是：當需要置換一頁時，選擇在最近一段時間里最久沒有使用過的頁面予以淘汰。,最近最少使用算法頁面置換序列,產生12次缺頁,LRU算法需要實際硬件的支持。實現(xiàn)時的問題是：怎樣確定最后訪問以來所經歷時間的順 序。有以下兩種可行的辦法： 計數(shù)器 棧,最近最少使用置換法,利用棧記錄目前訪問最多的頁面示例,5.8.5 第二次機會置換法（SCR）,第二次機會置換法（Second Chance Page Replacement, SCR）是對FIFO算法的改進 避免把經常使用的頁面置換出去。 當選擇某一頁面置換時

20、，就檢查最老頁面的引用位：如果是0，就立即淘汰該頁；如果該引用位是1，就給它第二次機會。,第二次機會法示例,5.8.6 時鐘置換法（Clock）,簡單時鐘置換法,該算法又稱最近未使用置換法（Not Recently Used, NRU）,改進的時鐘置換法 在頁表項中設置兩個狀態(tài)位： 引用位和修改位,時鐘置換法示意圖,5.8.7 最少使用置換法（LFU）,最少使用（Least Frequently Used，LFU）頁面置換算法是基于訪問計數(shù)的頁面置換法。 為每個頁面設置一個軟件計數(shù)器 將每頁的引用位R的值加到對應的計數(shù)器上。發(fā)生缺頁時，淘汰其計數(shù)值最小的頁。 老化（Aging）算法,5.8.8

21、 頁面緩沖算法,頁面緩沖算法（Page Buffering）是對FIFO簡單置換算法的改進。該算法維護兩個鏈表：一個是空閑頁鏈表，另一個是修改頁鏈表。 當發(fā)生缺頁時，按照FIFO算法選取一個淘汰頁，并不是拋棄它，而是把它放入兩個鏈表中的一個。如果該頁未被修改，就放入空閑頁鏈表中；否則，把它放入修改頁鏈表中。 駐留集：進程在內存映像的集合,5.9 內存塊的分配和抖動問題,5.9.1 內存塊的分配 1最少內存塊數(shù) 分給每個進程的最少內存塊數(shù)是指保證進程正常運行所需的最少內存塊數(shù)，它是由指令集結構決定的。 2內存塊的分配 固定分配策略分配給進程的內存塊數(shù)是固定的，且在最初裝入時（即進程創(chuàng)建時）確定塊

22、數(shù)。 可變分配策略允許分給進程的內存塊數(shù)隨進程的活動而改變。,頁面置換范圍 全局置換允許一個進程從全體存儲塊的集合中選取淘汰塊，盡管該塊當前分配給其他進程，還是能強行占用。 局部置換是每個進程只能從分給它的一組內存塊中選擇淘汰塊。 局部置換可與固定分配策略相結合 局部置換可與可變分配策略相結合 全局置換只能與可變分配策略相結合,內存塊的分配,3分配算法 （1）等分法內存塊按進程平分 （2）比例法 設進程pi的地址空間大小為si，則總地址空間為 S=si 若可用塊的總數(shù)是m，則分給進程pi的塊數(shù)是 ai m . si /S （3）優(yōu)先權法給高優(yōu)先級進程分配較多內存,5.9.2 抖動問題,整個系統(tǒng)

23、的頁面替換非常頻繁，以致大部分機器時間都用在來回進行的頁面調度上，只有一小部分時間用于進程的實際運算。這種局面稱為系統(tǒng)“抖動（Thrashing）”。 1產生抖動的原因 內存 不足 多道程序度高 CPU的利用率太低,CPU利用率與多道程序度之間的關系,2防止抖動的方法 采用局部置換策略 利用工作集策略防止抖動 掛起某些進程 采用缺頁頻度法（Page Fault Frequency, PFF）,缺頁頻度的上限和下限,3工作集 測試表明，虛擬存儲系統(tǒng)的有效操作依賴于程序中訪問的局部化程度。 （1）局部性模型 時間局部化是指一旦某條指令或數(shù)據(jù)被訪問過，它往往很快又被再次訪問。 空間局部化是指一旦某個位置被訪問過，它附近的位置也可能很快要用到。