第五章 虛拟存儲器【作業系統】

• ​​前言​​
• ​​推薦​​
• ​​第五章 虛拟存儲器​​

• ​​5.1 虛拟存儲器概述​​

• ​​5.1.1 正常存儲管理方式的特征和局部性原理​​
• ​​5.1.2虛拟存儲器的定義和特征​​
• ​​5.1.3虛拟存儲器的實作方法​​

• ​​5.2 請求分頁存儲管理方式​​

• ​​5.2.1 請求分頁中的硬體支援​​
• ​​5.2.2 請求分頁中的記憶體配置設定​​
• ​​5.2.3 頁面調入政策​​

• ​​5.3 頁面置換算法​​

• ​​5.3.1 最佳置換算法和先進先出置換算法​​
• ​​5.3.2 最近最久未使用和最少使用置換算法​​
• ​​5.3.3 Clock 置換算法​​
• ​​5.3.4 頁面緩沖算法 PBA​​
• ​​5.3.5 通路記憶體的有效時間​​

• ​​5.4 “抖動”與工作集​​

• ​​5.4.1 多道程式度與“抖動”​​
• ​​5.4.2 工作集​​
• ​​5.4.3 “抖動”的預防方法​​

• ​​5.5 請求分段存儲管理方式​​

• ​​5.5.1 請求分段中的硬體支援​​
• ​​5.5.2 分段的共享與保護​​

• ​​最後​​

前言

以下内容源自計算機作業系統（第四版）

關于作業系統，

CSDN有很多的優秀部落格。

在這裡，

本文摘取其他部落格内容，

并附上相關連結，

如有侵權，

聯系删除，

​

第五章 虛拟存儲器

5.1 虛拟存儲器概述

虛拟存儲器實作了記憶體擴充功能。但該功能并非是從實體上實際地擴大記憶體的容量，而是從邏輯上實作對記憶體容量的擴充。

第四章所介紹的各種存儲器管理方式有一個共同的特點，即它們都要求将一個作業全部裝入記憶體後方能運作。于是，出現了下面這樣兩種情況：

1）有的作業很大，其所要求的記憶體空間超過了記憶體總容量。

2）有大量作業要求運作，但由于記憶體容量不足以容納所有這些作業。

都是由于記憶體容量不夠大導緻的，一種解決方法是從邏輯上擴充記憶體容量，這正是虛拟存儲技術所要解決的主要問題。

5.1.1 正常存儲管理方式的特征和局部性原理

1.正常存儲器管理方式的特征

1）一次性。指作業必須一次性地全部裝入記憶體後方能開始運作。

2）駐留性。作業裝入記憶體後，整個作業會一直駐留在記憶體中，其中任何部分都不會被換出，直至作業運作結束。

一次性及駐留性特征，使許多在程式運作中不用或暫不用的程式(資料)占據了大量的記憶體空間，使得一些需要運作的作業無法裝入運作。

2.局部性原理

程式在執行時将呈現出局部性規律，即在一較短的時間内，程式的執行僅局限于某個部分，相應地，它所通路的存儲空間也局限于某個區域。 論點如下：

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

2）過程調用将會使程式的執行軌迹由一部分區域轉至另一部分區域。

3）程式中存在許多循環結構，這些雖然隻由少數指令構成，但是它們将多次執行。

4）程式中還包括許多對資料結構的處理，如對數組進行操作，它們往往都局限于很小的範圍内。

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

1）時間局限性。如果程式中的某條指令(或資料)一旦被執行(或被通路)，則不久以後該指令(或資料)可能再次被執行(或被通路)。産生時間局限性的典型原因是由于在程式中存在着大量的循環操作。

2）空間局限性。程式在一段時間内所通路的位址，可能集中在一定的範圍之内，其典型情況便是程式的順序執行。

3.虛拟存儲器的基本工作情況

基于局部性原理可知，應用程式在運作之前，沒有必要全部裝入記憶體，僅須将那些目前要運作的少數頁面或段先裝入記憶體便可運作，其餘部分暫留在盤上。程式在運作時，如果它所要通路的頁(段)已調入記憶體，便可繼續執行下去；但如果程式所要通路的頁(段)尚未調入

