第四章_虛擬存儲管理

1、操作系統(tǒng) Operating System第第4 4章章 存儲管理存儲管理4.1 4.1 存儲管理的原理存儲管理的原理 4.2 4.2 連續(xù)分配存儲管理連續(xù)分配存儲管理 4.3 4.3 離散分配存儲管理離散分配存儲管理4.4 4.4 內(nèi)核主存管理內(nèi)核主存管理4.5 4.5 虛擬存儲技術(shù)虛擬存儲技術(shù)4.6 4.6 虛擬頁式存儲管理虛擬頁式存儲管理 4.7 4.7 虛擬段式存儲管理虛擬段式存儲管理4.8 4.8 存儲管理實例存儲管理實例4.5 4.5 虛擬存儲技術(shù)虛擬存儲技術(shù)4.5.1 4.5.1 程序局部性原理程序局部性原理 4.5.2 4.5.2 虛擬存儲的實現(xiàn)虛擬存儲的實現(xiàn)&虛擬內(nèi)存

2、技術(shù)(Virtual Memory)(Virtual Memory)誕生于1961年。&廣泛使用是從上個世紀70年代初以后，今天幾乎所有的操作系統(tǒng)都采用虛擬內(nèi)存技術(shù)來管理內(nèi)存。&這是一種利用虛擬存儲器來邏輯擴充物理內(nèi)存的技術(shù)。其基本思想是用軟硬件技術(shù)把內(nèi)存與外存這兩級存儲器當成一級用軟硬件技術(shù)把內(nèi)存與外存這兩級存儲器當成一級存儲器來用，從而給用戶提供了一個比內(nèi)存也比任何應(yīng)用程存儲器來用，從而給用戶提供了一個比內(nèi)存也比任何應(yīng)用程序大得多的虛擬存儲器，使得用戶編程時再也不用考慮內(nèi)存序大得多的虛擬存儲器，使得用戶編程時再也不用考慮內(nèi)存大小的限制了，給用戶編程帶來極大的方便。大小的限制

3、了，給用戶編程帶來極大的方便。&虛擬內(nèi)存技術(shù)的實現(xiàn)也利用了自動覆蓋和交換技術(shù)。 4.5.1 4.5.1 程序局部性原理程序局部性原理&1.1.局部性原理局部性原理(principle of locality)： 指程序在執(zhí)行過程中的一個較短時期內(nèi)，所執(zhí)行的指令地址和指令的操作數(shù)地址，分別局限于一定區(qū)域。&2.2.局部性主要表現(xiàn)：局部性主要表現(xiàn)：F時間局部性：時間局部性：是指一段指令在某一時間段內(nèi)會被反復執(zhí)行。是指一段指令在某一時間段內(nèi)會被反復執(zhí)行。即程序某一部分的數(shù)據(jù)或指令被重復性地訪問，它們對應(yīng)于即程序某一部分的數(shù)據(jù)或指令被重復性地訪問，它們對應(yīng)于程序結(jié)構(gòu)中的循環(huán)、子

4、程序、常用到的變量及數(shù)據(jù)等程序結(jié)構(gòu)中的循環(huán)、子程序、常用到的變量及數(shù)據(jù)等 ；F空間局部性空間局部性：是指一旦某一個存儲單元被訪問，那么它附近是指一旦某一個存儲單元被訪問，那么它附近的單元也將很快被訪問。這對應(yīng)于程序結(jié)構(gòu)中的順序執(zhí)行的的單元也將很快被訪問。這對應(yīng)于程序結(jié)構(gòu)中的順序執(zhí)行的指令、線性數(shù)據(jù)結(jié)構(gòu)以及在相鄰位置存放的數(shù)據(jù)或變量等。指令、線性數(shù)據(jù)結(jié)構(gòu)以及在相鄰位置存放的數(shù)據(jù)或變量等。而程序中的分支和調(diào)用子程序只是將程序的訪問空間從一處而程序中的分支和調(diào)用子程序只是將程序的訪問空間從一處移到另外一處，仍具有局部性。移到另外一處，仍具有局部性。F排他性：排他性：程序運行不但體現(xiàn)在時間、空間的局部

5、性，還體現(xiàn)在某些程序段執(zhí)行的排他性。即程序設(shè)計者編程時要考慮程序執(zhí)行時所能遇到的各種情況，但具體到一次程序的執(zhí)行，并不會發(fā)生所有的狀況。因而某些程序段在進程整個運行期間，可能因而某些程序段在進程整個運行期間，可能根本不使用，如出錯處理、分支語句等。根本不使用，如出錯處理、分支語句等。因而，沒有用到的程序段就不必調(diào)入內(nèi)存。另外，有些程序段僅執(zhí)行一次，以后就再也不會用到，這樣的程序段也沒有必要一直占用內(nèi)存空間。 &綜上所述：綜上所述：程序只要裝入內(nèi)存一部分就可以運行，程序只要裝入內(nèi)存一部分就可以運行，當用到不在內(nèi)存的部分時，再將其裝入內(nèi)存。當用到不在內(nèi)存的部分時，再將其裝入內(nèi)存。換句換句話

