第5章虛擬存儲(chǔ)器

第五章虛擬存儲(chǔ)器5.1虛擬存儲(chǔ)器概述5.2請(qǐng)求分頁存儲(chǔ)管理方式5.3頁面置換算法5.4“抖動(dòng)”與工作集4.5請(qǐng)求分段存儲(chǔ)管理方式5.1虛擬存儲(chǔ)器概述第四章所介紹的各種存儲(chǔ)器管理方式有一個(gè)共同的特點(diǎn)，即它們都要求將一個(gè)作業(yè)全部裝入內(nèi)存后方能運(yùn)行。于是，出現(xiàn)了下面這樣兩種情況：

(1)有的作業(yè)很大，其所要求的內(nèi)存空間超過了內(nèi)存總?cè)萘浚鳂I(yè)不能全部被裝入內(nèi)存，致使該作業(yè)無法運(yùn)行；

(2)有大量作業(yè)要求運(yùn)行，但由于內(nèi)存容量不足以容納所有這些作業(yè)，只能將少數(shù)作業(yè)裝入內(nèi)存讓它們先運(yùn)行，而將其它大量的作業(yè)留在外存上等待。5.1虛擬存儲(chǔ)器概述5.1.1常規(guī)存儲(chǔ)管理方式的特征和局部性原理1.常規(guī)存儲(chǔ)器管理方式的特征

(1)一次性是指在作業(yè)運(yùn)行前，將作業(yè)全部裝入內(nèi)存，但實(shí)際上有許多作業(yè)在每次運(yùn)行時(shí)，并非用到其全部程序，因此，那種將作業(yè)“一次性”地全部裝入的方法，顯然是一種對(duì)內(nèi)存空間的浪費(fèi)。(2)駐留性是指作業(yè)裝入內(nèi)存后，便一直駐留在內(nèi)存直至作業(yè)運(yùn)行結(jié)束。2.局部性原理

(1)程序執(zhí)行時(shí)，除了少部分的轉(zhuǎn)移和過程調(diào)用指令外，在大多數(shù)情況下仍是順序執(zhí)行的。

(2)過程調(diào)用將會(huì)使程序的執(zhí)行軌跡由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域，但經(jīng)研究表明，過程調(diào)用的深度在大多數(shù)情況下都不超過5。也就是說，程序?qū)?huì)在一段時(shí)間內(nèi)，都局限在這些過程的范圍內(nèi)運(yùn)行。

(3)程序中存在許多循環(huán)結(jié)構(gòu)，這些雖然只由少數(shù)指令構(gòu)成，但是它們將多次執(zhí)行。

(4)程序中還包括許多對(duì)數(shù)據(jù)結(jié)構(gòu)的處理，如對(duì)數(shù)組進(jìn)行操作，它們往往都局限于很小的范圍內(nèi)。

局限性又表現(xiàn)在下述兩個(gè)方面：

(1)時(shí)間局限性如果程序中的某條指令一旦執(zhí)行，則不久以后該指令可能再次執(zhí)行；如果某數(shù)據(jù)被訪問過，則不久以后該數(shù)據(jù)可能再次被訪問。產(chǎn)生時(shí)間局限性的典型原因，是由于在程序中存在著大量的循環(huán)操作。

(2)空間局限性一旦程序訪問了某個(gè)存儲(chǔ)單元，在不久之后，其附近的存儲(chǔ)單元也將被訪問，即程序在一段時(shí)間內(nèi)所訪問的地址，可能集中在一定的范圍之內(nèi)，其典型情況便是程序的順序執(zhí)行。3.虛擬存儲(chǔ)器定義

所謂虛擬存儲(chǔ)器，是指具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量加以擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。其邏輯容量由內(nèi)存容量和外存容量之和所決定，其運(yùn)行速度接近于內(nèi)存速度，而每位的成本卻又接近于外存。可見，虛擬存儲(chǔ)技術(shù)是一種性能非常優(yōu)越的存儲(chǔ)器管理技術(shù)，故被廣泛地應(yīng)用于大、中、小型機(jī)器和微型機(jī)中。

5.1.2虛擬存儲(chǔ)器的實(shí)現(xiàn)方法1.分頁請(qǐng)求系統(tǒng)(1)硬件支持

