2020年秋招最新作業系統之存儲管理面試知識點集錦（下）

三、虛拟頁式存儲中軟體相關政策

3.1 駐留集

• 所謂駐留集，是指在某段時間間隔内，程序要通路的頁面集合
• 駐留集大小：給每個程序配置設定多少頁框？

• 固定配置設定政策

  程序建立時确定。可以根據程序類型（互動、批處理、應用類）或者基于程式員或系統管理者的需要來确定

• 可變配置設定政策

  根據缺頁率評估局部性表現

  缺頁率高–>增加頁框數

  缺頁率低–>減少頁框數

  系統開銷

3.2 置換問題

• 置換範圍

計劃置換頁面的集合是局限在産生缺頁中斷的程序，還是所有程序的頁框？

置換政策

在計劃置換的頁框集合中，選擇換出哪一個頁框？其目标是置換最近最不可能通路的頁。

根據局部性原理，最近的通路曆史和最近将要通路的模式間存線上慣性，是以，大多數政策都基于過去的行為來預測将來的行為。**注意：**置換政策設計得越精緻、越複雜，實作的軟硬體開銷就越大。當然有些被鎖定的頁框是不能被置換的。

3.3 頁框鎖定

為什麼要鎖定頁面？

• 采用虛拟存儲技術後，相關的開銷使得程序的運作時間變得不确定
• 給每一頁框增加一個鎖定位
• 通過設定相應的鎖定位不讓作業系統将程序使用的頁面換出記憶體，避免産生由交換過程帶來的不确定的延遲

• 例如：作業系統核心代碼、關鍵資料結構、

  I/O

  緩沖區。特别是正在

  I/O

  的記憶體頁面。

  Windows

  中的

  VirtualLock

  和

  VirtualUnLock

  函數。

3.4 清除政策

• 清除：從程序的駐留集中收回頁框
• 虛拟頁式系統工作的最佳狀态：發生缺頁異常時，系統中有大量的空閑頁框。
• 結論：在系統中儲存一定數目的空閑頁框供給比使用所有記憶體并在需要時搜尋一個頁框有更好的性能。是以一般清除的政策如下：

*   設計一個分頁守護程序，多數時間處于睡眠狀态，可定期喚醒以檢查記憶體的裝填      

• 如果空閑頁框過少，分頁守護程序通過預定的頁面置換算法選擇頁面換出記憶體
• 如果頁面裝入記憶體後被修改過，則将它們寫回磁盤分頁守護程序可保證所有的空閑頁框是“幹淨”的。
• 當程序需要使用一個已置換出的頁框時，如果該頁框還沒有被新的内容覆寫，将它從空閑頁框集合中移出即可恢複該頁面。就是說當程序還需要使用某個頁框，同時這個頁框雖然被移出了，但是内容還沒有被覆寫，則我們隻需要将其從空閑頁框集合中移出即可恢複頁面。于是可以利用此技術解決已經回收的頁框再利用的問題。注意：所有的讨論都是在程序沒有結束的情況下進行的。如果程序結束了，則所有的頁框都會還給系統。這種技術叫頁緩沖技術：

*   不丢棄置換出的頁，将它們放入兩個表之一：如果未被修改，則放到空閑頁連結清單中，如果修改了，則放到修改頁連結清單中。      

• • 被修改的頁定期寫回磁盤（不是一次隻寫一個，大大減少

    I/O

    操作的數量，進而減少了磁盤通路的時間）
  • 被置換的頁仍然保留在記憶體中，一旦程序又要通路該頁，可以迅速将它加入該程序的駐留集合（代價很小）

3.5 頁面置換算法(頁面淘汰算法)

最佳算法–>先進先出–>第二次機會–>時鐘算法–>最近未使用–>最近最少使用–>最不經常使用–>老化算法–>工作集–>工作集時鐘

3.5.1 最佳置換算法（OPT）

• 設計思想
• 置換以後不再需要的或最遠的将來才會用到的頁面

• 實作

  基于程序的走向來實作，更多的是作為一種标準來衡量其他算法的性能。

3.5.2 先進先出算法（FIFO）(重點)

• 選擇在記憶體中駐留時間最長的頁并置換它
• 實作：頁面連結清單法

3.5.3 第二次機會算法（SCR）

在先進先出算法的基礎上進行該機而來的，此算法按照先進先出算法選擇某一頁面，檢查其通路位

R

，如果為

，則置換該頁；如果為

1

，則給第二次機會，并将通路位置零，并将其從鍊頭取下放到鍊尾。

3.5.4 時鐘算法（CLOCK）

在第二次機會算法中當給某個頁面第二次機會的時候，将其通路位置零，然後将其挂到鍊尾，這都是需要開銷的，于是我們改進為時鐘算法。