記憶體(稱為缺頁或缺段)，此時程式應利用 OS 所提供的請求調頁(段)功能，将它們調入記憶體，以使程序能繼續執行下去。如果此時記憶體已滿，無法再裝入新的頁(段)，則還須再利用頁(段)的置換功能，将記憶體中暫時不用的頁(段)調至盤上，騰出足夠的記憶體空間後，再将要通路的頁(段)調入記憶體，使程式繼續執行下去。這樣，便可使一個大的使用者程式能在較小的記憶體空間中運作；也可在記憶體中同時裝入更多的程序使它們并發執行。

5.1.2虛拟存儲器的定義和特征

1.虛拟存儲器的定義

所謂虛拟存儲器，是指具有請求調入功能和置換功能，能從邏輯上對記憶體容量加以擴充的一種存儲器系統。其邏輯容量由記憶體容量和外存容量之和所決定，其運作速度接近于記憶體速度，而每位的成本卻又接近于外存。

2.虛拟存儲器的特征

1）多次性。是指一個作業中的程式和資料無需在作業運作時一次性地全部裝入記憶體，而是允許被分成多次調入記憶體運作，即隻需将目前要運作的那部分程式和資料裝入記憶體即可開始運作。

2）對換性。是指一個作業中的程式和資料，無須在運作時一直常駐記憶體，而是允許在作業的運作過程中進行換進、換出。

3）虛拟性。是指能夠從邏輯上擴充記憶體容量，使使用者所看到的記憶體容量遠大于實際記憶體容量。就可以在小的記憶體中運作大的作業，或者能提高多道程式度。

虛拟性是以多次性和對換性為基礎的，而多次性和對換性是必須建立在離散配置設定的基礎上。

5.1.3虛拟存儲器的實作方法

1.分頁請求系統

這是在分頁系統的基礎上，增加了請求調頁功能和頁面置換功能所形成的頁式虛拟存儲系統。置換時以頁面為機關。

1）硬體支援。

①請求分頁的頁表機制。

②缺頁中斷機構。

③位址變換機構。

2）實作請求分頁的軟體。

包括有用于實作請求調頁的軟體和實作頁面置換的軟體。

2.分段請求系統

這是在分段系統的基礎上，增加了請求調段及分段置換功能後所形成的段式虛拟存儲系統。置換時以段為機關。

1）硬體支援。

①請求分段的段表機制。

②缺段中斷機構。

③位址變換機構。

2）實作請求分段的軟體。

包括有用于實作請求調段的軟體和實作段置換的軟體。

因為請求分頁系統換進和換出的基本機關都是固定大小的頁面，是以在實作上要容易些。而請求分段系統換進換出的基本機關是段，其長度是可變的，分段的配置設定類似于動态分區方式，它在記憶體配置設定和回收上都比較複雜。

段頁式虛拟存儲器系統。

在段頁式系統基礎上，增加請求調頁和頁面置換功能形成段頁式虛拟存儲器系統。

5.2 請求分頁存儲管理方式

5.2.1 請求分頁中的硬體支援

1.請求頁表機制

在請求頁表中增加了四個字段：

1）狀态位(存在位) P：訓示該頁是否已調入記憶體。

2）通路字段A：記錄該頁在一段時間内的通路次數，或者最近多久未被通路，為置換算法選擇置換頁提供參考；

3）修改位M：訓示該頁在調入記憶體後是否被修改過。

4）外存位址：訓示該頁在外存的位址，通常是實體塊号。

2.缺頁中斷機構

在請求分頁系統中，每當所要通路的頁面不在記憶體時，便産生一缺頁中斷，請求 OS 将所缺之頁調入記憶體。缺頁中斷作為中斷，它們同樣需要經曆諸如保護 CPU 環境、分析中斷原因、轉入缺頁中斷處理程式進行處理、恢複 CPU 環境等幾個步驟。但缺頁中斷又是一種特殊的中斷，它與一般的中斷相比，有着明顯的差別，主要表現在下面兩個方面：

