10 課件資料李紅衛(wèi)-操作系統(tǒng)001OS-ch5

1、,江蘇理工學(xué)院,授課教師: 李紅衛(wèi),操作系統(tǒng),目錄,操作系統(tǒng),操作系統(tǒng),第5章 存儲管理,本章學(xué)習(xí)計算機存儲系統(tǒng)的層次結(jié)構(gòu)、存儲管理的基本概念、分區(qū)存儲管理方案；重點學(xué)習(xí)分頁式與請求頁式存儲管理方案、分段與段頁式存儲管理技術(shù)以及虛擬存儲管理技術(shù)的具體實現(xiàn)方法；簡單了解Linux操作系統(tǒng)的存儲管理技術(shù)。,內(nèi)容提要,教學(xué)目標(biāo),本章了解計算機系統(tǒng)的分級存儲體系、地址映射的基本概念與實現(xiàn)方法、分區(qū)存儲管理的有關(guān)概念與實現(xiàn)方法，重點掌握分頁式存儲管理、請求頁式存儲管理以及分段式、段頁式存儲管理的基本原理和相關(guān)技術(shù)。,5.1 存儲管理概述,5.1.1 計算機存儲系統(tǒng)分層結(jié)構(gòu) 存儲系統(tǒng)： 分層結(jié)構(gòu)模式 特點

2、： 速度（高速低速） 價格（高價低價） 容量（小容量大容量）,圖 5-1 計算機存儲系統(tǒng)的分層結(jié)構(gòu),5.1 存儲管理概述,5.1.2 用戶程序的處理過程,編譯：將用戶源代碼編譯成若干個目標(biāo)模塊 鏈接：將目標(biāo)代碼及其庫函數(shù)鏈接成裝入模塊 裝入：將裝入模塊裝入內(nèi)存,5.1 存儲管理概述,5.1.3 存儲管理的基本概念,1. 地址空間與邏輯地址 名字空間：存放源程序的空間 地址空間：目標(biāo)程序所占有的地址范圍 邏輯地址：各個地址以“0” 為參考地址順序編址（相對于0的地址，故又稱為相對地址 ）,5.1 存儲管理概述,5.1.3 存儲管理的基本概念,2. 存儲空間與物理地址 存儲空間：主存中全部物理單元

3、的集合 物理地址：存儲器里以字節(jié)為單位存儲信息， 每一個字節(jié)單元所給予的一個惟一的編號 由于它并不和任何相對地址相關(guān)，又被稱為絕對地址,5.1 存儲管理概述,5.1.3 存儲管理的基本概念,3. 地址重定位,5.1 存儲管理概述,5.1.3 存儲管理的基本概念,3. 地址重定位 靜態(tài)重定位：在用戶程序運行之前，由裝入程序把用戶程序中的相對地址全部轉(zhuǎn)換為存儲空間的絕對地址,5.1 存儲管理概述,5.1.3 存儲管理的基本概念,3. 地址重定位 動態(tài)重定位：在程序執(zhí)行過程中動態(tài)地進行地址轉(zhuǎn)換的方式,5.1 存儲管理概述,5.1.3 存儲管理的基本概念,4.存儲器共享 允許多個進程共享主存中的同一個

4、區(qū)域 共享區(qū)域可以是數(shù)據(jù)、程序代碼等 共享的程序必須是可重入程序（純代碼 ） 存儲器共享目的： 節(jié)省內(nèi)存空間，提高內(nèi)存利用率 通過數(shù)據(jù)共享實現(xiàn)進程通信,5.1 存儲管理概述,5.1.3 存儲管理的基本概念,5. 存儲器保護 防止地址越界 進程運行時所產(chǎn)生的所有訪問地址都必須被檢查，以確保只訪問為該進程分配的存儲空間 正確存取內(nèi)存 進程訪問公共區(qū)域時，檢查進程對內(nèi)存的操作方式，防止由于誤動作而破壞被存儲的內(nèi)容,5.2 分區(qū)存儲管理,5.2.1 單一連續(xù)區(qū)存儲管理,1. 內(nèi)存分配 整個內(nèi)存劃分為兩個區(qū)： 系統(tǒng)區(qū)：分配給操作系統(tǒng)專用的一個固定分區(qū) 用戶區(qū)：剩余的其它內(nèi)存區(qū)域,5.2 分區(qū)存儲管理,5

