983
緩存淘汰算法係列之3——FIFO類
緩存淘汰算法係列之3——FIFO類
1 FIFO
1.1. 原理
按照“先進先出（First In，First Out）”的原理淘汰數據。
1.2. 實現
FIFO隊列，具體實現如下：
1. 新訪問的數據插入FIFO隊列尾部，數據在FIFO隊列中順序移動；
2. 淘汰FIFO隊列頭部的數據；
1.3. 分析
l 命中率
命中率很低，因為命中率太低，實際應用中基本上不會采用。
l 複雜度
簡單
l 代價
實現代價很小。
2. Second Chance
2.1. 原理
FIFO算法的改進版，其思想是“如果被淘汰的數據之前被訪問過，則給其第二次機會（Second Chance）”。
2.2. 實現
每個數據會增加一個訪問標誌位，用於標識此數據放入緩存隊列後是否被再次訪問過。
如上圖，A是FIFO隊列中最舊的數據，且其放入隊列後沒有被再次訪問，則A被立刻淘汰；否則如果放入隊列後被訪問過，則將A移到FIFO隊列頭，並且將訪問標誌位清除。
如果所有的數據都被訪問過，則經過一次循環後就會按照FIFO的原則淘汰數據。
2.3. 分析
l 命中率
命中率比FIFO高。
l 複雜度
與FIFO相比，需要記錄數據的訪問標誌位，且需要將數據移動。
l 代價
實現代價比FIFO高。
3. Clock
3.1. 原理
Clock是Second Chance的改進版，通過一個環形隊列，避免將數據在FIFO隊列中移動。
3.2. 實現
如上圖，其具體實現如下：
l 當前指針指向C，如果C被訪問過，則清除C的訪問標誌，並將指針指向D；
l 如果C沒有被訪問過，則將新數據插入到C的位置,將指針指向D。
3.3. 分析
l 命中率
命中率比FIFO高，和Second Chance一樣。
l 複雜度
與FIFO相比，需要記錄數據的訪問標誌位，且需要將數據指針移動。
l 代價
實現代價比FIFO高，比Second Chance低。
4. FIFO類算法對比
|
對比點 |
對比 |
|
命中率 |
Clock = Second Chance > FIFO |
|
複雜度 |
Second Chance > Clock > FIFO |
|
代價 |
Second Chance > Clock > FIFO |
由於FIFO類算法命中率相比其他算法要低不少，因此實際應用中很少使用此類算法。
最後更新：2017-04-02 16:47:50