最近最久未使用演算法賦予每個頁面

A. 頁式管理的請求頁式管理中的置換演算法

功能：需要調入頁面時，選擇內存中哪個物理頁面被置換。稱為replacement policy。
出發點：把未來不再使用的或短期內較少使用的頁面調出，通常只能在局部性原理指導下依據過去的統計數據進行預測。
頁面鎖定(frame locking)：用於描述必須常駐內存的操作系統的關鍵部分或時間關鍵(time-critical)的應用進程。實現方法為在頁表中加上鎖定標志位(lock bit)。 輪轉法(RR,round robin)和先進先出演算法(FIFO,first in first out):輪轉法循回換出內存可用區內一個可以被換出的頁，無論該頁是剛被換進或已換進內存很長時間。FIFO演算法總是選擇在內存駐留時間最長的一員將其淘汰。
FIFO演算法認為先調入內存的頁不再被訪問的可能性要比其它頁大，因而選擇最先調入內存的頁換出。實現FIFO演算法需要把各個已分配頁面按分配時間順序鏈接起來，組成FIFO隊列，並設置一置換指針指向FIFO隊列的隊首頁面。這樣，當要進行置換時，只需把置換指針所指的FIFO隊列前頭的頁順次換出，而把換入的頁鏈接在FIFO隊尾即可。
由實驗和測試發現FIPO演算法和RR演算法的內存利用率不高。這是因為，這兩種演算法都是基於CPU按線性順序訪問地址空間這一假設。事實上，許多時候．CPU不是按線性順序訪問地址空間的。
Belady現象:一般來說，對於任一作業或進程，如果給它分配的內存頁面數越接近於它所要求的頁面數，則發生缺頁的次數會越少。在極限情況下，這個推論是成立的。因為如果給一個進程分配了它所要求的全部頁面，則不會發生缺頁現象。但是，使用FIFO演算法時，在未給進程或作業分配足它所要求的頁面數時，有時會出現分配的頁面數增多，缺頁次數反而增加的奇怪現象。這種現象稱為Belady現象。 最近最久未使用頁面置換演算法(LRU, Least Recently Used):
選擇內存中最久未使用的頁面被置換。這是局部性原理的合理近似，性能接近最佳演算法。但由於需要記錄頁面使用時間的先後關系，硬體開銷太大。硬體機構如：
(1) 一個特殊的棧：把被訪問的頁面移到棧頂，於是棧底的是最久未使用頁面。
(2) 每個頁面設立移位寄存器：被訪問時左邊最高位置1，定期右移並且最高位補0，於是寄存器數值最小的是最久未使用頁面。
比較常用的近似演算法有：
(a) 最不經常使用頁面淘汰演算法(LFU, Least Frequently Used)
(b) 最近沒有使用頁面淘汰(NRU, Not Recently Used) 理想型淘汰演算法（OPT,Optimal Replacement Algorithm）
該演算法淘汰在訪問串中將來再也不出現的或是離當前最遠的位置上出現的頁。它是一種理想化的演算法，性能最好，但在實際上難於實現。