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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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