張恒瑞，王紅

（遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院，葫蘆島 125105）

Cache替換算法LRU和2Q的深度分析

張恒瑞，王紅

（遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院，葫蘆島 125105）

Cache替換算法是內(nèi)存和CPU交互時速度保證的關(guān)鍵，傳統(tǒng)的LRU算法在處理偶然性數(shù)據(jù)訪問時造成緩存污染嚴(yán)重，但其實現(xiàn)簡單，命中率和效率尚可，故成為現(xiàn)今大多情況下使用的算法；2Q算法通過設(shè)置兩個隊列，A1隊列通過暫存數(shù)據(jù)減弱偶發(fā)性數(shù)據(jù)的影響，實現(xiàn)同樣簡單且有不錯的性能。通過編制的詞法分析器分析程序代碼得來的數(shù)據(jù)進行算法性能的比較。

Cache替換算法；LRU；2Q；命中率；性能

0 引言

Cache作為一種媒介大大提升了CPU和內(nèi)存的訪問速度，為了增加Cache的訪問命中率，替換策略的選取大為重要，如今的替換策略大都以程序的局部性原理作為理論基礎(chǔ)，分別從時間局部性和空間局部性作為著眼點，闡釋不一樣的替換算法。LRU作為經(jīng)典的替換策略，實現(xiàn)簡單，但對于特定的數(shù)據(jù)有很大的缺陷，2Q算法從某種程度上緩解了緩存污染，但是將一個隊列變成兩個隊列勢必會影響性能，如何平衡這兩者的關(guān)系成為重點。

1 問題抽象

將對Cache的操作簡化為get和set操作，get（key）表示通過其緩存地址key得到內(nèi)容value，未命中count++，增加鍵值對（key，value）表示入緩存，緩存滿時按策略刪除，set（key，value），若key存在則修改對應(yīng)緩存中value值，若不存在則增加鍵值對（key，value）表示入緩存，count，緩存滿時按策略刪除，可以通過其count值判斷其命中情況，運行時間來比較其效率。

2 LRU

2.1 LRU原理

LRU，最近最少使用算法，從時間局部性著手，如果數(shù)據(jù)在最近被訪問，將來也很有可能訪問，基本的思想是建立一個鏈表，當(dāng)訪問命中時，將節(jié)點插入鏈表頭部，當(dāng)鏈表達到長度限制時刪除鏈表尾節(jié)點。

上述過程在查找訪問過程和刪除尾節(jié)點處復(fù)雜度達到了O（n）[1]，鏈表的好處在于插入刪除的復(fù)雜度為O（1）,而在訪問節(jié)點處復(fù)雜度高達O（n），訪問檢索處的復(fù)雜度可以通過紅黑樹或hash表予以優(yōu)化，而普通的單鏈表在刪除某節(jié)點時需要知道上一個節(jié)點，當(dāng)檢索到當(dāng)前節(jié)點后，還需從頭訪問到上一個節(jié)點才能刪除該節(jié)點，同時最后一個節(jié)點的刪除也需要從頭訪問，時間復(fù)雜度為O（n），故采用雙向鏈表[2]，插入和刪除的復(fù)雜度都為O（1）。

2.2 具體實現(xiàn)

因為關(guān)于Cache替換中內(nèi)存也占有很大地位，而hash占有較大的空間復(fù)雜度，所以運用紅黑樹作為數(shù)據(jù)的存儲結(jié)構(gòu)，C++的標(biāo)準(zhǔn)庫Map實現(xiàn)了紅黑樹，list實現(xiàn)了雙向鏈表，總的時間復(fù)雜度為O（logn），去除Map的定位功能，對鏈表的插入刪除僅需O（1），以下的代碼為了精簡，使用了map和list的stl庫。

2.3 分析

LRU算法實現(xiàn)簡單，效率也不錯，但面對偶發(fā)性的訪問數(shù)據(jù)無力，造成緩存污染嚴(yán)重。假設(shè)緩存容量為100，操作序列為1-101循環(huán)訪問，若采用LRU算法，當(dāng)訪問101時會將1刪除，之后每次訪問都會將下次訪問數(shù)據(jù)從緩存刪除，命中率大大降低。

32 Q算法

3.1 基本原理

