為了達(dá)到降低隨后發(fā)生缺頁(yè)中斷的次數(shù)或者概率，人們?cè)O(shè)計(jì)出了各種各樣的頁(yè)面替換算法，這些算法大致可分為公平算法和非公平算法。

• 公平算法：隨機(jī)算法、FIFO算法、時(shí)鐘算法。

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

隨機(jī)算法

這種就是簡(jiǎn)單的隨機(jī)選擇進(jìn)行頁(yè)替換，無(wú)需多言，簡(jiǎn)單粗暴。

FIFO算法

這種就是先來(lái)后到，可以使用鏈表記錄頁(yè)分配的先后順序，淘汰時(shí)按照順序淘汰即可，也是非常的簡(jiǎn)單粗暴。

時(shí)鐘算法

內(nèi)存使用中的頁(yè)按照時(shí)鐘的邏輯形狀，淘汰頁(yè)時(shí)按照時(shí)鐘順序檢查，如果頁(yè)未訪問(wèn)到（每個(gè)頁(yè)對(duì)應(yīng)一個(gè)訪問(wèn)標(biāo)識(shí)，未訪問(wèn)到時(shí)設(shè)置為0），則直接替換；如果訪問(wèn)過(guò)則設(shè)置訪問(wèn)位為0，方便下次淘汰。時(shí)鐘邏輯圖如下：

NRU算法

最近未使用算法，將最近一段時(shí)間沒(méi)有訪問(wèn)過(guò)的頁(yè)面進(jìn)行替換，作出這種選擇是基于程序訪問(wèn)的時(shí)空局域性。依據(jù)時(shí)空局域性，一個(gè)最近沒(méi)有訪問(wèn)過(guò)的頁(yè)面，在隨后的時(shí)間內(nèi)也不太可能被訪問(wèn)，而NRU的實(shí)現(xiàn)就是利用頁(yè)面的訪問(wèn)和修改位來(lái)實(shí)現(xiàn)的。

時(shí)空局限性在很多程序設(shè)計(jì)思想中有體現(xiàn)，比如rocketmq中page cache緩存最近讀寫的消息數(shù)據(jù)等。

LRU算法

LRU是對(duì)NRU算法的改進(jìn)，其考慮的是最近使用的頻率而不是最近是否使用過(guò)。LRU算法的實(shí)現(xiàn)必須以某種方式記錄每個(gè)頁(yè)面被訪問(wèn)的次數(shù)，簡(jiǎn)單的辦法就是在頁(yè)表的記錄項(xiàng)里面增加一個(gè)計(jì)數(shù)域，一個(gè)頁(yè)面被訪問(wèn)一次，則這個(gè)計(jì)數(shù)器的值加1；或者使用鏈表結(jié)構(gòu)，每訪問(wèn)一次就將該頁(yè)移動(dòng)到鏈表頭。

工作集算法

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

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

工作集算法就是操作系統(tǒng)局限性的一種體現(xiàn)，一段時(shí)間內(nèi)，CPU操作的數(shù)據(jù)大都集中在少量數(shù)據(jù)上，因此可以應(yīng)用工作集算法來(lái)進(jìn)行頁(yè)的替換操作。

Redis中的內(nèi)存淘汰

以上分析了操作系統(tǒng)中的頁(yè)面更換算法，更廣義來(lái)講，頁(yè)面更換就是內(nèi)存淘汰，操作系統(tǒng)的頁(yè)面更換算法可能不能直接讓開(kāi)發(fā)者感同身受，畢竟這是OS層面的東東。下面就以實(shí)際開(kāi)發(fā)中常用到的Redis為例，來(lái)分析下Redis內(nèi)存淘汰策略，對(duì)比加深對(duì)內(nèi)存淘汰的理解。

Redis的內(nèi)存淘汰策略是指在Redis的用于緩存的內(nèi)存不足時(shí)，怎么處理需要新寫入且需要申請(qǐng)額外空間的數(shù)據(jù)。目前Redis的內(nèi)存淘汰策略有如下幾種：

• noeviction：當(dāng)內(nèi)存不足以容納新寫入數(shù)據(jù)時(shí)，新寫入操作會(huì)報(bào)錯(cuò)。

• allkeys-lru：當(dāng)內(nèi)存不足以容納新寫入數(shù)據(jù)時(shí)，在鍵空間中，移除最近最少使用的key。

• allkeys-random：當(dāng)內(nèi)存不足以容納新寫入數(shù)據(jù)時(shí)，在鍵空間中，隨機(jī)移除某個(gè)key。

• volatile-lru：當(dāng)內(nèi)存不足以容納新寫入數(shù)據(jù)時(shí)，在設(shè)置了過(guò)期時(shí)間的鍵空間中，移除最近最少使用的key。

• volatile-random：當(dāng)內(nèi)存不足以容納新寫入數(shù)據(jù)時(shí)，在設(shè)置了過(guò)期時(shí)間的鍵空間中，隨機(jī)移除某個(gè)key。

• volatile-ttl：當(dāng)內(nèi)存不足以容納新寫入數(shù)據(jù)時(shí)，在設(shè)置了過(guò)期時(shí)間的鍵空間中，有更早過(guò)期時(shí)間的key優(yōu)先移除。

對(duì)于LRU（Least Recent Used），淘汰掉最不經(jīng)常使用的，LRU可以通過(guò)hashMap + 雙向鏈表來(lái)實(shí)現(xiàn)，如果Redis也基于hashMap + 雙向鏈表實(shí)現(xiàn)，顯然要對(duì)目前的數(shù)據(jù)結(jié)構(gòu)做較大改動(dòng)，為了追求空間的利用率，Redis采用權(quán)衡的實(shí)現(xiàn)方案：Redis會(huì)基于server.maxmemory_samples配置選取固定數(shù)目的key，然后比較它們的lru訪問(wèn)時(shí)間，然后淘汰最近最久沒(méi)有訪問(wèn)的key，maxmemory_samples的值越大，Redis的近似LRU算法就越接近于嚴(yán)格LRU算法，但是相應(yīng)消耗也變高，對(duì)性能有一定影響，樣本值默認(rèn)為5。

從Redis的內(nèi)存淘汰實(shí)現(xiàn)方案來(lái)看，雖然遵循了LRU思想但不完全照搬，根據(jù)實(shí)際應(yīng)用場(chǎng)景進(jìn)行trade-off。