5、.2.1 單一連續(xù)區(qū)存儲管理,2.地址映射 采用靜態(tài)重定位 3. 存儲保護 使用界限寄存器保護法,5.2 分區(qū)存儲管理,5.2.2 固定分區(qū)存儲管理,1. 劃分方法 預(yù)先把可分配的主存空間分割成若干個連續(xù)的區(qū)域，每個區(qū)域的大小可以相同，也可以不同 每個用戶進程裝入連續(xù)的存儲區(qū)域,5.2 分區(qū)存儲管理,5.2.2 固定分區(qū)存儲管理,2. 分配與回收 系統(tǒng)設(shè)置 “主存分配表”，記錄各分區(qū)的信息及當(dāng)前使用情況,5.2 分區(qū)存儲管理,3. 地址映射 一般采用靜態(tài)重定位 分配某一個分區(qū)時，將該作業(yè)程序指令中的相對地址與該分區(qū)的起始地址相加，得到相應(yīng)的絕對地址 也可采用動態(tài)重定位,5.2.2 固定分區(qū)存儲

6、管理,5.2 分區(qū)存儲管理,5.2.2 固定分區(qū)存儲管理,固定分區(qū)存儲管理動態(tài)重定位,5.2 分區(qū)存儲管理,5.2.2 固定分區(qū)存儲管理,固定分區(qū)存儲管理的優(yōu)缺點 優(yōu)點 技術(shù)簡單，需要的硬件支持少 支持多道程序工作 缺點 “內(nèi)部碎片”降低了內(nèi)存的利用率,5.2 分區(qū)存儲管理,5.2.3 可變式分區(qū)存儲管理,1. 分配與回收 作業(yè)進入主存執(zhí)行之前并不建立分區(qū)，當(dāng)要裝入一個作業(yè)時，根據(jù)作業(yè)需要的主存量查看主存中是否有足夠的空間，若有，則按需要量分割一個分區(qū)分配給該作業(yè)；若無，則令該作業(yè)等待主存空間,也稱為動態(tài)分區(qū)分配，根據(jù)作業(yè)的實際需求動態(tài)地劃分內(nèi)存的分區(qū),5.2 分區(qū)存儲管理,5.2.3 可變式

7、分區(qū)存儲管理,可變式存儲管理的工作原理,5.2 分區(qū)存儲管理,5.2.3 可變式分區(qū)存儲管理,主存的分配與回收,5.2 分區(qū)存儲管理,5.2.3 可變式分區(qū)存儲管理,外部碎片 可變分區(qū)隨著作業(yè)對存儲區(qū)域的不斷申請與釋放，將使分區(qū)的數(shù)目逐漸增加，每個分區(qū)的長度會逐步減小，同時也導(dǎo)致空閑分區(qū)越來越小，使得空閑分區(qū)滿足作業(yè)存儲要求的能力下降，甚至有可能分配不出去 外部碎片(外零頭)：無法分配給用戶使用的空閑分區(qū) 內(nèi)部碎片(內(nèi)零頭)：分配給了用戶而未被用戶完全利用的空閑部分 空閑分區(qū)的合并是解決外部碎片的有效途徑,5.2 分區(qū)存儲管理,5.2.3 可變式分區(qū)存儲管理,2. 空閑分區(qū)的合并,5.2 分區(qū)

8、存儲管理,5.2.3 可變式分區(qū)存儲管理,3. 可變分區(qū)分配算法 首次適應(yīng)算法（First fit） 把最先找到的能滿足作業(yè)存儲要求的那個空閑分區(qū)分配給作業(yè) 要求空閑分區(qū)鏈以地址遞增的順序鏈接 分配方法：鏈?zhǔn)?第一個大小滿足的空閑分區(qū)分配,5.2 分區(qū)存儲管理,5.2.3 可變式分區(qū)存儲管理,3. 可變分區(qū)分配算法 首次適應(yīng)算法（First fit） 缺點 每次分配都需要從鏈?zhǔn)滓簿褪堑偷刂烽_始查找 低地址容易形成多個過小分區(qū)成為外部碎片 大分區(qū)逐漸分割成許多小分區(qū)，對大作業(yè)不利 小分區(qū)增加了查尋時的判斷時間，降低了分配的效率,5.2 分區(qū)存儲管理,5.2.3 可變式分區(qū)存儲管理,3. 可變分區(qū)

