lru淘汰演算法

A. lru演算法是什麼

lru演算法是一種常用的頁面置換演算法，選擇最近最久未使用的頁面予以淘汰。

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

特點：

LRU 置換演算法雖然是一種比較好的演算法，但要求系統有較多的支持硬體。為了了解一個進程在內存中的各個頁面各有多少時間未被進程訪問，以及如何快速地知道哪一頁是最近最久未使用的頁面，須有兩類硬體之一的支持：寄存器或棧。

在進程運行過程中，若其所要訪問的頁面不在內存而需把它們調入內存，但內存已無空閑空間時，為了保證該進程能正常運行，系統必須從內存中調出一頁程序或數據送磁碟的對換區中。

B. lru演算法是什麼呢

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

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

LRU原理

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

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

C. LRU 緩存淘汰演算法

當要緩存某個數據的時候，先在鏈表中查找這個數據。如果沒有找到，則直接將數據放到鏈表的尾部；如果找到了，我們就把它移動到鏈表的尾部，然後淘汰頭部數據。

因為查找數據需要遍歷鏈表，所以單純用鏈表實現的 LRU 緩存淘汰演算法的時間復雜很高，是 O(n)。如果我們將散列表和雙向鏈表兩種數據結構組合使用，可以將這三個操作的時間復雜度都降低到 O(1)。

因為我們的散列表是通過鏈表法解決散列沖突的，所以每個結點會在兩條鏈中。一個鏈是剛剛我們提到的雙向鏈表，另一個鏈是散列表中的拉鏈。前驅和後繼指針是為了將結點串在雙向鏈表中，hnext 指針是為了將結點串在散列表的拉鏈中。

這整個過程涉及的查找操作都可以通過散列表來完成。其他的操作，比如刪除頭結點、鏈表尾部插入數據等，通過雙向鏈表都可以在 O(1) 的時間復雜度內完成。所以，這三個操作的時間復雜度都是 O(1)。

至此，我們就通過散列表和雙向鏈表的組合使用，實現了一個高效的、支持 LRU 緩存淘汰演算法的緩存系統原型。

散列表中數據是經過散列函數打亂之後無規律存儲的，但是 LinkedHashMap可以 做到按照數據的插入順序來存儲。

每次調用 put() 函數，往 LinkedHashMap 中添加數據的時候，都會將數據添加到鏈表的尾部，再次將鍵值為 3 的數據放入到 LinkedHashMap 的時候，會先查找這個鍵值是否已經有了，然後，再將已經存在的 (3,11) 刪除，並且將新的 (3,26) 放到鏈表的尾部，訪問到 key 為 5 的數據的時候，我們將被訪問到的數據移動到鏈表的尾部。

所以按照訪問時間排序的 LinkedHashMap 本身就是一個支持 LRU 緩存淘汰策略的緩存系統。

散列表這種數據結構雖然支持非常高效的數據插入、刪除、查找操作，但是散列表中的數據都是通過散列函數打亂之後無規律存儲的。也就說，它無法支持按照某種順序快速地遍歷數據。如果希望按照順序遍歷散列表中的數據，那我們需要將散列表中的數據拷貝到數組中，然後排序，再遍歷。

因為散列表是動態數據結構，不停地有數據的插入、刪除，所以每當我們希望按順序遍歷散列表中的數據的時候，都需要先排序，那效率勢必會很低。為了解決這個問題，我們將散列表和鏈表（或者跳錶）結合在一起使用。

D. lru 淘汰演算法

最佳演算法（OPT演算法）

當需要淘汰一個內存頁面時，這種演算法力圖選擇該進程內存各個頁面中永遠不再需要的頁，若找不到，則選擇最久以後才會用到的頁。這種演算法有最小的缺頁率。問題是它需要知道運行進程今後的整個訪問蹤跡，這往往難以做到，因而它只有理論上的意義。

先進先出演算法（FIFO演算法）

FIFO演算法維護一個先進先出隊列，隊列長度為分配給這個進程的頁面數M。開始時隊列是空的，裝入進程的第一頁即可啟動運行，當訪問到某個不在內存的頁面時，把它從輔存調入，加入FIFO隊列的尾部。

最久未使用淘汰演算法（LRU演算法）

LRU（least recently used）演算法維護一個後進先出棧，棧大小為分配給這個進程的頁面數M。開始時棧是空的，裝入進程的第一頁即可啟動運行，當訪問到某個不在內存的頁面時，把它從輔存調入，加入棧頂。

FIFO和LRU演算法的例子：http://osjx.8100988.net/LWR/RAM/HLM/FIFOsf.HTM

CLOCK演算法

又叫NRU（Not Recently Used）演算法，NRU又名近似的LRU置換演算法。
當一存儲塊中的頁面訪問時，其相應的「頁面訪問」位由硬體自動置「1」，而由頁面管理體制軟體周期性地（設周期為T，其值通常為幾百毫秒），把所有的頁面訪問位重新置為「0」。這樣，在時間T內，某些被訪問的頁面，其對應的訪問位為「1」而未訪問的頁面，其對應的訪問位為「0」。查尋頁面訪問位為「0」的頁面。在查找過程中，那些被訪問的頁所對應的訪問位被重新置為「0」。由此可見，實際上這種近似LRU演算法，已經退化成一種「最近不用」的演算法NRU（Not Recently Used）。

CLOCK演算法的例子：http://www.cskaoyan.com/thread-4898-1-1.html

其實這個問題我也不太會，去臨時查的資料，第一個例子是我自己算的，不知道我理解得對不對；如果有錯誤的地方還請指正，共同進步~其他的演算法的例子我都給了鏈接，你自己去看吧。

E. 描述幾個常用的頁面轉換(淘汰)演算法基本原理

某虛擬存儲系統採用最近最少使用（LRU）頁面淘汰演算法，假定系統為每個作業分配3個頁面的主存空間，其中一個頁面用用來存放程序。現有某作業的部分語句如下：
Var A:Array[1...150,1...100] of integer；
i,j:interger;
for i=1 to 150 do
for j=1to 100 do a [i,,j]=0;
設每個頁面可存放150個證書變數，變數i，j放在程序頁中。初始時，程序及變數i，j已經在內存，其餘兩頁為空，舉證A按行序存放。在上述程序片段執行過程中，公產生（ ）次缺頁中斷。

每頁可以放150變數，而二維數組按行存儲，所以數組三行可以存入兩頁中，150行存入100頁中。循環也是按行操作，也就是每頁中的變數依次處理，各頁都在全處理完成後轉入下一頁處理（缺頁中斷），每頁只會發生一次缺頁中斷，所以缺頁中斷數為100。
程序段所在頁一直使用，所以在LRU演算法中不會被淘汰。另外兩個頁面在一段時間內只會使用一個頁面，直到它裡面的變數全處理完成，所以淘汰演算法會淘汰另外一頁用以裝入新頁，故不會造成額外的缺頁。

F. lru演算法是什麼

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

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

特點：

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

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

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

G. 頁面置換演算法之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實現——一個今日頭條的面試題