【例】在一個請求分頁存儲管理系統中進程P共有頁訪問串為OO時試采用LRU置換算法和LFU算法計算當分配給該進程的頁面數分別為和時訪問過程中發生的缺頁次數和缺頁率比較所得的結果分析原因（北方名校經典試題）
【分析】最近最久未使用（LRU）算法的基本思想是用最近的過去估計最近的將來假定在內存中的某個頁面在最近的一段時間內未被使用的時間最長那麼在最近的將來也可能不再被使用
最近最少使用LFU算法把在最近的一段時間內使用次數最少的頁面置換掉
一般來說頁框數目越多缺頁率也會相應降低
【解答】LRU算法如表所示頁框
表 LRU算法（頁框）的缺頁情況
缺頁
LRU算法缺頁缺頁率為/=%
LRU算法如表所示頁框
表 LRU算法（頁框）的缺頁情況
缺頁
LRU算法缺頁缺頁率為/=%
LFU算法如表所示頁框
LFU算法的缺頁情況
缺頁
LFU算法缺頁缺頁率為/=%
LFU算法如表所示頁框
表 LFU算法的缺頁情況
缺頁
LFU算法缺頁缺頁率為/=%
由上表可以得知內存分配的頁框越多缺頁中斷率就越低在這個例子中LFU甚至比LRU的缺頁中斷率還要低但實際上LFU並不能真正反映頁面的使用情況
在采用LFU算法時應為在內存中的每個頁面設置都有一個移位寄存器用來記錄該頁面被訪問的頻率該置換算法選擇在最近時期使用最少的頁面作為淘汰頁由於存儲器具有較高的訪問速度例如ns在ms時間內可能對某頁面連續訪問成千上萬次因此通常不能直接利用計數器來記錄對某頁的訪問次數而是采用移位寄存器方式每次訪問某頁時便對該頁移位寄存器的最高位置再每隔一定時間（例如ms）右移一次這樣在最近一段時間使用最少的頁面將是∑Ri最小的頁LFU置換算法的頁面的訪問圖與LRU置換算法的圖完全相同或者說是利用這樣一套硬件既可實現LRU算法也可實現LFU算法應該指出這種算法並不能真正反映出頁面的使用情況因為在每一時間間隔內只是用寄存器的一位來記錄頁的使用情況因此訪問一次和訪問次是等效的
返回《操作系統考研輔導教程》
[] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/czxt/201311/24100.html