1）在指令執行期間産生和進行中斷信号。即在指令執行期間，發現所要通路的指令或資料不在記憶體時所産生和處理的。

2）一條指令在執行期間，可能産生多次缺頁中斷。并保證最後能傳回到中斷前産生缺頁中斷的指令處繼續執行。

3.位址變換機構

在檢索塊表和頁表時，對于寫指令，還須将修改位置成“1”。

5.2.2 請求分頁中的記憶體配置設定

1.最小實體塊數的确定

這裡所說的最小實體塊數，是指能保證程序正常運作所需的最小實體塊數。程序應獲得的最少實體塊數與計算機的硬體結構有關，取決于指令的格式、功能和尋址方式。

2.記憶體配置設定政策

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

1）固定配置設定局部置換。

所謂固定配置設定，是指為每個程序配置設定一定數目的實體塊，在整個運作期間都不再改變。所謂局部置換，是指如果程序在運作中發現缺頁，則隻能從配置設定給該程序的 n 個頁面中選出一個頁換出，然後再調入一頁，以保證配置設定給該程序的記憶體空間不變。實作這種政策的困難在于：應為每個程序配置設定多少個實體塊難以确定。

2）可變配置設定全局置換。

所謂可變配置設定，是指先為系統中的每個程序配置設定一定數目的實體塊，在程序運作期間，可根據情況做适當的增加或減少。所謂全局置換，是指當程序發現缺頁時，則将 OS 所保留的空閑實體塊(一般組織為一個空閑實體塊隊列)取出一塊配置設定給該程序，或者以所有實體塊為标的，選擇一塊換出，然後将所缺之頁調入。

在采用這種政策時，凡産生缺頁(中斷)的程序，都将獲得新的實體塊，僅當空閑實體隊列中的實體塊用完時，OS 才能從記憶體中選擇一頁調出，而被選擇調出的頁所屬的程序擁有的實體塊就會減少，導緻其缺頁率增加。

3）可變配置設定局部置換。

該政策為每個程序配置設定一定數目的實體塊，但當某程序發現缺頁時，隻允許從該程序在記憶體的頁面中選出一頁換出，這樣就不會影響其它程序的運作。如果程序在運作中頻繁地發生缺頁中斷，則系統須再為該程序配置設定若幹附加的實體塊，直至該程序的缺頁率減少到适當程度為止；反之，若一個程序在運作過程中的缺頁率特别低，則此時可适當減少配置設定給該程序的實體塊數，但不應引起其缺頁率的明顯增加。

3.實體塊配置設定算法

在采用固定配置設定政策時，如何配置設定實體塊采用以下算法：

1）平均配置設定算法。

2）按比例配置設定算法，即根據程序的大小按比例配置設定實體塊的算法。

3）考慮優先權的配置設定算法。通常采取的方法是把記憶體中可供配置設定的所有實體塊分成兩部分：一部分按比例地配置設定給各程序；另一部分則根據各程序的優先權進行配置設定。

5.2.3 頁面調入政策

1.何時調入頁面

1）預調頁政策。一次調入若幹個相鄰的頁。

①可用于程序的首次調入時。②在采用工作集的系統中使用。

2）請求調頁政策。

程序在運作中提出缺頁請求時調入。這種政策每次僅調入一頁，故須花費較大的系統開銷，增加了磁盤 I/O 的啟動頻率。

2.從何處調入頁面

通常，由于對換區是采用連續配置設定方式，而檔案區是采用離散配置設定方式，故對換區的磁盤 I/O 速度比檔案區的高。

1）系統擁有足夠的對換區空間，這時可以全部從對換區調入所需頁面，以提高調頁速度。為此，在程序運作前，便須将與該程序有關的檔案從檔案區拷貝到對換區。

2）系統缺少足夠的對換區空間，這時凡是不會被修改的檔案都直接從檔案區調入；但對于那些可能被修改的部分，在将它們換出時，便須調到對換區，以後需要時，再從對換區調入。

3）UNIX 方式。凡是未運作過的頁面，都應從檔案區調入。而對于曾經運作過但又被換出的頁面，由于是被放在對換區，是以在下次調入時，應從對換區調入。

