第5章存儲管理

1、第5章 存儲管理n存儲管理的功能n分區(qū)存儲管理n覆蓋與交換技術(shù)n頁式管理n段式與段頁式管理n局部性原理和抖動問題第5章 存儲管理5.1 存儲管理的功能存儲器是計算機(jī)系統(tǒng)的重要資源之一。因為程序、數(shù)據(jù)和各種控制用的數(shù)據(jù)結(jié)構(gòu)都必須占用一定的存儲空間存儲器分兩類：n主存儲器（簡稱主存或內(nèi)存）n輔助存儲器（簡稱輔存或外存）5.1 存儲管理的功能存儲器的層次結(jié)構(gòu)n高速緩存Cache 少量的、非常快速、昂貴、易變的n內(nèi)存RAM 若干兆字節(jié)、中等速度、中等價格、易變的 n 磁盤 數(shù)百兆或數(shù)千兆字節(jié)、低速、價廉、不易變的 5.1 存儲管理的功能由操作系統(tǒng)協(xié)調(diào)這些存儲器的使用 重要性：直接存取要求內(nèi)存速度盡量快

2、到與CPU取指速度相匹配，大到能裝下當(dāng)前運(yùn)行的程序與數(shù)據(jù)，否則CPU執(zhí)行速度就會受到內(nèi)存速度和容量的影響而得不到充分發(fā)揮5.1 存儲管理的功能內(nèi)存：由順序編址的塊組成，每塊包含相應(yīng)的物理單元，用來存放當(dāng)前正在運(yùn)行程序的代碼及數(shù)據(jù)，是程序中指令本身地址所指的，即程序計數(shù)器所指的存儲器內(nèi)存可分為：n系統(tǒng)區(qū)：用于存放操作系統(tǒng)n用戶區(qū)：用于裝入并存放用戶程序和數(shù)據(jù)CPU要通過啟動相應(yīng)的輸入輸出設(shè)備后才能使外存與內(nèi)存交換信息5.1 存儲管理的功能5.1.1 虛擬存儲器虛擬存儲器是存儲管理的核心概念實驗表明：在一個進(jìn)程的執(zhí)行過程中，其大部分程序和數(shù)據(jù)并不經(jīng)常被訪問。因此，存儲管理系統(tǒng)將不經(jīng)常被訪問的程序和

3、數(shù)據(jù)放在外存，待需要訪問時再調(diào)入內(nèi)存。問題：進(jìn)程中一部分在內(nèi)存，另一部分在外存，如何實現(xiàn)？它們的地址如何安排？5.1.1 虛擬存儲器n用戶程序的處理過程通常，由用戶編寫的源程序，首先要由編譯程序編譯成CPU可執(zhí)行的目標(biāo)代碼，然后由鏈接程序把一個進(jìn)程的不同程序段鏈接起來以完成所要求的功能。顯然，對于不同的程序段，應(yīng)具有不同的地址用戶程序的多級處理過程用戶程序的多級處理過程源程序源程序編譯程序編譯程序或匯編程序或匯編程序目標(biāo)目標(biāo)模塊模塊鏈接程序鏈接程序裝配裝配模塊模塊裝配程序裝配程序裝配階段裝配階段編譯階段編譯階段 內(nèi)存中內(nèi)存中可執(zhí)行可執(zhí)行代碼代碼5.1.1 虛擬存儲器n如何安排目標(biāo)代碼的地址？按

4、照物理存儲器中的位置賦予實際物理地址n優(yōu)點：CPU執(zhí)行目標(biāo)代碼的速度高n問題：由于存儲器的容量限制，將減少內(nèi)存并發(fā)執(zhí)行的進(jìn)程數(shù)對于較大進(jìn)程，當(dāng)其所要求的總內(nèi)存容量大于內(nèi)存容量時，將無法執(zhí)行由于編譯程序必須清楚內(nèi)存使用情況，并且一個進(jìn)程的不同程序段要連續(xù)存放，從而造成編譯程序非常復(fù)雜5.1.1 虛擬存儲器n如何安排目標(biāo)代碼的地址方法？將源程序編譯后鏈接到虛擬地址空間地址空間和存儲空間n名空間：用匯編語言或高級語言編寫程序時，總是通過符號名來訪問某一單元，稱程序中由符號名組成的空間為名空間。n虛擬地址（邏輯地址或相對地址）：用戶的源程序經(jīng)過匯編或編譯后形成目標(biāo)代碼，目標(biāo)代碼通常采用相對地址的形式，

5、其首地址為0，其余指令中的地址都相對于首地址而編址，稱為虛擬地址。不能用邏輯地址在內(nèi)存中讀取信息5.1.1 虛擬存儲器n物理地址（絕對地址或?qū)嵉刂罚簝?nèi)存中存儲單元的地址，可直接尋址。p地址變換 為了保證CPU執(zhí)行指令時可正確訪問存儲單元，需將用戶程序中的邏輯地址轉(zhuǎn)換為運(yùn)行時由機(jī)器直接尋址的物理地址，這一過程稱為地址映射。 由源程序到實際存放該程序指令或數(shù)據(jù)的內(nèi)存物理位置的變換如圖5.1所示。源程序具有相對地址的目標(biāo)程序可執(zhí)行代碼（內(nèi)存中）地址空間名字空間存儲空間圖5.1 地址變換與物理存儲器5.1.1 虛擬存儲器虛擬存儲器：是指進(jìn)程中的目標(biāo)代碼、數(shù)據(jù)等的虛擬地址組成的虛擬空間虛擬存儲器不考慮

