lru演算法代碼

⑴ lru演算法是什麼

lru演算法是一種頁面置換演算法，在對於內存中但是又不用的數據塊，叫做LRU，操作系統會根據那些數據屬於LRU而將其移出內存而騰出空間來載入另外的數據。

LRU演算法：最近最少使用，簡單來說就是將數據塊中，每次使用過的數據放在數據塊的最前端，然後將存在的時間最長的，也就是數據塊的末端的數據剔除掉這就是LRU演算法。

如果進程被調度，該進程需要使用的外存頁（數據）不存在於數據塊中，這個現象就叫做缺頁。如果這個數據此時不在，就會將這個數據從加入到數據塊首部。

數據塊插入與剔除：每次有新數據到來時，會將其放入數據塊首部，當數據每次被訪問時，岩鍵肢將這個數據插入數據塊的首部如果數據塊滿了，每次新進的數據都會將數據塊尾部的數據擠出數據塊。

差距

為了盡量減少與理想演算法的差距，產生了各種精妙的演算法，最少使用頁面置換演算法便是其中一個。LRU演算法的提出，是基於這樣一個事實：在前面幾條指令中使用頻繁的頁面很可能在後面的幾條指令中頻繁使用。

反過來說，已經亮鉛很久沒有使用的頁面很可能在未來較長的一段時間內不會被用到。這個，就是著名的局部性原理——比內存速度還要快的cache，也是基於同樣的原理運行的。因此，我們只需要在每次調換時，找到最少使用的那個頁面調出內存。這就是LRU演算法的全部內容。

LRU在電子系統中的解釋：

Line Replaceable Unit—LRU，電子系統中常採用模塊化設計，這種可更換的模塊單元則被叫做LRU，中文名稱是「線性可粗世更換單元」。

⑵ 用C++語言編寫FIFO頁面置換演算法代碼