9、分配算法 循環(huán)首次適應(yīng)算法（Next fit） 增加一個起始查尋指針，不再每次都從鏈?zhǔn)组_始查找 找到適當(dāng)分區(qū)后，按首次適應(yīng)算法的分配方式進行分區(qū)劃分 優(yōu)缺點：減少了查尋次數(shù)，但缺失大空閑分區(qū),5.2 分區(qū)存儲管理,5.2.3 可變式分區(qū)存儲管理,3. 可變分區(qū)分配算法 最佳適應(yīng)算法（Best fit） 從所有能夠滿足作業(yè)要求的空閑分區(qū)中找到一個最小的分區(qū)分配給申請作業(yè) 要求分區(qū)鏈按照分區(qū)容量從小到大遞增的順序形成空閑分區(qū)鏈 分配時從鏈?zhǔn)组_始查找，找到第一個大小作業(yè)申請空間大小最接近的分區(qū)予以分配,5.2 分區(qū)存儲管理,5.2.3 可變式分區(qū)存儲管理,3. 可變分區(qū)分配算法 最佳適應(yīng)算法（Bes

10、t fit） 優(yōu)點 查找次數(shù)少，為分區(qū)數(shù)的一半 可避免把大的空閑分區(qū)分割成小的空閑分區(qū) 缺點 每次分配一個分區(qū)會造成一個無法再利用的小空閑區(qū),5.2 分區(qū)存儲管理,5.2.3 可變式分區(qū)存儲管理,3. 可變分區(qū)分配算法 最壞適應(yīng)算法（Worst fit） 從所有能夠滿足作業(yè)要求的空閑分區(qū)中找到一個最大的分區(qū)分配給申請作業(yè) 需要將空閑分區(qū)鏈按照分區(qū)容量從大到小遞減的順序排列 分配時從鏈?zhǔn)组_始，若鏈?zhǔn)追謪^(qū)大小不滿足，則可以肯定不存在能夠滿足要求的分區(qū),5.2 分區(qū)存儲管理,5.2.3 可變式分區(qū)存儲管理,3. 可變分區(qū)分配算法 最壞適應(yīng)算法（Worst fit） 優(yōu)點： 查找速度快 分區(qū)碎片少 缺

11、點： 會缺失大分區(qū),5.2 分區(qū)存儲管理,5.2.3 可變式分區(qū)存儲管理,可變分區(qū)分配算法示例,5.2 分區(qū)存儲管理,5.2.3 可變式分區(qū)存儲管理,4. 地址映射與存儲保護,5.2 分區(qū)存儲管理,5.2.4 可變式分區(qū)存儲管理,1. 內(nèi)存碎片與移動 存儲移動(存儲緊縮):將內(nèi)存中使用的區(qū)域經(jīng)過移動集中到內(nèi)存的某一個區(qū)域，使碎片集中到一個區(qū)域形成較大的可使用空閑空間 移動技術(shù)可以消除碎片，但增加了系統(tǒng)的開銷,5.3 內(nèi)存擴充技術(shù),5.3.1 覆蓋（Overlay）,覆蓋：將程序進行分割，將經(jīng)常活躍的部分常駐內(nèi)存，其余部分按調(diào)用關(guān)系分段，形成一個或多個覆蓋，每個覆蓋是一個相對獨立的程序單位 采用

12、覆蓋技術(shù)后，作業(yè)可以分為常駐內(nèi)存部分和覆蓋部分 常駐內(nèi)存部分：作業(yè)處理過程中始終需要的程序段 覆蓋部分：作業(yè)處理過程中動態(tài)調(diào)入內(nèi)存的程序段 處理過程： 先把常駐內(nèi)存部分調(diào)入 存放在輔存的覆蓋部分陸續(xù)調(diào)入,5.3 內(nèi)存擴充技術(shù),作業(yè)大?。?6K 僅需30K存儲空間,5.3 內(nèi)存擴充技術(shù),5.3.1 覆蓋（Overlay）,覆蓋的優(yōu)缺點： 優(yōu)點 可以在小內(nèi)存中運行大作業(yè) 缺點 用戶難以預(yù)知程序的覆蓋情況 用戶只能有效地利用自己程序所占用的內(nèi)存，而不能對整個內(nèi)存加以有效利用 各進程占用的分區(qū)仍會存在碎片,5.3 內(nèi)存擴充技術(shù),5.3.2 交換（Swapping）,交換：把內(nèi)存中暫時無法運行的進程或者