6、物理存儲器的大小和信息存放的實際位置n每個進(jìn)程都擁有自己的虛擬存儲器n虛擬存儲器的容量由計算機(jī)的地址結(jié)構(gòu)和尋址方式確定 假設(shè)CPU給出的有效地址長度為k字節(jié)，按字節(jié)尋址，則邏輯空間（虛存空間）大小為2k個字節(jié)。 k=18，則容量為218 =256 KB k=24，則容量為224 =16 MB k=32，則容量為232 =4 GB5.1.1 虛擬存儲器n虛擬存儲器的具體實現(xiàn)在硬件支持下，軟硬件相互協(xié)作，將內(nèi)存和外存結(jié)合起來統(tǒng)一使用。通過這種方法把內(nèi)存擴(kuò)充，使用戶在編制程序時不受內(nèi)存限制，實現(xiàn)虛擬存儲地址變換：建立虛擬地址與內(nèi)存地址的關(guān)系大容量的外存儲器的支持5.1 存儲管理的功能5.1.2 地址

7、變換內(nèi)存空間是一維線性空間虛擬空間是一維或多維線性空間問題：如何將幾個虛存空間變換到唯一的內(nèi)存n虛擬空間的劃分與計算機(jī)系統(tǒng)結(jié)構(gòu)有關(guān)例如，VAX-11型機(jī)中虛擬空間的劃分（如圖5.2）系統(tǒng)空間進(jìn)程空間：分為程序區(qū)和控制區(qū)圖5.2 虛擬空間的劃分5.1.2 地址變換問題：如何將幾個虛存空間變換到唯一的內(nèi)存n虛擬地址映射為內(nèi)存地址 原因：當(dāng)程序裝入內(nèi)存時， 操作系統(tǒng)要為該程序分配一個合適的內(nèi)存空間。由于程序的虛擬地址與分配到內(nèi)存物理地址不一致，而CPU執(zhí)行指令時，是按物理地址進(jìn)行的，所以要進(jìn)行地址變換。實現(xiàn)地址變換方法n靜態(tài)地址重定位n動態(tài)地址重定位5.1.2 地址變換1.靜態(tài)地址重定位 當(dāng)用戶程序

8、被裝入內(nèi)存時，一次性實現(xiàn)虛擬地址到物理地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換（一般在裝入內(nèi)存時由裝配程序完成）。靜態(tài)地址重定位Load 1,500123450100500700Load 1,5001234505100550057005000進(jìn)程進(jìn)程A的地址空間的地址空間進(jìn)程進(jìn)程A的存儲空間的存儲空間優(yōu)點：優(yōu)點：簡單易實現(xiàn)簡單易實現(xiàn)無需硬件支持無需硬件支持缺點：缺點：不能再移動不能再移動只能連續(xù)分配只能連續(xù)分配共享困難共享困難無法實現(xiàn)虛擬存儲無法實現(xiàn)虛擬存儲5.1.2 地址變換2.動態(tài)地址重定位在程序運(yùn)行過程中，在CPU訪問內(nèi)存之前，將要訪問的程序或數(shù)據(jù)地址轉(zhuǎn)換成內(nèi)存地址。即，在逐條指令執(zhí)行時完成地址映射。動

9、態(tài)地址重定位由硬件地址映射機(jī)制來完成n一個或多個基地址寄存器BRn一個或多個程序虛擬地址寄存器VRn指令或數(shù)據(jù)的內(nèi)存地址MA=(BR)+(VR)n動態(tài)重定位過程如圖5.3圖5.3 動態(tài)地址重定位5.1.2 地址變換2.動態(tài)地址重定位優(yōu)點n可以對內(nèi)存進(jìn)行非連續(xù)分配。顯然，同一進(jìn)程的各分散程序段，可分散存放，只需增加幾對寄存器。n提供了實現(xiàn)虛擬存儲器的基礎(chǔ)n易于實現(xiàn)共享缺點n需要附加硬件支持n算法復(fù)雜5.1 存儲管理的功能5.1.3 內(nèi)外存數(shù)據(jù)傳輸?shù)目刂埔獙崿F(xiàn)內(nèi)存擴(kuò)充，在程序執(zhí)行過程中，內(nèi)存與外存之間必須經(jīng)常交換數(shù)據(jù)。其控制方法有：用戶程序自己控制：覆蓋技術(shù)操作系統(tǒng)控制：交換技術(shù)5.1.3 內(nèi)外存

10、數(shù)據(jù)傳輸?shù)目刂聘采w技術(shù)n覆蓋技術(shù)要求用戶清楚地了解程序的結(jié)構(gòu)，并指定各程序段調(diào)入內(nèi)存的先后次序n覆蓋技術(shù)不能實現(xiàn)虛擬存儲器交換技術(shù)n交換方式：由操作系統(tǒng)將內(nèi)存中處于等待狀態(tài)的進(jìn)程換出內(nèi)存，而將處于就緒狀態(tài)進(jìn)程換入內(nèi)存n請求調(diào)入方式：在執(zhí)行時，當(dāng)所要訪問的程序或數(shù)據(jù)段不在內(nèi)存中，則操作系統(tǒng)自動從外存將其調(diào)入n預(yù)調(diào)入方式：由操作系統(tǒng)預(yù)測在不遠(yuǎn)的將來會訪問的那些程序段和數(shù)據(jù)段部分，并在它們被訪問之前，系統(tǒng)選擇適當(dāng)時機(jī)將它們調(diào)入內(nèi)存5.1 存儲管理的功能 5.1.4 內(nèi)存的分配與回收 內(nèi)存管理要為每一個進(jìn)程分配內(nèi)存空間；當(dāng)執(zhí)行結(jié)束時，要及時收回該進(jìn)程所占用的內(nèi)存資源。因此，為了有效合理利用內(nèi)存，設(shè)計內(nèi)