①請(qǐng)求分頁的頁表機(jī)制，它是在純分頁的頁表機(jī)制上增加若干項(xiàng)而形成的，作為請(qǐng)求分頁的數(shù)據(jù)結(jié)構(gòu)；②缺頁中斷機(jī)構(gòu)，即每當(dāng)用戶程序要訪問的頁面尚未調(diào)入內(nèi)存時(shí)便產(chǎn)生一缺頁中斷，以請(qǐng)求OS將所缺的頁調(diào)入內(nèi)存；③地址變換機(jī)構(gòu)，它同樣是在純分頁地址變換機(jī)構(gòu)的基礎(chǔ)上發(fā)展形成的。(2)實(shí)現(xiàn)請(qǐng)求分頁的軟件2.請(qǐng)求分段系統(tǒng)(1)硬件支持

①請(qǐng)求分段的段表機(jī)制，這是在純分段的段表機(jī)制基礎(chǔ)上，增加若干項(xiàng)而形成的；②缺段中斷機(jī)構(gòu)，每當(dāng)用戶程序要訪問的段尚未調(diào)入內(nèi)存時(shí)，產(chǎn)生一缺段中斷，以請(qǐng)求OS將所缺的段調(diào)入內(nèi)存；③地址變換機(jī)構(gòu)，它同樣是在純分段地址變換機(jī)構(gòu)的基礎(chǔ)上發(fā)展形成的。(2)實(shí)現(xiàn)請(qǐng)求分頁的軟件5.1.3虛擬存儲(chǔ)器的特征1.離散性離散性是指在內(nèi)存分配時(shí)采用離散分配的方式，這是其它幾個(gè)特征的基礎(chǔ)。沒有離散性，也就不可能實(shí)現(xiàn)虛擬存儲(chǔ)器。2.多次性多次性是指一個(gè)作業(yè)被分成多次地調(diào)入內(nèi)存運(yùn)行，亦即在作業(yè)運(yùn)行時(shí)沒有必要將其全部裝入，只須將當(dāng)前要運(yùn)行的那部分程序和數(shù)據(jù)裝入內(nèi)存即可；以后運(yùn)行到那一部分時(shí)，再將它調(diào)入。多次性是虛擬存儲(chǔ)器最重要的特征。

3.對(duì)換性對(duì)換性是指允許在作業(yè)的運(yùn)行過程中換進(jìn)、換出。4.虛擬性是指能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量。

練習(xí)題

1、在一請(qǐng)求分頁系統(tǒng)中，某程序在一個(gè)時(shí)間段內(nèi)有如下的存儲(chǔ)器引用：12、351、190、90、430、30、550（以上數(shù)字為虛存的邏輯地址）。假定主存中每塊的大小為100B，系統(tǒng)分配給該作業(yè)的主存塊數(shù)為3塊?；卮鹑缦聠栴}：（題中數(shù)字為十進(jìn)制數(shù)）(1)對(duì)于以上的存儲(chǔ)器引用序列，給出其頁面走向；(2)設(shè)程序開始運(yùn)行時(shí)，以裝入第0頁。在先進(jìn)先出頁面置換算法和最久未使用頁面置換算法（LRU算法）下，分別畫出每次訪問時(shí)該程序的主存頁面情況，并給出缺頁中斷次數(shù)。

2、試給一個(gè)請(qǐng)求分頁系統(tǒng)設(shè)計(jì)進(jìn)程調(diào)度的方案，使系統(tǒng)同時(shí)滿足以下條件。（1）有合理的響應(yīng)時(shí)間；（2）有較好的外部設(shè)備利用率；（3）缺頁對(duì)程序執(zhí)行速度的影響降到最低程度。畫出調(diào)度用的進(jìn)程狀態(tài)變遷圖，并說明這樣設(shè)計(jì)的理由。

5.2請(qǐng)求分頁存儲(chǔ)管理方式

與基本分頁存儲(chǔ)管理不同，請(qǐng)求式分頁管理系統(tǒng)只需作業(yè)的部分頁面調(diào)入內(nèi)存就可以運(yùn)行了。但系統(tǒng)需要解決下面三個(gè)問題：系統(tǒng)如何獲知進(jìn)程當(dāng)前所需頁面不在主存。

