分析lru演算法實現思路

① lru演算法是什麼呢

LRU演算法是最少使用頁面置換演算法（Least Recently Used），首先置換近期最長時間以來沒被訪問的頁面，是為虛擬頁式存儲管理服務的。

LRU演算法的設計原則是：如果一個數據在最近一段時間沒有被訪問到，那麼在將來它被訪問的可能性也很小。也就是說，當限定的空間已存滿數據時，應當把最久沒有被訪問到的數據淘汰。

LRU原理

該思想最初用於計算機操作系統中，內存中的容量較有限，為了能更加合理的利用內存中的性能，對用戶的使用作出假設，最近最少使用的越不重要，最近使用的越有可能使用到，使得該元素更容易獲取到。

如果元素當前容量超過了內存最大容量，則需要刪除掉最近最少使用的元素。在其之後，許多緩存及許多分布式系統都採用才思想。

② lru演算法是什麼

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

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

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

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

差距

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

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

LRU在電子系統中的解釋：

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

③ 頁面置換演算法之LRU演算法

三種常見的頁面置換演算法:FIFO、LFU、LRU
參考：
緩存演算法（頁面置換演算法）-FIFO、LFU、LRU

LRU（Least Recently Used，最近最少使用）演算法根據數據的歷史訪問記錄來進行淘汰數據，其核心思想是： 如果一個數據在最近一段時間沒有被訪問到，那麼在將來它被訪問的可能性也很小 。也就是說，當限定的空間已存滿數據時，應當把最久沒有被訪問到的數據淘汰。

假設 序列為 4 3 4 2 3 1 4 2
物理塊有3個 則
首輪 4調入內存 4
次輪 3調入內存 3 4
之後 4調入內存 4 3
之後 2調入內存 2 4 3
之後 3調入內存 3 2 4
之後 1調入內存 1 3 2（因為最少使用的是4，所以丟棄4）
之後 4調入內存 4 1 3（原理同上）
最後 2調入內存 2 4 1

如果讓我們設計一個LRU Cache的數據結構，它應該支持兩個操作：

一種是採用數組來存儲每個數據項，再對每個key關聯一個時間戳，在cache中維護一個最大時間戳，其設計要點如下：

另一種是採用hashmap+雙向鏈表的數據結構，其設計要點如下：

對比上一節的兩種設計思路，不難發現，設計1需要為每個key維護一個時間戳，而且set和get操作的時間復雜度都是O(n)。顯而易見，隨著數據量的增大，set和get操作的速度越來越慢。而設計2通過採用hashmap+雙向鏈表，set和get操作的時間復雜度只需O(1)，下面給出設計2的具體實現。

運行結果為：

參考：
LRU Cache
LRU原理和Redis實現——一個今日頭條的面試題

④ 編譯原理LRU分析法

（2）LRU演算法，也是往前看。前四次缺頁，第五、六次滿足；第七次1出5進；第第八次2出1進；第九次3出2進；第十次4出3進；第十一次5出4進；第

⑤ 實現LRU演算法的硬體支持是什麼

寄存器、棧

實現LRU演算法的硬體支持是寄存器、棧。寄存器用於記錄某進程在內存中各頁的使用情況；棧用於保存當前使用的各個頁面的頁面號。LRU是最近最少使用，是一種常用的頁面置換演算法，選擇最近最久未使用的頁面予以淘汰。寄存器的功能是存儲二進制代碼，它是由具有存儲功能的觸發器組合起來構成的。一個觸發器可以存儲1位二進制代碼，故存放n位二進制代碼的寄存器，需用n個觸發器來構成。

(5)分析lru演算法實現思路擴展閱讀：

大部分操作系統為最大化頁面命中率而廣泛採用的一種頁面置換演算法是LRU演算法。該演算法的思路是，發生缺頁中斷時，選擇未使用時間最長的頁面置換出去。從程序運行的原理來看，最近最少使用演算法是比較接近理想的一種頁面置換演算法，這種演算法既充分利用了內存中頁面調用的歷史信息，又正確反映了程序的局部問題。