11、存的分配與回收方法時，必須考慮以下內(nèi)容：分配結(jié)構(gòu)：登記內(nèi)存使用情況，供分配程序使用的表格與鏈表放置策略：確定調(diào)入內(nèi)存的程序和數(shù)據(jù)在內(nèi)存中的位置5.1 存儲管理的功能 5.1.4 內(nèi)存的分配與回收 交換策略：當(dāng)需要將某個程序段和數(shù)據(jù)調(diào)入內(nèi)存時，若內(nèi)存不足，決定將某些信息調(diào)出內(nèi)存的策略調(diào)入策略：決定外存中的程序段和數(shù)據(jù)段什么時間按什么方式裝入內(nèi)存。即與內(nèi)外存數(shù)據(jù)傳輸控制方式有關(guān)回收策略：包括回收時機(jī)；對所回收的內(nèi)存空閑區(qū)和已存在的內(nèi)存空閑區(qū)的調(diào)整5.1 存儲管理的功能 5.1.4 內(nèi)存信息的共享與保護(hù)內(nèi)存共享：兩個或多個進(jìn)程共用內(nèi)存中相同區(qū)域目的：n節(jié)省內(nèi)存空間，提高內(nèi)存利用率n實現(xiàn)進(jìn)程通信（數(shù)據(jù)

12、共享） 共享內(nèi)容：n代碼共享，要求代碼為純代碼n數(shù)據(jù)共享5.1 存儲管理的功能5.1.5 內(nèi)存信息的共享與保護(hù)內(nèi)存保護(hù)目的 為多個程序共享內(nèi)存提供保障，使在內(nèi)存中的各程序， 只能訪問它自己的區(qū)域，避免各程序間相互干擾和破壞，特別是當(dāng)一道程序發(fā)生錯誤時, 不致于影響其他程序的運(yùn)行。n保護(hù)系統(tǒng)程序區(qū)不被用戶侵犯（有意或無意的）n不允許用戶程序讀寫不屬于自己地址空間的數(shù)據(jù) （系統(tǒng)區(qū)地址空間，其他用戶程序的地址空間）5.1.5 內(nèi)存信息的共享與保護(hù)常用的內(nèi)存信息保護(hù)方法有硬件法、軟件法和軟硬結(jié)合3種n上下界保護(hù)法：每個進(jìn)程設(shè)置一對上下界寄存器。上下界寄存器中存放了被保護(hù)程序和數(shù)據(jù)段的起始地址和終止地址

13、。在程序執(zhí)行時，進(jìn)行訪址合法性檢查。即檢查地址是否在所規(guī)定的范圍內(nèi)，如圖5.45.1.5 內(nèi)存信息的共享與保護(hù)圖5.4 上、下界寄存器保護(hù)法5.1.5 內(nèi)存信息的共享與保護(hù)n保護(hù)鍵法：為每一個被保護(hù)存儲塊分配一個單獨的保護(hù)鍵，而在程序狀態(tài)字中則設(shè)置相應(yīng)的保護(hù)鍵開關(guān)字段，對不同的進(jìn)程賦予不同的開關(guān)代碼和與被保護(hù)的存儲塊中的保護(hù)鍵匹配。n保護(hù)鍵可設(shè)置成對讀寫同時保護(hù)或只對讀、寫進(jìn)行保護(hù)5.1.5 內(nèi)存信息的共享與保護(hù)圖5.5 保護(hù)鍵保護(hù)法5.2 分區(qū)存儲管理n分區(qū)管理是把內(nèi)存劃分為若干個大小不等的區(qū)域，除操作系統(tǒng)占用一個區(qū)域外，其余由各并發(fā)進(jìn)程共享。n分區(qū)管理是滿足多道程序設(shè)計的最簡單的一種存儲管

14、理方法，它允許多個用戶程序同時存在系統(tǒng)內(nèi)存中，即共享內(nèi)存空間5.2 分區(qū)存儲管理5.2.1 分區(qū)管理基本原理基本原理： 每一個進(jìn)程占據(jù)一個分區(qū)，以連續(xù)存放該進(jìn)程的程序和數(shù)據(jù)。按分區(qū)的時機(jī)，分區(qū)管理分為：n固定分區(qū)n動態(tài)分區(qū)5.2.1 分區(qū)管理基本原理1.固定分區(qū)法固定分區(qū)法：是將內(nèi)存區(qū)固定地劃分為若干個大小不等的區(qū)域。分區(qū)劃分的原則由一般系統(tǒng)操作員或操作系統(tǒng)決定。分區(qū)一旦劃分結(jié)束，在整個執(zhí)行過程中就保持不變5.2.1 分區(qū)管理基本原理內(nèi)存管理：設(shè)置分區(qū)說明表n分區(qū)說明表：說明各分區(qū)號、分區(qū)大小、起始地址以及是否空閑（分區(qū)狀態(tài)），如圖5.6(a)內(nèi)存分配：每個區(qū)分配一個進(jìn)程內(nèi)存回收：簡單缺點：內(nèi)