當(dāng)發(fā)現(xiàn)缺頁時(shí)，如何把所缺頁面調(diào)入主存。當(dāng)主存中沒有空閑的頁框時(shí)，為了要接受一個(gè)新頁，需要把老的一頁淘汰出去，根據(jù)什么策略選擇欲淘汰的頁面。5.2請(qǐng)求分頁存儲(chǔ)管理方式5.2.1請(qǐng)求分頁中的硬件支持1.頁表機(jī)制頁號(hào)物理塊號(hào)狀態(tài)位P訪問字段A修改位M外存地址

狀態(tài)位P

用于指示該頁是否已調(diào)入內(nèi)存，供程序訪問時(shí)參考。

訪問字段A

用于記錄本頁在一段時(shí)間內(nèi)被訪問的次數(shù)，或最近已有多長(zhǎng)時(shí)間未被訪問，提供給置換算法選擇換出頁面時(shí)參考。

修改位M

表示該頁在調(diào)入內(nèi)存后是否被修改過。作為該頁換出時(shí)是否寫回外存的依據(jù)。

外存地址

用于指出該頁在外存上的地址，通常是物理塊號(hào)，供調(diào)入該頁時(shí)使用。2.缺頁中斷機(jī)構(gòu)涉及6次缺頁中斷的指令特征：①在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)。一般中斷是在指令執(zhí)行完才檢查是否有中斷請(qǐng)求，而缺頁中斷是在指令執(zhí)行期間，發(fā)現(xiàn)所要訪問的指令或數(shù)據(jù)不在內(nèi)存時(shí)產(chǎn)生和處理的。②一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷，如右圖所示。在執(zhí)行一條copyAtoB的指令時(shí)，可能要產(chǎn)生6次缺頁中斷，其中指令本身跨了兩個(gè)頁面，A和B又分別各是一個(gè)數(shù)據(jù)塊，也都跨了兩個(gè)頁面。系統(tǒng)中的硬件機(jī)構(gòu)應(yīng)能保存多次中斷時(shí)的狀態(tài)，并保證最后能返回到中斷前產(chǎn)生缺頁中斷的指令處，繼續(xù)執(zhí)行。3.地址變換機(jī)構(gòu)請(qǐng)求分頁中的地址變換過程

3.地址變換機(jī)構(gòu)5.2.2內(nèi)存分配策略和分配算法1.最小物理塊數(shù)的確定

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

在請(qǐng)求分頁系統(tǒng)中，可采取兩種內(nèi)存分配策略，即固定和可變分配策略。在進(jìn)行置換時(shí)，也可采取兩種策略，即全局置換和局部置換。于是可組合出以下三種適用的策略。

1)固定分配局部置換(FixedAllocation,LocalReplacement)2)可變分配全局置換(VariableAllocation,GlobalReplacement)3)可變分配局部置換(VariableAllocation,LocalReplacemen）3.物理塊分配算法

1)平均分配算法

這是將系統(tǒng)中所有可供分配的物理塊，平均分配給各個(gè)進(jìn)程。例如，當(dāng)系統(tǒng)中有100個(gè)物理塊，有5個(gè)進(jìn)程在運(yùn)行時(shí)，每個(gè)進(jìn)程可分得20個(gè)物理塊。這種方式貌似公平，但實(shí)際上是不公平的，因?yàn)樗纯紤]到各進(jìn)程本身的大小。如有一個(gè)進(jìn)程其大小為200頁，只分配給它20個(gè)塊，這樣，它必然會(huì)有很高的缺頁率；而另一個(gè)進(jìn)程只有10頁，卻有10個(gè)物理塊閑置未用。

2)按比例分配算法

這是根據(jù)進(jìn)程的大小按比例分配物理塊的算法。如果系統(tǒng)中共有n個(gè)進(jìn)程，每個(gè)進(jìn)程的頁面數(shù)為Si，則系統(tǒng)中各進(jìn)程頁面數(shù)的總和為：

又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個(gè)進(jìn)程所能分到的物理塊數(shù)為bi，將有：

b應(yīng)該取整，它必須大于最小物理塊數(shù)。

