區(qū)別：LRU是最近最少使用頁(yè)面置換算法，淘汰最長(zhǎng)時(shí)間未被使用的頁(yè)面；而LFU是最近最不常用頁(yè)面置換算法，淘汰一定時(shí)期內(nèi)被訪問次數(shù)最少的頁(yè)。LRU關(guān)鍵是看頁(yè)面最后一次被使用到發(fā)生調(diào)度的時(shí)間長(zhǎng)短；而LFU關(guān)鍵是看一定時(shí)間段內(nèi)頁(yè)面被使用的頻率。

本教程操作環(huán)境：windows7系統(tǒng)、Dell G3電腦。

對(duì)于web開發(fā)而言，緩存必不可少，也是提高性能最常用的方式。無論是瀏覽器緩存(如果是chrome瀏覽器，可以通過chrome:://cache查看)，還是服務(wù)端的緩存(通過memcached或者redis等內(nèi)存數(shù)據(jù)庫(kù))。緩存不僅可以加速用戶的訪問，同時(shí)也可以降低服務(wù)器的負(fù)載和壓力。那么，了解常見的緩存淘汰算法的策略和原理就顯得特別重要。

常見的緩存算法

• LRU (Least recently used) 最近最少使用，如果數(shù)據(jù)最近被訪問過，那么將來被訪問的幾率也更高。
• LFU (Least frequently used) 最不經(jīng)常使用，如果一個(gè)數(shù)據(jù)在最近一段時(shí)間內(nèi)使用次數(shù)很少，那么在將來一段時(shí)間內(nèi)被使用的可能性也很小。
• FIFO (Fist in first out) 先進(jìn)先出， 如果一個(gè)數(shù)據(jù)最先進(jìn)入緩存中，則應(yīng)該最早淘汰掉。

LRU緩存

像瀏覽器的緩存策略、memcached的緩存策略都是使用LRU這個(gè)算法，LRU算法會(huì)將近期最不會(huì)訪問的數(shù)據(jù)淘汰掉。LRU如此流行的原因是實(shí)現(xiàn)比較簡(jiǎn)單，而且對(duì)于實(shí)際問題也很實(shí)用，良好的運(yùn)行時(shí)性能，命中率較高。下面談?wù)勅绾螌?shí)現(xiàn)LRU緩存：

• 新數(shù)據(jù)插入到鏈表頭部
• 每當(dāng)緩存命中（即緩存數(shù)據(jù)被訪問），則將數(shù)據(jù)移到鏈表頭部
• 當(dāng)鏈表滿的時(shí)候，將鏈表尾部的數(shù)據(jù)丟棄

LRU Cache具備的操作：

• set(key,value)：如果key在hashmap中存在，則先重置對(duì)應(yīng)的value值，然后獲取對(duì)應(yīng)的節(jié)點(diǎn)cur，將cur節(jié)點(diǎn)從鏈表刪除，并移動(dòng)到鏈表的頭部；若果key在hashmap不存在，則新建一個(gè)節(jié)點(diǎn)，并將節(jié)點(diǎn)放到鏈表的頭部。當(dāng)Cache存滿的時(shí)候，將鏈表最后一個(gè)節(jié)點(diǎn)刪除即可。
• get(key)：如果key在hashmap中存在，則把對(duì)應(yīng)的節(jié)點(diǎn)放到鏈表頭部，并返回對(duì)應(yīng)的value值；如果不存在，則返回-1。

LRU和LFU的區(qū)別：

LRU是最近最少使用頁(yè)面置換算法(Least Recently Used),也就是首先淘汰最長(zhǎng)時(shí)間未被使用的頁(yè)面！

LFU是最近最不常用頁(yè)面置換算法(Least Frequently Used),也就是淘汰一定時(shí)期內(nèi)被訪問次數(shù)最少的頁(yè)！

比如,第二種方法的時(shí)期T為10分鐘,如果每分鐘進(jìn)行一次調(diào)頁(yè),主存塊為3,若所需頁(yè)面走向?yàn)? 1 2 1 2 3 4

注意,當(dāng)調(diào)頁(yè)面4時(shí)會(huì)發(fā)生缺頁(yè)中斷

若按LRU算法,應(yīng)換頁(yè)面1(1頁(yè)面最久未被使用) 但按LFU算法應(yīng)換頁(yè)面3(十分鐘內(nèi),頁(yè)面3只使用了一次)

總結(jié)

可見LRU關(guān)鍵是看頁(yè)面最后一次被使用到發(fā)生調(diào)度的時(shí)間長(zhǎng)短；

而LFU關(guān)鍵是看一定時(shí)間段內(nèi)頁(yè)面被使用的頻率！