6、就是說程序全部裝入內(nèi)存并不是程序運行的必要話就是說程序全部裝入內(nèi)存并不是程序運行的必要條件。條件。 4.5.2 4.5.2 虛擬存儲的實現(xiàn)虛擬存儲的實現(xiàn)1.1.虛擬存儲技術(shù)虛擬存儲技術(shù) 如果把程序部分裝入內(nèi)存，其余大部分放在外存，而程序又能運行，這樣我們就擁有了一個比有限的實際內(nèi)存空間大得多的、邏輯的虛擬內(nèi)存空間。即用大容量的外存來模擬內(nèi)存，這種存儲模式就稱之為虛擬存儲技術(shù)。 2.2.虛擬技術(shù)實現(xiàn)的關(guān)鍵虛擬技術(shù)實現(xiàn)的關(guān)鍵(1)怎樣才能發(fā)現(xiàn)欲執(zhí)行的指令或數(shù)據(jù)不在內(nèi)存怎樣才能發(fā)現(xiàn)欲執(zhí)行的指令或數(shù)據(jù)不在內(nèi)存? 簡單有效方法就是進行標識簡單有效方法就是進行標識(2)怎樣將不在內(nèi)存的部分調(diào)入進來怎樣將不

7、在內(nèi)存的部分調(diào)入進來。 通常系統(tǒng)采用中斷技術(shù)完成調(diào)入工作。通常系統(tǒng)采用中斷技術(shù)完成調(diào)入工作。(3)在內(nèi)存中的作業(yè)如何組織？在內(nèi)存中的作業(yè)如何組織？ 一個進程可被分為多次調(diào)入內(nèi)存，這樣很難保證進程在內(nèi)存一個進程可被分為多次調(diào)入內(nèi)存，這樣很難保證進程在內(nèi)存中占據(jù)一個連續(xù)的空間，實際上進程在內(nèi)存中是離散存儲的。中占據(jù)一個連續(xù)的空間，實際上進程在內(nèi)存中是離散存儲的。 虛擬技術(shù)進一步說明虛擬技術(shù)進一步說明 系統(tǒng)要提供必要的硬件支持，如虛擬頁式存儲中的頁表機制、缺頁中斷機構(gòu)以及相應(yīng)的地址變換機構(gòu)。 虛擬存儲技術(shù)是將內(nèi)存與外存有機地結(jié)合在一起，從而得到一個容量很大的虛擬空間。使用戶感到有一個很大的內(nèi)存，不用

8、再考慮內(nèi)存的容量限制。 虛存雖然比內(nèi)存要大得多，但不可能無限大，其大小要受到外存空間的限制以及CPU地址所能表示范圍的限制。&大程序：大程序：可在較小的可用內(nèi)存中執(zhí)行較大的用戶可在較小的可用內(nèi)存中執(zhí)行較大的用戶程序；程序；&大的用戶空間：大的用戶空間：提供給用戶可用的虛擬內(nèi)存空間提供給用戶可用的虛擬內(nèi)存空間通常大于物理內(nèi)存通常大于物理內(nèi)存(real memory)(real memory)&并發(fā)：并發(fā)：可在內(nèi)存中容納更多程序并發(fā)執(zhí)行；可在內(nèi)存中容納更多程序并發(fā)執(zhí)行；&易于開發(fā)易于開發(fā)：與覆蓋技術(shù)比較，不必影響編程時的：與覆蓋技術(shù)比較，不必影響編程時的程序結(jié)構(gòu)程序

9、結(jié)構(gòu)3.3.引入虛擬存儲技術(shù)的好處引入虛擬存儲技術(shù)的好處總?cè)萘坎怀^物理內(nèi)存和外存交換區(qū)容量之和。其運行速度接近于內(nèi)存，每位的成本又接近于外存，是一種性能非常優(yōu)越的存儲管理技術(shù) 4. 4. 虛擬存儲技術(shù)的特征虛擬存儲技術(shù)的特征&不連續(xù)性：物理內(nèi)存分配的不連續(xù)，虛擬地址空間使用的不連續(xù)（數(shù)據(jù)段和棧段之間的空閑空間，共享段和動態(tài)鏈接庫占用的空間）&部分交換：與交換技術(shù)相比較，虛擬存儲的調(diào)入和調(diào)出是對部分虛擬地址空間進行的；&大空間：通過物理內(nèi)存和快速外存相結(jié)合，提供大范圍的虛擬地址空間虛擬存儲技術(shù)的種類：虛擬存儲技術(shù)的種類：虛擬頁式虛擬段式虛擬段頁式4.6 4.6 虛擬頁式

