第5章操作系統(tǒng)

1、第五章第五章 虛擬存儲器虛擬存儲器 5.1 5.1 虛擬存儲器的基本概念虛擬存儲器的基本概念5.2 5.2 請求分頁存儲管理方式請求分頁存儲管理方式5.3 5.3 頁面置換算法頁面置換算法 5.4 5.4 請求分段存儲管理方式請求分段存儲管理方式 5.1 虛擬存儲器概述虛擬存儲器概述 虛擬存儲器的引入虛擬存儲器的引入 1. 常規(guī)存儲器管理方式的特征常規(guī)存儲器管理方式的特征 (1) 一次性。 (2) 駐留性。 2. 局部性原理局部性原理 早在1968年， Denning.P就曾指出： (1) 程序執(zhí)行時， 除了少部分的轉(zhuǎn)移和過程調(diào)用指令外， 在大多數(shù)情況下仍是順序執(zhí)行的。 (2) 過程調(diào)用將會使

2、程序的執(zhí)行軌跡由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域， 但經(jīng)研究看出，過程調(diào)用的深度在大多數(shù)情況下都不超過5。 (3) 程序中存在許多循環(huán)結(jié)構(gòu)， 這些雖然只由少數(shù)指令構(gòu)成， 但是它們將多次執(zhí)行。 (4) 程序中還包括許多對數(shù)據(jù)結(jié)構(gòu)的處理， 如對數(shù)組進(jìn)行操作， 它們往往都局限于很小的范圍內(nèi)。 局限性又表現(xiàn)在下述兩個方面： (1) 時間局限性。如果程序中的某條指令一旦執(zhí)行， 則不久以后該指令可能再次執(zhí)行；如果某數(shù)據(jù)被訪問過， 則不久以后該數(shù)據(jù)可能再次被訪問。產(chǎn)生時間局限性的典型原因，是由于在程序中存在著大量的循環(huán)操作。 (2) 空間局限性。一旦程序訪問了某個存儲單元，在不久之后，其附近的存儲單元也將被訪問，

3、即程序在一段時間內(nèi)所訪問的地址，可能集中在一定的范圍之內(nèi)，其典型情況便是程序的順序執(zhí)行。 5.1.2. 虛擬存儲器定義虛擬存儲器定義 所謂虛擬存儲器， 是指具有請求調(diào)入功能和置換功能， 能從邏輯上對內(nèi)存容量加以擴(kuò)充的一種存儲器系統(tǒng)。其邏輯容量由內(nèi)存容量和外存容量之和所決定，其運(yùn)行速度接近于內(nèi)存速度，而每位的成本卻又接近于外存。可見，虛擬存儲技術(shù)是一種性能非常優(yōu)越的存儲器管理技術(shù)，故被廣泛地應(yīng)用于大、 中、 小型機(jī)器和微型機(jī)中。 2. 虛擬存儲器的特征虛擬存儲器的特征 1. 多次性多次性 2. 對換性對換性3. 虛擬性虛擬性 5.1.3 虛擬存儲器的實(shí)現(xiàn)方法虛擬存儲器的實(shí)現(xiàn)方法 1.請求分頁系統(tǒng)

4、請求分頁系統(tǒng) (1) 硬件支持。 請求分頁的頁表機(jī)制，它是在純分頁的頁表機(jī)制上增加若干項(xiàng)而形成的，作為請求分頁的數(shù)據(jù)結(jié)構(gòu)； 缺頁中斷機(jī)構(gòu)，即每當(dāng)用戶程序要訪問的頁面尚未調(diào)入內(nèi)存時 便產(chǎn)生一缺頁中斷，以請求OS將所缺的頁調(diào)入內(nèi)存； 地址變換機(jī)構(gòu)， 它同樣是在純分頁地址變換機(jī)構(gòu)的基礎(chǔ)上發(fā)展形成的。 (2) 實(shí)現(xiàn)請求分頁的軟件。2. 請求分段系統(tǒng)請求分段系統(tǒng) 5.2 請求分頁存儲管理方式請求分頁存儲管理方式 5.2.1 請求分頁中的硬件支持請求分頁中的硬件支持 1. 頁表機(jī)制頁表機(jī)制 頁號 物理塊號 狀態(tài)位P 訪問字段A 修改位M外存地址 2. 缺頁中斷機(jī)構(gòu)缺頁中斷機(jī)構(gòu) 圖 5-1 涉及6次缺頁中斷