13、暫時不需要的程序、數(shù)據(jù)移到輔存，并將具備運行條件的進程或者需要的程序、數(shù)據(jù)從輔存讀入內(nèi)存 引入交換技術(shù)的存儲管理系統(tǒng)中，外存被劃分為文件區(qū)和交換區(qū)兩個部分 換出(Swap out)：從主存到輔存的移出 換入(Swap in)：從輔存到主存的寫入,在分區(qū)存儲管理中，不論采用什么辦法都會出現(xiàn)碎片問題，從而降低了內(nèi)存的利用率。雖然采用壓縮存儲區(qū)的方法可以解決碎片問題，但系統(tǒng)開銷太大，而無實用價值，必須尋求新的技術(shù)來解決這一問題，于是分頁技術(shù)產(chǎn)生了。 分頁技術(shù)是由曼徹斯特大學(xué)提出，并于1960年前后在Atlas計算機上實現(xiàn)。這種技術(shù)對操作系統(tǒng)的發(fā)展產(chǎn)生了深遠(yuǎn)影響。,5.4 分頁式存儲管理,5.4 分頁

14、式存儲管理,5.4.1 分頁式存儲管理的基本原理,1. 頁框與頁面 頁框：將整個主存劃分成若干個大小為2的整數(shù)次冪的分區(qū)，每個分區(qū)大小相同，我們把這些分區(qū)稱為頁框，并對每個頁框從0開始加以編號，如0號頁框、1號頁框 頁面 ：將用戶作業(yè)的相對地址空間按頁框的尺寸進行劃分，所劃分的每個分區(qū)稱為頁面，并對每個頁面從0開始加以編號，如第0頁、第1頁,5.4 分頁式存儲管理,5.4.1 分頁式存儲管理的基本原理,2. 頁號與頁內(nèi)地址 將用戶作業(yè)空間分頁以后，每一個相對地址都可以改寫成“頁號，頁內(nèi)地址”的形式，地址結(jié)構(gòu)如圖所示： 這是一個32位的地址結(jié)構(gòu)，前一部分為頁號P，由1231位表示。后一部分為頁內(nèi)

15、地址，由011這12位表示，它決定了頁面的大小為4KB（即2的12次方，212B = 4096B = 4KB）,5.4 分頁式存儲管理,5.4.1 分頁式存儲管理的基本原理,3. 頁號與頁內(nèi)地址的計算,（1）通過下面的公式計算出頁號P和頁內(nèi)地址W： 頁號P = 邏輯地址 DIV 頁面大小 頁內(nèi)地址W = 邏輯地址 MOD 頁面大小 其中，DIV為整除運算，MOD 為求余運算 例：在頁面大小為4KB的系統(tǒng)中，若邏輯地址為28024，則： P = 28024 DIV 4096 = 6 W = 28024 MOD 4096 = 3448 由此得到頁號為6，頁內(nèi)地址為3448,5.4 分頁式存儲管理,

16、5.4.1 分頁式存儲管理的基本原理,3. 頁號與頁內(nèi)地址的計算,（2）計算機系統(tǒng)由存儲管理單元（Memory Management Unit，MMU）中的分頁機構(gòu)自動獲得頁號和頁內(nèi)地址。 例如，28024用32位二進制表示為： 0000 0000 0000 0000 0110 1101 0111 1000 因為頁面大小為4 KB = 212B，所以取低12位（1101 0111 1000）為頁內(nèi)地址，十進制為3448; 剩余高位為頁號（0000 0000 0000 0000 0110），十進制為6,5.4 分頁式存儲管理,5.4.2 分頁式存儲管理的地址映射,1. 頁表,分頁式存儲管理就是將

17、用戶作業(yè)的每個頁面裝入內(nèi)存中的頁框。因此，系統(tǒng)為每個作業(yè)建立了一張頁面映射表，稱為頁表，用于記錄用戶作業(yè)的每個頁面及其所裝入的相應(yīng)頁框號。,5.4 分頁式存儲管理,5.4.2 分頁式存儲管理的地址映射,2. 地址轉(zhuǎn)換過程,（1）設(shè)置頁表控制寄存器：執(zhí)行時，就執(zhí)行進程的頁表始址、頁表長度從進程控制塊中取出，放入頁表控制寄存器中； （2） 硬件地址分頁結(jié)構(gòu)自動將每條程序指令中的邏輯地址解釋成頁號和頁內(nèi)地址兩部分； （3）比較頁號與頁表長度，如果未出現(xiàn)越界中斷，則將頁號乘以頁面大小，得到頁內(nèi)相對地址； （4）頁內(nèi)相對地址加上頁表起始地址，便可得到該頁號在頁表中的具體位置； （5）從頁表具體位置處獲得

