作業系統記憶體分配問答 #3

問題：頁面錯誤何時發生？解釋各種頁面置換策略/演算法。

答案：在按需分頁記憶體管理技術中，如果需要執行的頁面不在主存中，則會發生頁面錯誤。為了將按需載入的頁面載入到主存中，會在主存中搜索一個空閒頁面幀並分配。如果沒有空閒頁面幀，記憶體管理器必須透過將內容交換到輔助儲存器來釋放一個幀，從而為所需頁面騰出空間。為了交換頁面，使用了許多方案或策略。

各種頁面置換策略/演算法

1. 最佳頁面置換演算法 − 該演算法替換最長時間內不會被使用的頁面。頁面錯誤發生時，記憶體中會有一組頁面。其中一個頁面將在下一條指令中被引用。其他頁面可能要到 10、100 或甚至 1000 條指令後才會被引用。此資訊可以與 PMT（頁面對映表）中的每個頁面一起儲存。

   P#	基地址	偏移量	其他資訊
   1			10
   2			空
   3			1000
   ...
   10			100

   最佳頁面演算法簡單地刪除指令數最多的頁面，這意味著它將在最遠的將來被需要。該演算法很久以前就被提出，並且難以實現，因為它需要對程式行為的未來知識。但是，可以透過使用在第一次執行時收集的頁面引用資訊，在第二次執行時實現最佳頁面替換。

2. NRU（最近未使用）頁面置換演算法 - 該演算法要求每個頁面有兩個額外的狀態位 'R' 和 'M'，分別稱為引用位和修改位。每當引用頁面時，引用位 (R) 會自動設定為 1。每當修改頁面時，修改位 (M) 會設定為 1。這些位儲存在 PMT 中，並在每次記憶體引用時更新。當發生頁面錯誤時，記憶體管理器會檢查所有頁面，並根據 R 和 M 位將它們劃分為 4 類。

   • 類 1：(0,0) − 最近未使用且未修改 - 最佳替換頁面。

   • 類 2：(0,1) − 最近未使用但已修改 - 替換前需要將頁面寫出。

   • 類 3：(1,0) − 最近使用但乾淨 - 可能很快會被再次使用。

   • 類 4：(1,1) − 最近使用且已修改 - 可能很快會被再次使用，並且替換前需要寫出。

   該演算法從編號最低的非空類中隨機刪除一個頁面。

   優點

   • 易於理解。

   • 易於實現。

3. FIFO（先進先出）頁面置換演算法 − 這是最簡單的頁面置換演算法之一。選擇並替換記憶體中停留時間最長的最舊頁面。該演算法藉助 FIFO 佇列來儲存記憶體中的頁面。頁面插入到佇列的後端，並在佇列的前端替換。

   

   在圖中，引用字串為 5、4、3、2、5、4、6、5、4、3、2、6，並且有 3 個空閒幀。前 3 次引用（5、4、3）導致頁面錯誤，並被帶入空閒幀。下一次引用（2）替換頁面 5，因為頁面 5 是最先載入的，依此類推。在 7 次頁面錯誤後，下一次引用是 5，而 5 已經在記憶體中，因此這次引用沒有頁面錯誤。類似地，對於下一次引用 4 也是如此。+ 標記表示頁面的傳入，而圓圈表示選擇的要刪除的頁面。

   優點

   • FIFO 易於理解。

   • 易於實現。

   缺點

   • 效能並不總是很好。它可能會替換一個活動頁面以引入一個新頁面，從而可能立即導致該頁面的頁面錯誤。

   • 另一個意想不到的副作用是 FIFO 異常或 Belady 異常。這種異常表明，隨著分配的頁面幀數的增加，頁面錯誤率可能會增加。

   例如，下圖顯示了相同的頁面跟蹤，但記憶體更大。這裡頁面幀數為 4。

   

   這裡的頁面錯誤是 10 而不是 9。

4. LRU（最近最少使用）演算法 − 最近最少使用 (LRU) 演算法替換最長時間未使用過的頁面。它基於這樣的觀察結果：長時間未使用過的頁面可能在最長時間內保持未使用，並且應該被替換。

   

   最初，3 個頁面幀是空的。前 3 次引用（7、0、1）導致頁面錯誤，並被帶入這些空閒幀。下一次引用（2）替換頁面 7。由於下一次頁面引用（0）已經在記憶體中，因此沒有頁面錯誤。現在，對於下一次引用（3），LRU 替換髮現，在記憶體中的三個幀中，頁面 1 最近最少使用，因此被替換。依此類推。

   優點

   • LRU 頁面置換演算法非常有效。

   • 它不受 Belady 異常的影響。

   缺點

   • 它的實現並不容易。

   • 它的實現可能需要大量的硬體輔助。