計算機操作系統(tǒng)第五章-虛擬存儲器教材

1、第五章 虛擬存儲器第一節(jié) 虛擬存儲器的基本概念一、虛擬存儲器的引入在前面介紹的各種存儲管理方式中，用戶作業(yè)一旦被裝入內(nèi)存， 就會一直駐留其中， 直到進程運行結(jié)束 (駐留性 )。有些存儲管理方式還 存在一次性。因此，用戶作業(yè)要最終運行完畢，系統(tǒng)必須給它提供不 短于作業(yè)長度的存儲空間。于是就出現(xiàn)了兩種問題：? 長作業(yè)無法運行? 大量作業(yè)無法同時運行程序運行的 局部性原理 ：在一段時間內(nèi)一個程序的執(zhí)行往往呈現(xiàn) 出高度的局部性。前期討論：P112-113;局部性還表現(xiàn)在兩方面：(1) 一條指令被執(zhí)行， 則不久以后該指令很可能再次執(zhí)行； 某個數(shù) 據(jù)被訪問，則不久以后該數(shù)據(jù)附近的數(shù)據(jù)很可能被訪問。產(chǎn)生這類

2、局 部性的典型原因，是由于在程序中存在著大量的循環(huán)操作。(2) 程序在 一段時間內(nèi) 所訪問的地址，可能 集中 在一定的范圍之 內(nèi)。若某一存儲單元被使用，則在一定時間內(nèi)，與該存儲單元相鄰 的單元很可能被使用。其典型情況便是程序的順序執(zhí)行、數(shù)組的處理等。局部性原理是在存儲分配時克服駐留性、實現(xiàn)虛擬存儲的依據(jù)。二、虛擬存儲器的定義 定義： 具有 請求調(diào)入 功能和置換功能，能從 邏輯上 對內(nèi)存容量進行擴 充的一種存儲器系統(tǒng)。其訪問速度接近于內(nèi)存，而其容量和每位的成本卻又接近于外存。從整體看 速度是主存 容量是輔存特性：虛擬存儲器連續(xù)性離散性一次性多次性駐留性交換性虛擬性對用戶而言，它訪問特性和內(nèi)存一樣

3、；它以 CPU時間和外存空間 換取寶貴內(nèi)存空間，是操作系統(tǒng)中的一種資源轉(zhuǎn)換技術(shù)。容量：? 一個虛擬存儲器的最大容量是由計算機的地址結(jié)構(gòu)確定的。如：若CPU的有效地址寬度為32位，則程序可以尋址范圍 是0232-1，即 虛存容量可達4GB。?虛擬存儲器的容量與主存的實際大小沒有直接的關(guān)系，而是在主存與輔存的容量之和的范圍內(nèi)。三、虛擬存儲技術(shù)基本原理：P115把內(nèi)存與外存有機地結(jié)合起來使用，從而得到一個容量很大的“內(nèi) 存”。當(dāng)進程開始運行時，先將它的一部分內(nèi)容裝入內(nèi)存，另一部分暫 時留在外存。 在運行過程中， 當(dāng)要訪問的指令 /數(shù)據(jù)不在內(nèi)存時， 由 OS 自動將內(nèi)存中的一些內(nèi)容調(diào)到外存，藤出空間，

4、再將馬上要訪問的內(nèi) 容從外存調(diào)入內(nèi)存。目的： 提高內(nèi)存利用率；為大作業(yè)的運行提供可能。實現(xiàn)方法：? 請求分頁系統(tǒng)? 請求分段系統(tǒng)第二節(jié) 請求分頁式存儲管理方式一、基本原理對靜態(tài)分頁式存儲管理進行改進 ：請求分頁式存儲管理在進程開 始運行之前，不是將作業(yè)的全部頁裝入，而是裝入開始的少數(shù)幾頁 （甚 至一頁）入內(nèi)存。之后根據(jù)進程運行的 需要，利用請求調(diào)入 技術(shù)，動態(tài) 地裝入后續(xù)頁；當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁時，則又利用 置換技術(shù)，根據(jù)某種算法 淘汰 一個頁，以便藤出空間 裝入 新的一頁。請求分頁式存儲管理需要解決下面三個問題：? OS 如何知道進程要訪問的頁面在不在內(nèi)存中；? 當(dāng)發(fā)現(xiàn)缺頁時，

