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

(1)有的作業很大，其所要求的內存空間超過了內存總容量，作業不能全部被裝入內存，致使該作業無法運行；

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

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

(1)程序執行時，除了少部分的轉移和過程調用指令外，在大多數情況下仍是順序執行的。

(2)過程調用將會使程序的執行軌跡由一部分區域轉至另一部分區域，但經研究表明，過程調用的深度在大多數情況下都不超過5。也就是說，程序將會在一段時間內，都局限在這些過程的范圍內運行。

(3)程序中存在許多循環結構，這些雖然只由少數指令構成，但是它們將多次執行。

(4)程序中還包括許多對數據結構的處理，如對數組進行操作，它們往往都局限于很小的范圍內。

局限性又表現在下述兩個方面：

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

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

所謂虛擬存儲器，是指具有請求調入功能和置換功能，能從邏輯上對內存容量加以擴充的一種存儲器系統。其邏輯容量由內存容量和外存容量之和所決定，其運行速度接近于內存速度，而每位的成本卻又接近于外存?？梢?，虛擬存儲技術是一種性能非常優越的存儲器管理技術，故被廣泛地應用于大、中、小型機器和微型機中。

5.1.2虛擬存儲器的實現方法1.分頁請求系統(1)硬件支持

①請求分頁的頁表機制，它是在純分頁的頁表機制上增加若干項而形成的，作為請求分頁的數據結構；②缺頁中斷機構，即每當用戶程序要訪問的頁面尚未調入內存時便產生一缺頁中斷，以請求OS將所缺的頁調入內存；③地址變換機構，它同樣是在純分頁地址變換機構的基礎上發展形成的。(2)實現請求分頁的軟件2.請求分段系統(1)硬件支持

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

3.對換性對換性是指允許在作業的運行過程中換進、換出。4.虛擬性是指能夠從邏輯上擴充內存容量，使用戶所看到的內存容量遠大于實際內存容量。

練習題

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

2、試給一個請求分頁系統設計進程調度的方案，使系統同時滿足以下條件。（1）有合理的響應時間；（2）有較好的外部設備利用率；（3）缺頁對程序執行速度的影響降到最低程度。畫出調度用的進程狀態變遷圖，并說明這樣設計的理由。

5.2請求分頁存儲管理方式

與基本分頁存儲管理不同，請求式分頁管理系統只需作業的部分頁面調入內存就可以運行了。但系統需要解決下面三個問題：系統如何獲知進程當前所需頁面不在主存。

當發現缺頁時，如何把所缺頁面調入主存。當主存中沒有空閑的頁框時，為了要接受一個新頁，需要把老的一頁淘汰出去，根據什么策略選擇欲淘汰的頁面。5.2請求分頁存儲管理方式5.2.1請求分頁中的硬件支持1.頁表機制頁號物理塊號狀態位P訪問字段A修改位M外存地址

狀態位P

用于指示該頁是否已調入內存，供程序訪問時參考。

訪問字段A

用于記錄本頁在一段時間內被訪問的次數，或最近已有多長時間未被訪問，提供給置換算法選擇換出頁面時參考。

修改位M

表示該頁在調入內存后是否被修改過。作為該頁換出時是否寫回外存的依據。

外存地址

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

3.地址變換機構5.2.2內存分配策略和分配算法1.最小物理塊數的確定

是指能保證進程正常運行所需的最小物理塊數。當系統為進程分配的物理塊數少于此值時，進程將無法運行。進程應獲得的最少物理塊數與計算機的硬件結構有關，取決于指令的格式、功能和尋址方式。對于某些簡單的機器，若是單地址指令且采用直接尋址方式，則所需的最少物理塊數為2。其中，一塊是用于存放指令的頁面，另一塊則是用于存放數據的頁面。如果該機器允許間接尋址時，則至少要求有三個物理塊。對于某些功能較強的機器，其指令長度可能是兩個或多于兩個字節，因而其指令本身有可能跨兩個頁面，且源地址和目標地址所涉及的區域也都可能跨兩個頁面。2.物理塊的分配策略

