LFU算法LFU算法過(guò)程是什么，呵LRU算？LRU是最近最少使用的頁(yè)面替換算法（least recently used），即首先消除最長(zhǎng)未使用的頁(yè)面！LFU是最近使用最少的頁(yè)面替換算法（最少頻繁使用）

LFU算法LFU算法過(guò)程是什么，呵LRU算？

LRU是最近最少使用的頁(yè)面替換算法（least recently used），即首先消除最長(zhǎng)未使用的頁(yè)面！LFU是最近使用最少的頁(yè)面替換算法（最少頻繁使用），即在一定的時(shí)間內(nèi)消除最少訪問(wèn)的頁(yè)面！例如，第二方法的周期T是10分鐘，如果每分鐘分頁(yè)一次，則主存儲(chǔ)器塊是3，如果所需的頁(yè)方向是21234。請(qǐng)注意，調(diào)用第4頁(yè)時(shí)，將出現(xiàn)缺頁(yè)中斷。根據(jù)LRU算法，應(yīng)該替換第1頁(yè)（第1頁(yè)最長(zhǎng)時(shí)間沒(méi)有使用），但是根據(jù)LFU算法，應(yīng)該替換第3頁(yè)（第3頁(yè)每十分鐘才使用一次）?？梢钥闯觯琇RU的關(guān)鍵是看頁(yè)面最后使用了多長(zhǎng)時(shí)間，而LFU的關(guān)鍵是看頁(yè)面在一段時(shí)間內(nèi)使用的頻率

lfu算法優(yōu)缺點(diǎn)？

在LFU算法中，可以為每個(gè)密鑰維護(hù)一個(gè)計(jì)數(shù)器。每次存取鑰匙時(shí)，計(jì)數(shù)器都會(huì)增加。計(jì)數(shù)器越大，訪問(wèn)頻率就越高。

上述簡(jiǎn)單算法有兩個(gè)問(wèn)題：

在LRU算法中，它可以維護(hù)一個(gè)雙向鏈表，然后簡(jiǎn)單地將被訪問(wèn)的節(jié)點(diǎn)移動(dòng)到鏈表的開頭，但在LFU中是不可行的。節(jié)點(diǎn)應(yīng)嚴(yán)格按照計(jì)數(shù)器排序。當(dāng)添加新節(jié)點(diǎn)或更新節(jié)點(diǎn)位置時(shí)，時(shí)間復(fù)雜度可能達(dá)到o（n）。

增加計(jì)數(shù)器的簡(jiǎn)單方法并不完美。訪問(wèn)模式將頻繁更改。在一段時(shí)間內(nèi)頻繁訪問(wèn)的密鑰在一段時(shí)間后可能很少被訪問(wèn)。僅僅增加計(jì)數(shù)器不能反映這一趨勢(shì)。

第一個(gè)問(wèn)題解決得很好。我們可以借鑒LRU實(shí)現(xiàn)的經(jīng)驗(yàn)來(lái)維護(hù)一個(gè)待淘汰的密鑰池。第二個(gè)問(wèn)題的解決方案是記錄上次訪問(wèn)密鑰的時(shí)間，然后隨著時(shí)間的推移減少計(jì)數(shù)器。

redis object的結(jié)構(gòu)如下：

typedef struct redisobject{

unsigned類型：4

未簽名編碼：4

未簽名lru:lru位/*LRU時(shí)間（相對(duì)于全局LRU時(shí)鐘）或

*LFU數(shù)據(jù)（最低有效8位頻率

*和最高有效16位訪問(wèn)時(shí)間）。*/

int refcount

void*ptr

}羅布