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

LFU算法LFU算法過程是什么，呵LRU算？

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

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

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

上述簡單算法有兩個問題：

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

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

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

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

typedef struct redisobject{

unsigned類型：4

未簽名編碼：4

未簽名lru:lru位/*LRU時間（相對于全局LRU時鐘）或

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

*和最高有效16位訪問時間）。*/

int refcount

void*ptr

}羅布