15、存利用率不高圖5.6 固定分區(qū)法5.2.1 分區(qū)管理基本原理2.動態(tài)分區(qū)法動態(tài)分區(qū)法：事先不劃定分區(qū)的大小，而是在作業(yè)的處理過程中，根據(jù)作業(yè)或進(jìn)程對內(nèi)存大小的要求來劃分內(nèi)存區(qū)域初始分配：采用動態(tài)分區(qū)法，在系統(tǒng)初啟時，除了操作系統(tǒng)中常駐內(nèi)存部分外，只有一個空閑區(qū)。隨后，分配程序?qū)⒃搮^(qū)依次劃分給調(diào)度選中的作業(yè)或進(jìn)程。如圖5.7圖5.7 內(nèi)存初始分配情況隨著進(jìn)程的執(zhí)行，會出現(xiàn)一系列的分配和釋放。圖5.8 內(nèi)存分配變化過程2.動態(tài)分區(qū)法n內(nèi)存管理分區(qū)說明表：說明各分區(qū)號、分區(qū)大小、起始地址、分區(qū)狀態(tài)可用分區(qū)表：每個表目記錄一個空閑分區(qū)，如圖5.9(a)可用分區(qū)自由鏈：利用每個空閑區(qū)的頭幾個單元存放本空

16、閑區(qū)的大小及下一個空閑區(qū)的起始地址，將所有的空閑區(qū)鏈接起來。然后，系統(tǒng)再設(shè)置一個自由鏈?zhǔn)字羔樦赶虻谝粋€空閑區(qū)。如圖5.9(b) 內(nèi)存資源請求表：描述各作業(yè)或進(jìn)程請求內(nèi)存資源大小的情況，如圖5.9(c)圖5.9 可用表、自由鏈及請求表5.2.2 分區(qū)的分配與回收 1.固定分區(qū)的分配與回收固定分區(qū)的分配n存儲管理程序根據(jù)請求表查詢分區(qū)說明表，從中找到一個滿足要求的空閑區(qū)，并將其分配給申請者。如圖5.10固定分區(qū)的回收n當(dāng)進(jìn)程執(zhí)行完畢，不再需要內(nèi)存資源時，管理程序?qū)?yīng)分區(qū)狀態(tài)置為空閑即可圖5.10 固定分區(qū)分配算法5.2.2 分區(qū)的分配與回收2.動態(tài)分區(qū)的分配與回收需要解決3個問題n如何根據(jù)要求尋

17、找合適的空閑區(qū)分配給程序n分配空閑區(qū)后，如何更新可用表或自由鏈n內(nèi)存資源釋放后，如何與相鄰塊鏈接合并，更新可用表或自由鏈動態(tài)分區(qū)的分配：從可用表或自由鏈中找空閑區(qū)n最先適應(yīng)法n最佳適應(yīng)法n最壞適應(yīng)法（1）最先適應(yīng)法n 當(dāng)接到內(nèi)存申請時，查可用表或自由鏈，找到第一個不小于請求的空塊，將其分割并分配。n 特點：簡單、快速分配可用表或自由鏈的數(shù)據(jù)結(jié)構(gòu)：空白區(qū)按起始地址大小遞增排序 如果請求分配的容量為S，則從X1開始比較，直至 XiS為止。然后，從Xi中分配S，剩余部分保留在空白區(qū)表中原來的位置或合并。如圖5.11n優(yōu)點：算法簡單，查找速度快n缺點：小的空白區(qū)集中在鏈的前端圖5.11 最先適應(yīng)算法（

18、2）最佳適應(yīng)法n當(dāng)接到內(nèi)存申請時，在可用表或自由鏈中找到一個不小于請求的最小空閑區(qū)進(jìn)行分配。n 特點：用最小空間滿足要求可用表或自由鏈的數(shù)據(jù)結(jié)構(gòu)：空白區(qū)按其容量大小遞增排列， 即： X1X2X3. Xn設(shè)請求分配的容量為S，則從X1開始比較，直至SXi。然后，從Xi中減去S，如有剩余，則將空白區(qū)插入適當(dāng)位置，否則（SSn），則分配失敗。剩余空白區(qū)的處理：如果Xi-SG(參數(shù))，則Xi全部給作業(yè)，否則，Xi-S插入適當(dāng)位置?？雌饋碜罴?，實際怎么樣？（2）最佳適應(yīng)法優(yōu)點n只要查找一半的表格便能找到最佳適應(yīng)的空白區(qū)n若空白區(qū)的容量正合適，則它必被選中n若沒有正合適的空白區(qū)，則選一個能滿足要求的最小空

19、白區(qū)缺點n碎片問題（3）最壞適配算法n 當(dāng)接到內(nèi)存申請時，在可用表或自由鏈中找到一個不小于請求的最大空塊進(jìn)行分配。n特點：當(dāng)分割后空閑塊仍為較大空塊可用表或自由鏈的數(shù)據(jù)結(jié)構(gòu)：空白區(qū)按其容量大小遞減連接起來。 即， X1X2X3. Xn如果請求分配的容量為S，并且X1S，則從X1中分配S；如果有剩余部分，將其插入適當(dāng)位置；如果并且X1 TrueTrueTrueTrue地址地址A Afalse false false false程序性中斷程序性中斷3.分區(qū)的保護(hù)措施 (2)基址寄存器、長度寄存器和動態(tài)地址轉(zhuǎn)換機(jī)構(gòu) 當(dāng)作業(yè)被調(diào)度運(yùn)行時，將作業(yè)所占內(nèi)存基址當(dāng)作業(yè)被調(diào)度運(yùn)行時，將作業(yè)所占內(nèi)存基址及長度送

