第5章虛擬存儲器

5虛擬存儲器管理前面介紹的分區(qū)（固定分區(qū)和可變分區(qū)）存儲管理和分頁、分段存儲管理技術(shù)，都要求作業(yè)在執(zhí)行之前必須將其全部信息裝入內(nèi)存，并且作業(yè)的邏輯地址空間不能比內(nèi)存空間大，否則該作業(yè)就無法裝入內(nèi)存。為了解決大作業(yè)與小內(nèi)存的矛盾，人們采用了虛擬存儲管理技術(shù)，對內(nèi)存在邏輯上進行擴充。5虛擬存儲器基本實現(xiàn)思想技術(shù)支持內(nèi)存物理頁面分配方式調(diào)頁策略缺頁中斷的處理過程頁面置換算法5虛擬存儲器管理引入：常規(guī)方式下“一次性”和“駐留性”依據(jù)：程序局部性

含義：虛擬存儲器特征：多次性、對換性、虛擬性實現(xiàn)方法：虛擬頁式、虛擬段式、虛擬段頁式局部性原理：程序在執(zhí)行時將呈現(xiàn)局部性規(guī)律，即在一較短的時間內(nèi)，程序的執(zhí)行僅局限于某個部分，它所訪問的存儲空間也局限于某個區(qū)域。局限性又表現(xiàn)在下述兩個方面：時間局部性和空間局部性局部性原理：時間局部性：如果程序中的某條指令一旦執(zhí)行，則不久以后該可能再次執(zhí)行；如果某數(shù)據(jù)被訪問過，則不久以后該數(shù)據(jù)可能再次被訪問。產(chǎn)生時間局限性的典型原因是程序中存在著大量的循環(huán)操作?？臻g局部性：一旦程序訪問了某個存儲單元，則不久后，其附近的存儲單元也將被訪問，即程序在一段時間內(nèi)訪問的地址，可能集中在一定的范圍內(nèi)，其典型情況是程序的順序執(zhí)行。5.1虛擬存儲器的概念基于程序的局部性考慮，就沒有必要把一個作業(yè)全部都調(diào)入內(nèi)存再執(zhí)行，而只需把當(dāng)前運行所需要的信息放入內(nèi)存，其余根據(jù)需要，由操作系統(tǒng)和硬件配合來完成主存和輔存之間信息的調(diào)度。這樣的計算機系統(tǒng)好像為用戶提供了一個比實際容量大得多的一個內(nèi)存，稱為虛擬存儲器。5.1虛擬存儲器的概念所謂虛擬存儲器，是指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量加以擴充的一種存儲器系統(tǒng)其邏輯容量由內(nèi)存容量和外存容量之和所決定，其運行速度接近于內(nèi)存，而每位的成本又接近于外存。虛擬存儲技術(shù)是一種性能優(yōu)越的存儲器管理技術(shù)，故被廣泛地應(yīng)用于大、中、小型機器和微型機中。

5.2虛擬存儲器的實現(xiàn)方法

基本思想：

部分頁面在內(nèi)存，部分在外存上（程序部分裝入），當(dāng)訪問到不在內(nèi)存頁時，產(chǎn)生缺頁中斷，由OS負責(zé)進行頁面的動態(tài)調(diào)度。需要考慮的問題：（1）進程訪問的頁不在內(nèi)存時，何時調(diào)頁？（2）需要調(diào)頁時，內(nèi)存無空閑頁面怎么辦？必須建立在離散分配的內(nèi)存管理技術(shù)基礎(chǔ)上。請求分頁系統(tǒng)基本分頁系統(tǒng)+請求調(diào)頁功能+頁面置換功能＝頁式虛擬存儲系統(tǒng)硬件支持：請求分頁的頁表機制、缺頁中斷機構(gòu)、動態(tài)地址變換機構(gòu)。軟件支持：請求分頁、頁面置換5.2虛擬存儲器的實現(xiàn)方法

1、硬件支持①請求分頁的頁表機制，它是在純分頁的頁表機制上增加若干項而形成的，作為請求分頁的數(shù)據(jù)結(jié)構(gòu)；②缺頁中斷機構(gòu)，即每當(dāng)用戶程序要訪問的頁面尚未調(diào)入內(nèi)存時，便產(chǎn)生一缺頁中斷，以請求OS將所缺的頁調(diào)入內(nèi)存；③地址變換機構(gòu)，它同樣是在純分頁地址變換機構(gòu)的基礎(chǔ)上發(fā)展形成的。5.3請求式分頁存儲管理方式5.3請求式分頁存儲管理方式1)一般來說，一個頁表包括以下信息：(1)狀態(tài)位：用于指示該頁是否已調(diào)入內(nèi)存，供程序訪問時參考。(2)訪問字段：用于記錄本頁是否被訪問，供選擇換出頁面時參考。(3)修改位：表示該頁在調(diào)入內(nèi)存后是否被修改過，供置換頁面時參考。(4)外存地址：用于指出該頁在外存上的地址，通常是物理塊號，供調(diào)入該頁時參考。2）缺頁中斷機構(gòu)缺頁中斷與一般中斷的區(qū)別：在指令執(zhí)行期間產(chǎn)生和處理中斷信號。一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。5.3請求式分頁存儲管理方式