**說明：**其實就是将之前的連結清單改為了環形連結清單，當給某個頁面第二次機會的時候不需要将其取下然後挂到鍊尾，隻需要移動一下指針即可，這樣可以降低開銷。

3.5.5 最近未使用算法（NRU）

• 選擇在最近一段時間内未使用過的一頁并置換
• 實作：置換頁表表象的兩位，通路位

  R

  ，修改位

  M

  。硬體會設定這些位，如果硬體沒有這些位，則可用軟體模拟。
• 程序啟動時，

  R、M

  位置零，

  R

  位被定期清零。
• 發生缺頁中斷時，作業系統檢查

  R、M

  ：

*   第一類：無通路，無修改（`00`）      

• • 第二類：無通路，有修改（

    01

    ）
  • 第三類：有通路，無修改（

    10

  • 第四類：有通路，有修改（

    11

• 算法思想

  随機從編号最小的非空類中選擇一頁置換出去。

• 時鐘算法的實作

對此算法有一個時鐘算法的實作

1、從指針的目前位置開始，掃描頁框緩沖區，選擇遇到的第一個頁框（

r=0，m=0

）用于置換（本掃描過程中，對使用位不做任何修改）

2、如果第一步失敗，則重新掃描，選擇第一個（r=0；m=1）的頁框（本次掃描工程中，對每個跳過的頁框，将其使用位置為零）

3、如果第二部失敗，指針将回到它的最初位置，并且集合中的所有頁框的使用位均為零。重複第一步，并且，如果有必要，重複第二步，這樣将可以找到置換的頁框。

3.5.6 最近最少使用算法（LRU）(重點)

選擇最後一次通路時間距離目前時間最長的一頁并置換，即置換未使用時間最長的一頁

• 性能接近最佳頁面置換算法
• 實作：時間戳或維護一個通路頁的棧，導緻開銷較大。下面看一種硬體實作：

• 

• **說明：**通路第0頁時先将頁的第0行置為1，然後将第0列置為0，

以此類推，在通路完之後将行編号最小的那一頁置換出去

我們看到j中最小的是第1行，于是将第1頁置換出去。當然這裡隻有四頁。

3.5.7 最不經常使用算法（NFU）

即

Not frequently Used

，選擇通路次數最少的頁面置換

• 一開始提出此算法是

  LRU

  （最近最少使用算法）的一種軟體解決方案，但是實際上差距有點大。

*   軟體計數器，一頁一個，初值為零      

• • 每次時鐘中斷時，計數器加

    R

• • • 發生缺頁中斷時，選擇計數器值最小的一頁置換。

3.5.8 老化算法（AGING）

• 改進（模拟

  LRU

  ）：計數器在加R前先右移一位，

  R

  位加到計數器的最左端。

• 

• 這樣如果

  R

  值為零，則計數器沒有影響，如果值為

  1

  ，則會變得很大，于是如果一個頁面長久不被通路，則計數器值就會越來越小。最後選擇值最小的置換出去。

3.5.9 頁面置換算法的應用

例子：

• 系統給某程序配置設定了三個頁框（采用固定配置設定政策），初始為空
• 程序執行時，頁面通路順序為：

  2 3 2 1 5 2 4 5 3 2 5 2

要求：

計算應用

FIFO、LRU、OPT

算法時的缺頁次數

應用

FIFO、LRU

頁面置換算法

可以看到

FIFO

發生六次缺頁異常，而

LRU

發生四次缺頁異常。

應用OPT頁面置換算法

發生三次缺頁異常。

3.5.10 BELADY現象

例子：系統給某程序配置設定

m

個頁框，初始為空頁面通路順序為

1 2 3 4 1 2 5 1 2 3 4 5

，采用

FIFO

算法，計算當

m=3

m=4

時的缺頁中斷次數。

結論：m=3時，缺頁中斷九次；m=4時，缺頁中斷十次。注意：FIFO頁面置換算法會産生異常現象（Belady現象），即：當配置設定給程序的實體頁面數增加時，缺頁次數反而增加。

3.5.11 頁面緩沖算法(PBA)(重點)

該算法采用了可變配置設定和局部置換方式，置換算法則采用FIFO。

該算法規定将一個被淘汰的頁放入兩個連結清單中的一個，若頁面未被修改，直接放入空閑連結清單末尾，否則放入已修改頁面連結清單末尾。

這種方式使得已修改和未修改的頁面都仍然留在記憶體中，當程序以後再次通路這些頁面時，隻需花較小的開銷，使這些頁面又傳回到該程序的駐留集中。

