虛拟記憶體之頁面置換算法

四種頁面置換算法：

• 最佳（OPT，Optional）
• 最近最少使用（LRU，Least Recently Used）
• 先進先出（FIFO，First In First Out）
• 時鐘（Clock）

一、最佳置換算法

OPT 政策選擇置換下次通路距目前時間最長的那些頁，可以看出該算法能導緻最少的缺頁中斷，但是由于它要求作業系統必須知道将來的事件，顯然這是不可能實作的。但它仍然能作為一種标準來衡量其他算法的性能。

二、最近最少使用算法

LRU 政策置換記憶體中上次使用距目前最遠的頁。根據局部性原理，這也是最不可能通路的頁。實際上，LRU 政策的性能接近于 OPT 政策。該方法的問題在于比較難以實作。一種實作方法是給每一頁添加一個最後通路的時間戳，并且必須每次通路記憶體時，都更新這個時間戳。即使有這種方案的硬體，開銷仍然是非常大的。另外一種可選的方法是維護一個關于通路頁的棧，但開銷同樣很大。

三、先進先出算法

FIFO 政策把配置設定給程序的頁框視為一個循環緩沖區，按循環方式移動頁。它所需的隻是一個指針，這個指針在該程序的頁框中循環。是以這是一種最簡單的頁面置換政策。除了它的簡單性，這種選擇方法所隐含的邏輯是置換駐留在記憶體中最長時間的頁：一個很久以前取入記憶體的頁，到現在可能已經不會再用了。這個推斷是錯誤的，因為經常出現一部分程式或資料在整個程式的生命周期中使用頻率很高的情況，如果使用 FIFO 算法，則這些頁會被反複的換入換出，增加了系統開銷。

四、時鐘

時鐘是 LRU 的近似實作。最簡單的時鐘政策需要給每一頁框管理一個附加位，稱為使用位。當某一頁首次裝入記憶體時，則将該頁框的使用位置為 1；當該頁随後被通路到時（在通路産生缺頁中斷後），他的使用位也會被置為 1。對于頁面置換算法用于置換的候選頁框集合被視為一個循環緩沖區，并且有一個指針與之相關聯。當一頁被置換時，該指針被設定成指向緩沖區中的下一個頁框。當需要置換一頁時，作業系統掃描緩沖區，以查找使用位被置為 0 的一個頁框。每當遇到一個使用位為 1 的頁框時，作業系統就将該為重新置為 0 ；如果在這個過程開始時，緩沖區所有頁框的使用位均為 0，則選擇遇到的第一個頁框置換；如果所有頁框的使用位均為 1，則指針在緩沖區中完整地循環一周，把所有使用位都置為 0，并且停留在最初的位置上，置換該頁框中的頁。

舉例：

某個程序的執行需要通路 5 個不同的頁，運作該程式需要的頁位址的順序為：

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