5、如何把所缺頁面調(diào)入內(nèi)存；? 當(dāng)內(nèi)存中沒有空閑塊時，為了要接受一個新頁，需要把老的一頁淘 汰出去，根據(jù)什么策略選擇準(zhǔn)備淘汰的頁。二、硬件的支持1、改進頁表的結(jié)構(gòu)頁號物理塊號狀態(tài)位P訪問字段A修改位M外存地址?狀態(tài)位（駐留位）：表示該頁目前是在內(nèi)存還是在外存；?訪問字段：記錄該頁最近 是否被訪問過或被訪問的次數(shù)；?修改位：表示該頁在本次讀入內(nèi)存后 是否在內(nèi)存中被改寫過；?外存地址：用于指出該頁在 外存上的地址，通常是物理塊號，供調(diào) 入該頁時參考。2、增加缺頁中斷機構(gòu)：每當(dāng)進程要訪問的一個邏輯地址所屬的頁目前不在內(nèi)存，就產(chǎn)生缺頁中斷，進行調(diào)頁或換頁處理。?在地址變換過程中，在頁表中發(fā)現(xiàn)所要訪問的頁不

6、在內(nèi)存，則產(chǎn)生 缺頁中斷。操作系統(tǒng)接到此中斷信號后，就調(diào)出 缺頁中斷處理程序， 根據(jù)頁表中給出的外存地址，將該頁調(diào)入內(nèi)存，使作業(yè)繼續(xù)運行下去（實 現(xiàn)了請求調(diào)入）；?如果內(nèi)存中有空閑塊，則 分配一塊，將新調(diào)入頁 裝入內(nèi)存，并修改 頁表中相應(yīng)頁表項目的駐留位及相應(yīng)的內(nèi)存塊號；?若此時內(nèi)存中沒有空閑塊，則要 淘汰某頁。若將被淘汰的頁在內(nèi)存 期間被修改過，則要將其 寫回外存（實現(xiàn)了置換）；缺頁中斷的中斷處理過程，見下圖左。3、修改后的地址變換流程，見下圖右P158T穿留CPU現(xiàn)場老多TO硯伴將一頁賦外存換入內(nèi)存從外存申授到猷頁將該頁寫回外存8命令CPU.以丹存讀缺頁倏改頁表圖4124請 的三、存儲分配

7、方法1、存儲分配方法的改進：?在進程開始執(zhí)行時，只將最開始和最常用的部分（如主程序、主菜單） 按頁裝入內(nèi)存。為整個進程建立頁表，記錄進程各頁使用內(nèi)存的情況。其他頁在進程執(zhí)行的過程中被動態(tài)地裝入。?當(dāng)需要訪問的頁不在內(nèi)存中時，系統(tǒng)產(chǎn)生并處理缺頁中斷。?頁表在頁被調(diào)入、換出時要被改寫，記錄進程的各頁對內(nèi)存使用情 況的變化。2、物理塊的分配策略和分配算法 ?最小物理塊數(shù)及其確定最小物理塊數(shù)是指能保證進程正常運行所需要的最小物理塊數(shù)。它取決于指令的格式、功能和尋址方式。? 物理塊的分配算法P138-140? 物理塊的置換策略P135-137四、調(diào)頁策略1、調(diào)頁時機 確定何時調(diào)頁? 預(yù)調(diào)入：一次調(diào)入一批