涉及6次缺頁中斷的指令

654321A:B:CopyAtoB指令3）地址變換機構(gòu)2、內(nèi)存分配策略和分配算法

（1）最小物理塊數(shù)的確定

是指能保證進程正常運行所需的最小物理塊數(shù)。

當(dāng)系統(tǒng)為進程分配的物理塊數(shù)少于此值時，進程將無法運行。當(dāng)系統(tǒng)為進程分配的物理塊數(shù)過多時，影響并發(fā)進程數(shù)，內(nèi)存利用率降低（2）物理塊的分配策略

在請求分頁系統(tǒng)中，可采取兩種內(nèi)存分配策略，即固定和可變分配策略。在進行置換時，也可采取兩種策略，即全局置換和局部置換。于是可組合出以下三種適用的策略。1)固定分配局部置換2)可變分配全局置換3)可變分配局部置換平均分配算法將空閑物理塊，平均分配給各個進程按比例分配算法根據(jù)進程的大小按比例分配物理塊考慮優(yōu)先權(quán)的分配算法按比例分配給各進程優(yōu)先權(quán)高的一次分得的物理塊數(shù)多（3）物理塊分配算法

3、調(diào)頁策略（1）何時調(diào)入頁面預(yù)調(diào)頁策略2)請求調(diào)頁策略系統(tǒng)擁有足夠的對換區(qū)空間系統(tǒng)缺少足夠的對換區(qū)空間UNIX方式（2）從何處調(diào)入頁面（2）從何處調(diào)入頁面

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

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

3)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)入。(3)頁面調(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)存中選出一頁準備換出；如果該頁未被修改過，可不必將該頁寫回磁盤；但如果此頁已被修改，則必須將它寫回磁盤，然后再把所缺的頁調(diào)入內(nèi)存，并修改頁表中的相應(yīng)表項，置其存在位為“1”，并將此頁表項寫入快表中。在缺頁調(diào)入內(nèi)存后，利用修改后的頁表，去形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)。向CPU發(fā)出缺頁中斷中斷處理程序保存CPU環(huán)境轉(zhuǎn)中斷處理程序該程序查找頁表，得到該頁在外存中的塊號若內(nèi)存未滿，啟動磁盤I/O讀入；若內(nèi)存已滿，先置換，再調(diào)入最后修改頁表對應(yīng)項的內(nèi)容，并將此頁表項寫入快表

(3)頁面調(diào)入過程4、頁面置換算法（1）最佳(Optimal)置換算法選擇永不再被使用或很久才被訪問的頁面淘汰特點：理論上，性能最佳；實際上，無法實現(xiàn)；通常用該算法來評價其他算法的優(yōu)劣

（1）最佳(Optimal)置換算法缺頁率f=8/15=53%

先進入內(nèi)存的頁，先退出內(nèi)存。實質(zhì)上是淘汰在內(nèi)存駐留時間最長的頁。其理由是：最早調(diào)入內(nèi)存的頁，不再被使用的可能性比近期調(diào)入內(nèi)存的大。

這種算法簡單，實現(xiàn)容易。它是一種最直觀，性能最差的算法，它有BELADY異?，F(xiàn)象：當(dāng)物理塊數(shù)增加時，缺頁次數(shù)增加。（2）先進先出(FIFO)頁面置換算法有一虛擬存儲系統(tǒng)，采用先進先出的頁面淘汰算法。在內(nèi)存中為每個進程分配3塊。進程執(zhí)行時使用頁號的順序為432143543215(1) 該進程運行時總共出現(xiàn)幾次缺頁。(2) 若每個進程在內(nèi)存有4塊，又將產(chǎn)生幾次缺頁。(3) 如何解釋所出現(xiàn)的現(xiàn)象。

例1（3）LRU(LeastRecentlyUsed)置換算法選擇在最近一段時間內(nèi)不常用的頁面進行淘汰需要周期性地對“頁面訪問位”進行檢查,記錄上次訪問以來經(jīng)歷的時間該類算法實現(xiàn)較困難,常用近似該算法的Clock算法（3）LRU(LeastRecentlyUsed)置換算法缺頁率f=11/15=75%