10、存儲管理虛擬頁式存儲管理 4.6.1 4.6.1 虛擬頁式存儲的實現(xiàn)虛擬頁式存儲的實現(xiàn) 4.6.2 4.6.2 頁面分配策略頁面分配策略 4.6.3 4.6.3 頁面置換方法頁面置換方法4.6.4 4.6.4 虛擬頁式存儲的優(yōu)缺點虛擬頁式存儲的優(yōu)缺點返回&系統(tǒng)自動地將作業(yè)的地址空間分頁，將系統(tǒng)的主存空間分塊，頁與塊等大小。&在作業(yè)運行前，只把初始需要的一部分頁面裝入內(nèi)存塊里，運行中需要訪問自己地址空間中的但當前不在內(nèi)存的頁面時產(chǎn)生缺頁中斷，由缺頁中斷服務(wù)程序?qū)⑺璧捻撁嬲{(diào)入內(nèi)存。&若此時內(nèi)存中沒有空閑物理塊安置請求調(diào)入的新頁面，則系統(tǒng)按預定的置換策略自動選擇一個或一些在

11、內(nèi)存的頁面，把它們換出到外存。&這里的請求調(diào)入和置換功能都是比實分頁存儲管理增加的內(nèi)容，是實現(xiàn)虛擬存儲的主要功能。 4.6.1 4.6.1 虛擬頁式存儲的實現(xiàn)虛擬頁式存儲的實現(xiàn) 頁面的動態(tài)調(diào)度步驟：頁面的動態(tài)調(diào)度步驟：1、找到被訪問頁面在外存的地址；2、在內(nèi)存中找一個空閑頁面； （1）如果沒有，按照淘汰算法選擇一個內(nèi)存頁面； （2）將此內(nèi)存頁面寫回外存，修改頁表及頁面分配表；3、讀入所需的頁面，修改頁表及頁面分配表；4、重新啟動進程執(zhí)行被中斷的指令。&標記某頁是否在內(nèi)存，用于查詢標記某頁是否在內(nèi)存，用于查詢要訪問的要訪問的頁在不在內(nèi)存。頁表如下：頁在不在內(nèi)存。頁表如下：頁號頁號

12、 物理塊號物理塊號 狀態(tài)位狀態(tài)位P P 訪問位訪問位A A 修改位修改位M M外存地址外存地址2.2.頁表機制頁表機制其中：外存地址外存地址指出該頁在外存的地址，供調(diào)入該頁時用；狀態(tài)狀態(tài)為指示該頁是否在內(nèi)存，供程序訪問時用，也是檢查是否缺頁的標志位，如置1表示在內(nèi)存 ；訪問位訪問位或訪問字段則是該頁被訪問過的標志或該頁被訪問過的次數(shù)；修改位修改位表示該頁是否被修改過；存取控制字段則是用來限制頁面被安全共享的。 3.3.動態(tài)地址變換動態(tài)地址變換&在虛擬頁式存儲中，應(yīng)采用動態(tài)地址變換方式，因為某一欲在虛擬頁式存儲中，應(yīng)采用動態(tài)地址變換方式，因為某一欲執(zhí)行的指令可能不在內(nèi)存，只能在指令執(zhí)行之

13、前完成地址變執(zhí)行的指令可能不在內(nèi)存，只能在指令執(zhí)行之前完成地址變換。換。任一作業(yè)都應(yīng)在自己的虛擬地址空間中執(zhí)行，任一作業(yè)都應(yīng)在自己的虛擬地址空間中執(zhí)行，所以要為所以要為用戶作業(yè)設(shè)置一個虛擬地址指針用戶作業(yè)設(shè)置一個虛擬地址指針VP，虛擬地址依然是由頁號，虛擬地址依然是由頁號和頁內(nèi)偏移地址組成的。和頁內(nèi)偏移地址組成的。&系統(tǒng)總是執(zhí)行系統(tǒng)總是執(zhí)行VP虛指針所指向的指令，為了將虛擬地址虛指針所指向的指令，為了將虛擬地址VP變換為對應(yīng)的實存地址，因此變換為對應(yīng)的實存地址，因此先要查找頁表。若從頁表中查先要查找頁表。若從頁表中查出此頁不在內(nèi)存（狀態(tài)位為出此頁不在內(nèi)存（狀態(tài)位為0），則產(chǎn)生一個缺頁中

14、斷。），則產(chǎn)生一個缺頁中斷。此時，此時，進程暫停當前指令執(zhí)行，進程暫停當前指令執(zhí)行，CPU轉(zhuǎn)去執(zhí)行缺頁中斷處理程序。轉(zhuǎn)去執(zhí)行缺頁中斷處理程序。若該頁已在內(nèi)存，若該頁已在內(nèi)存，則指令的地址映射過程與頁式存儲是一樣則指令的地址映射過程與頁式存儲是一樣的。即將塊號和頁內(nèi)地址相拼接形成物理地址的。即將塊號和頁內(nèi)地址相拼接形成物理地址IP，處理器再，處理器再從從IP中取指令執(zhí)行。中取指令執(zhí)行。4.4.缺頁中斷缺頁中斷 n no o y ye es s n no o y ye es s y ye es s n no o 硬 件 部 分 軟 件 部 分 圖 4.30 缺 頁 中 斷 處 理 流 程 進進 程

15、程 被被 創(chuàng)創(chuàng) 建建 后后 ， 進進 入入 就就 緒緒 隊隊 列列 進進 程程 被被 調(diào)調(diào) 度度 執(zhí)執(zhí) 行行 啟啟 動動 待待 執(zhí)執(zhí) 行行 指指 令令計計 算算 虛虛 頁頁 號號 與與頁頁 內(nèi)內(nèi) 地地 址址 該該 頁頁 在在 內(nèi)內(nèi) 存存 ？ 地地 址址 映映 射射 執(zhí)執(zhí) 行行 下下 一一 條條 指指 令令 訪訪 問問 內(nèi)內(nèi) 存存 完完 成成 該該 指指令 保保 留留 當當 前前 進進 程程 現(xiàn)現(xiàn) 場場 按按 某某 算算 法法 選選一一 頁頁 淘淘 汰汰 調(diào)調(diào) 入入 所所 需需 頁頁 面面 該該 頁頁 已已改改 過過 調(diào)調(diào) 整整 頁頁 表表 及及空空 閑閑 頁頁 面面 表表 恢恢 復復 被被 中

16、中斷斷 進進 程程 現(xiàn)現(xiàn)場 把把 該該 頁頁寫寫 回回 外外存存 有有 空空 閑閑頁頁面面嗎 ？ 5.5.缺頁率缺頁率&雖然通過缺頁中斷將所需要的頁調(diào)入內(nèi)存，但缺頁中斷的頻繁發(fā)生會嚴重影響程序執(zhí)行的效率。為了標識缺頁中斷發(fā)生的頻度，可以引入缺頁率來表示。 &設(shè)進程在其執(zhí)行期間共進行了S次訪頁操作，其中成功訪頁次數(shù)為A（訪問時該頁在主存），不成功的訪頁次數(shù)為B（即發(fā)生了缺頁中斷），顯然有：S=A+B，&則該進程的缺頁率f定義為：fB/S。&顯然缺頁率越低越好。4.6.2 4.6.2 頁面分配策略頁面分配策略&虛擬存儲管理在進行頁面分配時，要考慮這虛擬存儲管

17、理在進行頁面分配時，要考慮這樣的問題：空閑頁面如何管理；采用什么樣樣的問題：空閑頁面如何管理；采用什么樣的分配策略；為進程分配多少物理塊比較合的分配策略；為進程分配多少物理塊比較合適；在什么時間進行頁面分配等。適；在什么時間進行頁面分配等。 1.1.空閑頁面管理空閑頁面管理&同頁式存儲管理相似，虛擬存儲方式下的空閑頁面的管理也可以采用位示圖或空閑頁面鏈的形式。&由于主存中所有進程的虛擬地址空間之和遠大于主存空間，因此進程執(zhí)行時常發(fā)生缺頁中斷，這樣不斷地調(diào)入新頁，很快就使主存空間飽和。以后再發(fā)生缺頁時，要先淘汰一頁才能裝入新頁，這使得缺頁處理時間過長，減緩了進程的執(zhí)行速度，從而影

18、響到系統(tǒng)的性能。&在實際的系統(tǒng)中，總是維持一定數(shù)量的空閑塊，而不是耗盡所有的空閑塊。即空閑塊數(shù)可以在某一區(qū)間浮動，一旦空閑塊數(shù)小于下限值，系統(tǒng)就進行頁面置換，以釋放出一些空閑塊，使得總的空閑塊數(shù)不超過系統(tǒng)規(guī)定的上限值即可。即系統(tǒng)設(shè)置專門的獨立進程負責頁面置換，以保證鏈表的適當規(guī)模。2 2 分配策略（內(nèi)存）分配策略（內(nèi)存）&可變分配：可變分配：是指一個進程所擁有的物理塊數(shù)是不定的，這種是指一個進程所擁有的物理塊數(shù)是不定的，這種分配方式稱之為可變分配。分配方式稱之為可變分配。&固定分配固定分配是指為每個進程分配一固定頁數(shù)的內(nèi)存空間，在整是指為每個進程分配一固定頁數(shù)的內(nèi)存空間

19、，在整個運行期間都不再改變。個運行期間都不再改變。& 平均分配算法，平均分配算法，是將系統(tǒng)中所有可供分配的物理塊，平均是將系統(tǒng)中所有可供分配的物理塊，平均分配給每一個進程。例如，當系統(tǒng)中有分配給每一個進程。例如，當系統(tǒng)中有80個空閑塊，個空閑塊，4個進個進程時，每個進程可分得程時，每個進程可分得20個物理塊。這種平均分配方式因其個物理塊。這種平均分配方式因其未考慮各進程本身的大小，會造成事實上的不公平。如有一未考慮各進程本身的大小，會造成事實上的不公平。如有一個進程其大小為個進程其大小為100頁，只分配給它頁，只分配給它20個塊，這樣它必將會個塊，這樣它必將會有很高的缺頁率；而另一個進

20、程只有有很高的缺頁率；而另一個進程只有10頁，卻有頁，卻有10個塊在閑個塊在閑置未用。所以在平均的思想下，還要考慮進程的大小。置未用。所以在平均的思想下，還要考慮進程的大小。& 按比例分配算法，按比例分配算法，根據(jù)進程的大小按比例分配空閑塊。設(shè)根據(jù)進程的大小按比例分配空閑塊。設(shè)系統(tǒng)中現(xiàn)有系統(tǒng)中現(xiàn)有m個進程、個進程、n個空閑塊，每個進程擁有的頁數(shù)為個空閑塊，每個進程擁有的頁數(shù)為Si，則系統(tǒng)中所有進程頁數(shù)之和為：則系統(tǒng)中所有進程頁數(shù)之和為： S = S1 + S2 + S3 + + Sm 則為每個進程分配的物理塊數(shù)為：則為每個進程分配的物理塊數(shù)為： Bi = （Si / S） n ，Bi應(yīng)

21、向下取整。應(yīng)向下取整。& 優(yōu)先權(quán)分配算法，優(yōu)先權(quán)分配算法，為優(yōu)先權(quán)高的作業(yè)分配較多的內(nèi)存空間，為優(yōu)先權(quán)高的作業(yè)分配較多的內(nèi)存空間，這樣可以使重要或緊迫的任務(wù)盡快完成。這時可以將內(nèi)存中這樣可以使重要或緊迫的任務(wù)盡快完成。這時可以將內(nèi)存中的空閑塊分成兩部分：一部分按比例分配給各進程，另一部的空閑塊分成兩部分：一部分按比例分配給各進程，另一部分則根據(jù)各進程的優(yōu)先權(quán)，適當?shù)貫槠湓黾酉鄳?yīng)份額。分則根據(jù)各進程的優(yōu)先權(quán)，適當?shù)貫槠湓黾酉鄳?yīng)份額。2 2 分配策略（外存）分配策略（外存）1、靜態(tài)分配、靜態(tài)分配 一個進程在運行之前，將其頁面全部裝入外存。當某一外存頁面被調(diào)入內(nèi)存時，并不釋放所占用的外存頁面