3.頁面調入過程

每當程式所要通路的頁面未在記憶體時(存在位為“0”)，便向 CPU 發出一缺頁中斷，中斷處理程式首先保留 CPU 環境，分析中斷原因後轉入缺頁中斷處理程式。該程式通過查找頁表，得到該頁在外存的實體塊後，如果此時記憶體能容納新頁，則啟動磁盤 I/O 将所缺之頁調入記憶體，然後修改頁表。如果記憶體已滿，則須先按照某種置換算法從記憶體中選出一頁準備換出；如果該頁未被修改過(修改位為“0”)，可不必将該頁寫回磁盤；但如果此頁已被修改(修改位為“1”)，則必須将它寫回磁盤，然後再把所缺的頁調入記憶體，并修改頁表中的相應表項，置其存在位為“1”，并将此頁表項寫入快表中。在缺頁調入記憶體後，利用修改後的頁表，去形成所要通路資料的實體位址，再去通路記憶體資料。整個頁面的調入過程對使用者是透明的。

4.缺頁率

如果在程序的運作過程中，通路頁面成功(即所通路頁面在記憶體中)的次數為S，通路頁面失敗(即所通路頁面不在記憶體中，需要從外存調入)的次數為F，則該程序總的頁面通路次數為A = S + F，那麼該程序在其運作過程中的缺頁率即為

f=F/A

缺頁率受以下因素的影響：

1）頁面大小。

2）程序所配置設定實體塊的數目。

3）頁面置換算法。是以缺頁率是衡量頁面置換算法的重要名額。

4）程式固有特性。

事實上，在缺頁處理時，選擇被置換頁面還需要考慮置換的代價，如頁面是否被修改過。

5.3 頁面置換算法

把記憶體已無空閑空間時選擇換出頁面的算法稱為頁面置換算法(Page-Replacement Algorithms)。

不适當的算法可能會導緻程序發現“抖動”，即剛被換出的頁很快又要被通路，需要将它重新調入，可能會出現頻繁地更換頁面，以緻一個程序在運作中把大部分時間都花費在頁面置換工作上。

一個好的頁面置換算法，應具有較低的頁面更換頻率。

5.3.1 最佳置換算法和先進先出置換算法

最佳置換算法是一種理想化的算法，通常使用最佳置換算法作為标準，來評價其它算法的優劣。先進先出置換算法是最直覺的算法，由于與通常頁面的使用規律不服，可能是性能最差的算法，故實際應用極少。

1.最佳(Optimal)置換算法

其所選擇的被淘汰頁面，将是以後永不使用的，或許是在最長(未來)時間内不再被通路(即下一次通路時間最晚)的頁面。采用最佳置換算法，通常可保證獲得最低的缺頁率。

假定系統為某程序配置設定了三個實體塊，并考慮有以下的頁面好引用串：

7,0,1,2,0,3,0,4，2,3,0,3,2,1,2,0,1,7,0,1      

置換圖如下：

每次把最長（未來）時間内不在通路的頁面置換出

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7
  0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0
    1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1
+ + + +       +     +     +       +      

置換次數是6次，前三次不是置換，隻是缺頁

缺頁中斷次數9，缺頁率9/20

2.先進先出(FIFO)頁面置換算法

總是淘汰最先進入記憶體的頁面，即選擇在記憶體中駐留時間最久的頁面予以淘汰。

FIFO 置換算法性能之是以較差，是因為它所依據的條件是各個頁面調入記憶體的時間，而頁面調入的先後并不能反映頁面的使用情況。

假定系統為某程序配置設定了三個實體塊，并考慮有以下的頁面好引用串：

7,0,1,2,0,3,0,4，2,3,0,3,2,1,2,0,1,7,0,1      

置換圖如下：

置換出最先進入記憶體的頁面，置入放在最底了，這樣最頂就是最先進入記憶體

當不需要置換時，保持不變。

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
7 7 7 0 0 1 2 3 0 4 2 2 2 3 0 0 0 1 2 7
  0 0 1 1 2 3 0 4 2 3 3 3 0 1 1 1 2 7 0
    1 2 2 3 0 4 2 3 0 0 0 1 2 2 2 7 0 1