5、的指令 頁面B：A：654321指令copy ATO B3. 地址變換機(jī)構(gòu)地址變換機(jī)構(gòu) 缺頁中斷處理保留CPU現(xiàn)場從外存中找到缺頁內(nèi)存滿否？選擇一頁換出該頁被修改否？將該頁寫回外存OS命令CPU從外存讀缺頁啟動I/O硬件將一頁從外存換入內(nèi)存修改頁表否是是否頁表項(xiàng)在快表中？CPU檢索快表訪問頁表否頁在內(nèi)存？修改訪問位和修改位形成物理地址地址變換結(jié)束否頁號頁表長度?開始程序請求訪問一頁產(chǎn)生缺頁中斷請求調(diào)頁修改快表是越界中斷是是圖 5-2 請求分頁中的地址變換過程 5.2.2 內(nèi)存分配策略和分配算法內(nèi)存分配策略和分配算法 1. 最小物理塊數(shù)的確定最小物理塊數(shù)的確定 是指能保證進(jìn)程正常運(yùn)行所需的最小物

6、理塊數(shù)。當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)少于此值時，進(jìn)程將無法運(yùn)行。進(jìn)程應(yīng)獲得的最少物理塊數(shù)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、 功能和尋址方式。對于某些簡單的機(jī)器，若是單地址指令且采用直接尋址方式，則所需的最少物理塊數(shù)為2。其中，一塊是用于存放指令的頁面，另一塊則是用于存放數(shù)據(jù)的頁面。如果該機(jī)器允許間接尋址時，則至少要求有三個物理塊。對于某些功能較強(qiáng)的機(jī)器， 其指令長度可能是兩個或多于兩個字節(jié)，因而其指令本身有可能跨兩個頁面，且源地址和目標(biāo)地址所涉及的區(qū)域也都可能跨兩個頁面。2. 物理塊的分配策略物理塊的分配策略 在請求分頁系統(tǒng)中，可采取兩種內(nèi)存分配策略，即固定和可變分配策略。在進(jìn)行置換時，

7、 也可采取兩種策略，即全局置換和局部置換。于是可組合出以下三種適用的策略。 1) 固定分配局部置換(Fixed Allocation, Local Replacement) 2) 可變分配全局置換(Variable Allocation, Global Replacement) 3) 可變分配局部置換(Variable Allocation, Local Replacemen 3. 物理塊分配算法物理塊分配算法 1) 平均分配算法 這是將系統(tǒng)中所有可供分配的物理塊，平均分配給各個進(jìn)程。 例如，當(dāng)系統(tǒng)中有100個物理塊，有5個進(jìn)程在運(yùn)行時，每個進(jìn)程可分得20個物理塊。這種方式貌似公平，但實(shí)際上是

8、不公平的，因?yàn)樗纯紤]到各進(jìn)程本身的大小。如有一個進(jìn)程其大小為200頁，只分配給它20個塊，這樣，它必然會有很高的缺頁率；而另一個進(jìn)程只有10頁，卻有10個物理塊閑置未用。 2) 按比例分配算法 這是根據(jù)進(jìn)程的大小按比例分配物理塊的算法。如果系統(tǒng)中共有n個進(jìn)程，每個進(jìn)程的頁面數(shù)為Si，則系統(tǒng)中各進(jìn)程頁面數(shù)的總和為：又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個進(jìn)程所能分到的物理塊數(shù)為bi，將有：b應(yīng)該取整，它必須大于最小物理塊數(shù)。 niiSS1mSSbii 3) 考慮優(yōu)先權(quán)的分配算法 在實(shí)際應(yīng)用中，為了照顧到重要的、緊迫的作業(yè)能盡快地完成， 應(yīng)為它分配較多的內(nèi)存空間。通常采取的方法是把內(nèi)存中可供分配

