一、操作系統幾種主要的頁面置換算法

算法通常只是描述解決問題的一個步驟，具體用什么數據結構實現則是視情況而定。LRU“實現起來比較困難，且開銷大是因為LRU算法希望淘汰最后未使用的頁面，而CLOCK算法則放低的要求，較久未使用即可，不一定是最久的。CLOCK算法恰好可以充分使用現有的為“請求分頁存儲管理“設計的硬件機構，所以也會更加高效，而LRU則難以使用現成的硬件機構來加速算法執行。

LRU又稱最近最少使用，意為每次都淘汰最久未使用的頁面。按照LRU的思想，一種實現思路如下三點：

下面來逐一分析這三點：

名列前茅點：這塊內存空間不能太小，否則極易導致數據溢出，尤其是對于運行在server上OS來說，可能一開機就很久不關機，溢出的可能性更大。這段內存空間也不能太大，不然會造成空間浪費；

第二點：每執行一條指令必定帶來至少一次訪存，甚至更多，每次訪存都要去維護這個時間開銷無疑是很大的（CLOCK算法也要去維護一個bit，但是開銷卻小得多，原因后面再討論），因為使用數組記錄則需要線性的時間來維護，使用heap記錄則需要對數時間來維護，而訪存則是十分頻繁的，這個代價是不能接受的；值得一提的是雖然看起來heap開銷小一些，但是數據量很大的話heap相對無序array來說對緩存不友好，這也是一個問題，不過我不知道是否可以忽略；

第三點：選擇出最久未使用的頁面的開銷也很大，使用無序array記錄則需要線性的時間來查找，使用heap記錄則需要對數時間來查找；

綜合上述三點可知LRU具體實現起來確實很困難開銷也很大。那么CLOCK算法和LRU相比優勢在哪里？

未改進CLOCK算法需要維護一個bit，用來標志該頁面是否被使用過；很自然地想到同樣需要三點，即存儲，維護和查找，但是前兩點（存儲和維護）的實現和開銷相對LRU則簡單很多。

延伸閱讀：

二、全局頁面置換算法

功能：

當缺頁中斷發生，需要調入新的頁面而內存已滿時，選擇內存當中哪個物理頁面被置換。

目標：

盡可能地減少頁面的換進換出次數（既缺頁中斷的次數）。具體來說，把未來不再使用的或短期內較少使用的頁面換出，通常只能在局部性原理指導下依據過去的統計數據來進行預測。

頁面鎖定（frame locking）：

用于描述必須常駐內存的操作系統的關鍵部分或時間關鍵（time-critical）的應用程序。實現的方法是L在頁表中添加鎖定標志位（lock bit）。使其不在頁面置換算法范圍之內，也就說不會被換入換出。

通常只需要考慮頁號，因為偏移號一般不起作用。只保留頁號。基于這個list來設計各種的頁面替換算法。
通過模擬一個頁面置換的行為并且記錄產生頁缺失數的數量。一般情況下，產生的缺頁次數越少，性能就越高。