分別使用FIFO、OPT、LRU三種置換演算法來模擬頁面置換的過程。（Linux、Windows下皆可）
輸入：3//頁幀數
70120304230321201701//待處理的頁
輸出：頁面置換過程中各幀的變化過程和出現頁錯誤的次數
[cpp]
#include<iostream>
usingnamespacestd;
intinput[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
classpage
{
public:
intnum;
intmark;
page()
{
num=0;
mark=21;
}
};
voidFIFO()
{
cout<<"------FIFO-----------"<<endl;
interror=0;
pageframe[3];//頁幀
for(inti=0;i<3;i++)//處理前三個引用
{
frame[i].num=input[i];
error++;
cout<<frame[i].num<<"|";
for(intj=0;j<=i;j++)
cout<<frame[j].num<<'';
cout<<endl;
}
for(inti=3;i<20;i++)
{
intj;
for(j=0;j<3;j++)
if(input[i]==frame[j].num)
{
cout<<input[i]<<endl;
break;
}
if(j==3)
{
error++;
frame[((error-1)%3)].num=input[i];//換掉最舊的頁
cout<<input[i]<<"|";
for(intk=0;k<3;k++)
cout<<frame[k].num<<'';
cout<<endl;
}
}
cout<<"FrameError:"<<error<<endl<<endl;
}
voidOPT()
{
cout<<"------OPT------------"<<endl;
interror=0;
pageframe[3];
for(inti=0;i<3;i++)//處理前三個引用
{
frame[i].num=input[i];
error++;
cout<<frame[i].num<<"|";
for(intj=0;j<=i;j++)
cout<<frame[j].num<<'';
cout<<endl;
}
for(inti=3;i<20;i++)
{
intj;
for(j=0;j<3;j++)
if(input[i]==frame[j].num)
{
cout<<input[i]<<endl;
break;
}
if(j==3)
{
error++;
for(j=0;j<3;j++)
{
frame[j].mark=21;
for(intk=20;k>=i;k--)//向後遍歷，找到最長時間不用的頁
{
if(frame[j].num==input[k])
frame[j].mark=k;
}
}
if(frame[0].mark>frame[1].mark&&frame[0].mark>frame[2].mark)
frame[0].num=input[i];
elseif(frame[1].mark>frame[0].mark&&frame[1].mark>frame[2].mark)
frame[1].num=input[i];
else
frame[2].num=input[i];
cout<<input[i]<<"|";
for(intk=0;k<3;k++)
cout<<frame[k].num<<'';
cout<<endl;
}
}
cout<<"FrameError:"<<error<<endl<<endl;
}
voidLRU()
{
cout<<"------LRU------------"<<endl;
interror=0;
pageframe[3];
for(inti=0;i<3;i++)//處理前三個引用
{
frame[i].num=input[i];
error++;
cout<<frame[i].num<<"|";
for(intj=0;j<=i;j++)
cout<<frame[j].num<<'';
cout<<endl;
}
for(inti=3;i<20;i++)
{
intj;
for(j=0;j<3;j++)
if(input[i]==frame[j].num)
{
cout<<input[i]<<endl;
break;
}
if(j==3)
{
error++;
for(j=0;j<3;j++)
{
frame[j].mark=0;
for(intk=0;k<=i;k++)//向前遍歷，找到最近最少使用的
{
if(frame[j].num==input[k])
frame[j].mark=k;
}
}
if(frame[0].mark<frame[1].mark&&frame[0].mark<frame[2].mark)
frame[0].num=input[i];
elseif(frame[1].mark<frame[0].mark&&frame[1].mark<frame[2].mark)
frame[1].num=input[i];
else
frame[2].num=input[i];
cout<<input[i]<<"|";
for(intk=0;k<3;k++)
cout<<frame[k].num<<'';
cout<<endl;
}
}
cout<<"FrameError:"<<error<<endl<<endl;
}
intmain()
{
FIFO();
OPT();
LRU();
}

⑶ Redis的LRU緩存淘汰演算法實現

LRU， 最近最少使用 （Least Recently Used，LRU），經典緩存演算法。

LRU會使用一個鏈表維護緩存中每個數據的訪問情況，並根據數據的實時訪問，調整數據在鏈表中的位置，然後通過數據在鏈表中的位置，表示數據是最近剛訪問的，還是已有段時間未訪問。

LRU會把鏈頭、尾分別設為MRU端和LRU端：

LRU可分成如下情況：

case2圖解：鏈表長度為5，從鏈表頭部到尾部保存的數據分別是5，33，9，10，8。假設數據9被訪問一次，則9就會被移動到鏈表頭部，同時，數據5和33都要向鏈表尾部移動一位。

所以若嚴格按LRU實現，假設Redis保存的數據較多，還要在代碼中實現：

最終導致降低Redis訪問性能。

所以，無論是為節省內存 or 保持Redis高性能，Redis並未嚴格按LRU基本原理實現，而是 提供了一個近似LRU演算法實現 。

Redis的內存淘汰機制是如何啟用近似LRU演算法的？redis.conf中的如下配置參數：

所以，一旦設定maxmemory選項，且將maxmemory-policy配為allkeys-lru或volatile-lru，近似LRU就被啟用。allkeys-lru和volatile-lru都會使用近似LRU淘汰數據，區別在於：

Redis如何實現近似LRU演算法的呢？

近似LRU演算法仍需區分不同數據的訪問時效性，即Redis需知道數據的最近一次訪問時間。因此，有了LRU時鍾：記錄數據每次訪問的時間戳。

Redis對每個KV對中的V，會使用個redisObject結構體保存指向V的指針。那redisObject除記錄值的指針，還會使用24 bits保存LRU時鍾信息，對應的是lru成員變數。這樣，每個KV對都會把它最近一次被訪問的時間戳，記錄在lru變數。

redisObject定義包含lru成員變數的定義：

每個KV對的LRU時鍾值是如何計算的？Redis Server使用一個實例級別的全局LRU時鍾，每個KV對的LRU time會根據全局LRU時鍾進行設置。

這全局LRU時鍾保存在Redis全局變數server的成員變數 lruclock

當Redis Server啟動後，調用initServerConfig初始化各項參數時，會調用getLRUClock設置lruclock的值：

於是，就得注意， 若一個數據前後兩次訪問的時間間隔 1s，那這兩次訪問的時間戳就是一樣的！ 因為LRU時鍾精度就是1s，它無法區分間隔小於1秒的不同時間戳！

getLRUClock函數將獲得的UNIX時間戳，除以LRU_CLOCK_RESOLUTION後，就得到了以LRU時鍾精度來計算的UNIX時間戳，也就是當前的LRU時鍾值。

getLRUClock會把LRU時鍾值和宏定義LRU_CLOCK_MAX（LRU時鍾能表示的最大值）做與運算。

所以默認情況下，全局LRU時鍾值是以1s為精度計算得UNIX時間戳，且是在initServerConfig中進行的初始化。

那Redis Server運行過程中，全局LRU時鍾值是如何更新的？和Redis Server在事件驅動框架中，定期運行的時間事件所對應的serverCron有關。

serverCron作為時間事件的回調函數，本身會周期性執行，其頻率值由redis.conf的 hz配置項 決定，默認值10，即serverCron函數會每100ms（1s/10 = 100ms）運行一次。serverCron中，全局LRU時鍾值就會按該函數執行頻率，定期調用getLRUClock進行更新：

這樣，每個KV對就能從全局LRU時鍾獲取最新訪問時間戳。

對於每個KV對，它對應的redisObject.lru在哪些函數進行初始化和更新的呢？

對於一個KV對，其LRU時鍾值最初是在這KV對被創建時，進行初始化設置的，這初始化操作在 createObject函數 中調用，當Redis要創建一個KV對，就會調用該函數。

createObject除了會給redisObject分配內存空間，還會根據maxmemory_policy配置，初始化設置redisObject.lru。

LRU_CLOCK返回當前全局LRU時鍾值。因為一個KV對一旦被創建，就相當於有了次訪問，其對應LRU時鍾值就表示了它的訪問時間戳：

那一個KV對的LRU時鍾值又是何時再被更新？

只要一個KV對被訪問，其LRU時鍾值就會被更新！而當一個KV對被訪問時，訪問操作最終都會調用 lookupKey 。

lookupKey會從全局哈希表中查找要訪問的KV對。若該KV對存在，則lookupKey會根據maxmemory_policy的配置值，來更新鍵值對的LRU時鍾值，也就是它的訪問時間戳。

而當maxmemory_policy沒有配置為LFU策略時，lookupKey函數就會調用LRU_CLOCK函數，來獲取當前的全局LRU時鍾值，並將其賦值給鍵值對的redisObject結構體中的lru變數

這樣，每個KV對一旦被訪問，就能獲得最新的訪問時間戳。但你可能好奇：這些訪問時間戳最終是如何被用於近似LRU演算法進行數據淘汰的？

Redis之所以實現近似LRU，是為減少內存資源和操作時間上的開銷。

近似LRU主要邏輯在performEvictions。

performEvictions被evictionTimeProc調用，而evictionTimeProc函數又是被processCommand調用。

processCommand，Redis處理每個命令時都會調用：

然後，isSafeToPerformEvictions還會再次根據如下條件判斷是否繼續執行performEvictions：

一旦performEvictions被調用，且maxmemory-policy被設置為allkeys-lru或volatile-lru，近似LRU就被觸發執行了。

執行可分成如下步驟：

調用getMaxmemoryState評估當前內存使用情況，判斷當前Redis Server使用內存容量是否超過maxmemory配置值。

若未超過maxmemory ，則返回C_OK，performEvictions也會直接返回。

getMaxmemoryState評估當前內存使用情況的時候，若發現已用內存超出maxmemory，會計算需釋放的內存量。這個釋放內存大小=已使用內存量-maxmemory。

但已使用內存量並不包括用於主從復制的復制緩沖區大小，這是getMaxmemoryState通過調用freeMemoryGetNotCountedMemory計算的。

而若當前Server使用的內存量超出maxmemory上限 ，則performEvictions會執行while循環淘汰數據釋放內存。

為淘汰數據，Redis定義數組EvictionPoolLRU，保存待淘汰的候選KV對，元素類型是evictionPoolEntry結構體，保存了待淘汰KV對的空閑時間idle、對應K等信息：

這樣，Redis Server在執行initSever進行初始化時，會調用evictionPoolAlloc為EvictionPoolLRU數組分配內存空間，該數組大小由EVPOOL_SIZE決定，默認可保存16個待淘汰的候選KV對。

performEvictions在淘汰數據的循環流程中，就會更新這個待淘汰的候選KV對集合，即EvictionPoolLRU數組。

performEvictions調用evictionPoolPopulate，其會先調用dictGetSomeKeys，從待采樣哈希表隨機獲取一定數量K：

於是，dictGetSomeKeys返回採樣的KV對集合。evictionPoolPopulate根據實際采樣到的KV對數量count，執行循環：調用estimateObjectIdleTime計算在采樣集合中的每一個KV對的空閑時間：

接著，evictionPoolPopulate遍歷待淘汰的候選KV對集合，即EvictionPoolLRU數組，嘗試把采樣的每個KV對插入EvictionPoolLRU數組，取決於如下條件之一：

有一成立，evictionPoolPopulate就能把采樣KV對插入EvictionPoolLRU數組。等所有采樣鍵值對都處理完後，evictionPoolPopulate函數就完成對待淘汰候選鍵值對集合的更新了。

接下來，performEvictions開始選擇最終被淘汰的KV對。

因evictionPoolPopulate已更新EvictionPoolLRU數組，且該數組里的K，是按空閑時間從小到大排好序了。所以，performEvictions遍歷一次EvictionPoolLRU數組，從數組的最後一個K開始選擇，若選到的K非空，就把它作為最終淘汰的K。

該過程執行邏輯：

一旦選到被淘汰的K，performEvictions就會根據Redis server的惰性刪除配置，執行同步刪除或非同步刪除：

至此，performEvictions就淘汰了一個K。若此時釋放的內存空間還不夠，即沒有達到待釋放空間，則performEvictions還會 重復執行 前面所說的更新待淘汰候選KV對集合、選擇最終淘汰K的過程，直到滿足待釋放空間的大小要求。

performEvictions流程：

近似LRU演算法並未使用耗時且耗空間的鏈表，而使用 固定大小的待淘汰數據集合 ，每次隨機選擇一些K加入待淘汰數據集合。

最後，按待淘汰集合中K的空閑時間長度，刪除空閑時間最長的K。

根據LRU演算法的基本原理，發現若嚴格按基本原理實現LRU演算法，則開發的系統就需要額外內存空間保存LRU鏈表，系統運行時也會受到LRU鏈表操作的開銷影響。

而Redis的內存資源和性能都很重要，所以Redis實現近似LRU演算法：

一個演算法的基本原理和演算法的實際執行，在系統開發中會有一定折中，需綜合考慮所開發的系統，在資源和性能方面的要求，以避免嚴格按照演算法實現帶來的資源和性能開銷。

⑷ lru演算法是什麼

LRU是Least Recently Used的縮寫，是一種常用的頁面置換演算法，選擇最近最久未使用的頁面予以淘汰。

該演算法賦予每個頁面一個訪問欄位，用來記錄一個頁面自上次被訪問以來所經歷的時間t，當須淘汰一個頁面時，選擇現有頁面中其t值最大的，即最近最少使用的頁面予以淘汰。

特點：

LRU 演算法弊端是存在偶發性、周期性的批量操會降低緩存的命中率，對緩存造成污染，下面幾個就是改進演算法。

LRU-K會記錄每條數據的訪問歷史，當達到 k 時，才將數據存放到緩存，在緩存內存回收時，緩存中越接近 k 的數據被優先刪除。

Two queues（2Q）相當於 LRU-2，區別是訪問歷史（首次訪問）數據緩存於 FIFO 隊列，二次及以上的數據存放LRU緩存，FIFO 隊列數據遵循該緩存的內存回收機制，LRU緩存數據遵循該緩存的內存回收機制。