Cache miss不僅意味著需要從主存獲取數(shù)據(jù)，而且還需要將cache的某一個(gè)block替換出去。常用的算法包括FIFO、LRU、RR、Random等
FIFO: First in First out
如上圖，不同的色塊代表不同的主存數(shù)據(jù)，按既定的順序被load到cache中，位于cache中的特定的位置，當(dāng)需要被替換出去時(shí)，他們也按原來(lái)的順序依次被替換出去。
Round Robin
和FIFO相比，RR算法將cache劃分成若干個(gè)單元，新數(shù)據(jù)進(jìn)來(lái)時(shí)，根據(jù)cache單元的位置為順序，依次將原有數(shù)據(jù)替換，從結(jié)果看，數(shù)據(jù)被替換出cache 的順序和進(jìn)入時(shí)的順序沒(méi)有必然關(guān)系。
Random
真正意義上的隨機(jī)，你不知道下一次被替換出去的會(huì)是哪一個(gè)cache block
LRU（Least Recently Used）
按照Cache block被使用的先后順序組成鏈表，按最老的數(shù)據(jù)最先被替換的規(guī)則進(jìn)行替換
MRU（Most Recently Used）和LRU類(lèi)似，差別在于它是按使用的頻度來(lái)排序，按最少使用的數(shù)據(jù)最先被替換出去的規(guī)則進(jìn)行替換。
————————————————————-
FIFO、RR和Random算法都沒(méi)有考慮cache的使用歷史信息，而程序的時(shí)間和空間局部性都依賴(lài)于這些歷史信息，因此不少CPU使用了LRU算法。這并不意味著LRU就一定比這些算法強(qiáng)，理論和實(shí)驗(yàn)（參考1，參考2，參考3）都證明了LRU在某些場(chǎng)景下miss率比其他三種都高，比如訪問(wèn)數(shù)組{a, b, c, d, e}命中到同一個(gè)組時(shí), Miss的概率非常高，在這種情況下LRU并不比FIFO、RR好多少，而明顯弱于Random方式。
LRU算法沒(méi)有利用訪問(wèn)次數(shù)這個(gè)重要信息，在處理文件掃描這種空間局限性較弱的場(chǎng)景時(shí)就顯得有點(diǎn)力不從心，訪問(wèn)的數(shù)據(jù)量越大，miss率越高，因此LRU出現(xiàn)了改良算法：LRFU和LRU-K
LRFU是LRU和LFU（Least Frequently Used）兩者的結(jié)合，優(yōu)先替換訪問(wèn)次數(shù)少的數(shù)據(jù)。LRU-K記錄頁(yè)面訪問(wèn)的次數(shù)，K為最大值，實(shí)現(xiàn)方法是：先從使用次數(shù)為1的頁(yè)面中根據(jù)LRU查找頁(yè)面進(jìn)行替換，如果沒(méi)有1的頁(yè)面則查找訪問(wèn)次數(shù)為2的頁(yè)面，直到K為止。當(dāng)K=1時(shí)，等效于LRU?，F(xiàn)實(shí)中LRU-2比較常用。
LUR-K使用多個(gè)優(yōu)先級(jí)隊(duì)列，算法復(fù)雜度為O（Log2N），而LRU、FIFO這類(lèi)算法的復(fù)雜度位O(1)，因此采用LRU-K算法時(shí)需要耗費(fèi)更多的cycle，同時(shí)，多個(gè)隊(duì)列使用互相獨(dú)立的空間，消耗的空間也較多，因此出現(xiàn)了針對(duì)LRU-2優(yōu)化的2Q算法，其初衷是保證LRU-2效果不變的前提下，減小時(shí)間和空間的消耗。
2Q算法有兩種實(shí)現(xiàn)方式：Simplified 2Q和Full version 2Q，下節(jié)詳細(xì)介紹
參考1Alan Jay Smith [Sep. 1982].Cache Memories. Sep. 1982] ACM Computing Surveys Volume 14 Issue 3
參考2：GURURAJ S. RAO [Jul. 1978]. Performance Analysis of Cache Memories.?Journal the ACM（JACM）Vol 25, No 3.
參考3：Jan Reineke, Daniel Grund, Christoph Berg, andReinhard Wilhelm[Nov 2007]. Timing Predictabilityof Cache Replacement Policies. Real-Time Systems. Volume 37, Number 2.