18、該頁的物理存儲塊號（頁框號）； （6）計算物理地址： 物理地址 = 物理塊號 頁面大小 + 頁內(nèi)地址,5.4 分頁式存儲管理,5.4.2 分頁式存儲管理的地址映射,3.分頁存儲管理的地址變換過程圖,5.4 分頁式存儲管理,5.4.3 聯(lián)想存儲器與快表,出發(fā)點 頁表存放在寄存器，速度快但硬件代價高； 頁表放在主存中，給定的邏輯地址進行讀/寫操作時，必須訪問兩次主存，降低了運算速度； 大多數(shù)的程序在運行時，通常會在少數(shù)頁面中頻繁訪問； 聯(lián)想存儲器（快表） 利用高速緩沖寄存器存放當(dāng)前訪問的那些頁表項； 訪問地址時，總是先將頁號與快表中的所有頁號進行比較，從而降低地址映射時間。,5.4 分頁式存儲管理

19、,5.4.3 聯(lián)想存儲器與快表,引入快表后的地址映射過程,5.4 分頁式存儲管理,5.4.4 多級頁表,為降低頁表的存儲開銷，提出了多級頁表的概念，采取以下措施： 內(nèi)存僅存放當(dāng)前使用的頁表，其余暫時不用的頁表仍然放在磁盤上，待用到時再進行調(diào)入 頁表占用內(nèi)存空間不必連續(xù)，可分散存放 多級頁表方法： 把整個頁表進行分頁，分成一張張小頁表，每個小頁表的大小與頁框相同 為這些小頁表建一張頁目錄表，其表項指出小頁表所在頁框號及相關(guān)信息 系統(tǒng)為每個進程建一張頁目錄表，它的每個表項對應(yīng)一個小頁表，而小頁表的每個表項記錄了頁面和頁框的對應(yīng)關(guān)系 邏輯地址結(jié)構(gòu)由三部分組成：頁目錄、頁號和位移,5.4 分頁式存儲管

20、理,5.4.4 多級頁表,多級頁表的地址轉(zhuǎn)換過程： 由頁目錄表控制寄存器指出當(dāng)前運行進程的頁目錄表內(nèi)存所在地址； 由頁目錄表起址加上“頁目錄位移”為索引，找到某個小頁表在內(nèi)存頁框的地址； 再以“頁表頁位移”為索引，找到小頁表的頁表項，而該表項中包含了頁面對應(yīng)的頁框號，頁框號和“頁內(nèi)位移”便可生成物理地址。,5.5 分段式與段頁式存儲管理,5.5.1 分段式存儲管理的基本原理,用戶程序可以按其邏輯結(jié)構(gòu)劃分為若干段，如主程序段、子程序段、數(shù)據(jù)段、堆棧段等，每一段都是一組邏輯信息，并且都有一段連續(xù)的地址空間 將程序分段以后，每個段都有自己的名稱（段名）、段長度和段內(nèi)元素 將作業(yè)的地址空間分段以后，用

21、段號代替段名，段地址都從0開始編址 由于各個段內(nèi)的邏輯信息各異，決定了各段的長度不等,5.5.2 分段式存儲器的地址映射,設(shè)給定的邏輯地址中，段號為3，段內(nèi)地址為723，分段存儲管理的地址轉(zhuǎn)換過程如下： 段表中記錄了每個段的長度和該段在內(nèi)存的起始地址 段表保存于內(nèi)存，通過它來實現(xiàn)邏輯地址到內(nèi)存物理地址的轉(zhuǎn)換 為了完成地址轉(zhuǎn)換，需由硬件提供段表寄存器，用于保存段表的起始地址和段表的長度,5.5 分段式與段頁式存儲管理,5.5.2 分段式存儲器的地址映射,利用段表實現(xiàn)地址映射,5.5 分段式與段頁式存儲管理,5.5.2 分段式存儲器的地址映射,例如，設(shè)給定的邏輯地址中，段號為2，段內(nèi)地址為723，

