第四章虛擬存儲(chǔ)管理

1、第四章虛擬存儲(chǔ)管理第第4 4章章 存儲(chǔ)管理存儲(chǔ)管理 4.1 4.1 存儲(chǔ)管理的原理存儲(chǔ)管理的原理 4.2 4.2 連續(xù)分配存儲(chǔ)管理連續(xù)分配存儲(chǔ)管理 4.3 4.3 離散分配存儲(chǔ)管理離散分配存儲(chǔ)管理 4.4 4.4 內(nèi)核主存管理內(nèi)核主存管理 4.5 4.5 虛擬存儲(chǔ)技術(shù)虛擬存儲(chǔ)技術(shù) 4.6 4.6 虛擬頁(yè)式存儲(chǔ)管理虛擬頁(yè)式存儲(chǔ)管理 4.7 4.7 虛擬段式存儲(chǔ)管理虛擬段式存儲(chǔ)管理 4.8 4.8 存儲(chǔ)管理實(shí)例存儲(chǔ)管理實(shí)例 4.5 4.5 虛擬存儲(chǔ)技術(shù)虛擬存儲(chǔ)技術(shù) 4.5.1 4.5.1 程序局部性原理程序局部性原理 4.5.2 4.5.2 虛擬存儲(chǔ)的實(shí)現(xiàn)虛擬存儲(chǔ)的實(shí)現(xiàn)& 虛擬內(nèi)存技術(shù)(V

2、irtual Memory)誕生于1961年。& 廣泛使用是從上個(gè)世紀(jì)70年代初以后，今天幾乎所有的操作系統(tǒng)都采用虛擬內(nèi)存技術(shù)來管理內(nèi)存。&這是一種利用虛擬存儲(chǔ)器來邏輯擴(kuò)充物理內(nèi)存的技術(shù)。其基本思想是用軟硬件技術(shù)把內(nèi)存與外存這兩級(jí)存儲(chǔ)器當(dāng)成一級(jí)存儲(chǔ)器來用，從而給用戶提供了一個(gè)比內(nèi)存也比任何應(yīng)用程序大得多的虛擬存儲(chǔ)器，使得用戶編程時(shí)再也不用考慮內(nèi)存大小的限制了，給用戶編程帶來極大的方便。&虛擬內(nèi)存技術(shù)的實(shí)現(xiàn)也利用了自動(dòng)覆蓋和交換技術(shù)。 4.5.1 4.5.1 程序局部性原理程序局部性原理&1.1.局部性原理局部性原理(principle of locality)：

3、 指程序在執(zhí)行過程中的一個(gè)較短時(shí)期內(nèi)，所執(zhí)行的指令地址和指令的操作數(shù)地址，分別局限于一定區(qū)域。&2.2.局部性主要表現(xiàn)：局部性主要表現(xiàn)：F時(shí)間局部性：是指一段指令在某一時(shí)間段內(nèi)會(huì)被反復(fù)執(zhí)行。即程序某一部時(shí)間局部性：是指一段指令在某一時(shí)間段內(nèi)會(huì)被反復(fù)執(zhí)行。即程序某一部分的數(shù)據(jù)或指令被重復(fù)性地訪問，它們對(duì)應(yīng)于程序結(jié)構(gòu)中的循環(huán)、子程序、分的數(shù)據(jù)或指令被重復(fù)性地訪問，它們對(duì)應(yīng)于程序結(jié)構(gòu)中的循環(huán)、子程序、常用到的變量及數(shù)據(jù)等常用到的變量及數(shù)據(jù)等 ；F 空間局部性空間局部性：是指一旦某一個(gè)存儲(chǔ)單元被訪問，那么它附近的單元也將很快被訪問。是指一旦某一個(gè)存儲(chǔ)單元被訪問，那么它附近的單元也將很快被訪問。

4、這對(duì)應(yīng)于程序結(jié)構(gòu)中的順序執(zhí)行的指令、線性數(shù)據(jù)結(jié)構(gòu)以及在相鄰位置存放的數(shù)據(jù)或這對(duì)應(yīng)于程序結(jié)構(gòu)中的順序執(zhí)行的指令、線性數(shù)據(jù)結(jié)構(gòu)以及在相鄰位置存放的數(shù)據(jù)或變量等。而程序中的分支和調(diào)用子程序只是將程序的訪問空間從一處移到另外一處，變量等。而程序中的分支和調(diào)用子程序只是將程序的訪問空間從一處移到另外一處，仍具有局部性。仍具有局部性。F排他性：排他性：程序運(yùn)行不但體現(xiàn)在時(shí)間、空間的局部性，還體現(xiàn)在某些程序段執(zhí)行的排他性。即程序設(shè)計(jì)者編程時(shí)要考慮程序執(zhí)行時(shí)所能遇到的各種情況，但具體到一次程序的執(zhí)行，并不會(huì)發(fā)生所有的狀況。因而某些程序段因而某些程序段在進(jìn)程整個(gè)運(yùn)行期間，可能根本不使用，如出錯(cuò)處理、分支語(yǔ)在進(jìn)程

5、整個(gè)運(yùn)行期間，可能根本不使用，如出錯(cuò)處理、分支語(yǔ)句等。句等。因而，沒有用到的程序段就不必調(diào)入內(nèi)存。另外，有些程序段僅執(zhí)行一次，以后就再也不會(huì)用到，這樣的程序段也沒有必要一直占用內(nèi)存空間。 &綜上所述：程序只要裝入內(nèi)存一部分就可以運(yùn)行，當(dāng)用到不在內(nèi)綜上所述：程序只要裝入內(nèi)存一部分就可以運(yùn)行，當(dāng)用到不在內(nèi)存的部分時(shí)，再將其裝入內(nèi)存。換句話就是說程序全部裝入內(nèi)存存的部分時(shí)，再將其裝入內(nèi)存。換句話就是說程序全部裝入內(nèi)存并不是程序運(yùn)行的必要條件。并不是程序運(yùn)行的必要條件。 4.5.2 4.5.2 虛擬存儲(chǔ)的實(shí)現(xiàn)虛擬存儲(chǔ)的實(shí)現(xiàn)1.1.虛擬存儲(chǔ)技術(shù)虛擬存儲(chǔ)技術(shù) 如果把程序部分裝入內(nèi)存，其余大部分放在

6、外存，而程序又能運(yùn)行，這樣我們就擁有了一個(gè)比有限的實(shí)際內(nèi)存空間大得多的、邏輯的虛擬內(nèi)存空間。即用大容量的外存來模擬內(nèi)存，這種存儲(chǔ)模式就稱之為虛擬存儲(chǔ)技術(shù)。 2.2.虛擬技術(shù)實(shí)現(xiàn)的關(guān)鍵虛擬技術(shù)實(shí)現(xiàn)的關(guān)鍵(1)怎樣才能發(fā)現(xiàn)欲執(zhí)行的指令或數(shù)據(jù)不在內(nèi)存怎樣才能發(fā)現(xiàn)欲執(zhí)行的指令或數(shù)據(jù)不在內(nèi)存? 簡(jiǎn)單有效方法就是進(jìn)行標(biāo)識(shí)簡(jiǎn)單有效方法就是進(jìn)行標(biāo)識(shí)(2)怎樣將不在內(nèi)存的部分調(diào)入進(jìn)來。怎樣將不在內(nèi)存的部分調(diào)入進(jìn)來。 通常系統(tǒng)采用中斷技術(shù)完成調(diào)入工作。通常系統(tǒng)采用中斷技術(shù)完成調(diào)入工作。(3)在內(nèi)存中的作業(yè)如何組織？在內(nèi)存中的作業(yè)如何組織？ 一個(gè)進(jìn)程可被分為多次調(diào)入內(nèi)存，這樣很難保證進(jìn)程在內(nèi)存中占據(jù)一個(gè)連續(xù)的一個(gè)進(jìn)