+ + + +   + + + + + +     + +     + + +      

置換次數是12次，前三次不是置換，隻是缺頁

缺頁中斷次數15，缺頁率15/20

5.3.2 最近最久未使用和最少使用置換算法

1.LRU(Least Recently Used) 置換算法的描述

最近最久未使用(LRU)的頁面置換算法，是根據頁面調入記憶體後的使用情況進行決策的。即選擇最近最久未使用的頁面予以淘汰。該算法賦予每個頁面一個通路字段，用來記錄一個頁面自上次被通路以來所經曆的時間 t，當須淘汰一個頁面時，選擇現有頁面中其 t 值最大的，即最近最久未使用的頁面予以淘汰。

最佳置換算法是從“向後看”的觀點出發的，即它是依據以後各頁的使用情況；而 LRU 算法則是“向前看”的，即根據各頁以前的使用情況來判斷，而頁面過去和未來的走向之間并無必然的聯系。

2.LRU 置換算法的硬體支援

1）寄存器。

為每個在記憶體中的頁面配置一個移位寄存器，可表示為

R=Rn-1Rn-2Rn-3…R2R1R0

當程序通路某實體塊時，要将相應寄存器的 Rn－1 位置成 1。此時，定時信号将每隔一定時間(例如 100 ms)将寄存器右移一位。如果我們把 n 位寄存器的數看做是一個整數，那麼，具有最小數值的寄存器所對應的頁面，就是最近最久未使用的頁面。

2）棧。

可利用一個特殊的棧來儲存目前使用的各個頁面的頁面号。每當程序通路某頁面時，便将該頁面的頁面号從棧中移出，将它壓入棧頂。是以，棧頂始終是最新被通路頁面的編号，而棧底則是最近最久未使用頁面的頁面号。

假定系統為某程序配置設定了三個實體塊，并考慮有以下的頁面好引用串：

7,0,1,2,0,3,0,4，2,3,0,3,2,1,2,0,1,7,0,1      

置換圖如下：

置換出最進未使用入的頁面，置入放在最底了，這樣最頂就是最近最久未使用的頁面

當不需要置換是，也需把新頁面放在最底，保證了最底層是最近最久使用的頁面。

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
7 7 7 0 1 2 2 3 0 4 2 2 0 3 3 1 2 0 1 7
  0 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0
    1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
+ + + +   +   + + + +     +   +   +      

置換次數是9次，前三次不是置換，隻是缺頁

缺頁中斷次數12，缺頁率12/20

3.最少使用 LFU 置換算法

該算法用移位寄存器方式。每次通路某頁時，便将該移位寄存器的最高位置 1，再每隔一定時間(例如 100 ms)右移一次。LFU 置換算法的頁面通路圖與 LRU 置換算法的通路圖完全相同；或者說，利用這樣一套硬體既可實作 LRU 算法，又可實作 LFU 算法。但 LRU 算法是根據将 n 位看作一個整數找到最近最久未使用的頁面，而 LFU 算法的在最近一段時間使用最少的頁面将是∑Ri 最小的頁。

應該指出，LFU 算法并不能真正反映出頁面的使用情況，因為在每一時間間隔内，隻是用寄存器的一位來記錄頁的使用情況，是以，在該時間間隔内，對某頁通路一次和通路 1000 次是完全等效的。

5.3.3 Clock 置換算法

雖然 LRU 算法是較好的一種算法，但由于它要求有較多的硬體支援，故在實際應用中，大多采用 LRU 的近似算法。Clock 算法就是用得較多的一種 LRU 近似算法。

1.簡單的 Clock 置換算法。

隻需為每頁設定一位通路位，再将記憶體中的所有頁面都通過連結指針連結成一個循環隊列。當某頁被通路時，其通路位被置 1。置換算法在選擇一頁淘汰時，隻需檢查頁的通路位。如果是 0，就選擇該頁換出；若為 1，則重新将它置 0，暫不換出，而給該頁第二次駐留記憶體的機會，再按照 FIFO 算法檢查下一個頁面。該算法是循環地檢查各頁面的使用情況的。又把該算法稱為最近未用算法 NRU。