練習(xí)：在一個請求分頁系統(tǒng)中，假定系統(tǒng)分給一個作業(yè)的物理塊數(shù)為3，并且此作業(yè)的頁面走向為2，3，2，1，5，2，4，5，3，2，5，2。用FIFO、LRU、OPT計算缺頁次數(shù)和缺頁率。

分析：如果所訪問的頁還沒有裝入內(nèi)存，將發(fā)生一次缺頁中斷。訪問過程中發(fā)生缺頁中斷的次數(shù)就是缺頁次數(shù)。缺頁次數(shù)除以總的訪問次數(shù)，就是缺頁率。(4)簡單的Clock算法

每頁設(shè)置一位訪問位。當(dāng)某頁被訪問了，則訪問位置“1”。將內(nèi)存中的頁鏈成一個循環(huán)隊列,查詢指針循環(huán)移動入口查尋指針前進一步指向下一個表目訪問位=0?選擇該頁淘汰返回訪問位置0YF

又稱為“最近未使用”置換算法（NRU）Clock算法加上置換代價(盡量選擇未修改過的頁面淘汰)每頁有訪問頁u和修改位mu=0m=0未用過,未修改過,最佳淘汰頁面u=0m=1未用過,但改過,不是最佳淘汰頁面u=1m=0最近用過,但未被修改,可能被再次使用u=1m=1最近用過,被修改過,可能被再次使用算法需要重復(fù)多次Clock算法從當(dāng)前位置找u=0,m=0的頁面,有則淘汰否則第二遍找u=0,m=1的頁面,同時將u置為0,有則淘汰否則第三遍找u=0,m=0的頁面,有則淘汰否則第四遍找u=0,m=1的頁面,(肯定會找到)(5)改進型Clock算法性能分析1、抖動抖動:分給作業(yè)的物理塊太少或置換算法不當(dāng)引發(fā)的頻繁的產(chǎn)生缺頁中斷。工作集“△”是程序局部性的一個近似...161567675162324124234343432332...△=10t1WS(t1)={1,5,6,7}WS(t2)={2,3,4}△=10t2操作系統(tǒng)管理每一作業(yè)的工作集,為作業(yè)分配足夠的物理塊,以容納它的工作集若有空閑塊可考慮引入新進程若各作業(yè)工作集總和超過可供使用的物理塊數(shù),OS選擇一個作業(yè)暫停執(zhí)行,頁面寫回外存2、工作集模型拐點缺頁率

工作集的理論是在1968年由Denning提出來的。他認為，程序在運行時對頁面的訪問是不均勻的，即往往在某段時間內(nèi)的訪問僅局限于較少的若干個頁面，如果能夠預(yù)知程序在某段時間間隔內(nèi)要訪問哪些頁面，并能將它們提前調(diào)入內(nèi)存，將會大大地降低缺頁率，從而減少置換工作，提高CPU的利用率。圖中可以看出，缺頁率隨著所分得的物理塊數(shù)目的減少而遞增，并在所分到的物理塊數(shù)目較少處，出現(xiàn)一個拐點。在拐點上限以左時，隨著分到的物理塊數(shù)目的增加，缺頁率明顯地減少；而過了拐點，在下限以右時，隨著分到的物理塊數(shù)目的增加，卻對缺頁率的改善并不明顯。所以，為進程分配的物理塊數(shù)，應(yīng)取在該曲線的拐點左右。所分得的物理塊數(shù)訪問順序1,3,2,4,5,6,1,2,4,5,4,3分配3個塊,OPT,FIFO,LRU計算缺頁次數(shù)和缺頁率5.4請求分段存儲管理方式

1、請求分段中的硬件支持（1）段表機制

在段表項中，除了段名(號)、段長、段在內(nèi)存中的起始地址外，還增加了以下諸項：存取方式訪問字段A修改位M存在位P增補位外存始址（2）缺段中斷機構(gòu)

請求分段系統(tǒng)中的中斷處理過程（3）地址變換機構(gòu)圖請求分段系統(tǒng)的地址變換過程2、分段的共享與保護（1）共享段表圖4-33共享段表項（2）共享段的分配與回收