9、的所有物理塊分成兩部分：一部分按比例地分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)卦黾悠湎鄳?yīng)份額后，分配給各進(jìn)程。在有的系統(tǒng)中，如重要的實(shí)時控制系統(tǒng)，則可能是完全按優(yōu)先權(quán)來為各進(jìn)程分配其物理塊的。 5.2.3 調(diào)頁策略調(diào)頁策略 1. 何時調(diào)入頁面何時調(diào)入頁面 1) 預(yù)調(diào)頁策略 2) 請求調(diào)頁策略 2. 從何處調(diào)入頁面從何處調(diào)入頁面 在請求分頁系統(tǒng)中的外存分為兩部分：用于存放文件的文件區(qū)和用于存放對換頁面的對換區(qū)。通常，由于對換區(qū)是采用連續(xù)分配方式，而事件是采用離散分配方式，故對換區(qū)的磁盤I/O速度比文件區(qū)的高。這樣，每當(dāng)發(fā)生缺頁請求時，系統(tǒng)應(yīng)從何處將缺頁調(diào)入內(nèi)存，可分成如下三種情況： (

10、1) 系統(tǒng)擁有足夠的對換區(qū)空間，這時可以全部從對換區(qū)調(diào)入所需頁面，以提高調(diào)頁速度。為此，在進(jìn)程運(yùn)行前， 便須將與該進(jìn)程有關(guān)的文件，從文件區(qū)拷貝到對換區(qū)。 (2) 系統(tǒng)缺少足夠的對換區(qū)空間，這時凡是不會被修改的文件，都直接從文件區(qū)調(diào)入；而當(dāng)換出這些頁面時，由于它們未被修改而不必再將它們換出，以后再調(diào)入時，仍從文件區(qū)直接調(diào)入。但對于那些可能被修改的部分，在將它們換出時，便須調(diào)到對換區(qū)，以后需要時，再從對換區(qū)調(diào)入。 (3) UNIX方式。由于與進(jìn)程有關(guān)的文件都放在文件區(qū)，故凡是未運(yùn)行過的頁面，都應(yīng)從文件區(qū)調(diào)入。而對于曾經(jīng)運(yùn)行過但又被換出的頁面，由于是被放在對換區(qū)，因此在下次調(diào)入時，應(yīng)從對換區(qū)調(diào)入。由

11、于UNIX系統(tǒng)允許頁面共享，因此， 某進(jìn)程所請求的頁面有可能已被其它進(jìn)程調(diào)入內(nèi)存，此時也就無須再從對換區(qū)調(diào)入。 3. 頁面調(diào)入過程頁面調(diào)入過程 每當(dāng)程序所要訪問的頁面未在內(nèi)存時，便向CPU發(fā)出一缺頁中斷，中斷處理程序首先保留CPU環(huán)境，分析中斷原因后， 轉(zhuǎn)入缺頁中斷處理程序。該程序通過查找頁表，得到該頁在外存的物理塊后， 如果此時內(nèi)存能容納新頁，則啟動磁盤I/O將所缺之頁調(diào)入內(nèi)存，然后修改頁表。如果內(nèi)存已滿，則須先按照某種置換算法從內(nèi)存中選出一頁準(zhǔn)備換出；如果該頁未被修改過，可不必將該頁寫回磁盤；但如果此頁已被修改， 則必須將它寫回磁盤，然后再把所缺的頁調(diào)入內(nèi)存， 并修改頁表中的相應(yīng)表項(xiàng)，置其

12、存在位為“1”，并將此頁表項(xiàng)寫入快表中。在缺頁調(diào)入內(nèi)存后，利用修改后的頁表， 去形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)。 5.3 頁面置換算法頁面置換算法 5.3.1 最佳置換算法和先進(jìn)先出置換算法最佳置換算法和先進(jìn)先出置換算法 1. 最佳(Optimal)置換算法 最佳置換算法是由Belady于1966年提出的一種理論上的算法。 其所選擇的被淘汰頁面，將是以后永不使用的， 或許是在最長(未來)時間內(nèi)不再被訪問的頁面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁率。 假定系統(tǒng)為某進(jìn)程分配了三個物理塊， 并考慮有以下的頁面號引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，

13、0，1，7，0，1 進(jìn)程運(yùn)行時， 先將7，0，1三個頁面裝入內(nèi)存。 以后， 當(dāng)進(jìn)程要訪問頁面2時， 將會產(chǎn)生缺頁中斷。此時OS根據(jù)最佳置換算法， 將選擇頁面7予以淘汰。 引用率70770170122010320304243230321201201770101頁框(物理塊）203圖 5-3 利用最佳頁面置換算法時的置換圖 2. 先進(jìn)先出先進(jìn)先出(FIFO)頁面置換算法頁面置換算法 引用率70770170122010323104430230321013201770201頁框2304204230230127127011圖 5-4 利用FIFO置換算法時的置換圖 First-In-First-Out

14、(FIFO) AlgorithmReference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 53 frames (3 pages can be in memory at a time per process)4 framesFIFO Replacement Beladys Anomaly more frames less page faults1231234125349 page faults1231235124510 page faults443FIFO Illustrating Beladys Anamoly5.3.2 最近最久未使用最近最久未使用

15、(LRU)置換算法置換算法 1. LRU(Least Recently Used)置換算法的描述置換算法的描述 圖 5-5 LRU頁面置換算法 引用率70770170122010320304403230321132201710701頁框4024320321022. LRU置換算法的硬件支持置換算法的硬件支持 1) 寄存器寄存器 為了記錄某進(jìn)程在內(nèi)存中各頁的使用情況，須為每個在內(nèi)存中的頁面配置一個移位寄存器，可表示為 R=Rn-1Rn-2Rn-3 R2R1R0 圖 5-6 某進(jìn)程具有8個頁面時的LRU訪問情況 2) 棧棧 圖 5-7 用棧保存當(dāng)前使用頁面時棧的變化情況 4474707407047