7、程可被分為多次調(diào)入內(nèi)存，這樣很難保證進(jìn)程在內(nèi)存中占據(jù)一個(gè)連續(xù)的空間，實(shí)際上進(jìn)程在內(nèi)存中是離散存儲(chǔ)的?？臻g，實(shí)際上進(jìn)程在內(nèi)存中是離散存儲(chǔ)的。 虛擬技術(shù)進(jìn)一步說明虛擬技術(shù)進(jìn)一步說明 系統(tǒng)要提供必要的硬件支持，如虛擬頁(yè)式存儲(chǔ)中的頁(yè)表機(jī)制、缺頁(yè)中斷機(jī)構(gòu)以及相應(yīng)的地址變換機(jī)構(gòu)。 虛擬存儲(chǔ)技術(shù)是將內(nèi)存與外存有機(jī)地結(jié)合在一起，從而得到一個(gè)容量很大的虛擬空間。使用戶感到有一個(gè)很大的內(nèi)存，不用再考慮內(nèi)存的容量限制。 虛存雖然比內(nèi)存要大得多，但不可能無限大，其大小要受到外存空間的限制以及CPU地址所能表示范圍的限制。&大程序：可在較小的可用內(nèi)存中執(zhí)行較大的用戶程序；大程序：可在較小的可用內(nèi)存中執(zhí)行較大的用

8、戶程序；&大的用戶空間：提供給用戶可用的虛擬內(nèi)存空間通常大于大的用戶空間：提供給用戶可用的虛擬內(nèi)存空間通常大于物理內(nèi)存物理內(nèi)存(real memory)(real memory)&并發(fā)：可在內(nèi)存中容納更多程序并發(fā)執(zhí)行；并發(fā)：可在內(nèi)存中容納更多程序并發(fā)執(zhí)行；&易于開發(fā)：與覆蓋技術(shù)比較，不必影響編程時(shí)的程序結(jié)構(gòu)易于開發(fā)：與覆蓋技術(shù)比較，不必影響編程時(shí)的程序結(jié)構(gòu)3.3.引入虛擬存儲(chǔ)技術(shù)的好處引入虛擬存儲(chǔ)技術(shù)的好處總?cè)萘坎怀^物理內(nèi)存和外存交換區(qū)容量之和。其運(yùn)行速度接近于內(nèi)存，每位的成本又接近于外存，是一種性能非常優(yōu)越的存儲(chǔ)管理技術(shù) 4. 4. 虛擬存儲(chǔ)技術(shù)的特征虛擬存儲(chǔ)技術(shù)的

9、特征&不連續(xù)性：物理內(nèi)存分配的不連續(xù)，虛擬地址空間使用的不連續(xù)（數(shù)據(jù)段和棧段之間的空閑空間，共享段和動(dòng)態(tài)鏈接庫(kù)占用的空間）&部分交換：與交換技術(shù)相比較，虛擬存儲(chǔ)的調(diào)入和調(diào)出是對(duì)部分虛擬地址空間進(jìn)行的；&大空間：通過物理內(nèi)存和快速外存相結(jié)合，提供大范圍的虛擬地址空間虛擬存儲(chǔ)技術(shù)的種類：虛擬頁(yè)式虛擬段式虛擬段頁(yè)式 4.6 4.6 虛擬頁(yè)式存儲(chǔ)管理虛擬頁(yè)式存儲(chǔ)管理 4.6.1 4.6.1 虛擬頁(yè)式存儲(chǔ)的實(shí)現(xiàn)虛擬頁(yè)式存儲(chǔ)的實(shí)現(xiàn) 4.6.2 4.6.2 頁(yè)面分配策略頁(yè)面分配策略 4.6.3 4.6.3 頁(yè)面置換方法頁(yè)面置換方法 4.6.4 4.6.4 虛擬頁(yè)式存儲(chǔ)的優(yōu)缺點(diǎn)虛擬頁(yè)式

10、存儲(chǔ)的優(yōu)缺點(diǎn)返回&系統(tǒng)自動(dòng)地將作業(yè)的地址空間分頁(yè)，將系統(tǒng)的主存空間分塊，頁(yè)與塊等大小。&在作業(yè)運(yùn)行前，只把初始需要的一部分頁(yè)面裝入內(nèi)存塊里，運(yùn)行中需要訪問自己地址空間中的但當(dāng)前不在內(nèi)存的頁(yè)面時(shí)產(chǎn)生缺頁(yè)中斷，由缺頁(yè)中斷服務(wù)程序?qū)⑺璧捻?yè)面調(diào)入內(nèi)存。&若此時(shí)內(nèi)存中沒有空閑物理塊安置請(qǐng)求調(diào)入的新頁(yè)面，則系統(tǒng)按預(yù)定的置換策略自動(dòng)選擇一個(gè)或一些在內(nèi)存的頁(yè)面，把它們換出到外存。&這里的請(qǐng)求調(diào)入和置換功能都是比實(shí)分頁(yè)存儲(chǔ)管理增加的內(nèi)容，是實(shí)現(xiàn)虛擬存儲(chǔ)的主要功能。 4.6.1 4.6.1 虛擬頁(yè)式存儲(chǔ)的實(shí)現(xiàn)虛擬頁(yè)式存儲(chǔ)的實(shí)現(xiàn) 頁(yè)面的動(dòng)態(tài)調(diào)度步驟：頁(yè)面的動(dòng)態(tài)調(diào)度步驟：1、找到被訪

11、問頁(yè)面在外存的地址；2、在內(nèi)存中找一個(gè)空閑頁(yè)面； （1）如果沒有，按照淘汰算法選擇一個(gè)內(nèi)存頁(yè)面； （2）將此內(nèi)存頁(yè)面寫回外存，修改頁(yè)表及頁(yè)面分配表；3、讀入所需的頁(yè)面，修改頁(yè)表及頁(yè)面分配表；4、重新啟動(dòng)進(jìn)程執(zhí)行被中斷的指令。&標(biāo)記某頁(yè)是否在內(nèi)存，用于查詢標(biāo)記某頁(yè)是否在內(nèi)存，用于查詢要訪問的頁(yè)在不要訪問的頁(yè)在不在內(nèi)存。頁(yè)表如下：在內(nèi)存。頁(yè)表如下：頁(yè)號(hào) 物理塊號(hào)狀態(tài)位P訪問位A修改位M外存地址2.2.頁(yè)表機(jī)制頁(yè)表機(jī)制其中：外存地址外存地址指出該頁(yè)在外存的地址，供調(diào)入該頁(yè)時(shí)用；狀態(tài)狀態(tài)為指示該頁(yè)是否在內(nèi)存，供程序訪問時(shí)用，也是檢查是否缺頁(yè)的標(biāo)志位，如置1表示在內(nèi)存 ；訪問位訪問位或訪問字段則

12、是該頁(yè)被訪問過的標(biāo)志或該頁(yè)被訪問過的次數(shù)；修改位修改位表示該頁(yè)是否被修改過；存取控制字段則是用來限制頁(yè)面被安全共享的。 3.3.動(dòng)態(tài)地址變換動(dòng)態(tài)地址變換& 在虛擬頁(yè)式存儲(chǔ)中，應(yīng)采用動(dòng)態(tài)地址變換方式，因?yàn)槟骋挥麍?zhí)行的指令可能不在虛擬頁(yè)式存儲(chǔ)中，應(yīng)采用動(dòng)態(tài)地址變換方式，因?yàn)槟骋挥麍?zhí)行的指令可能不在內(nèi)存，只能在指令執(zhí)行之前完成地址變換。任一作業(yè)都應(yīng)在自己的虛擬地址在內(nèi)存，只能在指令執(zhí)行之前完成地址變換。任一作業(yè)都應(yīng)在自己的虛擬地址空間中執(zhí)行，所以要為用戶作業(yè)設(shè)置一個(gè)虛擬地址指針空間中執(zhí)行，所以要為用戶作業(yè)設(shè)置一個(gè)虛擬地址指針VP，虛擬地址依然，虛擬地址依然是由頁(yè)號(hào)和頁(yè)內(nèi)偏移地址組成的。是由頁(yè)