1)共享段的分配在為共享段分配內(nèi)存時，對第一個請求使用該共享段的進程，由系統(tǒng)為該共享段分配一物理區(qū)，再把共享段調(diào)入該區(qū)，同時將該區(qū)的始址填入請求進程的段表的相應(yīng)項中，還須在共享段表中增加一表項，填寫有關(guān)數(shù)據(jù)，把count置為1；之后，當(dāng)又有其它進程需要調(diào)用該共享段時，由于該共享段已被調(diào)入內(nèi)存，故此時無須再為該段分配內(nèi)存，而只需在調(diào)用進程的段表中，增加一表項，填寫該共享段的物理地址；在共享段的段表中，填上調(diào)用進程的進程名、存取控制等，再執(zhí)行count∶=count+1操作，以表明有兩個進程共享該段。

2)共享段的回收當(dāng)共享此段的某進程不再需要該段時，應(yīng)將該段釋放，包括撤在該進程段表中共享段所對應(yīng)的表項，以及執(zhí)行count∶=count-1操作。若結(jié)果為0，則須由系統(tǒng)回收該共享段的物理內(nèi)存，以及取消在共享段表中該段所對應(yīng)的表項，表明此時已沒有進程使用該段；否則(減1結(jié)果不為0)，則只是取消調(diào)用者進程在共享段表中的有關(guān)記錄。（3）分段保護越界檢查2)存取控制檢查例題某虛擬存儲器的用戶編程空間共32個頁面，每頁1KB，主存為16KB。假定某時刻用戶頁表中已調(diào)入主存的頁面的虛擬頁號和物理頁表對照表為表一，則下表中與虛擬地址相對應(yīng)的物理地址為表二（如果主存找不到，即為該頁失效）。虛擬存貯存的功能是由﹎﹎C﹎﹎完成的。在虛擬存貯系統(tǒng)中，采用﹎﹎D﹎﹎提高﹎﹎E﹎﹎的速度。表一虛頁號物理頁號 051102487 表二虛地址 物理地址 0A5C（H）﹎﹎A﹎﹎ 1A5C（H）﹎﹎B﹎﹎ 例題-1供選擇的答案：A，B：①頁失效②1E5C（H）③2A5C（H）④165C（H）⑤125C（H）⑥1A5C（H）C：①硬件②軟件③軟、硬件結(jié)合D：①高速輔助存貯器②高速光盤存貯器③快速通道④高速緩沖存貯器E：①連接編輯②虛地址分配③動態(tài)地址翻譯④動態(tài)連接例題-2解：每頁大小1KB，用16進制表示為400H，由虛地址通過直接映象的地址轉(zhuǎn)換成物理地址步驟如下：將虛地址分離成頁號p和頁內(nèi)地址d：頁號p＝（虛地址／頁大?。┤≌剑?A5CH/400H）取整＝2頁內(nèi)地址d＝虛地址－頁號p×每頁大小＝0A5C(H)－2×400(H)＝25C(H)根據(jù)頁號查頁表，由頁號p＝2查頁表得物理頁號為4將物理頁號和頁內(nèi)地址構(gòu)成物理地址＝物理頁號×頁大?。搩?nèi)地址＝4×400(H)＋25C(H)＝125C(H)同理虛擬地址1A5CH分離成頁號P＝6和頁內(nèi)位移25CH.查頁表知該頁不在內(nèi)存，頁失效產(chǎn)生缺頁中斷調(diào)入內(nèi)存。習(xí)題1．虛擬存儲管理系統(tǒng)的基礎(chǔ)是程序的局部性理論。此理論的基本含義是﹎﹎A﹎﹎。局部性有兩種表現(xiàn)形式：時間局限性和﹎﹎B﹎﹎。它們的意義分別為﹎﹎C﹎﹎和﹎﹎D﹎﹎。A、B，①程序執(zhí)行時對主存和訪問是不均勻的②代碼的順序執(zhí)行③變量的連續(xù)訪問④指令的局部性⑤數(shù)據(jù)的局部性⑥空間局部性C、D：①最近被訪問的單元，很可能在不久的將來還要被訪問②最近被訪問的單元，很可能在它附近的單元也即將被訪問③結(jié)構(gòu)化程序設(shè)計，很少出現(xiàn)轉(zhuǎn)移語句④程序中循環(huán)語句的執(zhí)行時間一般很長⑤程序中使用的數(shù)據(jù)局部于各子程序

