LRU

LRU是Least Recently Used的縮寫，即最近最少使用，是一種常用的頁面置換算法，選擇最近最久未使用的頁面予以淘汰。該算法賦予每個頁面一個訪問欄位，用來記錄一個頁面自上次被訪問以來所經歷的時間 t，當須淘汰一個頁面時，選擇現有頁面中其 t 值最大的，即最近最少使用的頁面予以淘汰。

基本介紹

• 中文名：最近最少使用
• 外文名：Least Recently Used
• 學科：計算機
• 簡寫：LRU
• 有關術語：頁面置換算法
• 套用：記憶體管理

簡介

最近最少使用算法（LRU）是大部分作業系統為最大化頁面命中率而廣泛採用的一種頁面置換算法。該算法的思路是，發生缺頁中斷時，選擇未使用時間最長的頁面置換出去。從程式運行的原理來看，最近最少使用算法是比較接近理想的一種頁面置換算法，這種算法既充分利用了記憶體中頁面調用的歷史信息，又正確反映了程式的局部問題。利用 LRU 算法對上例進行頁面置換的結果如圖1所示。當進程第一次對頁面 2 進行訪問時，由於頁面 7 是最近最久未被訪問的，故將它置換出去。當進程第一次對頁面 3進行訪問時，第 1 頁成為最近最久未使用的頁，將它換出。由圖1可以看出，前 5 個時間的圖像與最佳置換算法時的相同，但這並非是必然的結果。因為，最佳置換算法是從“向後看”的觀點出發的，即它是依據以後各頁的使用情況；而 LRU 算法則是“向前看”的，即根據各頁以前的使用情況來判斷，而頁面過去和未來的走向之間並無必然的聯繫。

圖 1 LRU 頁面置換算法

硬體支持

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

暫存器

為了記錄某進程在記憶體中各頁的使用情況，須為每個在記憶體中的頁面配置一個移位暫存器，可表示為

R = R_n-1 R_n-2 R_n-3 … R₂ R₁ R₀

當進程訪問某物理塊時，要將相應暫存器的 R _{n -1} 位置成 1。此時，定時信號將每隔一定時間(例如 100 ms)將暫存器右移一位。 如果我們把 n 位暫存器的數看做是一個整數， 那么，具有最小數值的暫存器所對應的頁面，就是最近最久未使用的頁面。圖2示出了某進程在記憶體中具有 8 個頁面，為每個記憶體頁面配置一個 8 位暫存器時的 LRU 訪問情況。這裡，把 8 個記憶體頁面的序號分別定為 1～8。由圖可以看出，第 3 個記憶體頁面的 R 值最小，當發生缺頁時，首先將它置換出去。

圖 2 某進程具有 8 個頁面時的 LRU 訪問情況

棧

可利用一個特殊的棧來保存當前使用的各個頁面的頁面號。每當進程訪問某頁面時，便將該頁面的頁面號從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的編號，而棧底則是最近最久未使用頁面的頁面號。假定現有一進程所訪問的頁面的頁面號序列為：

圖 3 用棧保存當前使用頁面時棧的變化情況

4，7，0，7，1，0，1，2，1，2，6

隨著進程的訪問， 棧中頁面號的變化情況如圖 3 所示。 在訪問頁面 6 時發生了缺頁，此時頁面 4 是最近最久未被訪問的頁，應將它置換出去。

其它頁面置換算法

在進程運行過程中，若其所要訪問的頁面不在記憶體而需把它們調入記憶體，但記憶體已無空閒空間時，為了保證該進程能正常運行，系統必須從記憶體中調出一頁程式或數據送磁碟的對換區中。但應將哪個頁面調出，須根據一定的算法來確定。通常，把選擇換出頁面的算法稱為頁面置換算法(Page-Replacement Algorithms)。 置換算法的好壞， 將直接影響到系統的性能。一個好的頁面置換算法，應具有較低的頁面更換頻率。從理論上講，應將那些以後不再會訪問的頁面換出，或把那些在較長時間內不會再訪問的頁面調出。存在著許多種置換算法，它們都試圖更接近於理論上的目標。

最佳置換算法（OPT）

這是一種理想情況下的頁面置換算法，但實際上是不可能實現的。該算法的基本思想是：發生缺頁時，有些頁面在記憶體中，其中有一頁將很快被訪問（也包含緊接著的下一條指令的那頁），而其他頁面則可能要到10、100或者1000條指令後才會被訪問，每個頁面都可以用在該頁面首次被訪問前所要執行的指令數進行標記。最佳頁面置換算法只是簡單地規定：標記最大的頁應該被置換。這個算法唯一的一個問題就是它無法實現。當缺頁發生時，作業系統無法知道各個頁面下一次是在什麼時候被訪問。雖然這個算法不可能實現，但是最佳頁面置換算法可以用於對可實現算法的性能進行衡量比較。

先進先出置換算法（FIFO）

最簡單的頁面置換算法是先入先出（FIFO）法。這種算法的實質是，總是選擇在主存中停留時間最長（即最老）的一頁置換，即先進入記憶體的頁，先退出記憶體。理由是：最早調入記憶體的頁，其不再被使用的可能性比剛調入記憶體的可能性大。建立一個FIFO佇列，收容所有在記憶體中的頁。被置換頁面總是在佇列頭上進行。當一個頁面被放入記憶體時，就把它插在隊尾上。這種算法只是在按線性順序訪問地址空間時才是理想的，否則效率不高。因為那些常被訪問的頁，往往在主存中也停留得最久，結果它們因變“老”而不得不被置換出去。

FIFO的另一個缺點是，它有一種異常現象，即在增加存儲塊的情況下，反而使缺頁中斷率增加了。當然，導致這種異常現象的頁面走向實際上是很少見的。

最少使用（LFU）置換算法

在採用最少使用置換算法時，應為在記憶體中的每個頁面設定一個移位暫存器，用來記錄該頁面被訪問的頻率。該置換算法選擇在之前時期使用最少的頁面作為淘汰頁。由於存儲器具有較高的訪問速度，例如100 ns，在1 ms時間內可能對某頁面連續訪問成千上萬次，因此，通常不能直接利用計數器來記錄某頁被訪問的次數，而是採用移位暫存器方式。每次訪問某頁時，便將該移位暫存器的最高位置1，再每隔一定時間(例如100 ns)右移一次。這樣，在最近一段時間使用最少的頁面將是∑Ri最小的頁。LFU置換算法的頁面訪問圖與LRU置換算法的訪問圖完全相同；或者說，利用這樣一套硬體既可實現LRU算法，又可實現LFU算法。應該指出，LFU算法並不能真正反映出頁面的使用情況，因為在每一時間間隔內，只是用暫存器的一位來記錄頁的使用情況，因此，訪問一次和訪問10 000次是等效的。