22、分段存儲管理的地址轉(zhuǎn)換過程如下：,5.5 分段式與段頁式存儲管理,5.5.2 分段式存儲器的地址映射,設(shè)給定的邏輯地址中，段號為3，段內(nèi)地址為723，分段存儲管理的地址轉(zhuǎn)換過程 ： 段號3與段表寄存器中的段表長度比較,如果段號大于段表長度,則發(fā)生越界中斷,終止程序運行 如果段號沒有越界，則計算該段在段表中的對應(yīng)位置： 段表項位置 = 段表起始地址 + 段號 段表項長度 找到段表中3號段的段表項位置，從中讀出該段在內(nèi)存的起始地址（段基址）為8 K 段基址與段內(nèi)地址相加得到物理地址： 物理地址 = 8K + 723 = 81024 + 723 = 8915 訪問內(nèi)存單元8915，得到需要的數(shù)據(jù)36

23、5,5.5 分段式與段頁式存儲管理,5.5.3 分段與分頁的比較,分段： 信息的邏輯單位 由源程序的邏輯結(jié)構(gòu)決定 用戶可見 段長可根據(jù)用戶的需要來決定 段起始地址可以是主存的任何地址 源程序（段號，段內(nèi)位移）經(jīng)連接裝配后仍保持二維結(jié)構(gòu),分頁： 信息的物理單位 與源程序的邏輯結(jié)構(gòu)無關(guān) 用戶不可見 頁長由系統(tǒng)決定 頁面只能以頁大小的整數(shù)倍地址開始 源程序（頁號，頁內(nèi)位移）經(jīng)連接裝配后變成了一維結(jié)構(gòu),5.5 分段式與段頁式存儲管理,段頁式存儲管理結(jié)合分頁式和分段式兩種存儲管理方案，其基本思想是： 將作業(yè)地址空間分成若干個邏輯段，每段都有自己的段名 每段內(nèi)再分成若干個大小固定的頁，每段都從零開始為自己

24、的各頁依次編寫連續(xù)的頁號 對內(nèi)存空間的管理仍然采取分頁式存儲管理方式，將其分成若干個與頁面大小相同的物理塊，對內(nèi)存空間的分配以物理塊為單位,5.5 分段式與段頁式存儲管理,5.5.4 段頁式存儲管理,作業(yè)的邏輯地址包括3個部分：段號、段內(nèi)頁號和頁內(nèi)位移 為實現(xiàn)地址變換，段頁式系統(tǒng)設(shè)立了段表和頁表 系統(tǒng)為每個作業(yè)建立一張段表，并為每個段建立一張頁表 段表表項中至少包含段號、頁表起始地址和頁表長度等信息 頁表表項中至少要包括頁號和塊號等信息 系統(tǒng)設(shè)置一個段表控制寄存器用來保存運行作業(yè)的段表起始地址和段表的長度,5.5 分段式與段頁式存儲管理,段頁式存儲管理的地址映射 將段號S與段表控制寄存器中的段

25、長進行比較，若超出段長則產(chǎn)生越界中斷。否則由段號和段表控制寄存器中的段表起始地址拼接，得到該段在段表中的相應(yīng)表項位置 查找段表中的表項，得到該段對應(yīng)的頁表在內(nèi)存的起始地址 頁表起始地址與物理地址中的段內(nèi)頁號P拼接，從而找到頁表中的相應(yīng)表項，從中得到該頁所在的物理塊號b 將物理塊號b與頁內(nèi)位移d拼接起來得到所需的物理地址,5.5 分段式與段頁式存儲管理,段頁式存儲管理的地址映射,5.5 分段式與段頁式存儲管理,5.6 請求分頁式存儲管理,虛擬存儲器,1)、問題的提出： a 程序大于內(nèi)存 b 程序暫時不執(zhí)行或運行完是否還要占用內(nèi)存,虛擬存儲器,虛擬存儲器的基本思想是：程序、數(shù)據(jù)、堆棧的大小可以超過

26、內(nèi)存的大小，操作系統(tǒng)把程序當(dāng)前使用的部分保留在內(nèi)存，而把其它部分保存在磁盤上，并在需要時在內(nèi)存和磁盤之間動態(tài)交換。 虛擬存儲器支持多道程序設(shè)計技術(shù)。,5.6 請求分頁式存儲管理,5.6 請求分頁式存儲管理,5.6.1 虛擬存儲管理,局部性原理(principle of locality) ：程序在執(zhí)行過程中，大部分的訪問操作都集中在該程序的某一小部分，呈現(xiàn)局部性規(guī)律 局部性原理主要表現(xiàn)在以下兩個方面： 時間局部性：程序執(zhí)行過程中的某條指令或數(shù)據(jù)如果被訪問，那么在短時間內(nèi)，該指令或數(shù)據(jù)很有可能會被再次訪問 空間局部性：程序執(zhí)行過程中訪問了某存儲單元，在短時間內(nèi)，其臨近的存儲單元也將被訪問,5.6

