操作系統3-內存管理(頁面置換算法)
7. 頁面置換算法
在上一節講過, 換入換出頁面要根據特定的算法來執行, 這種算法就是頁面置換算法. 不合適的算法可能會使系統發生抖動，所謂抖動即指剛剛換出的頁面又要換回來，換回來不久又要換出去，這樣就導致系統的大部分工作時間都花在了頁面調度上，導致效率不高。
下面是幾種常見的頁面置換算法：
7.1 先入先出頁面置換算法
顧名思義，根據隊列的數據結構的思想，總是將內存存在最久的頁面先換出。
7.2 最近最久未使用頁面置換算法(Least Recently Used)
這種算法是一種比較好的算法，但是主要問題在於如何找到哪一頁是最近最久未被使用的頁面。為此需要兩類硬件的支持：
-
寄存器。用於記錄某進程在內存中各頁的使用情況。系統為內存中每個進程都設置一個移位寄存器，可表示為$ R = R_{n-1} R_{n-2} ...R_1 $。
當進程訪問某物理塊時，要將相應寄存器的(R_{n-1})位置變成1。此時，定時信號每隔一段時間將寄存器右移一位。如果把這個n位的寄存器看成是一個n位的二進制數，則最小數值的寄存器所對應的頁面就是最近最久未使用的頁面。
-
棧。利用一個特殊的棧來保存當前使用的各個頁面的頁號。每當進程訪問某頁面時，便將該頁面從棧中移出，壓入棧中。這樣，位於棧底的總是最近最久未被使用的頁面。(這個比較易於理解)
7.3 最佳置換算法(Optimal Page Replacement)
是Belady於1966年提出的一種理論上的理想算法，它所選擇的淘汰的頁面是最長時間不被使用的，可以保證最低的缺頁率。之所以說是理論算法是因為該算法需要知道該進程整體的頁面走向，即知道在哪一步需要用到哪一頁，但這是很難實現的。但是可以用來做算法題以及評價其他算法。
7.4 時鐘置換算法
這是一種LRU的近似算法，但不像LRU那樣需要很多的硬件支持。
時鐘置換算法為每一頁都設置一位訪問位，再將內存中所有頁面都通過鏈接指針連成一個隊列。當某頁被訪問時，則將該位置為1。由於將修改過的頁面換出時，頁面需要重新寫入外存，話費一定的時間。所以在選擇淘汰頁面時，要同時考慮到頁面的修改位和訪問位。根據訪問位和修改位可以組合成下列四種類型的頁面：
- (A = 0,M = 0)。最佳淘汰頁，既未被修改，又最近未被訪問。
- 最近未被訪問，但已修改，不是很好的淘汰頁。
- 最近訪問了，但未被修改。可能會再次訪問。
- 最近既被訪問了，又有修改。最後淘汰的頁面。
尋找過程：
- 第一輪：指針從當前位置開始掃描循環隊列，尋找A=0，M=0的頁面。第一次掃描期間不改變訪問位A。
- 第二輪：若第二輪未找到可以淘汰的頁面，則第二輪掃描A=0,M=1的頁面。第二輪掃描期間將掃描過的頁面的訪問位置為0。
- 如果第二輪扔失敗。則再回到開始位置重複第一輪，如果再失敗，則再重複第二輪，這是一定能找到目標淘汰頁。因為所有的訪問位都已置為0。