13、號(hào)和頁(yè)內(nèi)偏移地址組成的。&系統(tǒng)總是執(zhí)行系統(tǒng)總是執(zhí)行VP虛指針?biāo)赶虻闹噶?，為了將虛擬地址虛指針?biāo)赶虻闹噶?，為了將虛擬地址VP變換為對(duì)應(yīng)的實(shí)變換為對(duì)應(yīng)的實(shí)存地址，因此先要查找頁(yè)表。若從頁(yè)表中查出此頁(yè)不在內(nèi)存（狀態(tài)位為存地址，因此先要查找頁(yè)表。若從頁(yè)表中查出此頁(yè)不在內(nèi)存（狀態(tài)位為0），則），則產(chǎn)生一個(gè)缺頁(yè)中斷。此時(shí)，進(jìn)程暫停當(dāng)前指令執(zhí)行，產(chǎn)生一個(gè)缺頁(yè)中斷。此時(shí)，進(jìn)程暫停當(dāng)前指令執(zhí)行，CPU轉(zhuǎn)去執(zhí)行缺轉(zhuǎn)去執(zhí)行缺頁(yè)中斷處理程序。若該頁(yè)已在內(nèi)存，則指令的地址映射過程與頁(yè)式存儲(chǔ)是一樣的。頁(yè)中斷處理程序。若該頁(yè)已在內(nèi)存，則指令的地址映射過程與頁(yè)式存儲(chǔ)是一樣的。即將塊號(hào)和頁(yè)內(nèi)地址相拼接形成物理地址即

14、將塊號(hào)和頁(yè)內(nèi)地址相拼接形成物理地址IP，處理器再?gòu)?，處理器再?gòu)腎P中取指令執(zhí)行。中取指令執(zhí)行。4.4.缺頁(yè)中斷缺頁(yè)中斷5.5.缺頁(yè)率缺頁(yè)率&雖然通過缺頁(yè)中斷將所需要的頁(yè)調(diào)入內(nèi)存，但缺頁(yè)中斷的頻繁發(fā)生會(huì)嚴(yán)重影響程序執(zhí)行的效率。為了標(biāo)識(shí)缺頁(yè)中斷發(fā)生的頻度，可以引入缺頁(yè)率來表示。 &設(shè)進(jìn)程在其執(zhí)行期間共進(jìn)行了S次訪頁(yè)操作，其中成功訪頁(yè)次數(shù)為A（訪問時(shí)該頁(yè)在主存），不成功的訪頁(yè)次數(shù)為B（即發(fā)生了缺頁(yè)中斷），顯然有：S=A+B，&則該進(jìn)程的缺頁(yè)率f定義為：fB/S。&顯然缺頁(yè)率越低越好。 4.6.2 4.6.2 頁(yè)面分配策略頁(yè)面分配策略&虛擬存儲(chǔ)管理在進(jìn)行頁(yè)面分配

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

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

17、指為每個(gè)進(jìn)程分配一固定頁(yè)數(shù)的內(nèi)存空間，在整個(gè)運(yùn)行期間都不再改變。不再改變。& 平均分配算法，是將系統(tǒng)中所有可供分配的物理塊，平均分配給每平均分配算法，是將系統(tǒng)中所有可供分配的物理塊，平均分配給每一個(gè)進(jìn)程。例如，當(dāng)系統(tǒng)中有一個(gè)進(jìn)程。例如，當(dāng)系統(tǒng)中有80個(gè)空閑塊，個(gè)空閑塊，4個(gè)進(jìn)程時(shí)，每個(gè)進(jìn)程可分得個(gè)進(jìn)程時(shí)，每個(gè)進(jìn)程可分得20個(gè)物理塊。這種平均分配方式因其未考慮各進(jìn)程本身的大小，會(huì)造成事實(shí)上的個(gè)物理塊。這種平均分配方式因其未考慮各進(jìn)程本身的大小，會(huì)造成事實(shí)上的不公平。如有一個(gè)進(jìn)程其大小為不公平。如有一個(gè)進(jìn)程其大小為100頁(yè)，只分配給它頁(yè)，只分配給它20個(gè)塊，這樣它必將會(huì)有個(gè)塊，這樣它必將會(huì)

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

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

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

21、物理塊數(shù)少于此值時(shí)，進(jìn)程將無法運(yùn)行。 123456涉及涉及6 6次缺頁(yè)中斷的指令次缺頁(yè)中斷的指令指令指令copy A to B數(shù)據(jù)數(shù)據(jù)A：數(shù)據(jù)數(shù)據(jù)B：& (2)(2)為使進(jìn)程能有效地工作，應(yīng)為它分配多少物理塊合適為使進(jìn)程能有效地工作，應(yīng)為它分配多少物理塊合適& 隨著為每個(gè)進(jìn)程所分配物理塊數(shù)目的減少，將使進(jìn)程執(zhí)行中的缺頁(yè)率提高，導(dǎo)致非生產(chǎn)性開銷過大，從而降低了進(jìn)程的執(zhí)行速度，嚴(yán)重時(shí)導(dǎo)致進(jìn)程不能向前推進(jìn)。最少物理塊數(shù)只能保證程序能執(zhí)行下去，而不是最合適的塊數(shù)。&在1968年，Denning提出了工作集理論。所謂工作集就是進(jìn)程在某段時(shí)間里實(shí)際上要訪問的頁(yè)的集合。依據(jù)程序執(zhí)行時(shí)

22、的局部特性，可以利用程序過去的行為來估計(jì)它未來的行為。故定義運(yùn)行進(jìn)程在定義運(yùn)行進(jìn)程在t tw w到到t t這個(gè)時(shí)間間隔內(nèi)這個(gè)時(shí)間間隔內(nèi)所訪問的頁(yè)的集合為該進(jìn)程在時(shí)間所訪問的頁(yè)的集合為該進(jìn)程在時(shí)間t t的工作集，記為的工作集，記為WW（t t，w w）。并把變量）。并把變量w w稱之稱之為為“工作集窗口尺寸工作集窗口尺寸”，工作集中所包含的頁(yè)面數(shù)稱為，工作集中所包含的頁(yè)面數(shù)稱為“工作集尺寸工作集尺寸”，記為，記為|W(t,w)|W(t,w)|。例如例如:訪問頁(yè)面：訪問頁(yè)面：Twt-wtW(t,w)=2,3,5,8訪問頁(yè)面：訪問頁(yè)面：Twwt1t2W(t1,w)=2,3,5,8W(t2,w)=3,

23、5,7,8,9(3)(3)工作集的應(yīng)用工作集的應(yīng)用&工作集工作集W W（t t，w w）是二元函數(shù)，隨）是二元函數(shù)，隨t t、w w的值而改變。首先工作集與時(shí)間有關(guān)，即不同的值而改變。首先工作集與時(shí)間有關(guān)，即不同時(shí)間的工作集其所包含的頁(yè)面可能不同，其所包含的頁(yè)面?zhèn)€數(shù)也可能不同；其次工作集也是時(shí)間的工作集其所包含的頁(yè)面可能不同，其所包含的頁(yè)面?zhèn)€數(shù)也可能不同；其次工作集也是工作集窗口尺寸工作集窗口尺寸w w的函數(shù)，體現(xiàn)在工作集尺寸的函數(shù)，體現(xiàn)在工作集尺寸|W(t,w)|W(t,w)|隨隨w w的增加而變大，的增加而變大，即滿足即滿足|W(t,w)|W(t,w+a)|W(t,w)|W(t,w

24、+a)|，a0a0。& 工作集窗口尺寸與缺頁(yè)率關(guān)系密切，若工作集窗口尺寸與缺頁(yè)率關(guān)系密切，若w w增大，工作集尺寸增大，工作集尺寸|W|W|隨之增加（即所含的隨之增加（即所含的頁(yè)面數(shù)增多），缺頁(yè)率就會(huì)下降。倘若頁(yè)面數(shù)增多），缺頁(yè)率就會(huì)下降。倘若w w含蓋了整個(gè)作業(yè)虛擬空間，缺頁(yè)率降含蓋了整個(gè)作業(yè)虛擬空間，缺頁(yè)率降為為0 0，也就失去了虛存意義；反之若，也就失去了虛存意義；反之若w w選取過小，將引起頻繁缺頁(yè)，導(dǎo)致系統(tǒng)性能下選取過小，將引起頻繁缺頁(yè)，導(dǎo)致系統(tǒng)性能下降。二者之間的關(guān)系可以如圖所示。降。二者之間的關(guān)系可以如圖所示。& 虛存中并不是要取消缺頁(yè)率，而是要使缺頁(yè)率維持在一個(gè)