27、 請求分頁式存儲管理,5.6.1 虛擬存儲管理,（1）利用技術(shù)手段，在固有內(nèi)存容量的基礎(chǔ)上實現(xiàn)存儲容量擴充的存儲系統(tǒng)稱作為“虛擬存儲器” （2）虛擬存儲器是利用設(shè)計技術(shù)，以輔助存儲器為支撐，在邏輯上實現(xiàn)對內(nèi)存容量的擴充 （3）根據(jù)程序局部性原理可知，程序在運行之前，沒有必要全部裝入內(nèi)存，而只需將當(dāng)前要使用的部分先裝入主存，其余暫時不用的部分仍然留在輔儲，待用到時再把它們裝入到主存投入運行 （4）為了區(qū)分虛擬存儲，把用戶作業(yè)空間稱為虛擬地址空間，其中的地址稱為虛地址,5.6 請求分頁式存儲管理,5.6.2 請求分頁式存儲管理基本原理,請求分頁式存儲管理是在分頁式存儲管理的理論基礎(chǔ)上實現(xiàn)的一種虛擬

28、存儲系統(tǒng) 先將內(nèi)存空間劃分為大小相等的塊，再將作業(yè)的虛擬地址空間劃分成與內(nèi)存塊大小相同的頁 并不把作業(yè)的程序和數(shù)據(jù)全部裝入主存，僅裝入立即使用的那些頁面 當(dāng)需要某個頁面時，就根據(jù)頁號查找頁表，如果該頁不在主存，系統(tǒng)發(fā)出調(diào)入頁面請求，把該頁從輔助存儲器調(diào)入主存，使作業(yè)正常運行。程序執(zhí)行過程中訪問了某存儲單元，在短時間內(nèi)，其臨近的存儲單元也將被訪問,5.6 請求分頁式存儲管理,5.6.2 請求分頁式存儲管理基本原理,請求分頁式虛存管理系統(tǒng)通過擴充頁表項來實現(xiàn)缺頁中斷請求，擴充后的頁表表項如圖： 其中，狀態(tài)位：表示該頁是否已在內(nèi)存中； 外存地址：該頁存放在輔助存儲器上的地址； 訪問字段：記錄該頁的訪

29、問次數(shù)，供選擇換出頁面時參考； 修改位：記錄該頁在內(nèi)存訪問過程中是否被修改,5.6 請求分頁式存儲管理,5.6.3 請求分頁式存儲管理的地址映射,請求分頁式存儲管理是在基本分頁式存儲管理的基礎(chǔ)上，增加缺頁中斷處理后實現(xiàn)的地址映射 所不同的是：請求分頁式存儲管理需要同時修改頁表項的訪問字段和修改位。當(dāng)需要訪問的頁不在內(nèi)存中時，則產(chǎn)生和處理缺頁中斷,5.6 請求分頁式存儲管理,缺頁中斷,在地址映射過程中,所訪問的頁不在內(nèi)存,則產(chǎn)生缺頁中斷。操作系統(tǒng)接到此中斷信號后,就調(diào)用缺頁中斷處理程序,根據(jù)頁表中給出的外存地址,將該頁調(diào)入內(nèi)存,使作業(yè)繼續(xù)運行下去。由于從外存向主存調(diào)入一頁需要的時間較長,故在調(diào)頁

30、過程中應(yīng)將請求調(diào)頁的進程置為阻塞狀態(tài)。直到該頁裝入主存再將其喚醒。另外,在產(chǎn)生缺頁中斷時,一條指令并沒有執(zhí)行完,這樣在操作系統(tǒng)進行缺頁中斷處理后,應(yīng)重新執(zhí)行被中斷的指令。當(dāng)重新執(zhí)行時,由于要訪問的頁已在主存,因此就可以正常地執(zhí)行下去。,5.6 請求分頁式存儲管理,缺頁中斷,如果內(nèi)存中有空閑塊，則分配一頁，將新調(diào)入頁裝入內(nèi)存，并修改頁表中相應(yīng)頁表項目的駐留位及相應(yīng)的內(nèi)存塊號。 若此時內(nèi)存中沒有空閑塊，則要淘汰某頁，若該頁在內(nèi)存期間被修改過，則要將其寫回外存。,5.6 請求分頁式存儲管理,缺頁中斷,由圖可知，當(dāng)主存容量增加時，缺頁中斷次數(shù)減少，但主存容量增加到80KB以后，缺頁中斷次數(shù)的減少就不明