16、1704101740107412107421207412107426210765.3.3 Clock置換算法置換算法 1. 簡單的簡單的Clock置換算法置換算法 圖 5-8 簡單Clock置換算法的流程和示例 入口查尋指針前進(jìn)一步，指向下一個表目頁面訪問位0?選擇該頁面淘汰是返回置頁面訪問位“0”否塊號頁號訪問位指針0124034215650711替換指針2. 改進(jìn)型改進(jìn)型Clock置換算法置換算法 由訪問位A和修改位M可以組合成下面四種類型的頁面： 1類(A=0, M=0): 表示該頁最近既未被訪問， 又未被修改， 是最佳淘汰頁。 2類(A=0, M=1)： 表示該頁最近未被訪問， 但已被

17、修改， 并不是很好的淘汰頁。 3類(A=1, M=0)： 最近已被訪問， 但未被修改， 該頁有可能再被訪問。 4類(A=1, M=1): 最近已被訪問且被修改， 該頁可能再被訪問。 其執(zhí)行過程可分成以下三步： (1) 從指針?biāo)甘镜漠?dāng)前位置開始， 掃描循環(huán)隊(duì)列， 尋找A=0且M=0的第一類頁面， 將所遇到的第一個頁面作為所選中的淘汰頁。 在第一次掃描期間不改變訪問位A。 (2) 如果第一步失敗，即查找一周后未遇到第一類頁面， 則開始第二輪掃描，尋找A=0且M=1的第二類頁面，將所遇到的第一個這類頁面作為淘汰頁。在第二輪掃描期間，將所有掃描過的頁面的訪問位都置0。 (3) 如果第二步也失敗，亦即

18、未找到第二類頁面，則將指針返回到開始的位置，并將所有的訪問位復(fù)0。 然后重復(fù)第一步，如果仍失敗，必要時再重復(fù)第二步，此時就一定能找到被淘汰的頁。 5.3.4 其它置換算法（自學(xué)）其它置換算法（自學(xué)） 1. 最少使用(LFU： Least Frequently Used)置換算法2. 頁面緩沖算法(PBA： Page Buffering Algorithm) 5.3.5 訪問內(nèi)存的有效時間（自學(xué)）訪問內(nèi)存的有效時間（自學(xué)）5.4“抖動”與工作集 If a process does not have “enough” pages, the page-fault rate is very high

19、Page fault to get page Replace existing frame But quickly need replaced frame back This leads to: Low CPU utilization Operating system thinking that it needs to increase the degree of multiprogramming Another process added to the system Thrashing a process is busy swapping pages in and out5.4“抖動”與工作

20、集Graph of Page Faults Versus The Number of Frames5.5 請求分段存儲管理方式請求分段存儲管理方式 5.5.1 請求分段中的硬件支持請求分段中的硬件支持 1. 段表機(jī)制段表機(jī)制 段名 段長 段的基址 存取方式 訪問字段A 修改位M 存在位P 增補(bǔ)位 外存始址 在段表項(xiàng)中， 除了段名(號)、 段長、 段在內(nèi)存中的起始地址外， 還增加了以下諸項(xiàng)：(1) 存取方式。 (2) 訪問字段A。 (3) 修改位M。 (4) 存在位P。 (5) 增補(bǔ)位。 (6) 外存始址。 2. 缺段中斷機(jī)構(gòu)缺段中斷機(jī)構(gòu) 虛段S不在內(nèi)存阻塞請求進(jìn)程內(nèi)存中有合適的空閑區(qū)嗎？從外存讀入段S修改段表及內(nèi)存空區(qū)鏈喚醒請求進(jìn)程返回空區(qū)容量總和能否滿足？空區(qū)拼接，以形成一個合適的空區(qū)淘汰一個或幾個實(shí)段，以形成一個合適空區(qū)否否是是圖圖 5-12 請求分段系統(tǒng)中的中斷處理過程請求分段系統(tǒng)中的中斷處理過程3. 地址變換機(jī)構(gòu)地址變換機(jī)構(gòu) 訪問sww段長?符合存取方式?段S在主存?修改訪問字段,如寫訪問,置修改位1形成訪問主存地址(A) (主存始址) (位移量w)返回分段越界中斷處理分段保護(hù)中斷處理缺段中斷處理是是是否否否圖 5-1