習(xí)題-12.什么叫虛擬存貯器?試述虛擬存貯器的實現(xiàn)原理和它的物質(zhì)基礎(chǔ)。3．在請求分頁內(nèi)存管理的頁表表項中，其中狀態(tài)位供﹎﹎A﹎﹎時參考；修改位供﹎﹎B﹎﹎時參考；訪問位供﹎﹎C﹎﹎時參考；外存始址供﹎﹎D﹎﹎時參考。A，B，C，D：（l）分配頁面；（2）置換算法；（3）程序訪問；（4）換出頁面；（5）調(diào)入頁面。4.在請求調(diào)頁系統(tǒng)中，凡未裝入過內(nèi)存的頁都應(yīng)從﹎﹎A﹎﹎調(diào)入；已運行過的頁主要是從﹎﹎B﹎﹎調(diào)入，有時也可以從﹎﹎C﹎﹎調(diào)入。A，B，C：（1）系統(tǒng)區(qū)；（2）文件區(qū)；（3）對換區(qū)；（4）頁面緩沖池。5.詳述在設(shè)有快表的請求分頁存儲管理系統(tǒng)中，一個虛地址轉(zhuǎn)換成物理內(nèi)存地址的過程。習(xí)題-26．在請求調(diào)頁系統(tǒng)中有著多種置換算法：（1）選擇最先進入內(nèi)存的頁面予以淘汰的算法稱為﹎﹎A﹎﹎；（2）選擇在以后不再使用的頁面予以淘汰的算法稱為﹎﹎B﹎﹎；（3）選擇自上次訪問以來所經(jīng)歷時間最長的頁面予以淘汰的算法稱為﹎﹎C﹎﹎。A，B，C，D：（1）FIFO算法；（2）OPT算法；（3）LRU算法；（4）NRU算法。7．在一個請求分頁系統(tǒng)中，采用FIFO頁面置換算法時，假如一個作業(yè)的頁面訪問順序為4，3，2，1，4，3，5，4，3，2，l，5，當(dāng)分配給該作業(yè)的物理塊數(shù)M分別為3和4時，試計算訪問過程中所發(fā)生的缺頁次數(shù)分別為﹎﹎A﹎﹎和﹎﹎B﹎﹎，缺頁率分別為A/C和B/C，其中﹎﹎C﹎﹎為訪問次數(shù)。比較所得的結(jié)果為﹎﹎D﹎﹎。A，B，C，D：見8題習(xí)題-38．在一個請求分頁系統(tǒng)中，采用LRU頁面置換算法時，假如一個作業(yè)的頁面訪問順序為4，3，2，1，4，3，5，4，3，2，l，5，當(dāng)分配給該作業(yè)的物理塊數(shù)M分別為3和4時，試計算訪問過程中所發(fā)生的缺頁次數(shù)﹎﹎A﹎﹎和﹎﹎B﹎﹎，缺頁率分別為A/C和B/C，其中﹎﹎C﹎﹎為訪問次數(shù)。比較所得的結(jié)果為﹎﹎D﹎﹎。A，B，C：（1）7；（2）8；（3）9；（4）10；(5)11；(6)12；(7)13。D:(1)正?，F(xiàn)象，即存儲塊增加，缺頁次數(shù)減少；(2)存在奇異現(xiàn)象，即存儲塊增加，缺頁次數(shù)反而增加；(3)存儲塊增加，缺頁次數(shù)不變。

9.在分頁系統(tǒng)環(huán)境下,程序員編制的程序,其地址空間是連續(xù)的,分頁是由(

)完成的 A.

程序員

B編譯地址

C用戶

D系統(tǒng) 10.在請求分頁存儲管理系統(tǒng)中，若采用FIFO頁面淘汰算法，則當(dāng)分配的頁面數(shù)增加時，缺頁中斷的次數(shù)（

） A減少

B

增加

C無影響

D可能增加也可能減少

11.采用段式存儲管理的系統(tǒng)中，若地址用24位表示，其中8位表示段號，D則允許每段的最大長度是（）

A

224

B216

C28

D232

12.作業(yè)在執(zhí)行中發(fā)生了缺頁中斷，經(jīng)操作系統(tǒng)處理后，應(yīng)讓其執(zhí)行（）指令 A被中斷的前一條

B被中斷的

C被中斷的后一條

D啟動時的第一條13.LRU頁面調(diào)度算法淘汰——的頁。A.最近最少使用B.最近最久未使用C.最先進入內(nèi)存D.將來最久使用14.頁面置換算法中——不是基于程序執(zhí)行的局部性理論。A.先進先出調(diào)度算法B.LRUC.OPTD.CLOCK算法15.在存儲管理中，采用覆蓋與交換技術(shù)的目的是——。

A.節(jié)省內(nèi)存空間B.物理上擴充內(nèi)存容量C.提高CPU利用率D.實現(xiàn)內(nèi)存共享16.可變分區(qū)方式常用的內(nèi)存分配算法中，——總是找到能滿足作業(yè)要求的最小空閑區(qū)分配。