31、顯了。大多數(shù)程序都有一個這樣的特定點 試驗分析表明：對所有程序來說，要使其有效地工作，它在主存中的頁面數(shù)應(yīng)不低于它的總頁面數(shù)的一半,存儲容量與缺頁中斷次數(shù)的關(guān)系,5.6 請求分頁式存儲管理,5.6.4 頁面置換算法,理想淘汰算法最佳頁面算法（OPT） 淘汰以后不再需要的或最遠(yuǎn)的將來才會用到的頁面 先進先出頁面淘汰算法（FIFO） 最簡單的算法是先進先出淘汰算法。當(dāng)淘汰一頁時,選擇在主存駐留時間最長的那一頁。為此,操作系統(tǒng)維護一張當(dāng)前頁表。表的長度為當(dāng)前運行作業(yè)分配的主存塊數(shù)。另外設(shè)置一個指針指向最早進入的頁。當(dāng)需要淘汰一頁時，就選擇指針?biāo)傅捻摗?FIFO算法較易實現(xiàn)，但會出現(xiàn)抖動。,5.6

32、請求分頁式存儲管理,5.6.4 頁面置換算法,1. 先進先出頁面置換算法FIFO（First In First Out） 基本思想：把最先進入內(nèi)存的頁面作為置換的對象 例，分配三個物理塊，需要執(zhí)行的頁面引用序列為： 0、1、2、3、2、4、0、2、0、1、2、3， 根據(jù)FIFO算法，該序列的頁面置換情況：,5.6 請求分頁式存儲管理,5.6.4 頁面置換算法,FIFO算法雖然易于實現(xiàn)，但出現(xiàn)抖動外，還會有一種異?，F(xiàn)象。Belady在1969年發(fā)現(xiàn)，采用FIFO算法時，為作業(yè)分配的主存塊越多，反而缺頁中斷次數(shù)越多。這種奇怪的現(xiàn)象就叫做Belady異常。下面舉例說明這一異常。某作業(yè)有5個頁面，執(zhí)行

33、時引用的頁序列為： 0,1,2,3,0,1,4,0,1,2,3,4。共訪問12個頁面。當(dāng)分配3個存貯塊時，共產(chǎn)生9次缺頁中斷。當(dāng)分配4個主存塊時卻產(chǎn)生了10次中斷。缺頁用“x”成功用“v”表示。,5.6 請求分頁式存儲管理,5.6.4 頁面置換算法,2. 最佳頁面置換算法OPT（Optimal） 基本思想：選擇最長時間內(nèi)不會被訪問或者是以后不會再使用的頁面予以置換。例，0、1、2、3、2、4、0、2、0、1、2、3引用序列，根據(jù)OPT算法，該序列的頁面置換情況：,5.6 請求分頁式存儲管理,5.6.4 頁面置換算法,3. 最近最久未用頁面置換算法LRU（Least Recently Used）

34、 基本思想：選擇最近一段時間內(nèi)，最長時間未被訪問過的頁面予以替換 例，0、1、2、3、2、4、0、2、0、1、2、3引用序列，根據(jù)LRU算法，該序列的頁面置換情況：,5.6 請求分頁式存儲管理,5.6.4 頁面置換算法,4. LRU近似算法 基本思想：在頁表中設(shè)置一個“引用位”，當(dāng)某頁被訪問時，該位由硬件自動置“1”，而頁面管理軟件周期性地(設(shè)周期為T)把所有引用位置“0” 在時間T內(nèi)，某些被訪問的頁面的引用位為“1”，而未被訪問過的頁面的引用位為“0” 根據(jù)引用位的狀態(tài)可判別各頁最近的使用情況，當(dāng)需要置換一個最“老”的頁面時，選擇其引用位為“0”的頁 當(dāng)所有頁的使用位都為“1”時，則按FIFO策略淘汰頁面 優(yōu)點：比較簡單，易于實現(xiàn) 缺點：周期T的大小不易確定,5.6 請求分頁式存儲管理,5.6.5 系統(tǒng)抖動,系統(tǒng)進行頻繁的頁面置換，這種現(xiàn)象被稱