lru頁面淘汰演算法

① lru演算法是什麼呢

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

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

LRU原理

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

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

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

某虛擬存儲系統採用最近最少使用（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演算法中不會被淘汰。另外兩個頁面在一段時間內只會使用一個頁面，直到它裡面的變數全處理完成，所以淘汰演算法會淘汰另外一頁用以裝入新頁，故不會造成額外的缺頁。

③ lru演算法是什麼

是一種緩存淘汰策略。計算機的緩存容量有限，如果緩存滿了就要刪除一些內容，給新內容騰位置。大家肯定希望刪掉哪些沒什麼用的緩存，而把有用的數據繼續留在緩存里，方便之後繼續使用。

計算機（computer）俗稱電腦，是現代一種用於高速計算的電子計算機器，可以進行數值計算，又可以進行邏輯計算，還具有存儲記憶功能。是能夠按照程序運行，自動、高速處理海量數據的現代化智能電子設備。

由硬體系統和軟體系統所組成，沒有安裝任何軟體的計算機稱為裸機。可分為超級計算機、工業控制計算機、網路計算機、個人計算機、嵌入式計算機五類，較先進的計算機有生物計算機、光子計算機、量子計算機等。

發展歷史

計算工具的演化經歷了由簡單到復雜、從低級到高級的不同階段，例如從「結繩記事」中的繩結到算籌、算盤計算尺、機械計算機等。它們在不同的歷史時期發揮了各自的歷史作用，同時也啟發了現代電子計算機的研製思想。

1889年，美國科學家赫爾曼·何樂禮研製出以電力為基礎的電動製表機，用以儲存計算資料。

④ 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 緩存淘汰策略的緩存系統。

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

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

⑤ lru演算法是什麼

是一種緩存淘汰策略。計算機的緩存容量有限，如果緩存滿了就要刪除一些內容，給新內容騰位置。大家肯定希望刪掉哪些沒什麼用的緩存，而把有用的數據繼續留在緩存里，方便之後繼續使用。

LRU緩存淘汰演算法就是一種常用策略，也就是說認為最近使用過的數據應該是是「有用的」，很久都沒用過的數據應該是無用的，內存滿了就優先刪那些很久沒用過的數據。

LRU-K原理

LRU-K中的K代表最近使用的次數，因此LRU可以認為是LRU-1。LRU-K的主要目的是為了解決LRU演算法「緩存污染」的問題，其核心思想是將「最近使用過1次」的判斷標准擴展為「最近使用過K次」。

相比LRU，LRU-K需要多維護一個隊列，用於記錄所有緩存數據被訪問的歷史。只有當數據的訪問次數達到K次的時候，才將數據放入緩存。當需要淘汰數據時，LRU-K會淘汰第K次訪問時間距當前時間最大的數據。

⑥ 最佳頁面淘汰演算法是怎樣計算的

1;
50%指令順序執行
2;25%指令均勻散步在前地址部分
3;25%指令均勻散步在後地址部分
題目中選用:命中率=1-頁面失敗次數(只選用2的冪次)/葉地址流長度
演算法:opt
fifo
rlu(定義)(至少用兩個演算法)程序流程圖開始:產生給定長度符合假定的指令地址流->為每一個指令地址的成對應的訪問頁號->置初算size=1~8(1,2,4,8)(頁面大上)實存
=4~32(4,8,16,32)->輸入淘汰演算法->A->ALG=FIFO(OR)(LRU)->FIFO->用FIFO計算命中率->用LRU計算命中率->輸出結果->結束演算法定義:理想淘汰演算法--最佳頁面演算法(OPT)
淘汰以後不再需要的或最遠的將來才會用到的頁面
先進先出頁面淘汰演算法(FIFO)
選擇在內存中駐留時間最長的頁並淘汰之
最近最少使用頁面淘汰演算法(LRU)
選擇最後一次訪問時間距離當前時間最長的一頁並淘汰之即淘汰沒有使用的時間最長的頁.

⑦ lru頁面置換演算法是什麼

用雙向鏈表和哈希表來實現。

LRU演算法的提出，是基於這樣一個事實：在前面幾條指令中使用頻繁的頁面很可能在後面的幾條指令中頻繁使用。

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

一種LRU近似演算法是最近未使用演算法。

它在存儲分塊表的每一表項中增加一個引用位，操作系統定期地將它們置為0。當某一頁被訪問時，由硬體將該位置1。過一段時間後，通過檢查這些位可以確定哪些頁使用過，哪些頁自上次置0後還未使用過。就可把該位是0的頁淘汰出去，因為在之前最近一段時間里它未被訪問過。

以上內容參考：網路-頁面置換演算法

⑧ 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

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

⑨ 資料庫LRU 頁面淘汰演算法

餓，LRU 最近最久未使用演算法

當前頁面內容：
頁面一 2 2 2 1 1 1 4

頁面二 3 3 3 5 5 5

頁面三 2 2 2 2 2

頁面訪問順序 2 3 2 1 5 2 4 .............
缺 缺 缺 缺 缺 不缺 缺
注意這步 和下面那步

這只是個演算法，和資料庫之類的沒關系

我暈 ，幾行內容咋對不上，我編輯時是正常的