25、較低的水平上。因虛存中并不是要取消缺頁(yè)率，而是要使缺頁(yè)率維持在一個(gè)較低的水平上。因此可以取拐點(diǎn)所對(duì)應(yīng)的工作集尺寸作為分給進(jìn)程的物理塊數(shù)，實(shí)驗(yàn)分析表明，此可以取拐點(diǎn)所對(duì)應(yīng)的工作集尺寸作為分給進(jìn)程的物理塊數(shù)，實(shí)驗(yàn)分析表明，這個(gè)數(shù)應(yīng)是進(jìn)程總頁(yè)面數(shù)的一半。即一個(gè)進(jìn)程應(yīng)獲得其所需頁(yè)數(shù)一半的空間這個(gè)數(shù)應(yīng)是進(jìn)程總頁(yè)面數(shù)的一半。即一個(gè)進(jìn)程應(yīng)獲得其所需頁(yè)數(shù)一半的空間時(shí)，再進(jìn)入內(nèi)存執(zhí)行。時(shí)，再進(jìn)入內(nèi)存執(zhí)行。 4.4.頁(yè)面調(diào)入時(shí)機(jī)頁(yè)面調(diào)入時(shí)機(jī) 何時(shí)將一個(gè)頁(yè)面由外存調(diào)入內(nèi)存。 預(yù)調(diào)頁(yè)策略 & 也稱先行調(diào)度，即一頁(yè)面被訪問前就已經(jīng)預(yù)先置入內(nèi)存，以減少今后的缺頁(yè)率。&主要適于進(jìn)程的許多頁(yè)存放在外存的連續(xù)區(qū)

26、域中的情況。有的系統(tǒng)結(jié)合請(qǐng)求調(diào)入使用，即每次缺頁(yè)時(shí)裝入多個(gè)頁(yè)面。優(yōu)點(diǎn)：提高調(diào)頁(yè)的I/O效率。缺點(diǎn)：基于預(yù)測(cè)，若調(diào)入的頁(yè)在以后很少被訪問，則效率低。預(yù)調(diào)頁(yè)的成功率僅約50%，常用于程序裝入時(shí)的調(diào)頁(yè)。& 請(qǐng)求調(diào)頁(yè)策略&當(dāng)發(fā)生頁(yè)面故障時(shí)進(jìn)行調(diào)度，即當(dāng)進(jìn)程訪問不在內(nèi)存的頁(yè)面引發(fā)缺頁(yè)中斷時(shí)，由系統(tǒng)根據(jù)這種訪問請(qǐng)求把所缺頁(yè)面裝入內(nèi)存。&優(yōu)點(diǎn)：由請(qǐng)求調(diào)入策略裝入的頁(yè)一定會(huì)被訪問，再加之比較容易實(shí)現(xiàn)，故在目前的虛擬存儲(chǔ)器中，大多采用此策略。&缺點(diǎn)：每次僅調(diào)入一頁(yè)，增加了磁盤I/O的啟動(dòng)頻率。&在請(qǐng)求分頁(yè)系統(tǒng)中，常把外存分為兩部分：一部分是文件區(qū)，用于存放文件；另一部分是

27、對(duì)換區(qū)，用于存放對(duì)換頁(yè)面。通常，對(duì)換區(qū)的磁盤輸入輸出速度比文件區(qū)的高，這是因?yàn)閷?duì)換區(qū)所規(guī)定的盤塊要比文件區(qū)的大得多。 從交換區(qū)調(diào)入&若系統(tǒng)擁有足夠的對(duì)換區(qū)空間，可在進(jìn)程運(yùn)行前，將與該進(jìn)程有關(guān)的文件拷貝到對(duì)換區(qū)。以后就從對(duì)換區(qū)調(diào)入所需頁(yè)面，以提高調(diào)頁(yè)速度。 5.5.從何處調(diào)入頁(yè)面從何處調(diào)入頁(yè)面 從交換區(qū)及文件區(qū)調(diào)入& 若系統(tǒng)缺少足夠的對(duì)換區(qū)空間，則在交換區(qū)中只保存被修改過的頁(yè)面。因?yàn)槲幢恍薷牡捻?yè)面在文件區(qū)中有副本。因此凡是沒被修改的頁(yè)，均從文件區(qū)調(diào)入；而已修改過的頁(yè)面則從交換區(qū)調(diào)入。 UNIX方式& 與進(jìn)程有關(guān)的文件都放在文件區(qū)，故凡是未運(yùn)行過的頁(yè)面，都應(yīng)從文件區(qū)調(diào)入。而

28、對(duì)于曾經(jīng)運(yùn)行過而又被換出的頁(yè)面，總是存放在對(duì)換區(qū)中。因此在下次調(diào)入時(shí)，應(yīng)從對(duì)換區(qū)調(diào)入。由于在UNIX系統(tǒng)中允許頁(yè)面共享，因此，某進(jìn)程所請(qǐng)求的頁(yè)面有可能已由其它進(jìn)程調(diào)入內(nèi)存，此時(shí)也就無須再?gòu)膶?duì)換區(qū)調(diào)入。1.頁(yè)面置換方式 當(dāng)內(nèi)存空間已沒有空閑頁(yè)面而又要調(diào)入新頁(yè)時(shí)，必須采用一定的算法在內(nèi)存中選擇某一頁(yè)面淘汰，所采用的算法稱之為頁(yè)面置換算法。 如果被淘汰的頁(yè)面在內(nèi)存期間曾被修改過，還要將此頁(yè)重新寫回到外存，以便保留最新的副本。然后再換進(jìn)新的頁(yè)面。(1)頁(yè)面置換方式 頁(yè)面淘汰可以在整個(gè)內(nèi)存空間范圍內(nèi)進(jìn)行，稱之為全局置換。也可以只在一個(gè)進(jìn)程空間范圍內(nèi)考慮，稱之為局部置換。即當(dāng)某一進(jìn)程請(qǐng)求新頁(yè)時(shí)，而該進(jìn)程又

29、沒有空閑塊，則只能淘汰自己的一個(gè)頁(yè)面而不能淘汰其它進(jìn)程的頁(yè)面。 4.6.3 4.6.3 頁(yè)面置換方法頁(yè)面置換方法 (2) (2) 空閑塊分配方式空閑塊分配方式& 若為進(jìn)程分配固定的物理塊數(shù)，在其執(zhí)行期間再也不改變，則稱為固定分配。初始進(jìn)程塊數(shù)的多少難以確定。若太少，則缺頁(yè)頻繁，系統(tǒng)開銷大；若太多，則并發(fā)進(jìn)程數(shù)目少，造成CPU空閑或其它資源空閑的情況。& 為進(jìn)程分配的物理塊數(shù)在其運(yùn)行期間是可變的，則稱為可變分配。進(jìn)程在運(yùn)行中，系統(tǒng)可調(diào)整為該進(jìn)程分配的物理塊，直至進(jìn)程的缺頁(yè)率達(dá)到適當(dāng)程度。在頁(yè)面置換算法討論中，為了比較各種方法的優(yōu)劣，總是限定為固定分配局部置換。固定分配局部置換：固

