LRU

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

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

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

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

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

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

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

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

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