摘要：頁面置換算法是操作系統內存管理中的一個重要問題。為了研究不同頁面置換算法的區別與聯系以及它們對系統顛簸的影響，在此采用了將不同置換算法對比介紹的方法，闡釋了幾種常見的頁面置換算法的原理和思想，并通過它們對系統顛簸影響的分析實驗，得到了通過改進頁面置換算法解決系統顛簸的三個途徑。通過采用局部頁面置換算法，動態調整的頁面置換算法和跟蹤缺頁率，可以有效地實現系統顛簸的控制。

　　關鍵詞：頁面置換算法;系統顛簸;缺頁中斷;內存管理;操作系統;虛擬內存

　　0引言

　　在系統運行過程中，若程序所要訪問的頁面不在內存而需要把他們調入內存，但內存已經沒有空閑空間時，為了保證該進程能正常運行，系統必須從內存中調出一頁程序或數據送到磁盤的交換區中，這個過程稱為頁面置換。決定將哪個頁面調出，需根據一定的算法來確定，通常，把選擇換出頁面的算法成為頁面置換算法。

　　置換算法的好壞，將直接影響到系統的性能。當發生缺頁中斷時，雖然可以隨機地選擇一個頁面置換，但是如果一個被頻繁使用的頁面被置換出內存，很可能它在很短時間內又要被調入內存，這會帶來不必要的開銷。一個好的頁面置換算法，應具有較低的頁面更換頻率。從理論上講，應將那些以后不再會訪問的頁面置換出，或者把那些在較長時間內不會再訪問的頁面調出。這對提高系統性能極其重要。

　　1常見的頁面置換算法

　　1.1最優頁面置換算法

　　1.1.1算法思想介紹

　　最佳頁面置換算法(OptimalPageReplacementAlgorithm，OPT)是一種理想情況下的頁面置換算法，它在所有頁面置換算法中產生的頁錯誤率最低，但實際上該算法是不可能實現的。

　　該算法的基本思想是：發生缺頁時，有些頁面在內存中，其中有一頁將很快被訪問(也就是下一條指令要訪問的那一頁)，而其他頁面則可能要到10、100或者1000條指令后才會被訪問，每個頁面都可以用在該頁面首次被訪問前所要執行的指令數進行標記。

　　最佳頁面置換算法規定：標記最大的頁應該被置換。例如，如果某頁在800萬條指令內不會被使用，另一頁在600萬條指令內不會被使用，則置換前一個頁面。這個算法惟一的一個問題就是它無法實現，因為當缺頁發生時，操作系統無法知道各個頁面下一次是在什么時候被訪問。雖然最佳頁面置換算法不可能實現，但是該算法可以用于對可實現算法的性能進行衡量比較。如果一個頁面置換算法不是最優的，但是它的性能與最優置換相比相差不大(如僅有2%的性能差距)，那么就可以判定該算法是有實用價值的。

　　1.1.2算法分析

　　從理論上說，當置換一個頁面出內存時，被置換出的頁面在將來仍然需要被訪問，那個時候將發生缺頁中斷。既然不好的事情(缺頁中斷)總會發生，計算機也和人一樣，希望把不愉快的事情盡可能地向后拖延。一個最好的頁面置換算法應該把因為需要調入這個頁面而發生的缺頁中斷推遲到將來，越久越好。因此選擇最久之后才會被訪問的頁面換出內存是理論上最佳的，這也是這個算法被稱為最優置換的原因。

　　1.2先進先出頁面置換算法(FIFO)

　　1.2.1算法思想介紹

　　FIFO算法總是淘汰在內存中停留得最久的那個頁面。具體實現方法是由操作系統維護一個所有當前在內存中的頁面的鏈表，最新進入的頁面放在表尾，最久進入的頁面放在表頭。當發生缺頁中斷時，淘汰表頭頁面并把新調入的頁面加到表尾。FIFO頁面置換算法容易理解和實現，但是其性能并不總是很好。

　　1.2.2算法分析

　　FIFO算法僅僅考慮到在內存中滯留了很久的頁面的需求性可能比新進入的頁面更小。就像在超級市場中，新引進的商品往往比已經庫存了很久的商品更容易被購買，因此當新引進商品時，通常淘汰那個庫存了最久的商品。

　　但是這種考慮顯然不太準確，誰說新上架的東西一定比庫存很久的東西更有用呢?考慮一個頁面，它在很早的時候被調入內存，之后被頻繁的引用，這個頁面很容易被FIFO算法當作沒用的頁面從而被淘汰。因此純粹的FIFO算法很容易淘汰重要的頁面，實際很少使用。

　　1.3第二次機會頁面置換算法

　　1.3.1算法思想介紹

　　第二次機會頁面置換算法是對FIFO算法的改進。它在FIFO的基礎上進行了修改，其性能較FIFO有了很大的提高，避免了把經常使用的頁面置換出去。

　　和FIFO算法一樣，操作系統維護一個所有當前在內存中的頁面的鏈表，最新進入的頁面放在表尾，最久進入的頁面放在表頭。當需要置換頁面是，檢查最老頁面的R位，如果它為0，表示它最近未被使用，也就是說，它又老又沒用，可以立即置換。如果是1，則把R位置為0，并把該頁面放在鏈表尾端(即把它作為剛裝入的頁面一樣)，然后繼續搜索。

　　1.3.2算法示例

　　如圖1(a)所示，頁面A到頁面H按照進入內存的時間先后順序保存在鏈表中。頁面上的數字是該頁面進入內存時的時間。第二次機會算法的一個執行示例過程如下：

　　(1)在時間20發生了一次缺頁中斷;

　　(2)檢查最老的頁面A，如果A的R位為0，則將它淘汰出內存;

　　(3)現在頁面A的R位為1，則將A放到鏈表的尾部，并且重新設置頁面的進入時間為當前時刻，并置A的R位為0。即讓A頁面好像是剛剛調入內存一樣;

　　(4)檢查當前最老的頁面B，重復以上過程。

　　可以看出在上面的過程中，如果A到H頁面都被訪問過了，那么在遍歷了一次之后，仍然是頁面A被淘汰，此算法就變成了純粹的FIFO算法。

　　1.3.3算法分析

　　該算法的思想是找到一個最近的時鐘滴答中從來沒有被訪問過的頁面，而且這個頁面是最老的(最先調入內存)，這樣綜合了兩個方面的考慮：

　　(1)老的頁面比新的頁面需求量小(FIFO算法的想法)

　　(2)局部性：最近未被訪問的頁面今后也可能不被訪問

　　并且算法優先考慮局部性，例如在上面的過程中，如果A～H頁面都被訪問過了，那么在遍歷了一次之后，仍然是最老的頁面A被淘汰，此算法就變成了純粹的FIFO算法。