22、。2、動態(tài)分配、動態(tài)分配 一個進程在運行之前，僅將未裝入內(nèi)存的那部分頁面裝入外存。當某一外存頁面被調(diào)入內(nèi)存時，釋放所占用的外存頁面。3.3.工作集工作集&(1)(1)為保證進程能正常運行最少需要多少物理塊。為保證進程能正常運行最少需要多少物理塊。 從理論上講，進程只要獲得一個物理塊就可以運行。但是進程正常運行所需的最少物理塊數(shù)與計算機的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式。由于分頁是系統(tǒng)的行為，可能會出現(xiàn)下面的情景： 由此可見，由此可見，系統(tǒng)應(yīng)保證任一條系統(tǒng)應(yīng)保證任一條指令執(zhí)行時，其所涉及的虛擬地址指令執(zhí)行時，其所涉及的虛擬地址所在的頁都應(yīng)在內(nèi)存中。這個頁數(shù)所在的頁都應(yīng)在內(nèi)存

23、中。這個頁數(shù)就是進程所需要的最小塊數(shù)就是進程所需要的最小塊數(shù)，若系，若系統(tǒng)為進程所分配的物理塊數(shù)少于此統(tǒng)為進程所分配的物理塊數(shù)少于此值時，進程將無法運行。值時，進程將無法運行。 123456涉及涉及6 6次缺頁中斷的指令次缺頁中斷的指令指令指令copy A to B數(shù)據(jù)數(shù)據(jù)A：數(shù)據(jù)數(shù)據(jù)B：&(2)(2)為使進程能有效地工作，應(yīng)為它分配多少物理塊合適為使進程能有效地工作，應(yīng)為它分配多少物理塊合適&隨著為每個進程所分配物理塊數(shù)目的減少，將使進程執(zhí)行中的缺頁率提高，導致非生產(chǎn)性開銷過大，從而降低了進程的執(zhí)行速度，嚴重時導致進程不能向前推進。最少物理塊數(shù)只能保證程序能執(zhí)行下去，而不是最