當被修改頁面達到一定數量時，才一次性地将他們寫回到外存，這樣就顯著地減少了外存的I/O次數

假設采取FIFO固定配置設定局部置換，每次缺頁都要淘汰該程序最早裝入記憶體的頁面，而這裡采用可變配置設定局部置換，即配置設定程序一個空白塊，将原本應該淘汰的最早裝入的頁面挂在兩個隊列之一，直到沒有空白塊或修改頁面達到上限才啟動磁盤寫回外存

3.6 頁面置換算法2：工作集算法

3.6.1 影響缺頁次數的因素

• 頁面置換算法的不同
• 頁面本身的大小
• 程式的編制方法
• 配置設定給程序的頁框數量
• 缺頁越多，系統的性能越差，這稱為颠簸（抖動）：虛存中，頁面在記憶體與磁盤之間頻繁排程，使得排程頁面所需的時間比程序實際運作的時間還多，這樣導緻系統效率急劇下降，這種現象稱為颠簸或抖動。

3.6.2 頁面尺寸問題

• 确定頁面大小對分頁的硬體設計非常重要，而對作業系統是個可選的參數

• 要考慮的因素

  内部碎片

  頁表長度

  輔存的實體特性

• Intel 80x86/Pentium: 4096

  或

  4M

• 多種頁面尺寸：為了有效使用

  TLB

  帶來靈活性，但給作業系統帶來複雜性。

3.6.3 程式編制方法對缺頁次數的影響

配置設定了一個頁框，頁面大小為

128

個整數，矩陣

A(128 x 128)

按行存放。

可以看到左邊是按列指派，右邊是按行指派。按列編制就是首先讀入第一頁（一行，因為矩陣是按行存放的），然後給第0個位置指派，每次讀入一行，直到将第0列指派完，讀完之後再給第1列指派，這樣會産生128*128次缺頁異常；而按行指派，第一次讀入一頁，給第0行的所有元素指派，這樣會産生128次缺頁異常。于是可以看到程式的編制方法對缺頁次數是有很大影響的。

3.6.4 配置設定給程序的頁框數與缺頁率的關系

**說明：**可以看到頁框數越多那麼缺頁率越低，但是我們不可能給出所有的頁框，于是需要找到一個平衡點

W

，超過這個點之後頁框數的增加對缺頁率的降低有限，這也是工作集算法的出發點。

3.7 工作集模型

• 基本思想
• 根據程式的局部性原理，一般情況下，程序在一段時間内總是集中通路一些頁面，這些頁面稱為活躍頁面，如果配置設定給一個程序的實體頁面數太少了，使得該程序所需的活躍頁面不能全部裝入記憶體，則程序在運作過程中将頻繁發生中斷。

如果能為程序提供與活躍頁面數相等的實體頁面數，則可減少缺頁中斷次數，這是由Denning提出的。

工作集：一個程序目前正在使用的頁框集合

例子

3.8 工作集算法

• 基本思路

  找出一個不在工作集的頁面并置換它

*   每個頁表項中有一個字段：記錄該頁面最後一次被通路的時間      

設定一個時間值T

判斷

根據一個頁面的通路時間是否落在“目前時間 - T”之前或之中決定其在工作集之外還是之内。

實作：掃描所有頁表項，執行操作

1、如果一個頁面的R位是1，則将該頁面的最後一次通路時間設為目前時間，将R位清零

2、如果一個頁面的R位為0，則檢查該頁面的通路時間是否在“目前時間 - T”之前，如果是，則該頁面是需要被置換的頁面；否則，記錄目前所有被掃描過頁面的最後通路時間裡面最小值。掃描下一個頁面并重複上述操作。

四、其他與存儲管理相關技術

4.1 記憶體映射檔案

• 程序通過一個系統調用（mmap）将一個檔案（或部分）映射到其虛拟位址空間的一部分，通路這個檔案就像通路記憶體中的一個大數組，而不是對檔案進行讀寫

在多數實作中，在映射共享的頁面時不會實際讀入頁面的内容，而是在通路頁面時，頁面才會被每次一頁的讀入，磁盤檔案則被當作後備存儲。

當程序退出或顯式地解除檔案映射時，所有被修改頁面會寫回檔案

4.2 支援寫時複制技術

**說明：**如圖，兩個程序共享同一塊實體記憶體，每個頁面都被标志成了寫時複制。注意：共享的實體記憶體中每個頁面都是隻讀的。如果每個程序想改變某個頁面時，就會與隻讀标記沖突，而系統在檢測出頁面是寫時複制的，則會在記憶體中複制一個頁面，然後進行寫操作。新複制的頁面對執行寫操作的程序是私有的，對其他共享寫時複制頁面的程序是不可見的。