20、基址、長度寄存器，每次內(nèi)存訪問時，及長度送基址、長度寄存器，每次內(nèi)存訪問時，先看訪問地址是否小于長度，然后先看訪問地址是否小于長度，然后+ +基址進(jìn)行訪基址進(jìn)行訪存。用戶程序代碼是動態(tài)浮動的。存。用戶程序代碼是動態(tài)浮動的。CPUCPU主存主存基地址寄存器基地址寄存器長度寄存器長度寄存器 =Lpp. . .快表快表 B+頁號頁號p p 頁內(nèi)地址頁內(nèi)地址dPd物理地址物理地址頁表地址寄存器頁表地址寄存器頁表長度寄存器頁表長度寄存器邏輯地址邏輯地址地址映射機(jī)制舉例1、設(shè)每個頁面長度為1 KB（即1024B），某進(jìn)程的頁表如圖5.19所示。請簡述執(zhí)行下述指令的地址變換過程。 100 LOAD 1, 2

21、500圖5.19 頁號與頁面號解：執(zhí)行指令100 LOAD 1, 2500的地址變換過程為：（1）取指令 首先根據(jù)該指令的邏輯地址100，得到相應(yīng)的虛擬頁式地址為（0，100），然后查頁表得到其頁面號為2，計算出物理內(nèi)存地址為21024+1002148 因此，從內(nèi)存地址為2148單元中取出指令執(zhí)行（2）取數(shù)據(jù) 首先根據(jù)數(shù)據(jù)的虛擬地址2500，得到相應(yīng)的虛擬頁式地址為（2，452），然后查頁表得到其頁面號為8，計算出物理內(nèi)存地址為81024+4528644 因此，從內(nèi)存地址為8644單元中取出數(shù)據(jù)，放入寄存器1中。 該地址變換過程如圖5.20所示 圖5.20 地址變換3.地址變換取一個指令或數(shù)據(jù)

22、至少要訪問內(nèi)存兩次以上由于頁表是駐留在內(nèi)存的某個固定區(qū)域中，而取指令或數(shù)據(jù)必須經(jīng)過頁表變換才能得到實際物理地址。n一次訪問頁表，以確定所取數(shù)據(jù)或指令的物理地址n另一次是根據(jù)地址取數(shù)據(jù)或指令為了提高速度，采用高速聯(lián)想寄存器 CPUCPU有一個用于有一個用于頁號頁號塊塊轉(zhuǎn)換的聯(lián)想存儲器。將轉(zhuǎn)換的聯(lián)想存儲器。將頁表存入聯(lián)想存儲器的地址，其轉(zhuǎn)換原理如下：頁表存入聯(lián)想存儲器的地址，其轉(zhuǎn)換原理如下：P dn k-10f dn k-10P2f2P1f1.Pf.Pmfm 關(guān)鍵字關(guān)鍵字 值值高速聯(lián)想存儲器P dn k-10f dn k-10P2f2P1f1.Pf.Pmfmf頁表始地頁表始地+頁表頁表聯(lián)想存儲器聯(lián)