24、合適的塊數(shù)。&在1968年，Denning提出了工作集理論。所謂工作集就是進程在某段時間里實際上要訪問的頁的集合。依據(jù)程序執(zhí)行時的局部特性，可以利用程序過去的行為來估計它未來的行為。故定義運行進程在定義運行進程在t tw w到到t t這個時間間隔內(nèi)所訪問的頁的集合這個時間間隔內(nèi)所訪問的頁的集合為該進程在時間為該進程在時間t t的工作集，記為的工作集，記為WW（t t，w w）。并把變量）。并把變量w w稱稱之為之為“工作集窗口尺寸工作集窗口尺寸”，工作集中所包含的頁面數(shù)稱為，工作集中所包含的頁面數(shù)稱為“工作集尺寸工作集尺寸”，記為，記為|W(t,w)|W(t,w)|。例如例如:訪問頁面

25、：訪問頁面：Twt-wtW(t,w)=2,3,5,8訪問頁面：訪問頁面：Twwt1t2W(t1,w)=2,3,5,8W(t2,w)=3,5,7,8,9(3)(3)工作集的應(yīng)用工作集的應(yīng)用&工作集工作集W W（t t，w w）是二元函數(shù)，隨）是二元函數(shù)，隨t t、w w的值而改變。的值而改變。首先工作首先工作集與時間有關(guān)，即不同時間的工作集其所包含的頁面可能不集與時間有關(guān)，即不同時間的工作集其所包含的頁面可能不同，其所包含的頁面?zhèn)€數(shù)也可能不同；同，其所包含的頁面?zhèn)€數(shù)也可能不同；其次工作集也是工作其次工作集也是工作集窗口尺寸集窗口尺寸w w的函數(shù)，體現(xiàn)在工作集尺寸的函數(shù)，體現(xiàn)在工作集尺寸|