在請求分頁系統中，可采取兩種內存分配策略，即固定和可變分配策略。在進行置換時，也可采取兩種策略，即全局置換和局部置換。于是可組合出以下三種適用的策略。

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

1)平均分配算法

這是將系統中所有可供分配的物理塊，平均分配給各個進程。例如，當系統中有100個物理塊，有5個進程在運行時，每個進程可分得20個物理塊。這種方式貌似公平，但實際上是不公平的，因為它未考慮到各進程本身的大小。如有一個進程其大小為200頁，只分配給它20個塊，這樣，它必然會有很高的缺頁率；而另一個進程只有10頁，卻有10個物理塊閑置未用。

2)按比例分配算法

這是根據進程的大小按比例分配物理塊的算法。如果系統中共有n個進程，每個進程的頁面數為Si，則系統中各進程頁面數的總和為：

又假定系統中可用的物理塊總數為m，則每個進程所能分到的物理塊數為bi，將有：

b應該取整，它必須大于最小物理塊數。

3)考慮優先權的分配算法

在實際應用中，為了照顧到重要的、緊迫的作業能盡快地完成，應為它分配較多的內存空間。通常采取的方法是把內存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進程；另一部分則根據各進程的優先權，適當地增加其相應份額后，分配給各進程。在有的系統中，如重要的實時控制系統，則可能是完全按優先權來為各進程分配其物理塊的。5.2.3調頁策略1.何時調入頁面

預調頁策略

就是將那些預計在不久之后便會被訪問的頁面預先調入內存。2)請求調頁策略

當進程在運行中需要訪問某部分程序和數據時，若發現其所在的頁面不在內存，便立即提出請求，由OS將其所需頁面調入內存。2.從何處調入頁面

在請求分頁系統中的外存分為兩部分：用于存放文件的文件區和用于存放對換頁面的對換區。通常，由于對換區是采用連續分配方式，而文件區采用離散分配方式，故對換區的磁盤I/O速度比文件區的高。這樣，每當發生缺頁請求時，系統應從何處將缺頁調入內存，可分成如下三種情況：

(1)系統擁有足夠的對換區空間，這時可以全部從對換區調入所需頁面，以提高調頁速度。為此，在進程運行前，便須將與該進程有關的文件，從文件區拷貝到對換區。

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

(3)UNIX方式。由于與進程有關的文件都放在文件區，故凡是未運行過的頁面，都應從文件區調入。而對于曾經運行過但又被換出的頁面，由于是被放在對換區，因此在下次調入時，應從對換區調入。由于UNIX系統允許頁面共享，因此，某進程所請求的頁面有可能已被其它進程調入內存，此時也就無須再從對換區調入。3.頁面調入過程

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

假定系統為某進程分配了三個物理塊，并考慮有以下的頁面號引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。進程運行時，先將7，0，1三個頁面裝入內存。以后，當進程要訪問頁面2時，將會產生缺頁中斷。此時OS根據最佳置換算法，將選擇頁面7予以淘汰。利用最佳頁面置換算法時的置換圖2.先進先出(FIFO)頁面置換算法利用FIFO置換算法時的置換圖

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

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

當進程訪問某物理塊時，要將相應寄存器的Rn-1位置成1。此時，定時信號將每隔一定時間將寄存器右移一位。如果把n位寄存器的數看做是一個整數，那么具有最小數值的寄存器所對應的頁面，就是最近最久未使用的頁面。某進程具有8個頁面時的LRU訪問情況

2)棧用棧保存當前使用頁面時棧的變化情況

練習題

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

2、試給一個請求分頁系統設計進程調度的方案，使系統同時滿足以下條件。（1）有合理的響應時間；（2）有較好的外部設備利用率；（3）缺頁對程序執行速度的影響降到最低程度。畫出調度用的進程狀態變遷圖，并說明這樣設計的理由。

5.4請求分段存儲管理方式5.4.1請求分段中的硬件支持1.段表機制段名段長段的基址存取方式訪問字段A修改位M存在位P增補位外存始址

在段表項中，除了段名(號)、段長、段在內存中的起始地址外，還增加了以下諸項：(1)存取方式(2)訪問字段A