一、OPT：最佳替換算法（optional replacement）
1. 算法思想
此算法是用來評價其他算法的钦听。永遠(yuǎn)不可實(shí)現(xiàn)谎倔。
算法核心是算法所淘汰的數(shù)據(jù)是以后永遠(yuǎn)不會訪問的，或者是在最長時間內(nèi)不再訪問的那條數(shù)據(jù)爽航。但是人們無法預(yù)知未來哪個頁面才會被訪問。OPT算法即為命中率最高的算法乾忱。
二讥珍、 FIFO：先進(jìn)先出算法（First-in, first-out）
1. 算法思想
該算法是最簡單的緩存淘汰算法。
隊(duì)列的末尾存放最近添加到緩存的對象窄瘟。隊(duì)列的頭部存放最早放進(jìn)緩存的對象衷佃。
當(dāng)內(nèi)存滿了的時候，淘汰最早放入緩存的對象蹄葱。
2. 算法缺陷
FIFO算法在某些情況下會出現(xiàn)當(dāng)所分配的物理內(nèi)存增大氏义，但是命中率反而更低的異常現(xiàn)象图云。這是因?yàn)闊o法判斷將要訪問哪個頁面造成的惯悠，又稱為Belady異常。僅有FIFO算法會產(chǎn)生這種異常竣况。
三克婶、 LRU：最近最久未使用算法（Least recently used）
1. 算法思想
數(shù)據(jù)結(jié)構(gòu)：鏈表
當(dāng)訪問一條數(shù)據(jù)時，
如果數(shù)據(jù)在緩存中，則將該數(shù)據(jù)移動到鏈表頭部情萤。
如果數(shù)據(jù)不在緩存中鸭蛙，則把數(shù)據(jù)插入到鏈表頭部。
如果鏈表滿了筋岛，則把鏈表尾部的數(shù)據(jù)刪除娶视，然后把該數(shù)據(jù)插入到鏈表頭部。
2. LCR-K
為了解決“緩存污染”問題睁宰。
K代表最近使用的次數(shù)肪获。
其核心思想是將“最近使用過1次”的判斷標(biāo)準(zhǔn)擴(kuò)展為“最近使用過K次”。
相比LRU柒傻，LRU-K需要多維護(hù)一個隊(duì)列贪磺，用于記錄所有緩存數(shù)據(jù)被訪問的歷史。只有當(dāng)數(shù)據(jù)的訪問次數(shù)達(dá)到K次的時候诅愚，才將數(shù)據(jù)放入緩存寒锚。當(dāng)需要淘汰數(shù)據(jù)時，LRU-K會根據(jù)LRU算法淘汰緩存鏈表尾部的數(shù)據(jù)违孝。
緩存污染：是指系統(tǒng)將不常用的數(shù)據(jù)從內(nèi)存移到緩存刹前，造成常用數(shù)據(jù)的擠出，降低了緩存效率的現(xiàn)象雌桑。
實(shí)現(xiàn)過程：
(1). 數(shù)據(jù)第一次被訪問喇喉，加入到訪問歷史列表；
(2). 如果數(shù)據(jù)在訪問歷史列表里后沒有達(dá)到K次訪問校坑，則按照一定規(guī)則（FIFO拣技，LRU）淘汰；
(3). 當(dāng)訪問歷史隊(duì)列中的數(shù)據(jù)訪問次數(shù)達(dá)到K次后耍目，將數(shù)據(jù)索引從歷史隊(duì)列刪除膏斤，將數(shù)據(jù)移到緩存隊(duì)列的頭部，緩存此數(shù)據(jù)邪驮；
(4). 緩存數(shù)據(jù)隊(duì)列中被再次訪問后莫辨，重新排序；
(5). 需要淘汰數(shù)據(jù)時毅访，淘汰緩存隊(duì)列中排在末尾的數(shù)據(jù)
即：訪問歷史可按照FIFO算法或LRU算法實(shí)現(xiàn)沮榜。緩存鏈表按LRU算法實(shí)現(xiàn)。
LRU-K具有LRU的優(yōu)點(diǎn)喻粹，同時能夠避免LRU的缺點(diǎn)蟆融，實(shí)際應(yīng)用中LRU-2是綜合各種因素后最優(yōu)的選擇，LRU-3或者更大的K值命中率會高守呜，但適應(yīng)性差型酥，需要大量的數(shù)據(jù)訪問才能將歷史訪問記錄清除掉山憨。
3. 2Q（Two queues）
類似于LRU-2。
訪問歷史隊(duì)列使用FIFO算法規(guī)則冕末。
緩存鏈表使用LRU算法規(guī)則萍歉。
四侣颂、CLOCK：時鐘算法
1. 算法思想
LRU算法的性能接近于OPT,但是實(shí)現(xiàn)起來比較困難档桃，且開銷大；FIFO算法實(shí)現(xiàn)簡單憔晒，但性能差藻肄。所以有了CLOCK算法。
數(shù)據(jù)結(jié)構(gòu)：循環(huán)鏈表
簡單的CLOCK算法是給每個緩存數(shù)據(jù)關(guān)聯(lián)一個訪問標(biāo)志位拒担。
新添加到緩存循環(huán)鏈表中的數(shù)據(jù)嘹屯，或者在循環(huán)鏈表中被訪問的數(shù)據(jù)，都把訪問標(biāo)志位設(shè)置為1从撼。
有個指針指向最早添加到循環(huán)鏈表中的數(shù)據(jù)州弟。
當(dāng)鏈表滿了，需要刪除的時候低零，從當(dāng)前指針開始婆翔，如果當(dāng)前指針指向的數(shù)據(jù)的標(biāo)志位為1，則置位0掏婶，指向下一位置啃奴。直到當(dāng)前指針指向的數(shù)據(jù)的標(biāo)志位為0，則淘汰此數(shù)據(jù)雄妥。
實(shí)現(xiàn)過程
(1). 數(shù)據(jù)第一次被訪問最蕾，加入到循環(huán)鏈表中，且將此數(shù)據(jù)的訪問標(biāo)志位設(shè)置為1老厌，指針指向加入到循環(huán)鏈表中的第一個數(shù)據(jù)瘟则；
(2). 緩存鏈表第一次達(dá)到分配內(nèi)存的最大值，此時指針仍舊指向最早加入循環(huán)鏈表中的第一個數(shù)據(jù)枝秤，所有緩存數(shù)據(jù)的標(biāo)志位為1壹粟；
(3). 新訪問的數(shù)據(jù)不在已滿的緩存循環(huán)鏈表中，判斷指針當(dāng)前指向數(shù)據(jù)的標(biāo)志位的值宿百。如果為1趁仙，則重置為0，指針指向下一個數(shù)據(jù)垦页。如果為0雀费，則淘汰此數(shù)據(jù)。（第一次循環(huán)鏈表被填滿后痊焊，所有數(shù)據(jù)的標(biāo)志位都為1盏袄，此時指針指向最早被加入到循環(huán)鏈表中的第一個數(shù)據(jù)忿峻。然后指針根據(jù)上述規(guī)則，循環(huán)一周辕羽，把所有數(shù)據(jù)的標(biāo)志位置位0逛尚，再次循環(huán)訪問到最早被加入到循環(huán)鏈表中的第一個數(shù)據(jù)，此時該數(shù)據(jù)標(biāo)志位為0刁愿，淘汰此數(shù)據(jù)）
(4). 緩存數(shù)據(jù)再次被訪問绰寞，無論此時的此緩存數(shù)據(jù)的標(biāo)志位是0還是1，都重新設(shè)置為1铣口。指針不做任何變化滤钱。
(5). 數(shù)據(jù)不在緩存的循環(huán)鏈表中，判斷指針指向的當(dāng)前數(shù)據(jù)的標(biāo)志位脑题，如果為0件缸，則淘汰此數(shù)據(jù)。如果為1叔遂，則將此數(shù)據(jù)置位0他炊，指針指向下一個數(shù)據(jù)，繼續(xù)判斷標(biāo)志位已艰。
參考鏈接：
https://www.cnblogs.com/junyuhuang/p/5805168.html
https://www.cnblogs.com/junyuhuang/p/5993612.html
http://c.biancheng.net/cpp/html/2614.html