2Q算法緩解了LRU對弱空間局限性的無力，在2Q算法里，有兩個隊列A1和A2[3]，A1為FIFO隊列，A2為LRU隊列，若數(shù)據(jù)在A1和A2中都沒命中，將數(shù)據(jù)插入A1隊列尾部，若A1滿，A1頭部出隊，當(dāng)數(shù)據(jù)在A1命中時，將其刪除，并將數(shù)據(jù)插入A2尾部，A2滿時將A2頭部出隊。

3.2 具體實現(xiàn)

程序中對A1和A2隊列采用list雙向鏈表，并采用map進行訪問檢索，保證插入刪除時的復(fù)雜度為O（1）,對key先在A2進行map訪問檢查，若未命中檢查A1，若命中執(zhí)行l(wèi)ist刪除操作，并將數(shù)據(jù)插入A2，代表數(shù)據(jù)入Cache，為hot數(shù)據(jù)，避免LRU中一次訪問就入Cache造成偶發(fā)性數(shù)據(jù)污染緩存，若在A1未命中，將數(shù)據(jù)以FIFO的形式入A1。

3.3 分析

以上為簡化的2Q操作，在簡化操作中，A1和A2所占比例是問題的關(guān)鍵，A1比例大時，緩存容量變少，命中率降低，而A1比例小時，找出數(shù)據(jù)人緩存的時間變長，如何平衡好A1和A2所占比例是問題的關(guān)鍵[4]。如圖1所示，比較下LRU和2Q在緩存為3000，200000次隨機數(shù)測試下的運行效率和命中率可以發(fā)現(xiàn)2Q的運行效率明顯較好。

仔細看后，發(fā)現(xiàn)兩種算法的未命中次數(shù)都顯得很高，原因在于測試選用的是隨機數(shù)進行的，在隨機數(shù)模式下，程序的局部性原理便不再起作用，替換算法之間的差距也變小了，如何進行有效果且具有一定的規(guī)模的數(shù)據(jù)測試呢。下面決定采用編寫的簡易詞法分析器對大量程序分析后得到的數(shù)據(jù)結(jié)果作為替換算法的測試數(shù)據(jù)。運用詞法分析器對超過7000行的代碼進行分析得到50000余條數(shù)據(jù)，作為替換算法的輸入文件進行運算，在數(shù)據(jù)范圍在1000以內(nèi)，緩存容量為300得到如圖2結(jié)果。

圖1 LRU和2Q比較結(jié)果

圖2 三種算法比較結(jié)果

結(jié)果中可看出最簡單的FIFO算法命中次數(shù)最差，在實際的情況下多次訪問主存會造成時間效率差，相對的LRU和2Q算法命中次數(shù)較好，雖然運行時間稍長于FIFO，在較少的訪問主存下會使總的時間效率大大提升，在大多實際情況下，LRU算法運行效率尚可，在大量偶發(fā)性數(shù)據(jù)下，可以采用2Q算法予以改進。

[1]海子.LRU Cache.[2014-5-23].http://www.cnblogs.com/dolphin0520/p/3741519.html.

[2]黃賢明.基于LRU改進算法的實時數(shù)據(jù)庫緩存機制[J].工業(yè)控制計算機，2015（12）：63-64.

[3]flychao88.緩存淘汰算法-LRU算法.[2013-11-20].http://flychao88.iteye.com/blog/1977653.

[4]Linux Memory.Cache替換算法之：2Q.[2015-5-20].http://www.jianshu.com/p/4f3ca27300c2.

Depth Analysis of LRU and 2Q on Cache Replacement Algorithm

ZHANG Heng-rui，WANG Hong

（School of Electronic and Information Engineering,Liaoning Technical University,Huludao 125105）

Cache replacement algorithm is the key to ensure the speed of memory and CPU interaction,the traditional LRU algorithm in dealing with accidental data access caused by cache pollution,but its implementation is simple and the hit rate and efficiency can be used now,in most cases the algorithm,the 2Q algorithm by setting two queue,queue A1 reduces the influence of sporadic data through the temporary storage of data,to achieve the same performance is simple and has good,through the use of lexical analyzer analysis program code to compare the performance of the data algorithm.

Cache Replacement Algorithm;LRU;2Q；Hit Rate;Performance

1007-1423（2017）04-0017-03

10.3969/j.issn.1007-1423.2017.04.014

王紅（1979-），女，遼寧莊河人，講師,碩士研究生，研究方向為計算機系統(tǒng)結(jié)構(gòu)、計算機控制及應(yīng)用

2016-12-07

2017-01-20

張恒瑞（1996-），男，本科生