2.改進型 Clock 置換算法

在改進型 Clock 算法中，除須考慮頁面的使用情況外，還須再增加一個因素，即置換代價，這樣，選擇頁面換出時，既要是未使用過的頁面，又要是未被修改過的頁面。把同時滿足這兩個條件的頁面作為首選淘汰的頁面。由通路位 A 和修改位 M 可以組合成下面四種類型的頁面：

1 類(A=0，M=0)：表示該頁最近既未被通路，又未被修改，是最佳淘汰頁。

2 類(A=0，M=1)：表示該頁最近未被通路，但已被修改，并不是很好的淘汰頁。

3 類(A=1，M=0)：表示該頁最近已被通路，但未被修改，該頁有可能再被通路。

4 類(A=1，M=1)：表示該頁最近已被通路且被修改，該頁可能再被通路。

在記憶體中的每個頁必定是這四類頁面之一，在進行頁面置換時，與簡單 Clock 算法差别在于該算法須同時檢查通路位與修改位，以确定該頁是四類頁面中的哪一種。其執行過程可分成以下三步：

1）從指針所訓示的目前位置開始，掃描循環隊列，尋找 A=0 且 M=0 的第一類頁面，将所遇到的第一個頁面作為所選中的淘汰頁。在第一次掃描期間不改變通路位 A。

2）如果第一步失敗，即查找一周後未遇到第一類頁面，則開始第二輪掃描，尋找 A=0 且 M=1 的第二類頁面，将所遇到的第一個這類頁面作為淘汰頁。在第二輪掃描期間，将所有掃描過的頁面的通路位都置 0。

3）如果第二步也失敗，亦即未找到第二類頁面，則将指針傳回到開始的位置，并已将所有的通路位複 0。然後重複第一步，如果仍失敗，必要時再重複第二步，此時就一定能找到被淘汰的頁。

該算法與簡單 Clock 算法比較，可減少磁盤的 I/O 操作次數。但為了找到一個可置換的頁，可能須經過幾輪掃描。換言之，實作該算法本身的開銷将有所增加。

5.3.4 頁面緩沖算法 PBA

1.影響頁面換進換出效率的若幹因素

1）頁面置換算法。

2）寫回磁盤的頻率。對于已經被修改過的頁面，在将其換出時，應當寫回磁盤。

但如果在系統中已建立了一個已修改換出頁面的連結清單，則對每一個要被換出的頁面(已修改)，系統可暫不把它們寫回磁盤，而是将它們挂在已修改換出頁面的連結清單上，僅當被換出頁面數目達到一定值時，例如64個頁面，再将它們一起寫回到磁盤上，這樣就顯著減少了磁盤 I/O的操作次數。或者說，減少已修改頁面換出的開銷。

3）讀入記憶體的頻率。在設定了已修改換出頁面連結清單後，在該連結清單上就暫時有一批裝有資料的頁面，如果有程序在這批資料還未寫回磁盤時需要再次通路這些頁面時，就不需從外存上調入，而直接從已修改換出頁面連結清單中擷取，這樣也可以減少将頁面從磁盤讀入記憶體的頻率，減少頁面換出的開銷。

2.頁面緩沖算法 PBA

PBA 算法特點：① 顯著地降低了頁面換進、換出的頻率。② 正是由于換入換出的開銷大幅度減小，才能使其可采用一種較簡單的置換政策，如先進先出(FIFO)算法。

介紹VAX/VMS作業系統所使用的頁面緩沖算法。在該系統中記憶體配置設定政策上采用了可變配置設定和局部置換方式，同時在記憶體中設定了兩個連結清單：

1）空閑頁面連結清單。

實際上是一個空閑實體塊連結清單。當程序需要讀入一個頁面時，便可利用空閑實體塊連結清單中的第一個實體塊來裝入該頁。當有一個未被修改的頁要換出時，而是把它們所在的實體塊挂在空閑連結清單表尾。

2）修改頁面連結清單。