26、W(t,w)|W(t,w)|隨隨w w的增加的增加而變大，即滿足而變大，即滿足|W(t,w)|W(t,w+a)|W(t,w)|W(t,w+a)|，a0a0。&工作集窗口尺寸與缺頁率關(guān)系密切，工作集窗口尺寸與缺頁率關(guān)系密切，若若w w增大，工作集尺寸增大，工作集尺寸|W|W|隨之增加（即所含的頁面數(shù)增多），缺頁率就會下降。隨之增加（即所含的頁面數(shù)增多），缺頁率就會下降。倘倘若若w w含蓋了整個作業(yè)虛擬空間，缺頁率降為含蓋了整個作業(yè)虛擬空間，缺頁率降為0 0，也就失去了虛，也就失去了虛存意義；反之若存意義；反之若w w選取過小，將引起頻繁缺頁，導致系統(tǒng)性能選取過小，將引起頻繁缺頁，導致系統(tǒng)

27、性能下降。二者之間的關(guān)系可以如圖所示。下降。二者之間的關(guān)系可以如圖所示。&虛存中并不是要取消缺頁率，而是要使缺頁率維持在一個較低的水平上。因此可以取拐點所對應(yīng)的工作集尺寸作為分給進程的物理塊數(shù)，實驗分析表明，這個數(shù)應(yīng)是進程總頁面數(shù)的一半。即一個進程應(yīng)獲得其所需頁數(shù)一半的空間時，再進入內(nèi)存執(zhí)行。 缺 頁 率 f 拐 點 工 作 集 尺 寸 |W| 圖 4.31 缺 頁 率 與 工 作 集 尺 寸 之 間 的 關(guān) 系 4.4.頁面調(diào)入時機頁面調(diào)入時機 何時將一個頁面由外存調(diào)入內(nèi)存。 預調(diào)頁策略 &也稱先行調(diào)度，即一頁面被訪問前就已經(jīng)預先置入內(nèi)存，以減少今后的缺頁率。&主要適

28、于進程的許多頁存放在外存的連續(xù)區(qū)域中的情況。有的系統(tǒng)結(jié)合請求調(diào)入使用，即每次缺頁時裝入多個頁面。優(yōu)點：提高調(diào)頁的I/O效率。缺點：基于預測，若調(diào)入的頁在以后很少被訪問，則效率低。預調(diào)頁的成功率僅約50%，常用于程序裝入時的調(diào)頁。& 請求調(diào)頁策略請求調(diào)頁策略&當發(fā)生頁面故障時進行調(diào)度，即當進程訪問不在當發(fā)生頁面故障時進行調(diào)度，即當進程訪問不在內(nèi)存的頁面引發(fā)缺頁中斷時，由系統(tǒng)根據(jù)這種訪內(nèi)存的頁面引發(fā)缺頁中斷時，由系統(tǒng)根據(jù)這種訪問請求把所缺頁面裝入內(nèi)存。問請求把所缺頁面裝入內(nèi)存。&優(yōu)點：優(yōu)點：由請求調(diào)入策略裝入的頁一定會被訪問，由請求調(diào)入策略裝入的頁一定會被訪問，再加之比較容

29、易實現(xiàn)，故在目前的虛擬存儲器中，再加之比較容易實現(xiàn)，故在目前的虛擬存儲器中，大多采用此策略。大多采用此策略。&缺點：缺點：每次僅調(diào)入一頁，增加了磁盤每次僅調(diào)入一頁，增加了磁盤I/OI/O的啟動的啟動頻率。頻率。&在請求分頁系統(tǒng)中，常把外存分為兩部分：一部分是文件區(qū)，用于存放文件；另一部分是對換區(qū)，用于存放對換頁面。通常，對換區(qū)的磁盤輸入輸出速度比文件區(qū)的高，這是因為對換區(qū)所規(guī)定的盤塊要比文件區(qū)的大得多。 從交換區(qū)調(diào)入&若系統(tǒng)擁有足夠的對換區(qū)空間，可在進程運行前，將與該進程有關(guān)的文件拷貝到對換區(qū)。以后就從對換區(qū)調(diào)入所需頁面，以提高調(diào)頁速度。 5.5.從何處調(diào)入頁面從何處調(diào)

30、入頁面 從交換區(qū)及文件區(qū)調(diào)入&若系統(tǒng)缺少足夠的對換區(qū)空間，則在交換區(qū)中只保存被修改過的頁面。因為未被修改的頁面在文件區(qū)中有副本。因此凡是沒被修改的頁，均從文件區(qū)調(diào)入；而已修改過的頁面則從交換區(qū)調(diào)入。 UNIX方式&與進程有關(guān)的文件都放在文件區(qū)，故凡是未運行過的頁面，都應(yīng)從文件區(qū)調(diào)入。而對于曾經(jīng)運行過而又被換出的頁面，總是存放在對換區(qū)中。因此在下次調(diào)入時，應(yīng)從對換區(qū)調(diào)入。由于在UNIX系統(tǒng)中允許頁面共享，因此，某進程所請求的頁面有可能已由其它進程調(diào)入內(nèi)存，此時也就無須再從對換區(qū)調(diào)入。1.頁面置換方式 當內(nèi)存空間已沒有空閑頁面而又要調(diào)入新頁時，必須采用一定的算法在內(nèi)存中選擇某一頁面

