Second Change

傳統(tǒng)的FIFO和LRU算法都沒有使用訪問次數(shù)這個信息畦木，使得對于空間局限性較弱的場景效率很低濒憋，Second Change算法對FIFO算法做了略微的修改顶吮，在一定程度上可以改善這種場景下的效率聪富。該算法依然使用隊(duì)列的方式訪問斧账，同時為隊(duì)列的每一項(xiàng)設(shè)置一個參考位：

second change

Hit：將reference bit設(shè)置為1

Miss：從Front端查找可以替換的entry

如果Reference bit 為1：清除該位埋市，將數(shù)據(jù)放入Rear冠桃，繼續(xù)往后查找，到達(dá)Rear后依然沒有合適的替換位置道宅，回到Front端繼續(xù)查找食听。

如果為0，將該entry替換污茵，并將數(shù)據(jù)放入Rear樱报，清除Reference bit

Clock

Clock算法是針對LRU遍歷鏈表等開銷較大的一種改進(jìn)，將Second Change使用的列表改成環(huán)形鏈表泞当，屬于FIFO的復(fù)雜度迹蛤。Clock 不需要從Front移除數(shù)據(jù)到Rear端，使用Head指針替代了Front和Rear指針襟士。

替換方式和Second Change相似：

Hit：將reference bit設(shè)置為1

Miss：從Head開始查找Reference bit為0 的entry

如果Reference bit為1盗飒，清除該位，指針前移敌蜂，直到找到為0的entry為止箩兽。

如果Reference bit 為0， 將數(shù)據(jù)放入該entry章喉，并將Reference bit置1。

clock

LIRS

LIRS算法中使用了IRR（Inter-Reference Recency）和Recency兩個參數(shù)

IRR：一個頁面最近兩次的訪問間隔

Recency：頁面上次訪問至今訪問了多少其他頁身坐。

IRR和Recency參數(shù)不包含重復(fù)的頁數(shù)秸脱，因?yàn)轫撁娴闹貜?fù)計算對當(dāng)前頁面的優(yōu)先權(quán)沒有太多影響。如下圖所示：

Recency

上圖中部蛇，頁面1的最近一次訪問間隔中摊唇，有3個不重復(fù)的頁面：2，3涯鲁，4巷查，因此IRR為3有序，最近一次訪問到當(dāng)前時間有兩個不重復(fù)的頁面5和6，因此Recency 為2

在下表中有一個更復(fù)雜的訪問序列：

訪問順序?yàn)閧A岛请，D旭寿，B，C崇败，B盅称，A，D后室，A缩膝，E}，表格的最右邊列出了第10拍時IRR和Recency的值岸霹。

以頁面D為例疾层，最后一次訪問的時間為第七拍，Recency為2贡避；第2~7拍中有3個不同的頁面被訪問過痛黎，因此IRR為3。頁面C和E的IRR為infinite贸桶，表示在指定的時間間隔內(nèi)舅逸，沒有對該頁面重復(fù)訪問。

LIRS算法首先替換IRR最大的頁面皇筛，其中infinite的值最大琉历，當(dāng)IRR相同時，替換Recency最大的頁面水醋。IRR在一定程度上反應(yīng)了頁面的訪問頻度旗笔，LIRS傾向于認(rèn)為：一個頁面的IRR越大，將來的IRR會變得更大拄踪。Recency參數(shù)相當(dāng)于LRU蝇恶，替換時IRR優(yōu)先于Recency，這就降低了最后一次訪問數(shù)據(jù)的優(yōu)先級惶桐，因?yàn)橛行?shù)據(jù)雖然最近訪問卻不一定常用撮弧，可能訪問過一次之后很久都不再使用，如果Recency優(yōu)于IRR姚糊，這些只使用了一次數(shù)據(jù)有可能會停留相當(dāng)長時間贿衍。