30、定分配局部置換：固定分配全局置換：固定分配全局置換：可變分配局部置換可變分配局部置換可變分配全局置換可變分配全局置換(3) 內(nèi)存管理策略內(nèi)存管理策略&( (1)最佳淘汰算法OPT(Optimal)&這是Belady于1966年提出的一種理論上的算法。該算法每次都淘汰以后永不使用的，或者過最長(zhǎng)的時(shí)間后才會(huì)被訪問的頁(yè)面。&顯然，采用這種算法會(huì)保證最低的缺頁(yè)率，但它是無法實(shí)現(xiàn)的，因?yàn)樗仨氈理?yè)面“將來”的訪問情況。不過，該算法仍有一定意義，可作為衡量其他算法優(yōu)劣的一個(gè)標(biāo)準(zhǔn)。 2.2.頁(yè)面置換算法頁(yè)面置換算法 假定系統(tǒng)為某個(gè)進(jìn)程分配了三個(gè)物理塊，進(jìn)程的訪問順序?yàn)?，0，1，2

31、，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 32 4 3 *2 4 32 4 32 0 3 *2 0 32 0 32 1 3 *2 1 3缺頁(yè)次數(shù)8，成功訪問次數(shù)7次，缺頁(yè)率f=8/15=53.33%（2 2）先進(jìn)先出淘汰算法）先進(jìn)先出淘汰算法FIFOFIFO&這是最早出現(xiàn)的淘汰算法。&總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面。它實(shí)現(xiàn)簡(jiǎn)單，只需把進(jìn)程中已調(diào)入內(nèi)存的頁(yè)面，按先后次序鏈成一個(gè)隊(duì)列，并設(shè)置一個(gè)所謂的替

32、換指針，使它總是指向內(nèi)存中最老的頁(yè)面。&缺點(diǎn)：效率不高，因?yàn)樗c進(jìn)程實(shí)際的運(yùn)行規(guī)律不相適應(yīng)，比如常用的全局變量所在的頁(yè)面或者循環(huán)體所在頁(yè)面都可能被它選為淘汰對(duì)象。出現(xiàn)belady現(xiàn)象。 &Belady現(xiàn)象：采用FIFO算法時(shí)，如果對(duì)一個(gè)進(jìn)程未分配它所要求的全部頁(yè)面，有時(shí)就會(huì)出現(xiàn)分配的頁(yè)面數(shù)增多，缺頁(yè)率反而提高的異常現(xiàn)象。&Belady現(xiàn)象的描述：一個(gè)進(jìn)程P要訪問M個(gè)頁(yè)，OS分配N個(gè)內(nèi)存頁(yè)面給進(jìn)程P；對(duì)一個(gè)訪問序列S，發(fā)生缺頁(yè)次數(shù)為PE（S,N）。當(dāng)N增大時(shí)，PE(S, N)時(shí)而增大，時(shí)而減小。&Belady現(xiàn)象的原因：FIFO算法的置換特征與進(jìn)程訪問內(nèi)存的動(dòng)態(tài)特

33、征是矛盾的，即被置換的頁(yè)面并不是進(jìn)程不會(huì)訪問的。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 *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)存時(shí)，缺頁(yè)率塊內(nèi)存時(shí)，缺頁(yè)率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

34、 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 *練習(xí)練習(xí): 對(duì)如下的頁(yè)面訪問序列: 1 2 3 4 1 2 5 1 2 3 4 5 設(shè)進(jìn)程開始運(yùn)行時(shí)所有頁(yè)面均在外存,采用FIFO淘汰算法, 計(jì)算進(jìn)程所分的物理塊分別為3和4時(shí),缺頁(yè)率各是多少?(3)(3)最近最久未使用算法最近最久未使用算法(LRU, (LRU, Least Recently UsedLeast Recently Used） 根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況，選擇內(nèi)存中最久未使用的頁(yè)面被置換

35、。這是局部性原理的合理近似，性能接近最佳算法。 OPT算法使用頁(yè)面將要被訪問的時(shí)間，LRU算法使用頁(yè)面最后一次被訪問的時(shí)間。二者唯一的差別是：OPT是向后看的，而LRU是向前看的。 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 0 3 *4 0 2 *4 3 2 *0 3 2 *0 3 20 3 21 3 2 *1 3 2 10次，缺頁(yè)率次，缺頁(yè)率f=10/15=66.67%LRULRU的兩個(gè)實(shí)現(xiàn)算法：的兩個(gè)實(shí)現(xiàn)算法： &計(jì)時(shí)法：計(jì)時(shí)法：對(duì)于每一頁(yè)面增設(shè)一個(gè)訪問時(shí)間計(jì)時(shí)器，每當(dāng)一個(gè)

36、頁(yè)面被訪問時(shí)，就將當(dāng)時(shí)的絕對(duì)時(shí)鐘拷貝到對(duì)應(yīng)的訪問時(shí)間計(jì)時(shí)器中，這樣系統(tǒng)記錄了內(nèi)存中所有頁(yè)面最后一次被訪問的時(shí)間。淘汰時(shí)，選取訪問時(shí)間計(jì)時(shí)器的值最小的頁(yè)面。&堆棧法：堆棧法：每當(dāng)進(jìn)程訪問某頁(yè)面時(shí)，便將該頁(yè)面的頁(yè)號(hào)從棧中移出，將它壓入棧頂。棧頂始終是最新被訪問的頁(yè)面的編號(hào)。棧底則是最近最久未被使用的頁(yè)面的頁(yè)面號(hào)。 假定現(xiàn)有一進(jìn)程所訪問的頁(yè)面的頁(yè)面號(hào)序列為：假定現(xiàn)有一進(jìn)程所訪問的頁(yè)面的頁(yè)面號(hào)序列為：4 4，8 8，0 0，8 8，1 1，0 0，2 2，1 1，2 2，6 6&隨著進(jìn)程的訪問，棧中頁(yè)面號(hào)的變化情況隨著進(jìn)程的訪問，棧中頁(yè)面號(hào)的變化情況：4，8，0，8，1，0，1，2，1

37、，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 8LRU的開銷是很大的，必須有硬件的支持，完全由軟件實(shí)現(xiàn)其速度至少會(huì)減少10倍，因此LRU近似算法更實(shí)用些。 &這是一種LRU的近似算法，是通過對(duì)FIFO算法進(jìn)行簡(jiǎn)單改造，結(jié)合頁(yè)表中的訪問位而得來一種淘汰算法。&該算法首先檢查位于FIFO鏈鏈?zhǔn)椎捻?yè)，如果它的訪問位為0，則選擇該頁(yè)淘汰；如果它的訪問位為1，則清除其訪問位，將它移至FIFO鏈的鏈尾，重復(fù)此算法的查找過程，直至遇到新鏈?zhǔn)醉?yè)是一個(gè)訪問位為0的較早進(jìn)入內(nèi)

38、存的頁(yè)為止，把它選為被淘汰的頁(yè)。 (4)(4)二次機(jī)會(huì)淘汰算法二次機(jī)會(huì)淘汰算法SC(Second Chance)SC(Second Chance)（5 5）時(shí)鐘）時(shí)鐘(Clock)(Clock)淘汰算法淘汰算法 &缺點(diǎn)：就是需要把訪問位為1的處于鏈?zhǔn)椎捻?yè)移至鏈尾，這需要一定的開銷。一種改進(jìn)的方法就是把進(jìn)程所訪問的頁(yè)面鏈成一個(gè)環(huán)形鏈表，再設(shè)一個(gè)指針指向最老的頁(yè)面，于是形成了一種簡(jiǎn)單實(shí)用的LRU近似算法時(shí)鐘淘汰算法。&該算法首先檢測(cè)指針?biāo)傅捻?yè)面，如果它的訪問位為0，則淘汰該頁(yè)，新裝入的頁(yè)插入到此位置，然后指針前進(jìn)一個(gè)位置；如果它的訪問位為1，則清除為0，并將指針前進(jìn)一個(gè)位置，繼續(xù)