是由已修改的頁面所形成的連結清單。當程序需要将一個已修改的頁面換出時，系統并不立即把它換出到外存上，而是将它所在的實體塊挂在修改頁面連結清單的末尾。當達到一定數量時，再将它們一起寫回磁盤。

5.3.5 通路記憶體的有效時間

在請求分頁管理方式中，記憶體有效通路時間不僅要考慮通路頁表和通路實際實體位址資料的時間，還必須考慮缺頁中斷的處理時間。

1）被通路頁在記憶體中，且其對應的頁表項在快表中。

2）被通路頁在記憶體中，且其對應的頁表項不在快表中。

3）被通路頁不在記憶體中，即需要進行缺頁中斷處理。

事實計算時還要考慮快表命中率和頁面缺頁率的因素。

5.4 “抖動”與工作集

5.4.1 多道程式度與“抖動”

1.多道程式度與處理機的使用率

随着多道程式度的增大，處理機的使用率先上升後下降。當多道程式度過高時，會發生“抖動”。

2.産生“抖動”的原因

根本原因是，同時在系統中運作的程序太多，由此配置設定配給每一個程序的實體塊太少，不能滿足程序正常運作的基本要求，緻使每個程序在運作時，頻繁地出現缺頁，必須請求系統将所缺之頁調入記憶體。造成每個程序的大部分時間都用于頁面的換進/換出，而幾乎不能再去做任何有效的工作，進而導緻發生處理機的使用率急劇下降并趨于0的情況。

5.4.2 工作集

1.工作集的基本概念

程序發生缺頁率的時間間隔與程序所獲得的實體塊數有關(即成反比)。

基于程式運作時的局部性原理得知，程式在運作期間，對頁面的通路時不均勻的，在一段時間内僅局限于較少的頁面。這些頁面被稱為活躍頁面。

2.工作集的定義

所謂工作集，是指在某段時間間隔Δ裡，程序實際所要通路頁面的集合。具體地說，把某程序在時間 t 的工作集記作 w(t, Δ)，其中的變量 Δ 稱為工作集的“視窗尺寸”。可将工作集的定義為，程序在時間間隔 (t-Δ, t) 中引用頁面的集合。

工作集是視窗尺寸 Δ 的非降函數。即 w(t, Δ) ⊆ w(t, Δ+1)。

5.4.3 “抖動”的預防方法

這些方法幾乎都是采用調節多道程式度來控制“抖動”發生的。

1.采取局部置換政策。

即使該程序發生了“抖動”，也不會對其它程序産生影響，于是可把該程序“抖動”所造成的影響限制在較小的範圍内。但在某程序發生“抖動”後，它還會長期處在磁盤 I/O 的等待隊列中，使隊列的長度增加，這會延長其它程序缺頁中斷的處理時間。

2.把工作集算法融入到處理機排程中

當排程程式發現處理機使用率低下時，它将試圖從外存調入一個新作業進入記憶體，在從外存調入作業之前，必須檢查每個程序在記憶體的駐留頁面是否足夠多。如果都足夠多，此時便可以從外存調入新的作業，不會因新作業的調入而導緻缺頁率的增加；反之，如果有些程序的記憶體頁面不足，則應首先為那些缺頁率居高的作業增加新的實體塊，此時将不再調入新的作業。

3.利用“L=S”準則調節缺頁率

其中L是缺頁之間的平均時間，S是平均缺頁服務時間，即用于置換一個頁面所需的時間。如果是L遠比S大，說明很少發生缺頁，磁盤的能力尚未得到充分的利用；反之，如果是L比S小，則說明頻繁發生缺頁，缺頁的速度已超過磁盤的處理能力。隻有當L與S接近時，磁盤和處理機都可達到它們的最大使用率。理論和實踐都已證明，利用“L=S”準則，對于調節缺頁率是十分有效的。

4.選擇暫停程序

基于某種原則選擇暫停某些程序。将它們調出到磁盤上，以便騰出記憶體空間配置設定給缺頁率發生偏高的程序。

5.5 請求分段存儲管理方式

5.5.1 請求分段中的硬體支援

1.請求段表機制

除了段名(号)、段長、段在記憶體中的起始位址外，還增加了以下諸項：