8、預(yù)計即將訪問的頁。本方法主要用于進程的首次頁調(diào)入。? 請求調(diào)入：缺頁時調(diào)入，一次調(diào)入一頁。2、調(diào)頁地址 確定從何處調(diào)入? 全部從 對換區(qū) 調(diào)入、調(diào)出；? 需要修改的部分從對換區(qū)調(diào)入、調(diào)出，其他部分從文件區(qū)調(diào)入；? 初次調(diào)入，從文件區(qū)；調(diào)出放到交換區(qū)；再次調(diào)入，從交換區(qū)。3、調(diào)頁過程 確定如何調(diào)頁調(diào)頁過程即缺頁中斷處理程序的處理過程，如前面的框圖。調(diào)頁 過程中，重要的一步是按照一定的 頁面置換算法 淘汰內(nèi)存中的一頁， 空出一塊來存放新調(diào)入的頁。第三節(jié) 頁面置換算法頁面置換算法 是“ 選擇一頁，換出內(nèi)存 ”時選擇哪一頁的原則和 方法。置換算法的好壞，直接影響存儲管理的 性能 。置換算法的理想方案，

9、是將那些訪問概率高的頁面留在內(nèi)存中， 而將那些訪問概率最低的頁面換出內(nèi)存。對換出頁面的不同選擇形成 不同的置換算法。 一個好的頁面置換算法應(yīng)該 有較低 的頁面更換頻率 ， 避免頻繁地換頁造成系統(tǒng)性能的下降。一、幾種簡單的算法1、隨機淘汰算法當(dāng)系統(tǒng)設(shè)計人員無法確定哪類頁訪問的頻率低的情況下，就隨機 地選擇一個用戶頁，將其換出。2、最佳置換算法(只是一種理論上的算法)每次將以后最長時間內(nèi)不再被訪問或永遠不再被訪問的頁換出。 該算法保證最低的缺頁率。二、先進先出(FIFO)置換算法1、算法思想：選擇在內(nèi)存中駐留時間最長的頁，交換出去。例如：假定系統(tǒng)為某進程分配了三個物理塊，并考慮有以下的頁面訪問串：

10、7，0，1, 2，0，3, 0，4，2, 3, 0，3，2，1, 2，0，1,7, 0, 1頁框圖4-26利用FIFO置換算法時的置換圖2、算法的實現(xiàn)：將一個進程已調(diào)入的 頁按進入的先后次序鏈成一個 隊列，設(shè)一個頭指針、一個尾指針。每次將頭指針指向的頁替換出去；新調(diào)入的頁插到隊尾。3、算法的特點:?簡單、易實現(xiàn)，需要的硬件支持少。?但是，經(jīng)常要使用的頁，頻繁地被選擇換出（最先被調(diào)入的頁可能是 最常使用的）。三、最近最久未使用（LRU）置換算法1、算法思想：選擇最后一次訪問時間距離當(dāng)前時間最長的一頁并淘汰 之。即淘汰沒有使用的時間最長的頁。該算法需要較多的硬件支持。頁框圖427 LRU頁面置換算

11、法2、硬件支持與實現(xiàn)（1）移位寄存器：為每個在內(nèi)存中的頁面配置一個移位寄存器（字），可表示為R=Rn-lRn-2Rn-3 R2R1R0?當(dāng)該頁面被訪問時，將R的最高位置1;?系統(tǒng)定時將所有頁面的移位寄存器邏輯右移一位，進行除2操作；?換頁時將移位寄存器值最小的頁淘汰。（2）棧：保存當(dāng)前頁面使用的變化情況為每個進程建立一個 棧，棧的大小等于分配給進程的塊數(shù)。換頁 時淘汰棧底的頁，最近訪問的頁放在棧頂3、算法特點?比較接近理想的置換算法；?需要較多的硬件支持。四、Clock置換算法（簡化的LRU算法）1、算法思想：頁每被訪問一次，將該頁的訪問位置 1塊號頁號訪問位指針替換01240指針342156