39、檢查訪問位。重復(fù)此過程，直到找到訪問位為0的頁(yè)面為止。 (6)(6)最近未用淘汰算法最近未用淘汰算法NUR(NUR(Not Used RecentlyNot Used Recently) ) &它把FIFO算法的思想與頁(yè)面的訪問位和修改位結(jié)合起來確定一個(gè)接近LRU算法的淘汰對(duì)象。&該算法每次都盡量選擇最近最久未被寫過的頁(yè)面淘汰，這種干凈的頁(yè)面可以不被寫回到磁盤。在實(shí)現(xiàn)時(shí)，為每一個(gè)頁(yè)面設(shè)置初始值為0的訪問位和修改位。當(dāng)對(duì)某頁(yè)面執(zhí)行寫操作時(shí)，其修改位和訪問位均由硬件置成1；當(dāng)對(duì)某頁(yè)面執(zhí)行讀操作時(shí)，只有其訪問位被硬件置成1。按照下列次序選擇被淘汰的頁(yè)面：按照下列次序選擇被淘汰的頁(yè)面：

40、訪問位，修改位；直接淘汰； 訪問位，修改位；淘汰之前寫回外存；訪問位，修改位；直接淘汰；訪問位，修改位；淘汰之前寫回外存；最近未使用淘汰算法就是最近未使用淘汰算法就是LRULRU的一種近似算法，它總是淘汰最近未使用的頁(yè)，如果被淘汰的一種近似算法，它總是淘汰最近未使用的頁(yè)，如果被淘汰的頁(yè)在內(nèi)存期間沒有被修改過，該頁(yè)可不必重新寫入外存，將新頁(yè)覆蓋到被淘汰的頁(yè)上即的頁(yè)在內(nèi)存期間沒有被修改過，該頁(yè)可不必重新寫入外存，將新頁(yè)覆蓋到被淘汰的頁(yè)上即可。可。訪問位訪問位A A0 0 表示該頁(yè)未被訪問過；表示該頁(yè)未被訪問過； 1 1 表示該頁(yè)已被訪問過；表示該頁(yè)已被訪問過； 修改位修改位M M 0 0 表示該頁(yè)

41、未被修改過表示該頁(yè)未被修改過 1 1 表示該頁(yè)已被修改過表示該頁(yè)已被修改過(1)(1)分配給作業(yè)的內(nèi)存塊數(shù)分配給作業(yè)的內(nèi)存塊數(shù) & 作業(yè)的缺頁(yè)中斷率與作業(yè)所占內(nèi)存塊數(shù)成反比。分配給作業(yè)的內(nèi)存塊數(shù)太少是導(dǎo)致抖動(dòng)現(xiàn)象發(fā)生的最主要的原因;& 實(shí)驗(yàn)分析表明：對(duì)所有的程序來說，要使其有效地工作，它在內(nèi)存中的頁(yè)面數(shù)不應(yīng)少于它的總頁(yè)面數(shù)的一半。 3.影響缺頁(yè)中斷率的因素 (2)(2)頁(yè)面大小的選擇頁(yè)面大小的選擇&雖然缺頁(yè)中斷率與頁(yè)面尺寸成反比，但頁(yè)面尺寸卻不能一味地求大，它一般在0.5KB4KB之間，是個(gè)實(shí)驗(yàn)統(tǒng)計(jì)值。因?yàn)轫?yè)面大時(shí)，頁(yè)表較小，占空間少，查表速度快，缺頁(yè)中斷次數(shù)少，但頁(yè)面

42、調(diào)度時(shí)間長(zhǎng)，頁(yè)內(nèi)碎片較大。頁(yè)面小時(shí)，恰恰相反。 (3)(3)用戶程序編制的方法用戶程序編制的方法 作業(yè)的缺頁(yè)中斷率與程序的局部化（包括時(shí)間局部化和空間作業(yè)的缺頁(yè)中斷率與程序的局部化（包括時(shí)間局部化和空間局部化）程度成反比。用戶程序編制的方法不合適可能導(dǎo)致程序局部化）程度成反比。用戶程序編制的方法不合適可能導(dǎo)致程序運(yùn)行的時(shí)空復(fù)雜度高，缺頁(yè)次數(shù)多。運(yùn)行的時(shí)空復(fù)雜度高，缺頁(yè)次數(shù)多。 例如：一個(gè)程序?qū)⒗纾阂粋€(gè)程序?qū)?28*128的數(shù)組置初值的數(shù)組置初值“0”，假定它僅，假定它僅分得一個(gè)主存塊，頁(yè)面尺寸為分得一個(gè)主存塊，頁(yè)面尺寸為128個(gè)字，數(shù)組中的元素各個(gè)字，數(shù)組中的元素各行分別存放在一頁(yè)中，開始時(shí)

43、第一頁(yè)在主存中，若程序如下行分別存放在一頁(yè)中，開始時(shí)第一頁(yè)在主存中，若程序如下兩種方式編寫：兩種方式編寫：int A128128;for(int j=0;j128;j+) for(int i=0;i128;i+)Aij=0;缺頁(yè)中斷缺頁(yè)中斷(128*128-1)次次int A128128;for(int i=0;i128;i+) for(int j=0;j128;j+)Aij=0; 缺頁(yè)中斷（缺頁(yè)中斷（128-1）次）次&(4)(4)頁(yè)面調(diào)度算法頁(yè)面調(diào)度算法 &抖動(dòng)又叫顛簸，是指一段時(shí)間里，頁(yè)面在內(nèi)存與外存之間頻繁地調(diào)度或換入換出，以至于系統(tǒng)用于調(diào)度頁(yè)面所需要的時(shí)間比進(jìn)程實(shí)際運(yùn)

44、行所占用的時(shí)間還要多。& 好的淘汰算法會(huì)維持一個(gè)較低的缺頁(yè)率。若頁(yè)面置換算法不好，會(huì)使系統(tǒng)出現(xiàn)抖動(dòng)現(xiàn)象。 & 顯然，抖動(dòng)是由于缺頁(yè)中斷率很高而引起的一種壞現(xiàn)象，它將嚴(yán)重影響系統(tǒng)的效率，甚至可能使系統(tǒng)全面崩潰。 防止抖動(dòng)現(xiàn)象的產(chǎn)生和擴(kuò)展，具體方法防止抖動(dòng)現(xiàn)象的產(chǎn)生和擴(kuò)展，具體方法:采取局部置換策略采取局部置換策略 這樣，即使有某個(gè)進(jìn)程發(fā)生了這樣，即使有某個(gè)進(jìn)程發(fā)生了“抖動(dòng)抖動(dòng)”，也不致引起其它進(jìn)程也產(chǎn)生抖，也不致引起其它進(jìn)程也產(chǎn)生抖動(dòng)，從而把抖動(dòng)局限于較小的范圍內(nèi)。動(dòng)，從而把抖動(dòng)局限于較小的范圍內(nèi)。 這種方法并不很好，因?yàn)樗荒軓母旧戏乐苟秳?dòng)的發(fā)生；而且在某進(jìn)這種方法并不很好，

