虛擬記憶體之頁面替換演算法

先來寫些關於頁面替算演算法的心得。

分類可分三類:

1.先進先出演算法(FIFO)

2.最久未用演算法(LRU)

3.最久未用近似法(LRU近似)

先進先出演算法(FIFO)

和這個頁面替換法相關的資訊是頁面的「載入時間」,「載入時間」越早的頁面會被替換出去,所以這個演算法才叫「先進先出」。載入時間是指第一次載入到頁框的時間,所以如果之前被換出然後再重新載入進來,最近載入進來的時間才是它的載入時間。

最久未用演算法(LRU)

和這個頁面替換法相關的資訊是頁面的「存取時間」,「存取時間」越久之前的頁面會被替換出去,因為最久沒用嘛,所以這個演算法才叫「最久未用」。存取時間是指頁面被存取時所記錄的時間,如果載入之後一直沒有被存取,它的存取時間就會一直維持不變。

最久未用近似法(LRU近似)
老化演算法

此演算法是替頁框加上一個參考位元組(byte),當該頁面被存取時,這個參考位元組的最左邊的位元會設為1,例:10000000,然後利用計時器中斷,定期將所有頁面的參考位元組向右移一個位元,最左邊的位元則補0,例:01000000,此動作相當於將原本的值除以2。在需要頁面替換的時候,會以參考位元組最小的頁面優先替換,因為經常使用的頁面它的最左邊位元經常補1,所以參考位元組的值最小,代表該頁面的使用頻率越小,就類似最久未用。

二次機會演算法

在這個方法下,每個頁框會對應到一個參考位元,它的初始值為0,當頁面被存取時它會被設為1。當系統要進行頁面替換時,會先以FIFO法找到最早載入的頁面,然後看它的參考位元是不是0,如果是0則替換該頁面;如果是1,則把它設為0,並將它在FIFO法下的搜尋順序移到最後,然後再繼續從頭開始找頁面,看看參考位元是不是0。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

Proudly using Dynamic Headers by Nicasio WordPress Design