3)考慮優(yōu)先權(quán)的分配算法

在實(shí)際應(yīng)用中，為了照顧到重要的、緊迫的作業(yè)能盡快地完成，應(yīng)為它分配較多的內(nèi)存空間。通常采取的方法是把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)卦黾悠湎鄳?yīng)份額后，分配給各進(jìn)程。在有的系統(tǒng)中，如重要的實(shí)時(shí)控制系統(tǒng)，則可能是完全按優(yōu)先權(quán)來為各進(jìn)程分配其物理塊的。5.2.3調(diào)頁策略1.何時(shí)調(diào)入頁面

預(yù)調(diào)頁策略

就是將那些預(yù)計(jì)在不久之后便會(huì)被訪問的頁面預(yù)先調(diào)入內(nèi)存。2)請(qǐng)求調(diào)頁策略

當(dāng)進(jìn)程在運(yùn)行中需要訪問某部分程序和數(shù)據(jù)時(shí)，若發(fā)現(xiàn)其所在的頁面不在內(nèi)存，便立即提出請(qǐng)求，由OS將其所需頁面調(diào)入內(nèi)存。2.從何處調(diào)入頁面

在請(qǐng)求分頁系統(tǒng)中的外存分為兩部分：用于存放文件的文件區(qū)和用于存放對(duì)換頁面的對(duì)換區(qū)。通常，由于對(duì)換區(qū)是采用連續(xù)分配方式，而文件區(qū)采用離散分配方式，故對(duì)換區(qū)的磁盤I/O速度比文件區(qū)的高。這樣，每當(dāng)發(fā)生缺頁請(qǐng)求時(shí)，系統(tǒng)應(yīng)從何處將缺頁調(diào)入內(nèi)存，可分成如下三種情況：

(1)系統(tǒng)擁有足夠的對(duì)換區(qū)空間，這時(shí)可以全部從對(duì)換區(qū)調(diào)入所需頁面，以提高調(diào)頁速度。為此，在進(jìn)程運(yùn)行前，便須將與該進(jìn)程有關(guān)的文件，從文件區(qū)拷貝到對(duì)換區(qū)。

(2)系統(tǒng)缺少足夠的對(duì)換區(qū)空間，這時(shí)凡是不會(huì)被修改的文件，都直接從文件區(qū)調(diào)入；而當(dāng)換出這些頁面時(shí)，由于它們未被修改而不必再將它們換出，以后再調(diào)入時(shí)，仍從文件區(qū)直接調(diào)入。但對(duì)于那些可能被修改的部分，在將它們換出時(shí)，便須調(diào)到對(duì)換區(qū)，以后需要時(shí)，再?gòu)膶?duì)換區(qū)調(diào)入。

(3)UNIX方式。由于與進(jìn)程有關(guān)的文件都放在文件區(qū)，故凡是未運(yùn)行過的頁面，都應(yīng)從文件區(qū)調(diào)入。而對(duì)于曾經(jīng)運(yùn)行過但又被換出的頁面，由于是被放在對(duì)換區(qū)，因此在下次調(diào)入時(shí)，應(yīng)從對(duì)換區(qū)調(diào)入。由于UNIX系統(tǒng)允許頁面共享，因此，某進(jìn)程所請(qǐng)求的頁面有可能已被其它進(jìn)程調(diào)入內(nèi)存，此時(shí)也就無須再?gòu)膶?duì)換區(qū)調(diào)入。3.頁面調(diào)入過程

每當(dāng)程序所要訪問的頁面未在內(nèi)存時(shí)，便向CPU發(fā)出一缺頁中斷，中斷處理程序首先保留CPU環(huán)境，分析中斷原因后，轉(zhuǎn)入缺頁中斷處理程序。該程序通過查找頁表，得到該頁在外存的物理塊后，如果此時(shí)內(nèi)存能容納新頁，則啟動(dòng)磁盤I/O將所缺之頁調(diào)入內(nèi)存，然后修改頁表。如果內(nèi)存已滿，則須先按照某種置換算法從內(nèi)存中選出一頁準(zhǔn)備換出；如果該頁未被修改過，可不必將該頁寫回磁盤；但如果此頁已被修改，則必須將它寫回磁盤，然后再把所缺的頁調(diào)入內(nèi)存，并修改頁表中的相應(yīng)表項(xiàng)，置其存在位為“1”，并將此頁表項(xiàng)寫入快表中。在缺頁調(diào)入內(nèi)存后，利用修改后的頁表，去形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)。5.3頁面置換算法5.3.1最佳置換算法和先進(jìn)先出置換算法1.最佳(Optimal)置換算法最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的，或許是在最長(zhǎng)(未來)時(shí)間內(nèi)不再被訪問的頁面。采用最佳置換算法，通常可保證獲得最低的缺頁率。

