LRU

記憶體管理的一種頁面置換算法，對於在記憶體中但又不用的數據塊（記憶體塊）叫做LRU，作業系統會根據哪些數據屬於LRU而將其移出記憶體而騰出空間來載入另外的數據。 什麼是LRU算法？ LRU是Least Recently Used的縮寫，即最近最少使用，常用於頁面置換算法，是為虛擬頁式存儲管理服務的。 關於作業系統的記憶體管理，如何節省利用容量不大的記憶體為最多的進程提供資源，一直是研究的重要方向。而記憶體的虛擬存儲管理，是現在最通用，最成功的方式—— 在記憶體有限的情況下，擴展一部分外存作為虛擬記憶體，真正的記憶體只存儲當前運行時所用得到信息。這無疑極大地擴充了記憶體的功能，極大地提高了計算機的並發度。虛擬頁式存儲管理，則是將進程所需空間劃分為多個頁面，記憶體中只存放當前所需頁面，其餘頁面放入外存的管理方式。 然而，有利就有弊，虛擬頁式存儲管理增加了進程所需的記憶體空間，卻也帶來了運行時間變長這一缺點：進程運行過程中，不可避免地要把在外存中存放的一些信息和記憶體中已有的進行交換，由於外存的低速，這一步驟所花費的時間不可忽略。因而，採取儘量好的算法以減少讀取外存的次數，也是相當有意義的事情。

基本信息

• 中文名：LRU
• 其他外文名：Least Recently Used
• 定義：虛擬頁式存儲管理服務

• 差 距：最少使用頁面置換算法
• 例 子：LRU最少使用
• 參考資料：這三種置換算法的缺頁次數

說明

對於虛擬頁式存儲，內外存信息的替換是以頁面為單位進行的——當需要一個放在外存的頁面時，把它調入記憶體，同時為了保持原有空間的大小，還要把一個記憶體中的頁面調出至外存。這種調動越少，進程執行的效率也就越高。那么，把哪個頁面調出去可以達到調動儘量少的目的？我們需要一個算法。

其實，達到這樣一種情形的算法是最理想的了——每次調換出的頁面是所有記憶體頁面中最遲將被使用的——這可以最大限度的推遲頁面調換，這種算法，被稱為理想頁面置換算法。可惜的是，這種算法是無法實現的。

差距

為了儘量減少與理想算法的差距，產生了各種精妙的算法，最少使用頁面置換算法便是其中一個。LRU算法的提出，是基於這樣一個事實：在前面幾條指令中使用頻繁的頁面很可能在後面的幾條指令中頻繁使用。反過來說，已經很久沒有使用的頁面很可能在未來較長的一段時間內不會被用到。這個，就是著名的局部性原理——比記憶體速度還要快的cache，也是基於同樣的原理運行的。因此，我們只需要在每次調換時，找到最近最久未使用的那個頁面調出記憶體。這就是LRU算法的全部內容。

LRU在電子系統中的解釋：

Line Replaceable Unit — LRU，電子系統中常採用模組化設計，這種可更換的模組單元則被叫做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

又如：

考慮下述頁面走向：

1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6

1 1

2 21

3 321

4 432 1

2 2 4 3 1

1 1 2 4 3

5 5 1 2 4

6 6 5 1 2

2 2 6 5 1

1 1 2 6 5

2 2 1 6 5

3 3 2 1 6

7 7 3 2 1

6 6 7 3 2

3 3 6 7 2

2 2 3 6 7

1 1 2 3 6

2 2 1 3 6

3 3 2 1 6

6 6 3 2 1

LRU

發生缺頁中斷的次數為15。在LRU算法中，最少使用的頁面被先換出。當頁6要調入時，記憶體的狀態為5、1、2，考查頁6之前調入的頁面，分別為5、1、2，可見2為一段時間內使用最少的，本次應換出，然後把頁6調入記憶體。