12、50711V圖4-30簡單Clock置換算法的流程和示例2、改進型Clock置換算法由訪問位A和修改位M可以組合成下面四種類型的頁面：?1類（A=0，M=0）:表示該頁最近既未被訪問，又未被修改，是最佳淘汰頁。? 2類（A=0，M=1）:表示該頁最近未被訪問，但已被修改，并不是很 好的淘汰頁。? 3類(A=1 , M=0):最近已被訪問， 但未被修改，該頁有可能再被 訪問。? 4類(A=1 , M=1):最近已被訪問且被修改，該頁有可能再被訪問。其淘汰的過程可分成以下三步:(1) 從指針?biāo)甘镜漠?dāng)前位置開始，循環(huán)掃描隊列，尋找 A=0 且 M=0 的第一類頁面，將所遇到的第一個這樣的頁面作為所

13、選中的淘汰頁。 在第一次掃描期間不改變訪問位 A。(2) 如果第一步失敗， 即查找一周后未遇到第一類頁面， 則開始第二輪掃描，尋找 A=0 且 M=1 的第二類頁面， 將所遇到的第一個這類頁面作 為淘汰頁。在第二輪掃描期間，將所有掃描過的頁面的訪問位都置0。(3) 如果第二步也失敗， 即未找到第二類頁面， 則將指針返回到開始的 位置，并已將所有的訪問位 A 復(fù) 0。然后重復(fù)第一步，如果仍失敗， 必要時再重復(fù)第二步，此時就一定能找到被淘汰的頁。五、其他置換算法1、最少使用(LFU : Least Frequently Used置換算法2、 頁面緩沖算法 (PBA：Page Buffering A

14、lgorithm)P166-169六、虛擬存儲器的性能問題缺頁次數(shù)是影響性能的一個主要因素。1 、影響缺頁次數(shù)的因素? 分配給進程的物理塊數(shù)? 頁面本身的大小 ? 程序的編制方法?頁面淘汰算法2、抖動問題在虛存中，頁面在內(nèi)存與外存之間頻繁調(diào)度，以至于調(diào)度頁面所 需時間比進程實際運行的時間還多，此時系統(tǒng)效率急劇下降，甚至導(dǎo) 致系統(tǒng)崩潰。這種現(xiàn)象稱為顛簸或抖動。原因：?分配給進程的物理頁面數(shù)太少?頁面淘汰算法不合理第四節(jié) 請求分段存儲管理方式一、硬件支持1、改進段表：P171-172段名段長段的存取訪問修改存在增補外存基址方式字段A位M位P位始址2、增加缺段中斷機構(gòu)，每當(dāng)進程要調(diào)用或訪問的一個邏輯

15、段目前 不在 內(nèi)存，就產(chǎn)生缺段中斷。圖4-31請求分段系統(tǒng)中的缺斷處理過程3、改變地址變換過程(訪問訂寸|是是否 _1分段越界 中斷處理分段保護 中斷處理否 缺段中段長？合存取萬式二是修改訪問字段，如寫 訪問，置修改位=1形成訪問主存地址(A)蛙存始址)-K位移量段主存？返回圖432請求分段系統(tǒng)的地址變換過程二、段的共享與保護1、共享段表為實現(xiàn)段的共享，系統(tǒng)建立一個 共享段表，每個共享段在其中占一個表項。1駐1舷主密址tts共享段的作遊席lij段名|段検|主存始址|狀態(tài)共亭本段的作遊沽作業(yè)名作業(yè)號段號存取控制2、共享段的存儲分配?對第一個請求使用該共享段的進程，由系統(tǒng)為該共享段分配一物理 區(qū)，再把共享段調(diào)入該區(qū)，同時將該區(qū)的有關(guān)信息填入請求進程的段表的相應(yīng)項中。還須在共享段表中增加一表項，填寫有關(guān)信息，把count 置為1；?當(dāng)又有其它進程請求調(diào)用該共享段時，由于該共享段已被調(diào)入內(nèi)存，故此時無須再為該段分配內(nèi)存，而只需在 請求進程的段表 中，增 加一表項，填寫該共享段的有關(guān)信息；在 共享段的段表中，填上請求 進程的進程名、存取控制等信息，再執(zhí)行 count ：二count+1操作，以表 明增加了一個進程共享該段。3、共