1）存取方式：根據資訊的屬性對分段實施保護。如果該字段為兩位，則存取屬性是隻執行、隻讀和允許讀/寫。

2）通路字段 A：記錄該段被通路的頻繁程度。

3）修改位 M：表示該段在進入記憶體後是否已被修改過。

4）存在位 P：訓示本段是否已調入記憶體。

5）增補位：表示本段在運作過程中是否做過動态增長。

6）外存始址：訓示本段在外存中的起始位址，即起始盤塊号。

2.缺段中斷機構

每當發現運作程序所要通路的段尚未調入記憶體時，便由缺段中斷機構産生一缺段中斷信号，進入 OS 後由缺段中斷處理程式将所需的段調入記憶體。缺段中斷機構與缺頁中斷機構類似，它同樣需要在一條指令的執行期間，産生和進行中斷，以及在一條指令執行期間，可能産生多次缺段中斷。但由于分段是資訊的邏輯機關，因而不可能出現一條指令被分割在兩個分段中和一組資訊被分割在兩個分段中的情況。由于段不是定長的，這使對缺段中斷的處理要比對缺頁中斷的處理複雜。

3.位址變換機構

上圖中的段表的的起始編号是從 1 開始的。

5.5.2 分段的共享與保護

1.共享段表

為了實作分段共享，可在系統中配置一張共享段表，所有各共享段都在共享段表中占有一表項。記錄了共享段的資訊和共享

此分段的某個程序的情況。

1）共享程序計數 count。非共享段僅為一個程序所需要。而共享段是為多個程序所需要的，當某程序不再需要而釋放它時，系統并不立即回收該段所占記憶體區，而是檢查 count 是否為 0，若不是 0，則表示還有程序需要它，僅當所有共享該段的程序全不再需要它使，此時 count 為 0，才由系統回收該段所占的記憶體區。

2）存取控制字段。對于一個共享段，應給不同的程序以不同的存取權限。

3） 段号。對于一個共享段，在不同的程序中可以具有不同的短号，每個程序可用自己程序的段号去通路該共享段。

2.共享段的配置設定與回收

1）共享段的配置設定。

在為共享段配置設定記憶體時，對第一個請求使用該共享段的程序，由系統為該共享段配置設定一實體區，再把共享段調入該區，同時将該區的始址填入請求程序的段表的相應項中，還須在共享段表中增加一表項，填寫有關資料，把 count 置為 1。之後，當

又有其它程序需要調用該共享段時，由于該共享段已被調入記憶體，故此時無須再為該段配置設定記憶體，而隻需在調用程序的段表中增加一表項，填寫該共享段的實體位址；以及在共享段的段表中，填上調用程序的程序名、存取控制等，再執行 count = count+1 操作。

2）共享段的回收。

當共享此段的某程序不再需要該段時，應将該段釋放，包括撤消在該程序段表中共享

段所對應的表項，以及執行 count = count-1 操作。若結果為 0，表明此時已沒有程序在使用該段，則須由系統回收該共享段的實體記憶體，以及取消在共享段表中目前調用程序所對應的表項。否則(減 1 結果不為 0)，隻是取消調用者程序在共享段表中的有關記錄。

3.分段保護

1）越界檢查。

越界檢查時利用位址變換機構來完成的。①短号和段表長度的比較。②段内位址和段長的比較。

2）存取控制檢查。

存取控制檢查是以段為基本機關進行的。在段表的每個表項中都設定了一個“存取控制”字段，用于規定對該段的通路方式。對于共享段而言，存取控制就顯得尤為重要。

3）環保護機構。

這是一種功能較完善的保護機制。在該機制中規定：低編号的環具有高優先權。OS 核心處于 0 環内；某些重要的實用程式和作業系統服務占居中間環；而一般的應用程式則被安排在外環上。在環系統中，程式的通路和調用應遵循以下規則：

1）一個程式可以通路駐留在相同環或較低特權環中(較之編号高的環)的資料。類似于讀。

2）一個程式可以調用駐留在相同環或較高特權環中(較之編号低的環)的服務。類似于執行。