lru算法

lru算法

lru算法是一種常用的頁面置換算法，選擇最近最久未使用的頁面予以淘汰。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經(jīng)歷的時間 t，當須淘汰一個頁面時，選擇現(xiàn)有頁面中其 t 值最大的，即最近最少使用的頁面予以淘汰。

LRU算法是大部分操作系統(tǒng)為最大化頁面命中率而廣泛采用的一種頁面置換算法。該算法的思路是，發(fā)生缺頁中斷時，選擇未使用時間最長的頁面置換出去。從程序運行的原理來看，最近最少使用算法是比較接近理想的一種頁面置換算法，這種算法既充分利用了內(nèi)存中頁面調(diào)用的歷史信息，又正確反映了程序的局部問題。利用 LRU 算法對上例進行頁面置換的結(jié)果如圖1所示。當進程第一次對頁面 2 進行訪問時，由于頁面 7 是最近最久未被訪問的，故將它置換出去。當進程第一次對頁面 3進行訪問時，第 1 頁成為最近最久未使用的頁，將它換出。由圖1可以看出，前 5 個時間的圖像與最佳置換算法時的相同，但這并非是必然的結(jié)果。因為，最佳置換算法是從“向后看”的觀點出發(fā)的，即它是依據(jù)以后各頁的使用情況;而 LRU 算法則是“向前看”的，即根據(jù)各頁以前的使用情況來判斷，而頁面過去和未來的走向之間并無必然的聯(lián)系。