為了達到降低隨后發生缺頁中斷的次數或者概率，人們設計出了各種各樣的頁面替換算法，這些算法大致可分為公平算法和非公平算法。

• 公平算法：隨機算法、FIFO算法、時鐘算法。

• 非公平算法：NRU算法、LRU算法、工作集算法。

隨機算法

這種就是簡單的隨機選擇進行頁替換，無需多言，簡單粗暴。

FIFO算法

這種就是先來后到，可以使用鏈表記錄頁分配的先后順序，淘汰時按照順序淘汰即可，也是非常的簡單粗暴。

時鐘算法

內存使用中的頁按照時鐘的邏輯形狀，淘汰頁時按照時鐘順序檢查，如果頁未訪問到（每個頁對應一個訪問標識，未訪問到時設置為0），則直接替換；如果訪問過則設置訪問位為0，方便下次淘汰。時鐘邏輯圖如下：

NRU算法

最近未使用算法，將最近一段時間沒有訪問過的頁面進行替換，作出這種選擇是基于程序訪問的時空局域性。依據時空局域性，一個最近沒有訪問過的頁面，在隨后的時間內也不太可能被訪問，而NRU的實現就是利用頁面的訪問和修改位來實現的。

時空局限性在很多程序設計思想中有體現，比如rocketmq中page cache緩存最近讀寫的消息數據等。

LRU算法

LRU是對NRU算法的改進，其考慮的是最近使用的頻率而不是最近是否使用過。LRU算法的實現必須以某種方式記錄每個頁面被訪問的次數，簡單的辦法就是在頁表的記錄項里面增加一個計數域，一個頁面被訪問一次，則這個計數器的值加1；或者使用鏈表結構，每訪問一次就將該頁移動到鏈表頭。

工作集算法

考慮到LRU算法實現，其需要對每個頁面保持某種記錄，并在每次頁面訪問時或周期性對這些記錄更新，造成時間空間成本高。工作集概念來源于程序訪問的時空局域性，在一段時間內，程序訪問的頁面將局限在一組頁面集合上。

例如，最近K次訪問均發生在某m個頁面上，那么m就是參數為k時的工作集。用w(k, t)表示時間t時k次訪問所涉及的頁面數量。顯然隨著k的增長，w(k, t)的值將隨之增長，在k增長至某個數值后，w(k, t)值增長將及其緩慢甚至接近停滯，并維持一段時間。

工作集算法就是操作系統局限性的一種體現，一段時間內，CPU操作的數據大都集中在少量數據上，因此可以應用工作集算法來進行頁的替換操作。

Redis中的內存淘汰

以上分析了操作系統中的頁面更換算法，更廣義來講，頁面更換就是內存淘汰，操作系統的頁面更換算法可能不能直接讓開發者感同身受，畢竟這是OS層面的東東。下面就以實際開發中常用到的Redis為例，來分析下Redis內存淘汰策略，對比加深對內存淘汰的理解。

Redis的內存淘汰策略是指在Redis的用于緩存的內存不足時，怎么處理需要新寫入且需要申請額外空間的數據。目前Redis的內存淘汰策略有如下幾種：

• noeviction：當內存不足以容納新寫入數據時，新寫入操作會報錯。

• allkeys-lru：當內存不足以容納新寫入數據時，在鍵空間中，移除最近最少使用的key。

• allkeys-random：當內存不足以容納新寫入數據時，在鍵空間中，隨機移除某個key。

• volatile-lru：當內存不足以容納新寫入數據時，在設置了過期時間的鍵空間中，移除最近最少使用的key。

• volatile-random：當內存不足以容納新寫入數據時，在設置了過期時間的鍵空間中，隨機移除某個key。

• volatile-ttl：當內存不足以容納新寫入數據時，在設置了過期時間的鍵空間中，有更早過期時間的key優先移除。

對于LRU（Least Recent Used），淘汰掉最不經常使用的，LRU可以通過hashMap + 雙向鏈表來實現，如果Redis也基于hashMap + 雙向鏈表實現，顯然要對目前的數據結構做較大改動，為了追求空間的利用率，Redis采用權衡的實現方案：Redis會基于server.maxmemory_samples配置選取固定數目的key，然后比較它們的lru訪問時間，然后淘汰最近最久沒有訪問的key，maxmemory_samples的值越大，Redis的近似LRU算法就越接近于嚴格LRU算法，但是相應消耗也變高，對性能有一定影響，樣本值默認為5。

從Redis的內存淘汰實現方案來看，雖然遵循了LRU思想但不完全照搬，根據實際應用場景進行trade-off。