頁面置換演算法及其優缺點詳解

本節，討論幾種頁面置換演算法。為此，假設有 3 個幀並且參照串為：

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

FIFO頁面置換

FIFO 演算法是最簡單的頁面置換演算法。FIFO 頁面置換演算法為每個頁面記錄了調到記憶體的時間，當必須置換頁面時會選擇最舊的頁面。

注意，並不需要記錄調入頁面的確切時間，可以建立一個 FIFO 佇列，來管理所有的記憶體頁面。置換的是佇列的首個頁面。當需要調入頁面到記憶體時，就將它加到佇列的尾部。

對於樣例參照串，3 個幀開始為空。首次的 3 個參照（7，0，1）會引起缺頁錯誤，並被調到這些空幀。之後將調入這些空閒幀。

下一個參照（2）置換 7，這是因為頁面 7 最先調入。由於 0 是下一個參照並且已在記憶體中，所以這個參照不會有缺頁錯誤。

對 3 的首次參照導致頁面 0 被替代，因為它現在是佇列的第一個。因為這個置換，下一個對 0 的參照將有缺頁錯誤，然後頁面1被頁面0置換。該進程按圖 1 所示方式繼續進行。每當有缺頁錯誤時，圖 1 顯示了哪些頁面在這三個幀中。總共有 15 次缺頁錯誤。

---