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 243 2

1 124 3

5 512 4

6 651 2

2 265 1

1 126 5

2 216

3 321 6

7 732 1

6 673 2

3 367 3

2 236 7

1 123 6

2 213

3 312

6 631 2

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

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

寄存器

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

R = Rn-1 Rn-2 Rn-3 … R2 R1 R0

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

棧

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

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次是等效的。