31、淘汰，所采用的算法稱之為頁面置換算法。 如果被淘汰的頁面在內(nèi)存期間曾被修改過，還要將此頁重新寫回到外存，以便保留最新的副本。然后再換進新的頁面。(1)頁面置換方式 頁面淘汰可以在整個內(nèi)存空間范圍內(nèi)進行，稱之為全局置換。也可以只在一個進程空間范圍內(nèi)考慮，稱之為局部置換。即當某一進程請求新頁時，而該進程又沒有空閑塊，則只能淘汰自己的一個頁面而不能淘汰其它進程的頁面。 4.6.3 4.6.3 頁面置換方法頁面置換方法 (2) (2) 空閑塊分配方式空閑塊分配方式&若為進程分配固定的物理塊數(shù)，在其執(zhí)行期間再也不改變，則稱為固定分配。初始進程塊數(shù)的多少難以確定。若太少，則缺頁頻繁，系統(tǒng)開銷大；若

32、太多，則并發(fā)進程數(shù)目少，造成CPU空閑或其它資源空閑的情況。&為進程分配的物理塊數(shù)在其運行期間是可變的，則稱為可變分配。進程在運行中，系統(tǒng)可調(diào)整為該進程分配的物理塊，直至進程的缺頁率達到適當程度。在頁面置換算法討論中，為了比較各種方法的在頁面置換算法討論中，為了比較各種方法的優(yōu)劣，總是限定為固定分配局部置換。優(yōu)劣，總是限定為固定分配局部置換。固定分配局部置換：固定分配局部置換：固定分配全局置換：固定分配全局置換：可變分配局部置換可變分配局部置換可變分配全局置換可變分配全局置換(3) 內(nèi)存管理策略內(nèi)存管理策略&( (1)最佳淘汰算法OPT(Optimal)&這是Belad

33、y于1966年提出的一種理論上的算法。該算法每次都淘汰以后永不使用的，或者過最長的時間后才會被訪問的頁面。&顯然，采用這種算法會保證最低的缺頁率，但它是無法實現(xiàn)的，因為它必須知道頁面“將來”的訪問情況。不過，該算法仍有一定意義，可作為衡量其他算法優(yōu)劣的一個標準。 2.2.頁面置換算法頁面置換算法 假定系統(tǒng)為某個進程分配了三個物理塊，進程的訪問順序為7，0，1，2，0，3，0，4，2，3，0，3，2，1，2OPTOPT置換算法示例：置換算法示例：7，0，1， 2，0，3，0，4，2， 3，0 ，3， 2，1， 27 *7 0 *7 0 1 *2 0 1 *2 0 12 0 3 *2 0

34、32 4 3 *2 4 32 4 32 0 3 *2 0 32 0 32 1 3 *2 1 3缺頁次數(shù)8，成功訪問次數(shù)7次，缺頁率f=8/15=53.33%（2 2）先進先出淘汰算法）先進先出淘汰算法FIFOFIFO&這是最早出現(xiàn)的淘汰算法。&總是淘汰最先進入內(nèi)存的頁面。它實現(xiàn)簡單，只需把進程中已調(diào)入內(nèi)存的頁面，按先后次序鏈成一個隊列，并設(shè)置一個所謂的替換指針，使它總是指向內(nèi)存中最老的頁面。&缺點：效率不高，因為它與進程實際的運行規(guī)律不相適應(yīng)，比如常用的全局變量所在的頁面或者循環(huán)體所在頁面都可能被它選為淘汰對象。出現(xiàn)belady現(xiàn)象。 &Belady現(xiàn)象：采用F

35、IFO算法時，如果對一個進程未分配它所要求的全部頁面，有時就會出現(xiàn)分配的頁面數(shù)增多，缺頁率反而提高的異常現(xiàn)象。&Belady現(xiàn)象的描述：一個進程P要訪問M個頁，OS分配N個內(nèi)存頁面給進程P；對一個訪問序列S，發(fā)生缺頁次數(shù)為PE（S,N）。當N增大時，PE(S, N)時而增大，時而減小。&Belady現(xiàn)象的原因：FIFO算法的置換特征與進程訪問內(nèi)存的動態(tài)特征是矛盾的，即被置換的頁面并不是進程不會訪問的。FIFOFIFO淘汰算法示例：淘汰算法示例：7，0，1， 2，0，3，0，4， 2， 3，0 ，3， 2，1， 27 *7 0 *7 0 1 *2 0 1 *2 0 12 3 1

36、*2 3 0 *4 3 0 *4 2 0 *4 2 3 *0 2 3 *0 2 30 2 30 1 3 *0 1 2 *3 3塊內(nèi)存時，缺頁率塊內(nèi)存時，缺頁率f=12/15=80%f=12/15=80%；4 4塊塊f=8/15=53.33%f=8/15=53.33%7，0，1， 2，0，3，0，4， 2， 3，0 ，3， 2，1， 27 *7 0 *7 0 1 *7 0 1 2 *7 0 1 23 0 1 2 *3 0 1 2 3 4 1 2 *3 4 1 2 3 4 1 2 3 4 0 2 *3 4 0 23 4 0 23 4 0 1 *2 4 0 1 *練習練習: 對如下的頁面訪問序列:

37、1 2 3 4 1 2 5 1 2 3 4 5 設(shè)進程開始運行時所有頁面均在外存,采用FIFO淘汰算法, 計算進程所分的物理塊分別為3和4時,缺頁率各是多少?(3)(3)最近最久未使用算法最近最久未使用算法(LRU, (LRU, Least Recently UsedLeast Recently Used） 根據(jù)頁面調(diào)入內(nèi)存后的使用情況，選擇內(nèi)存中最久未使用的頁面被置換。這是局部性原理的合理近似，性能接近最佳算法。 OPT算法使用頁面將要被訪問的時間，LRU算法使用頁面最后一次被訪問的時間。二者唯一的差別是：OPT是向后看的，而LRU是向前看的。 7，0，1， 2，0，3，0，4， 2， 3，

38、0 ，3， 2，1， 27 *7 0 *7 0 1 *2 0 1 *2 0 12 0 3 *2 0 34 0 3 *4 0 2 *4 3 2 *0 3 2 *0 3 20 3 21 3 2 *1 3 2 10次，缺頁率次，缺頁率f=10/15=66.67%LRULRU的兩個實現(xiàn)算法：的兩個實現(xiàn)算法： &計時法：計時法：對于每一頁面增設(shè)一個訪問時間計時器，每當一個頁面被訪問時，就將當時的絕對時鐘拷貝到對應(yīng)的訪問時間計時器中，這樣系統(tǒng)記錄了內(nèi)存中所有頁面最后一次被訪問的時間。淘汰時，選取訪問時間計時器的值最小的頁面。&堆棧法：堆棧法：每當進程訪問某頁面時，便將該頁面的頁號從棧中移出

39、，將它壓入棧頂。棧頂始終是最新被訪問的頁面的編號。棧底則是最近最久未被使用的頁面的頁面號。 假定現(xiàn)有一進程所訪問的頁面的頁面號序列為：假定現(xiàn)有一進程所訪問的頁面的頁面號序列為：4 4，8 8，0 0，8 8，1 1，0 0，2 2，1 1，2 2，6 6&隨著進程的訪問，棧中頁面號的變化情況隨著進程的訪問，棧中頁面號的變化情況：4，8，0，8，1，0，1，2，1，2，6 2 1 2 6 1 0 1 1 2 1 2 0 8 8 1 0 0 0 0 1 8 8 0 0 8 8 8 8 8 0 4 4 4 4 4 4 4 4 4 4 8LRULRU的開銷是很大的，必須有硬件的支持，完全由軟件

40、實的開銷是很大的，必須有硬件的支持，完全由軟件實現(xiàn)其速度至少會減少現(xiàn)其速度至少會減少1010倍，因此倍，因此LRULRU近似算法更實用些。近似算法更實用些。 &這是一種LRU的近似算法，是通過對FIFO算法進行簡單改造，結(jié)合頁表中的訪問位而得來一種淘汰算法。&該算法首先檢查位于FIFO鏈鏈首的頁，如果它的訪問位為0，則選擇該頁淘汰；如果它的訪問位為1，則清除其訪問位，將它移至FIFO鏈的鏈尾，重復此算法的查找過程，直至遇到新鏈首頁是一個訪問位為0的較早進入內(nèi)存的頁為止，把它選為被淘汰的頁。 (4)(4)二次機會淘汰算法二次機會淘汰算法SC(Second Chance)SC(Se

41、cond Chance)（5 5）時鐘）時鐘(Clock)(Clock)淘汰算法淘汰算法 &缺點：就是需要把訪問位為1的處于鏈首的頁移至鏈尾，這需要一定的開銷。一種改進的方法就是把進程所訪問的頁面鏈成一個環(huán)形鏈表，再設(shè)一個指針指向最老的頁面，于是形成了一種簡單實用的LRU近似算法時鐘淘汰算法。&該算法首先檢測指針所指的頁面，如果它的訪問位為0，則淘汰該頁，新裝入的頁插入到此位置，然后指針前進一個位置；如果它的訪問位為1，則清除為0，并將指針前進一個位置，繼續(xù)檢查訪問位。重復此過程，直到找到訪問位為0的頁面為止。 (6)(6)最近未用淘汰算法最近未用淘汰算法NUR(NUR(Not

42、 Used RecentlyNot Used Recently) ) &它把FIFO算法的思想與頁面的訪問位和修改位結(jié)合起來確定一個接近LRU算法的淘汰對象。&該算法每次都盡量選擇最近最久未被寫過的頁面淘汰，這種干凈的頁面可以不被寫回到磁盤。在實現(xiàn)時，為每一個頁面設(shè)置初始值為0的訪問位和修改位。當對某頁面執(zhí)行寫操作時，其修改位和訪問位均由硬件置成1；當對某頁面執(zhí)行讀操作時，只有其訪問位被硬件置成1。按照下列次序選擇被淘汰的頁面：按照下列次序選擇被淘汰的頁面：訪問位，修改位；直接淘汰； 訪問位，修改位；淘汰之前寫回外存；訪問位，修改位；直接淘汰；訪問位，修改位；淘汰之前寫回外存；最近未使用淘汰算法就是最近未使用淘汰算法就是LRULRU的一種近似算法，它總是淘汰最近的一種近似算法，它總是淘汰最近未使用的頁，如果被淘汰的頁在內(nèi)存期間沒有被修改過，該頁未使用的頁，如果被淘汰的頁在內(nèi)存期間沒有被修改過，該頁可不必重新寫入外存，將新頁覆蓋到被淘汰的頁上即可。可不必重新寫入外存，將新頁覆蓋到被淘汰的頁上即可。訪問位訪問位A A0 0 表示該頁未被訪問過；表示該頁未被訪問過； 1 1 表示該頁已被訪問過