45、因?yàn)樗荒軓母旧戏乐苟秳?dòng)的發(fā)生；而且在某進(jìn)程發(fā)生抖動(dòng)后，還會(huì)長(zhǎng)期地處于磁盤輸入輸出的等待隊(duì)列中，這又會(huì)使其程發(fā)生抖動(dòng)后，還會(huì)長(zhǎng)期地處于磁盤輸入輸出的等待隊(duì)列中，這又會(huì)使其它進(jìn)程缺頁(yè)中斷的處理時(shí)間增長(zhǎng)，從而延長(zhǎng)了等效的訪問時(shí)間。它進(jìn)程缺頁(yè)中斷的處理時(shí)間增長(zhǎng)，從而延長(zhǎng)了等效的訪問時(shí)間。 L=S準(zhǔn)則準(zhǔn)則 Denning于于202X年提出了年提出了“L=S準(zhǔn)則準(zhǔn)則”，用來調(diào)整多道程序度，以使產(chǎn)生缺，用來調(diào)整多道程序度，以使產(chǎn)生缺頁(yè)的平均時(shí)間頁(yè)的平均時(shí)間L等于系統(tǒng)處理進(jìn)程缺頁(yè)的平均時(shí)間等于系統(tǒng)處理進(jìn)程缺頁(yè)的平均時(shí)間S。理論和實(shí)踐表明，此時(shí)的。理論和實(shí)踐表明，此時(shí)的CPU利用得最好。該準(zhǔn)則也得到其它研究

46、人員的證實(shí)。利用得最好。該準(zhǔn)則也得到其它研究人員的證實(shí)。防止抖動(dòng)現(xiàn)象的產(chǎn)生和擴(kuò)展，具體方法防止抖動(dòng)現(xiàn)象的產(chǎn)生和擴(kuò)展，具體方法:掛起若干進(jìn)程掛起若干進(jìn)程 為了防止發(fā)生“抖動(dòng)”，可用的一個(gè)簡(jiǎn)單易行的辦法是掛起一些進(jìn)程，以便騰出內(nèi)存空間來分配給抖動(dòng)的進(jìn)程。 被掛起的進(jìn)程通常是選擇優(yōu)先權(quán)最低或較低的；當(dāng)內(nèi)存非常擁擠時(shí)，也可以選擇一個(gè)并不很重要的、但確較大的進(jìn)程掛起，以便能一次釋放出較大的內(nèi)存空間；或者是將具有最多剩余執(zhí)行時(shí)間的進(jìn)程掛起。 4.6.4 4.6.4 虛擬頁(yè)式存儲(chǔ)的優(yōu)缺點(diǎn)虛擬頁(yè)式存儲(chǔ)的優(yōu)缺點(diǎn)&1.1.優(yōu)點(diǎn)優(yōu)點(diǎn)& 主存利用率比較高。平均每個(gè)用戶作業(yè)只浪費(fèi)一半的頁(yè)空間，內(nèi)主存利用

47、率比較高。平均每個(gè)用戶作業(yè)只浪費(fèi)一半的頁(yè)空間，內(nèi)存規(guī)范易于管理。存規(guī)范易于管理。& 對(duì)磁盤管理比較容易。因?yàn)轫?yè)的大小一般取磁盤物理塊對(duì)磁盤管理比較容易。因?yàn)轫?yè)的大小一般取磁盤物理塊大小的整數(shù)倍。大小的整數(shù)倍。& 地址映射和變換的速度比較快。在把用戶程序裝入到主存儲(chǔ)器的過地址映射和變換的速度比較快。在把用戶程序裝入到主存儲(chǔ)器的過程中，只要建立用戶程序的虛頁(yè)號(hào)與主存儲(chǔ)器的實(shí)頁(yè)號(hào)之間的對(duì)應(yīng)關(guān)系程中，只要建立用戶程序的虛頁(yè)號(hào)與主存儲(chǔ)器的實(shí)頁(yè)號(hào)之間的對(duì)應(yīng)關(guān)系即可（拼接得到物理地址），不必使用整個(gè)主存的地址長(zhǎng)度，也不必考即可（拼接得到物理地址），不必使用整個(gè)主存的地址長(zhǎng)度，也不必考慮每頁(yè)的

48、長(zhǎng)度等。慮每頁(yè)的長(zhǎng)度等。& 2. 2.缺點(diǎn)缺點(diǎn)& 程序的模塊化性能不好。程序的模塊化性能不好。&由于用戶程序是強(qiáng)制按照固定大小的頁(yè)來劃分的，而程序段的實(shí)際長(zhǎng)度一由于用戶程序是強(qiáng)制按照固定大小的頁(yè)來劃分的，而程序段的實(shí)際長(zhǎng)度一般是不固定的。因此，虛擬頁(yè)式存儲(chǔ)器中一頁(yè)通常不能表示一個(gè)完整的程般是不固定的。因此，虛擬頁(yè)式存儲(chǔ)器中一頁(yè)通常不能表示一個(gè)完整的程序功能。一頁(yè)可能只是一個(gè)程序段中的一部分，也可能在一頁(yè)中包含了兩序功能。一頁(yè)可能只是一個(gè)程序段中的一部分，也可能在一頁(yè)中包含了兩個(gè)或兩個(gè)以上程序段。個(gè)或兩個(gè)以上程序段。& 頁(yè)表很長(zhǎng)，需要占用很大的存儲(chǔ)空間。頁(yè)表很長(zhǎng)，

49、需要占用很大的存儲(chǔ)空間。& 通常，虛擬存儲(chǔ)器中的每一頁(yè)在頁(yè)表中都要占一個(gè)頁(yè)表項(xiàng)。假設(shè)有一個(gè)虛擬頁(yè)式存儲(chǔ)通常，虛擬存儲(chǔ)器中的每一頁(yè)在頁(yè)表中都要占一個(gè)頁(yè)表項(xiàng)。假設(shè)有一個(gè)虛擬頁(yè)式存儲(chǔ)器，它的虛擬存儲(chǔ)空間大小為器，它的虛擬存儲(chǔ)空間大小為4GB，每一頁(yè)的大小為，每一頁(yè)的大小為1KB，則頁(yè)表的容量為，則頁(yè)表的容量為4M（個(gè)頁(yè)表項(xiàng)）。如果每個(gè)頁(yè)表項(xiàng)占用（個(gè)頁(yè)表項(xiàng)）。如果每個(gè)頁(yè)表項(xiàng)占用4個(gè)字節(jié)，則頁(yè)表的存儲(chǔ)容量為個(gè)字節(jié)，則頁(yè)表的存儲(chǔ)容量為16MB。 4.7 4.7 虛擬段式存儲(chǔ)管理虛擬段式存儲(chǔ)管理 4.7.1 4.7.1 虛擬段式存儲(chǔ)的實(shí)現(xiàn)虛擬段式存儲(chǔ)的實(shí)現(xiàn) 4.7.2 4.7.2 段的共享和保護(hù)段的

50、共享和保護(hù) 虛擬段式存儲(chǔ)管理的優(yōu)缺點(diǎn)虛擬段式存儲(chǔ)管理的優(yōu)缺點(diǎn) 4.7.4 4.7.4 虛擬段頁(yè)式存儲(chǔ)管理虛擬段頁(yè)式存儲(chǔ)管理 4.7.1 4.7.1 虛擬段式存儲(chǔ)的實(shí)現(xiàn)虛擬段式存儲(chǔ)的實(shí)現(xiàn)1.1.虛擬段式存儲(chǔ)原理虛擬段式存儲(chǔ)原理 邏輯地址空間中的程序段在運(yùn)行時(shí)并不全部裝入邏輯地址空間中的程序段在運(yùn)行時(shí)并不全部裝入內(nèi)存。內(nèi)存。 首先調(diào)入一個(gè)或若干個(gè)程序段運(yùn)行，在運(yùn)行過程中首先調(diào)入一個(gè)或若干個(gè)程序段運(yùn)行，在運(yùn)行過程中調(diào)用到哪段時(shí)，就根據(jù)該段長(zhǎng)度在內(nèi)存分配一個(gè)連續(xù)的調(diào)用到哪段時(shí)，就根據(jù)該段長(zhǎng)度在內(nèi)存分配一個(gè)連續(xù)的分區(qū)給它使用。分區(qū)給它使用。 若內(nèi)存中沒有足夠大的空閑分區(qū)，則考慮進(jìn)行若內(nèi)存中沒有足夠大的空