假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下的頁面號(hào)引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。進(jìn)程運(yùn)行時(shí)，先將7，0，1三個(gè)頁面裝入內(nèi)存。以后，當(dāng)進(jìn)程要訪問頁面2時(shí)，將會(huì)產(chǎn)生缺頁中斷。此時(shí)OS根據(jù)最佳置換算法，將選擇頁面7予以淘汰。利用最佳頁面置換算法時(shí)的置換圖2.先進(jìn)先出(FIFO)頁面置換算法利用FIFO置換算法時(shí)的置換圖

5.3.2最近最久未使用(LRU)置換算法1.LRU(LeastRecentlyUsed)置換算法的描述LRU頁面置換算法

是根據(jù)頁面調(diào)入內(nèi)存后的使用情況進(jìn)行決策的。2.LRU置換算法的硬件支持1)寄存器為了記錄某進(jìn)程在內(nèi)存中各頁的使用情況，須為每個(gè)在內(nèi)存中的頁面配置一個(gè)移位寄存器，可表示為R=Rn-1Rn-2Rn-3…R2R1R0

當(dāng)進(jìn)程訪問某物理塊時(shí)，要將相應(yīng)寄存器的Rn-1位置成1。此時(shí)，定時(shí)信號(hào)將每隔一定時(shí)間將寄存器右移一位。如果把n位寄存器的數(shù)看做是一個(gè)整數(shù)，那么具有最小數(shù)值的寄存器所對(duì)應(yīng)的頁面，就是最近最久未使用的頁面。某進(jìn)程具有8個(gè)頁面時(shí)的LRU訪問情況

2)棧用棧保存當(dāng)前使用頁面時(shí)棧的變化情況

練習(xí)題

1、在一請(qǐng)求分頁系統(tǒng)中，某程序在一個(gè)時(shí)間段內(nèi)有如下的存儲(chǔ)器引用：12、351、190、90、430、30、550（以上數(shù)字為虛存的邏輯地址）。假定主存中每塊的大小為100B，系統(tǒng)分配給該作業(yè)的主存塊數(shù)為3塊?；卮鹑缦聠栴}：（題中數(shù)字為十進(jìn)制數(shù)）(1)對(duì)于以上的存儲(chǔ)器引用序列，給出其頁面走向；(2)設(shè)程序開始運(yùn)行時(shí)，以裝入第0頁。在先進(jìn)先出頁面置換算法和最久未使用頁面置換算法（LRU算法）下，分別畫出每次訪問時(shí)該程序的主存頁面情況，并給出缺頁中斷次數(shù)。

2、試給一個(gè)請(qǐng)求分頁系統(tǒng)設(shè)計(jì)進(jìn)程調(diào)度的方案，使系統(tǒng)同時(shí)滿足以下條件。（1）有合理的響應(yīng)時(shí)間；（2）有較好的外部設(shè)備利用率；（3）缺頁對(duì)程序執(zhí)行速度的影響降到最低程度。畫出調(diào)度用的進(jìn)程狀態(tài)變遷圖，并說明這樣設(shè)計(jì)的理由。

5.4請(qǐng)求分段存儲(chǔ)管理方式5.4.1請(qǐng)求分段中的硬件支持1.段表機(jī)制段名段長(zhǎng)段的基址存取方式訪問字段A修改位M存在位P增補(bǔ)位外存始址

在段表項(xiàng)中，除了段名(號(hào))、段長(zhǎng)、段在內(nèi)存中的起始地址外，還增加了以下諸項(xiàng)：(1)存取方式(2)訪問字段A