⑥ FIFO和LRU小結

 一:FIFO演算法

     1.0,FIFO (First in First out) 先進先出(核心原則:最先進來的,最先淘汰); 其實在操作系統的設計理念中很多地方都是利用到了先進先出的思想就是因為這個原則簡單切符合人們的慣性思維,具備公平性實現起來也簡單,直接使用數據結構中的隊列即可實現

     1.1,在FIFO 中應該支持這些操作: 一,get(key),如果Cache中存在該key,則返回對應的value值,否則返回 -1; 二,set(key,value),如果Cache中存在該key,則重置value值,如果不存在則將該key插入到Cache中,若Cache已滿則淘汰最先進入Cache的數據

     1.2,那麼利用什麼數據結構來實現呢?有這一種思路, 利用一個雙向鏈表保存數據,當來了新數據之後便添加到鏈表末尾,如果Cache存滿數據,則把鏈表頭部數據刪除,然後把次年數據添加到鏈表末尾,在訪問數據的時候,如果在Cache中存在該數據的話,則返回對應的value值,否則返回 -1,如果想提高訪問效率,可以利用hashmap來保存每個key在鏈表中的位置(參考下面拓展)

     二:LRU演算法

     1.0,LRU (Least recently used) 最近最久未使用調度,其核心思想是"如果數據最近被訪問過,那麼將來被訪問的幾率也更高"; 最常見的實現是使用一個鏈表保存緩存數據,詳細演算法實現如下:

       1,新數據插入到鏈表頭部

       2,每當緩存命中(即緩存數據被訪問),則將數據移到鏈表頭部;

       3,當鏈表滿的時候,將鏈表尾部的數據丟棄

     1.1,LRU的優缺點 1.命中率,當存在熱點數據時,LRU的效率很好,但偶發性的,周期性的批量操作會導致LRU命中率急劇下降,緩存污染情況比較嚴重 2,實現相對簡單 3,命中時需要遍歷鏈表,找到命中的數據塊索引,然後需要將數據移到頭部

     2.0,LRU-K K代表最近使用的次數,因此LRU也可以認為是LRU-1,它主要是為了解決LRU演算法"緩存污染"的問題,其核心思想是將"最近使用過1次"的判斷標准擴展為"最近使用過K次"; 相比LRU要多維護一個隊列,用於記錄所有緩存數據被訪問的歷史,只有當數據的訪問次數達到K次的時候,才將數據放入緩存.當需要淘汰數據時,LRU-k會淘汰第K次訪問時間距離當前時間最大的數據.詳細實現如下:

     2.1,一,數據第一次被訪問,加入到訪問歷史列表; 二,如果數據在訪問歷史列表裡後達到K次訪問,則按照一定(FIFO, LRU)淘汰; 三,當訪問歷史隊列中的數據訪問次數達到k次後,將數據l索引從歷史隊列刪除,將數據移到緩存隊列中,並緩存此數據,緩存隊列重新按照時間排序; 四,緩存數據隊列中被再次訪問後,重新排序; 五,需要淘汰數據時,淘汰緩存隊列中排在末尾的數據(即:淘汰倒數第K次訪問離現在最久的數據)

     2.2,LRU-K具有LRU的優點,同時能夠避免LRU的缺點,實際應用中LRU-2是綜合各種因素後最優的選擇,LRU-3或者更大的K值命中率會高,但適應性差,需要大量的數據訪問才能將歷史記錄緩存或者清除掉

     2.3優缺,LRU-K降低了"緩存污染"帶來的問題,命中率比LRU要高,但LRU-K隊列是一個優先順序隊列,演算法復雜度和代價相對LRU較高,並且LRU需要記錄那些被訪問過,但是沒有達到K次也就是還沒有放入緩存的對象,因此b內存消耗會比LRU要多,當然如果數據量很大的時候,內存消耗會比較可觀

     3.0,Two queues (2Q) 演算法類似於LRU-2,不同點在於2Q將LRU-2演算法中的訪問歷史隊列(歷史隊列,還沒有緩存數據)改為一個FIFO緩存隊列,即: 2Q演算法有兩個緩存隊列,一個是FIFO隊列,一個是LRU隊列.

     3.1,當數據第一次訪問時,2Q演算法會將數據緩存在FIFO隊列裡面,當數據第二次被訪問時,則將數據從FIFO隊列移到LRU隊列裡面,兩個隊列各自按照自己的方法淘汰數據; 一,新訪問的數據插入到FIFO隊列, 二,如果數據在FIFO隊列中一直沒有被再次訪問,則最終按照FOFO規則淘汰, 三,如果數據在FIFO隊列中被再次訪問,則將數據移到LRU隊列頭部, 四,如果數據在LRU隊列再次被訪問,則將數據移到LRU隊列頭部, 五,LRU隊列淘汰末尾的數據

     3.2,可能會感覺FIFO隊列比LRU隊列短,但並不代表這是演算法的要求,實際應用中兩者比例沒有硬性要求

     3.3,2Q演算法命中率高於LRU,切需要兩個隊列,但兩個隊列本身都比較簡單,代價是FIFO和LRU代價之和; 2Q演算法和LRU-2演算法命中率類似,內存消耗也比較接近,但對於最後的緩存數據來說,2Q減少一次從原始儲存讀取數據或者計算數據的操作

     4.0,Multi Queue (MQ) 演算法根據訪問頻率將數據劃分為多個隊列,不同的隊列具有不同的訪問優先順序,其核心思想是:優先緩存訪問次數多的數據

     4.1,MQ演算法將緩存劃分為多個LRU隊列,每個隊列對應不同的訪問優先順序,訪問優先順序是根據訪問次數計算出來的,詳情: 一,新插入的數據放入Q0; 二,每個隊列按照LRU管理數據; 三,當數據訪問次數達到一定次數需要提升優先順序時將數據從當前隊列刪除,加入到高一級的隊列頭部; 四,為了防止高優先順序數據永遠不被淘汰,每個隊列淘汰數據時,將數據從緩存中刪除,將數據加入Q-history頭部; 五,需要淘汰數據時,從最低一級隊列開始按照LRU淘汰,每個隊列淘汰數據時,將數據從緩存中刪除,將數據索引加入Q-history頭部; 六,如果數據在Q-history中被重新訪問,則重新計算其優先順序,移到目標隊列的頭部; 七,Q-history按照LRU淘汰數據的索引

     4.2,MQ降低了"緩存污染"帶來的問題,命中率比LRU高,但MQ需要維護多個隊列,切需要維護每個數據的訪問時間,復雜度比較高,並且MQ需要記錄每個數據的訪問時間,需要定時掃碼所有隊列,代價也比較高

     4.3,雖然MQ的隊列看起來數量比較多,但由於所有隊列之和受限於緩存容量的大小,因此這里多個隊列長度之和和一個LRU隊列是一樣的,因此隊列掃碼性能接近

     小結: 命中率  LRU-2 > MQ(2) > 2Q > LRU ; 復雜度 LRU-2 > MQ(2) > 2Q >LRU ; 代價 LRU-2 > MQ(2) > 2Q > LRU ; 需要注意的是,命中率並不是越高越好,實際中應該根據業務需求和對數據的訪問情況進行分析選擇,LRU雖然看起來命中率低一些,切存在"緩存污染"的問題,但其簡單切代價小,實際中反而應用更多

     拓展:基於 雙鏈表的 LRU 實現: 一,傳統意義的LRU演算法是每一個Cache對象設置一個定時器,每次Cache命中則給定時器 +1,而Cache用完需要淘汰舊內容,放置新內容時就查看所有的計時器,並將使用的內容替換掉; 其弊端很明顯,如果Cache的數量少,問題不大,但如果Cache的空間過大,達到10W或者100W以上,一旦需要淘汰,則需要遍歷所有計時器,其性能與資源消耗巨大,效率也就非常的慢了; 二,雙鏈表原理,將Cache的所有位置都用雙鏈表連接起來,當一個位置被命中之後,就將通過調整鏈表的指向,將該位置調整到鏈表頭的位置,新加入Cache直接加到鏈表頭中,這樣在多次進行Cache操作後,最近被命中的就會被向鏈表頭方向移動,而沒有命中的則向鏈表後部移動,鏈表尾則表示最近最少命中的Cache,當需要替換內容時我們只需要淘汰鏈表最後的部分即可!

如果錯誤或者建議,歡迎下方留言,謝謝!