51、閑分區(qū)，則考慮進(jìn)行段的緊湊或?qū)⒛扯位蚰承┒翁蕴鋈ァ６蔚木o湊或?qū)⒛扯位蚰承┒翁蕴鋈ァ?.2.段表段表 &為了實(shí)現(xiàn)動(dòng)態(tài)地址變換和存儲(chǔ)保護(hù)，系統(tǒng)要為每一個(gè)作業(yè)建立一張段表。為了實(shí)現(xiàn)動(dòng)態(tài)地址變換和存儲(chǔ)保護(hù)，系統(tǒng)要為每一個(gè)作業(yè)建立一張段表。段表中的每一個(gè)表目對(duì)應(yīng)著作業(yè)地址空間的一個(gè)程序段，其一般格式為：段表中的每一個(gè)表目對(duì)應(yīng)著作業(yè)地址空間的一個(gè)程序段，其一般格式為： 邏輯地址同前：邏輯地址同前：段號(hào)存在位P訪問位A修改位M存取方式增補(bǔ)位段長(zhǎng)度段的基址外存地址存在位存在位P P表示該段是否在內(nèi)存，如為表示該段是否在內(nèi)存，如為0 0表示不在，為表示不在，為1 1表示在內(nèi)存；表示在內(nèi)存；存取方式表

52、示可對(duì)該段施加的操作，如只讀、讀寫、還是執(zhí)行。存取方式表示可對(duì)該段施加的操作，如只讀、讀寫、還是執(zhí)行。增補(bǔ)位表示該段在運(yùn)行期間是否可以擴(kuò)展空間增補(bǔ)位表示該段在運(yùn)行期間是否可以擴(kuò)展空間 3.3.請(qǐng)求式分段動(dòng)態(tài)地址變換過程請(qǐng)求式分段動(dòng)態(tài)地址變換過程 圖圖4.32 地址變換與中斷處理流程地址變換與中斷處理流程4.4.缺段中斷缺段中斷&在虛擬段式存儲(chǔ)系統(tǒng)中，采用的是請(qǐng)求調(diào)段策略。在虛擬段式存儲(chǔ)系統(tǒng)中，采用的是請(qǐng)求調(diào)段策略。&再調(diào)入新段時(shí)，也會(huì)有內(nèi)存空間不夠用的情況，也需要淘汰內(nèi)存中的一個(gè)再調(diào)入新段時(shí)，也會(huì)有內(nèi)存空間不夠用的情況，也需要淘汰內(nèi)存中的一個(gè)或多個(gè)段。如果此程序段從裝入內(nèi)存起一

53、直沒有被修改過，只要用新調(diào)入或多個(gè)段。如果此程序段從裝入內(nèi)存起一直沒有被修改過，只要用新調(diào)入的程序段把它覆蓋掉即可。若這個(gè)程序段被修改過，則必須先把該程序段的程序段把它覆蓋掉即可。若這個(gè)程序段被修改過，則必須先把該程序段全部寫回到磁盤存儲(chǔ)器中，才能占用被淘汰段原來存放的空間。全部寫回到磁盤存儲(chǔ)器中，才能占用被淘汰段原來存放的空間。&因?yàn)槎我加眠B續(xù)的空間，因此當(dāng)內(nèi)存中沒有能夠滿足段長(zhǎng)需要的因?yàn)槎我加眠B續(xù)的空間，因此當(dāng)內(nèi)存中沒有能夠滿足段長(zhǎng)需要的空閑區(qū)時(shí)，系統(tǒng)還要合并空閑區(qū)，以便滿足分段的需求?？臻e區(qū)時(shí)，系統(tǒng)還要合并空閑區(qū)，以便滿足分段的需求。 4.7.2 4.7.2 段的共享和保護(hù)段

54、的共享和保護(hù)&1.1.段的共享段的共享& 在多道環(huán)境下，常常有許多子程序和應(yīng)用程序是被多用戶所使用的。最好的辦法在多道環(huán)境下，常常有許多子程序和應(yīng)用程序是被多用戶所使用的。最好的辦法是在內(nèi)存中只保留一個(gè)副本，供多個(gè)用戶使用，稱為共享。是在內(nèi)存中只保留一個(gè)副本，供多個(gè)用戶使用，稱為共享。& 段共享時(shí)，用戶可以使用不相同的段名來共享同一個(gè)段。進(jìn)程將共享段填寫到自己的段共享時(shí)，用戶可以使用不相同的段名來共享同一個(gè)段。進(jìn)程將共享段填寫到自己的段表中，并置以適當(dāng)?shù)淖x寫控制權(quán)，就可以做到共享一個(gè)邏輯上完整的內(nèi)存段信息。段表中，并置以適當(dāng)?shù)淖x寫控制權(quán)，就可以做到共享一個(gè)邏輯上完整的內(nèi)

55、存段信息。& 由于系統(tǒng)中有許多的共享段，而每一個(gè)共享段都可能被多個(gè)進(jìn)程共享。因此系統(tǒng)由于系統(tǒng)中有許多的共享段，而每一個(gè)共享段都可能被多個(gè)進(jìn)程共享。因此系統(tǒng)需要對(duì)共享段進(jìn)行統(tǒng)一的管理，設(shè)一張共享段表，每一個(gè)共享段都在表中占據(jù)一需要對(duì)共享段進(jìn)行統(tǒng)一的管理，設(shè)一張共享段表，每一個(gè)共享段都在表中占據(jù)一個(gè)表項(xiàng)。個(gè)表項(xiàng)。&共享段應(yīng)該是可重入的。共享段應(yīng)該是可重入的。 圖圖4.33 段式系統(tǒng)中共享內(nèi)存副本示意圖段式系統(tǒng)中共享內(nèi)存副本示意圖共享段表共享段表& 其中存在位表示該共享段是否已被調(diào)入內(nèi)存，共享計(jì)數(shù)是用來統(tǒng)計(jì)當(dāng)前有多少個(gè)進(jìn)程其中存在位表示該共享段是否已被調(diào)入內(nèi)存，共享計(jì)數(shù)是用來

56、統(tǒng)計(jì)當(dāng)前有多少個(gè)進(jìn)程共享該段。系統(tǒng)可以為不同的進(jìn)程使用該段設(shè)置不同的權(quán)限，以防止進(jìn)程越權(quán)操作。共享該段。系統(tǒng)可以為不同的進(jìn)程使用該段設(shè)置不同的權(quán)限，以防止進(jìn)程越權(quán)操作。& 當(dāng)進(jìn)程請(qǐng)求共享段時(shí)，若該共享段未在內(nèi)存，也是由缺段中斷將其調(diào)入內(nèi)存，同當(dāng)進(jìn)程請(qǐng)求共享段時(shí)，若該共享段未在內(nèi)存，也是由缺段中斷將其調(diào)入內(nèi)存，同時(shí)為該段建立相應(yīng)的共享段表項(xiàng)，共享計(jì)數(shù)設(shè)為時(shí)為該段建立相應(yīng)的共享段表項(xiàng)，共享計(jì)數(shù)設(shè)為1，將進(jìn)程填寫到共享段表項(xiàng)，將進(jìn)程填寫到共享段表項(xiàng)中，再將共享段填寫到進(jìn)程的段表中。若該共享段已在內(nèi)存，只要將共享計(jì)中，再將共享段填寫到進(jìn)程的段表中。若該共享段已在內(nèi)存，只要將共享計(jì)數(shù)加數(shù)加1，再修改相應(yīng)的表項(xiàng)即可。不用時(shí)做相反工作。，再修改相應(yīng)的表項(xiàng)即可。不用時(shí)做相反工作。段名段長(zhǎng)存在位共享計(jì)數(shù)內(nèi)存基址外存始址 共享該段的進(jìn)程登記表狀態(tài)進(jìn)程名進(jìn)程號(hào)段號(hào)存取權(quán)限2.2.段的保護(hù)段的保護(hù)( (兩種保護(hù)方式兩種保護(hù)方式) )&(1)(1)地址越界保護(hù)法。地址越界保護(hù)法。&(2)(2)存取方式控制保護(hù)法。存取