23、想存儲器聯(lián)想存儲器可以看成是頁表的聯(lián)想存儲器可以看成是頁表的cachecachen采用“雙管齊下”p命中率：選用812項組成的聯(lián)想存儲器，并采用適當(dāng)?shù)奶鎿Q策略，在聯(lián)想存儲器中匹配成功的可能性可達(dá)80%90%。p等效訪問時間：設(shè)訪存時間為750ns，搜索聯(lián)想存儲器的時間為50ns，命中率為80%，則： 80%(750+50)+20%(750+50+750）950nsp 在進(jìn)程被調(diào)度占用CPU時，將進(jìn)程頁表始址裝入頁表始地址寄存器，同時用新的頁表內(nèi)容替換聯(lián)想存儲器中的原內(nèi)容。利用聯(lián)想寄存器加速查表5.4.3 動態(tài)頁式管理連續(xù)性 ； 離散性駐留性 ； 交換性一次性； 多次性n虛擬存儲器 以CPU時間

24、和外存空間換取昂貴內(nèi)存空間，這是操作系統(tǒng)中的資源轉(zhuǎn)換技術(shù)5.4.3 動態(tài)頁式管理n虛擬存儲技術(shù)問題的提出 n程序大于內(nèi)存 n程序暫時不執(zhí)行或運(yùn)行完是否還要占用內(nèi)存 虛擬存儲器的基本思想是：程序、數(shù)據(jù)、堆棧的大小可以超過內(nèi)存大小，操作系統(tǒng)把程序當(dāng)前使用的部分保留在內(nèi)存，而把其它部分保存在磁盤上，并在需要時在內(nèi)存和磁盤之間動態(tài)交換X60K-64KX56K-60KX52K-56KX48K-52K744K-48KX40K-44K536K-40KX32K-36KX28K-32KX24K-28K320K-24K416K-20K012K-16K6 8K-12K1 4K-8K2 0K-4KXX34061228

25、K-32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K虛地址空間虛地址空間物理地址空間物理地址空間 虛頁虛頁頁框頁框0001150001140001130001121110110001101010 90001 80001 70001 60110 51000 40000 31100 20010 10100 00010000000000100110在在/不在內(nèi)存不在內(nèi)存頁表頁表虛地址虛地址8196物理地址物理地址2458001100000000001005.4.3 動態(tài)頁式管理n虛擬存儲技術(shù)程序局部性原理 在一段時間內(nèi)一個程序的執(zhí)行往往呈現(xiàn)出高度的

26、局部性，表現(xiàn)在時間與空間兩方面n時間局部性：一條指令被執(zhí)行了，則在不久的將來它可能再被執(zhí)行n空間局部性：若某一存儲單元被使用，則在一定時間內(nèi)，與該存儲單元相鄰的單元可能被使用5.4.3 動態(tài)頁式管理n虛擬存儲技術(shù)虛存：把內(nèi)存與外存有機(jī)的結(jié)合起來使用，從而得到一個容量很大的“內(nèi)存”，這就是虛存實現(xiàn)思想：當(dāng)進(jìn)程運(yùn)行時，先將一部分程序裝入內(nèi)存，另一部分暫時留在外存，當(dāng)要執(zhí)行的指令不在內(nèi)存時，由系統(tǒng)自動完成將它們從外存調(diào)入內(nèi)存工作5.4.3 動態(tài)頁式管理n動態(tài)頁式管理思想：在作業(yè)或進(jìn)程開始執(zhí)行之前，不一次性地將其程序段和數(shù)據(jù)段全部裝入內(nèi)存，而只裝入被認(rèn)為經(jīng)常反復(fù)執(zhí)行和調(diào)用的部分，其他部分則在執(zhí)行過程中

27、動態(tài)裝入方法分為：n請求頁式管理n預(yù)調(diào)入頁式管理5.4.3 動態(tài)頁式管理兩種管理的調(diào)入方式不同n請求頁式管理：當(dāng)需要執(zhí)行某條指令而又發(fā)現(xiàn)它不在內(nèi)存時，或當(dāng)執(zhí)行某條指令需要訪問其他數(shù)據(jù)或指令時，這些指令和數(shù)據(jù)不在內(nèi)存中，從而發(fā)生缺頁中斷，系統(tǒng)將外存中相應(yīng)的頁面調(diào)入內(nèi)存n預(yù)調(diào)入頁式管理：系統(tǒng)對那些在外存中的頁進(jìn)行調(diào)入順序計算，估計出這些頁中指令和數(shù)據(jù)的執(zhí)行和被訪問順序，并按此順序?qū)⑺鼈冺槾握{(diào)入和調(diào)出內(nèi)存請求頁式管理原理n基本工作原理 在進(jìn)程開始運(yùn)行之前，不是裝入全部頁面，而是裝入一個或零個頁面，之后根據(jù)進(jìn)程運(yùn)行的需要，動態(tài)裝入其它頁面；當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁面時，則根據(jù)某種算法淘汰某個

28、頁面，以便裝入新的頁面。n必須解決的問題只有一部分在內(nèi)存中，作業(yè)是否能運(yùn)行？如何發(fā)現(xiàn)要訪問的虛頁是否在內(nèi)存中？如果所需的虛頁不在內(nèi)存中，從何處裝？裝到何處？ 內(nèi)存已滿怎么辦？ n 擴(kuò)充頁表表項頁號頁面號改變位：查看此頁是否在內(nèi)存中被修改過？引用位：表示該頁最近是否被訪問過？根據(jù)引用位來決定淘汰哪一頁（由不同的算法決定）狀態(tài)位：表示該頁是在內(nèi)存還是在外存外存地址頁號頁面號改變位引用位狀態(tài)位外存地址請求頁式管理原理n缺頁中斷在地址映射過程中，在頁表中發(fā)現(xiàn)所要訪問的頁不在內(nèi)存，則產(chǎn)生缺頁中斷。操作系統(tǒng)接到此中斷信號后，就調(diào)出缺頁中斷處理程序，根據(jù)頁表中給出的外存地址，將該頁調(diào)入內(nèi)存，使作業(yè)繼續(xù)運(yùn)行下

29、去。 如果內(nèi)存中有空閑頁面，則分配一頁，將新調(diào)入頁裝入內(nèi)存，并修改頁表中相應(yīng)頁表項目的狀態(tài)位及相應(yīng)的頁面號。 若此時內(nèi)存中沒有空閑頁面，則要淘汰某頁，若該頁在內(nèi)存期間被修改過，則要將其寫回外存。請求頁式管理原理圖5.23 動態(tài)頁式管理流程圖5.4.4 請求頁式管理中的置換算法n常用的置換算法隨機(jī)淘汰算法：隨機(jī)選擇某個用戶的頁面，并將其換出輪轉(zhuǎn)置換算法：循環(huán)換出內(nèi)存可用區(qū)內(nèi)的一頁先進(jìn)先出置換算法（FIFO）：選擇在內(nèi)存中駐留時間最長的頁并淘汰之。最近最久未使用頁面置換算法（LRU）：選擇最后一次訪問時間距離當(dāng)前時間最長的一頁并淘汰之。 即淘汰沒有使用的時間最長的頁。理想置換算法（最佳頁面算法OP

30、T）：淘汰以后不再需要的或最遠(yuǎn)的將來才會用到的頁面。常用的置換算法性能分析例1：計算缺頁次數(shù) 某程序在內(nèi)存中分配3個頁面，初始為空，頁面走向為4，3，2，1，4，3，5，4，3，2，1，5。FIFO 4 3 2 1 4 3 5 4 3 2 1 5頁1 4 3 2 1 4 3 5 5 5 2 1 1頁2 4 3 2 1 4 3 3 3 5 2 2頁3 4 3 2 1 4 4 4 3 5 5 x x x x x x x x x 共缺頁中斷9次先進(jìn)先出置換算法（FIFO） LRU 4 3 2 1 4 3 5 4 3 2 1 5頁1 4 3 2 1 4 3 5 4 3 2 1 5頁2 4 3 2 1

31、4 3 5 4 3 2 1頁3 4 3 2 1 4 3 5 4 3 2 x x x x x x x x x x共缺頁中斷10次最近最久未使用頁面置換算法（LRU） OPT 4 3 2 1 4 3 5 4 3 2 1 5頁1 4 3 2 1 1 1 5 5 5 2 1 1頁2 4 3 3 3 3 3 3 3 5 5 5頁3 4 4 4 4 4 4 4 4 4 4 x x x x x x x 共缺頁中斷7次理想置換算法（最佳頁面算法OPT）例2，計算缺頁次數(shù)與缺頁率 某程序在內(nèi)存中分配m頁初始為空，頁面走向為1，2，3，4，1，2，5，1，2，3，4，5。當(dāng)m=3，m=4時缺頁中斷分別為多少？用F

32、IFO算法。n當(dāng)進(jìn)程分得3個頁面是，執(zhí)行過程中內(nèi)存頁面變化如下圖所示。n由圖可知，共缺頁9次，其缺頁率為9/12=75%n當(dāng)進(jìn)程分得4個頁面是，執(zhí)行過程中內(nèi)存頁面變化如下圖所示。n由圖可知，共缺頁10次，其缺頁率為10/12=83.3%FIFO算法的Belady現(xiàn)象nBelady現(xiàn)象： FIFO頁面置換算法會產(chǎn)生異?，F(xiàn)象，當(dāng)分配給進(jìn)程的物理頁面數(shù)增加時，缺頁次數(shù)反而增加。n原因：根本沒有考慮程序執(zhí)行的動態(tài)特性圖5.24 FIFO算法的Belady現(xiàn)象n 地址越界保護(hù)：設(shè)置頁表長度寄存器，查頁表前，先檢查頁號是否越界。n 操作訪問保護(hù)：在每個頁表項中增設(shè)一存儲保護(hù)域，用于說明對該頁的訪問權(quán)限，每

33、一個對該頁存儲的訪問都首先比照是否滿足該頁訪問權(quán)限的說明，滿足則訪問，否則報錯。5.4.5 存儲保護(hù)舉例：設(shè)為每一頁表項增加三位，R位表示讀權(quán)限，W位表示寫權(quán)限，E位表示執(zhí)行權(quán)限RWE000 不可進(jìn)行任何操作001 可以執(zhí)行,不可以讀寫010 只可以寫0111001011101115.4.6 頁式管理的優(yōu)缺點n優(yōu)點有效解決了碎片問題動態(tài)頁式管理提供了內(nèi)存與外存統(tǒng)一管理的虛存實現(xiàn)方式，提高了方便了用戶、系統(tǒng)效率n缺點要求有相應(yīng)的硬件支持，如地址變換機(jī)構(gòu)增加了系統(tǒng)開銷，如缺頁中斷置換算法如選擇不當(dāng)，可能會造成抖動5.5 段式與段頁式管理5.5.1 段式管理的基本思想段式管理的基本思想n邏輯上：程序

34、按內(nèi)容或過程（函數(shù)）關(guān)系分成段，每段有自己的名字。一個作業(yè)或進(jìn)程所包含的段對應(yīng)于一個二維線性虛擬空間n物理上：以段為單位分配內(nèi)存n采用虛擬存儲技術(shù)：只把那些經(jīng)常訪問的段駐留內(nèi)存，而把那些在將來一段時間內(nèi)不被訪問的段放入外存，待需要時自動調(diào)入的方法實現(xiàn)二維虛擬存儲器5.5 段式與段頁式管理5.5.2 段式管理的實現(xiàn)原理1.段式虛存空間用戶程序劃分n 按程序自身的邏輯關(guān)系劃分為若干個程序段，每個程序段都有一個段名，且有一個段號。段號從0開始，每一段也從0開始編址，段內(nèi)地址是連續(xù)的。n段式虛擬地址包括兩部分：段號和段式地址段號 段內(nèi)地址.0S工作區(qū)段工作區(qū)段B主程序段主程序段M.0EP子程序段子程序

35、段X0K.CALL X E.CALL Y FCALL A 116.0FL子程序段子程序段Y0116N數(shù)組數(shù)組A12345.5.5.2 段式管理的實現(xiàn)原理2.段式管理的內(nèi)存分配與釋放在作業(yè)或進(jìn)程執(zhí)行過程中動態(tài)進(jìn)行分配與釋放內(nèi)存劃分n內(nèi)存空間被動態(tài)的劃分為若干個長度不相同的區(qū)域，這些區(qū)域被稱為物理段，每個物理段由起始地址和長度確定。內(nèi)存分配n以段為單位分配內(nèi)存，每一個段在內(nèi)存中占據(jù)連續(xù)空間（內(nèi)存隨機(jī)分割，需要多少分配多少），但各段之間可以不連續(xù)存放。2.段式管理的內(nèi)存分配與釋放段表n它記錄了段號，段的首（地）址和長度之間的關(guān)系。n每一個程序設(shè)一個段表段號段號012段長度L20K110K220K段首

36、地址B58K100K260K段表的作用作業(yè)空間作業(yè)空間（MAIN），），0030K00020K10K15K（X），），1（D），），2（S），），3段表段表30K 40K20K 80K10K 120K15K 150K段長段長 基址基址段號段號0123內(nèi)存空間內(nèi)存空間（MAIN），），0（X），），0（D），），0（S），），0040K80K120K150K2.段式管理的內(nèi)存分配與釋放（1）內(nèi)存中有足夠的空閑區(qū)滿足要求空閑塊管理：采用和動態(tài)分區(qū)管理相同的空閑區(qū)管理方法內(nèi)存的分配算法n最先適應(yīng)法n最佳適應(yīng)法n最壞適應(yīng)法內(nèi)存回收：采用和分區(qū)管理相同的內(nèi)存回收方法2.段式管理的內(nèi)存分配與釋放（2）內(nèi)存

37、中沒有足夠的空閑區(qū)滿足要求置換算法：可以采用動態(tài)頁式管理的淘汰算法nFIFO算法nLRU算法若需要調(diào)入的某段長度大于被淘汰的一段程序或數(shù)據(jù)的長度，則再淘汰，直到滿足要求缺段中斷處理過程如圖5.29所示圖5.29 缺段中斷處理過程 5.5.2 段式管理的實現(xiàn)原理3.段式管理的地址變換段式地址變換機(jī)構(gòu)：實現(xiàn)虛地址到物理地址轉(zhuǎn)換（1）段表：擴(kuò)充內(nèi)容，實現(xiàn)虛擬存儲狀態(tài)位或內(nèi)外位（在/不在內(nèi)存，是否可共享）存取方式（讀，寫，執(zhí)行，用于存取保護(hù)）訪問位（是否訪問過）改變位（是否修改過）增補(bǔ)位（固定長/可擴(kuò)充 ）圖 5.30 段表3.段式管理的地址變換（2）動態(tài)地址變換段表區(qū)：在內(nèi)存中給出一塊固定區(qū)域存放段

38、表硬件支持：一對寄存器n段表始址寄存器：用于保存正在運(yùn)行進(jìn)程的段表的始址。n段表長度寄存器：用于保存正在運(yùn)行進(jìn)程的段表的長度 Cl Cb+段號段號S S 段內(nèi)地址段內(nèi)地址d比較比較比較比較B + d段段表表S= Cl快表快表物理地址物理地址段表始址寄存器段表始址寄存器段表長度寄存器段表長度寄存器邏輯地址邏輯地址LB.S LB地址越界地址越界d=Ld=L地址映射及存儲保護(hù)機(jī)制地址越界地址越界地址越界地址越界比較比較（2）動態(tài)地址變換圖5.31 段式地址變換過程3.段式管理的地址變換取一個指令或數(shù)據(jù)至少要訪問內(nèi)存兩次以上由于段表是駐留在內(nèi)存的某個固定區(qū)域中，而取指令或數(shù)據(jù)必須經(jīng)過段表變換才能得到實

39、際物理地址。n一次訪問段表，以確定所取數(shù)據(jù)或指令的物理地址n另一次是根據(jù)地址取數(shù)據(jù)或指令為了提高速度，采用高速聯(lián)想寄存器n用途：保存正在運(yùn)行進(jìn)程的段表的子集（部分表項）n特點：按內(nèi)容并行查找n快表項目：段號、段始址、段長度等5.5.2 段式管理的實現(xiàn)原理4.段的共享與保護(hù) 由于段是按邏輯意義來劃分的，可以按段名訪問，因此段式管理可以方便實現(xiàn)內(nèi)存信息共享與內(nèi)存保護(hù)。段的共享n共享：內(nèi)存中只保留一個副本，供多個用戶使用n段的共享：只要用戶使用相同的段名，在段表中填入相關(guān)信息即可實現(xiàn)共享圖5.32 段式系統(tǒng)中共字內(nèi)存副本5.5.2 段式管理的實現(xiàn)原理4.段的共享與保護(hù)段的保護(hù)n地址越界保護(hù)法：利用段

40、表中的段長項與虛擬地址中的段內(nèi)相對地址比較。若段內(nèi)相對地址大于段長，再查段表中的“增補(bǔ)位”，看是否允許段動態(tài)增長；若可以，則繼續(xù)，否則產(chǎn)生越界中斷處理，按出錯處理。n存取方式控制保護(hù)法n優(yōu)點： 內(nèi)外存統(tǒng)一管理的虛存實現(xiàn) 允許動態(tài)增加段的長度 便于共享 便于實現(xiàn)動態(tài)鏈接n缺點：需要硬件支持，提高了機(jī)器成本有碎片問題每段的長度受內(nèi)存可用區(qū)大小的限制5.5.3 段式管理的優(yōu)缺點 5.5.4 段頁式管理的基本思想n段式管理反映了程序的邏輯結(jié)構(gòu)，有利于段的動態(tài)增長、段的共享與保護(hù)等n頁式管理有效克服了碎片，提高了存儲器的利用率n段頁式管理結(jié)合了二者優(yōu)點，克服了二者的缺點一般只用于大型機(jī)系統(tǒng)中5.5.5

41、段頁式管理的實現(xiàn)原理1.虛地址的構(gòu)成邏輯程序按段劃分，物理內(nèi)存按頁劃分內(nèi)存劃分：按頁式存儲管理方法內(nèi)存分配：以頁為單位進(jìn)行分配虛擬地址：n由3部分組成：段號S、頁號p和頁內(nèi)相對地址d31201916頁號頁號P頁內(nèi)地址頁內(nèi)地址W編號編號015相對地址相對地址04096虛擬地址段號段號 段內(nèi)位移段內(nèi)位移 -段號段號頁號頁號頁內(nèi)位移頁內(nèi)位移記做：記做：S,P,dS,P,d段號段號S815編號編號0255段頁式虛擬地址 主程序段04K8K12K15K16K子程序段04K8K數(shù)據(jù)段04K8K12K10K（a）一個作業(yè)地址空間的結(jié)構(gòu)段號S段內(nèi)頁號P頁內(nèi)偏移量d（b）段頁式地址結(jié)構(gòu)的組成5.5.5 段頁式管理的實現(xiàn)原理2.管理段表：每個作業(yè)建立一張段表，記錄每一段的頁表始址、頁表長度、狀態(tài)等頁表：每段建立一張頁表，記錄虛擬頁號與內(nèi)存頁面號的對應(yīng)關(guān)系。（每一段有一個，一個程序可能有多個頁表）空閑區(qū)管理：同頁式管理內(nèi)存分配：同頁式管理作業(yè)空間的內(nèi)