對于一個隨機(jī)訪問的隊(duì)列，要在短時間內(nèi)精確計算出IRR和Recency的值并不容易救恨，實(shí)際上很多情況下并不需要獲取這兩個參數(shù)的精確值贸辈，有時候知道一個參數(shù)就可以了，比如在獲取IRR時肠槽，只要有一個Infinite擎淤，就不需要比較其他結(jié)果奢啥，如果有多個Infinite，比如C和D嘴拢，需要進(jìn)一步比較Recency桩盲。

LIRS的實(shí)現(xiàn)過程沒有精算計算IRR和Recency兩個參數(shù)，而是給出基于LIRS stack的近似值炊汤，根據(jù)IRR的不同正驻，將頁面分為LIR（Low IRR）和HIR（High IRR）兩類，并盡量使得LIR頁面更多地再Cache中命中抢腐，當(dāng)發(fā)生沖突時姑曙，優(yōu)先替換HIR中的頁面。

LIRS Stack中包含一個LRU Stack迈倍，Stack的大小固定伤靠，由Cache決定，存放cache中有效的頁面啼染。淘汰頁面時使用LRU算法宴合。算法使用了兩個隊(duì)列：

LIRS Stack S:保存參數(shù)Recency不超過其最大值(Rmax)的LIR和HIR，其中HIR可能不在cache中迹鹅，但依然使用LRU算法卦洽，其長度可變，用于判斷IRR的大小

LIRS Stack Q:維護(hù)cache中的HIR頁面斜棚，以加快其索引速度阀蒂，在需要釋放頁面時，首先淘汰這類弟蚀。淘汰操作會引起一系列連鎖反應(yīng)蚤霞，如下圖所示：

LIRS

最開始的時候，Stack S中存放著頁面{7, 5, 3, 4, 8}义钉，Q中存放這{7昧绣， 5}，Stack S中的頁面都在Cache中捶闸，其中{7, 5}為HIR夜畴， {3, 4, 8}為LIR頁面。Cache的大小為5删壮，其中兩個存放HIR斩启， 3個存放LIR。

Case 1 訪問頁面9：cache miss（不在Stack S中）的過程：

頁面9不在隊(duì)列中醉锅，Cache miss，需要淘汰一個頁面：將隊(duì)列Q前端（front側(cè)）的頁面5 淘汰

頁面5是之前LIR且在Cache中发绢，被淘汰后繼續(xù)留在Stack S硬耍，狀態(tài)依舊是LIR

頁面9壓入Stack S垄琐，狀態(tài)設(shè)置為LIR，棧長度+1

Case 2 訪問頁面5：cache miss（在stack S中）的過程：

新的頁面要進(jìn)入內(nèi)存经柴，先釋放隊(duì)列Q中的一個頁面：將隊(duì)列Q中的頁面7 淘汰

隊(duì)列S中頁面7的狀態(tài)修改為不在cache中

隊(duì)列S中的頁面8落入到Q中狸窘，狀態(tài)從LIR轉(zhuǎn)換成HIR，Stack S長度-1

頁面8仍然在cache中坯认，重新壓棧

頁面5沒有在Cache中翻擒，但在隊(duì)列S中命中，需要將其移出牛哺，重新入棧

頁面5的狀態(tài)修改為在Cache中命中

詳細(xì)的算法細(xì)節(jié)參考1.

Clock-Pro

Clock-Pro是LIRS思想在Clock算法上的體現(xiàn)陋气，Clock-Pro算法實(shí)現(xiàn)開銷更小，適用于操作系統(tǒng)的虛擬內(nèi)存管理引润，Linux和BSD都是用了該算法巩趁；

LIRS適用于I/O存儲領(lǐng)域，比如MySQL和Apache Derby淳附，LIRS較完美的解決了弱空間局部性的問題议慰。

參考1. Song Jiang and Xiaodong Zhang [Jun 2002]. LIRS: An efficient low inter-reference recency set replacement policy to improve buffer cache performance. In Proc. ACM SIGMETRICS Conf., 2002