頁面置換算法與系統顛簸分析

2013-04-12 00:00:00潘亮銘汪夢澤

現代電子技術 2013年20期

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

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

中圖分類號： TN964?34 文獻標識碼： A 文章編號： 1004?373X（2013）20?0065?06

0 引言

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

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

1 常見的頁面置換算法

1.1 最優頁面置換算法

1.1.1 算法思想介紹

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

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

最佳頁面置換算法規定：標記最大的頁應該被置換。例如，如果某頁在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算法。

當選擇置換頁面時，依然和FIFO一樣，選擇最早置入內存的頁面。但是二次機會法還設置了一個訪問狀態位。所以還要檢查頁面的的訪問位。如果是0，就淘汰這頁；如果訪問位是1，就給它第二次機會，并選擇下一個FIFO頁面。當一個頁面得到第二次機會時，它的訪問位就清為0，它的到達時間就置為當前時間。如果該頁在此期間被訪問過，則訪問位置為1。這樣給了第二次機會的頁面將不被淘汰，直至所有其他頁面被淘汰過（或者也給了第二次機會）。因此，如果一個頁面經常使用，它的R位總保持為1，它就從來不會被淘汰出去。算法的這個特點使它被稱為第二次機會算法。

1.4 時鐘頁面置換算法

時鐘頁面置換算法是對第二次機會算法的改進，也是現實中最常用的頁面置換算法之一。第二次機會算法比較合理，但是效率較低，由于它經常需要在鏈表中移動頁面。因此，時鐘頁面置換算法改進了鏈表的組織方式。它將所有頁面放置在一個類似鐘面的環形鏈表中，用一個表針指向最老的頁面。

當發生缺頁中斷時，算法首先檢查表指針指向的頁面，如果它的R位是0就淘汰該頁面，并把置換進來的新的頁面插入到這個位置，然后把表針前移一個位置。如果R位是1，那么清除R位并把表針前移一個位置。重復這個過程直到找到了一個R位為0的頁面為止。

算法的示意圖如圖2所示。

1.5 最近最少使用頁面置換算法（LRU）

1.5.1 算法思想介紹

LRU算法基于這樣的原理：在前面幾條指令中頻繁使用的頁面很可能在后面幾條指令中被使用。而已經很久沒有使用的頁面很有可能在未來較長的一段時間內仍然不會被使用。

因此，可以置換未使用時間最長的頁面。這個策略就是LRU（最近最少未使用）頁面置換算法的核心。顯然，LRU算法的主要問題是如何找出最近未被使用時間最長的頁面。

1.5.2 LRU算法的實現方法

方式1：硬件有一個64位的計數器C，它在每條指令執行完后自動加1。每個頁表項中有一個足夠容納這個計數器值的域。在每次訪問內存之后，將當前的C值保存到被訪問頁面的頁表項中。發生缺頁中斷時，操作系統檢查所有頁表項中計數器的值，找到一個該值最小的頁面，這個頁面顯然就是最近最少使用的頁面。

方式2：在一個有n個頁幀的機器中，LRU硬件維持一個初值都為0的n×n位矩陣。當訪問到頁幀k時，硬件首先把k行的位都置為1，再把第k列的位都置為0。在任何時刻，二進制數值最小的行就是最近最少使用的，第二小的行是下一個最近最少使用的，以此類推。

1.5.3 LRU算法的優缺點

LRU的優點是性能很好，它提供了對最優頁面置換算法很好的近似，并且它在理論上可以實現。但是LRU算法的缺點在于它實際上實現很難。因為以上討論的實現方式都需要硬件的參與，在現實中只有非常少的計算機擁有這種硬件。通常在實踐中，人們使用軟件方案實現一個LRU的近似算法。最著名的近似LRU算法是最不經常使用頁面置換算法（NFU）和老化算法。

1.6 最不經常使用頁面置換算法（NFU）

1.6.1 算法思想介紹

最不經常使用頁面置換算法（NFU）是一種用軟件實現的對LRU粗略的近似。

算法的基本思想是每個頁面擁有一個軟件計數器，計數器的初始值為0。每次時鐘中斷時，操作系統掃描內存中的所有頁面，將每個頁面的R位加到它的計數器上。（R為1則代表在最近的一個時鐘周期內頁面被訪問了，因此頁面的該計數器值大致代表了該頁面被訪問了多少次）。在N個時鐘周期內，如果頁面有m次R位為1，則表示N個時鐘周期內，在m個時鐘周期里該頁面被訪問了，因此這個計數器跟蹤了該頁面被訪問的頻繁程度。發生缺頁中斷時，將置換計數器值最小的頁面。

算法蘊含的思想是：統計從程序開始運行到現在為止，每個頁面被訪問的頻繁程度。換頁時，選擇訪問最不頻繁的頁面換出內存。

1.6.2 NFU算法的問題

NFU算法的問題，用一句話簡單概括就是：它從來不忘記任何事情。

例如，可能某頁面一開始被頻繁使用，其計數器值可能已經高達10 000，但是這個頁面在程序運行后期就很少使用了。但是由于前期的頻繁訪問，它的計數器值已經很高了，因此按NFU算法的原理，它很難被換出，盡管它應該在程序執行的后期被換出才是合理的。

1.7 老化算法

1.7.1 算法思想介紹

老化算法是對NFU的一個修改，實現了對LRU的很好的近似。

對NFU的修改：

在R位被加進之前先將計數器右移1位。

將R位加到計數器最左端的位而不是最右端的位。

發生缺頁中斷時，將置換計數器值最小的頁面。

1.7.2 算法示例

如圖3所示，一開始5個頁面的計數器值均為0。第0個時鐘周期內，各個頁面的R位分別為1，0，1，0，1，1，將其加到計數器的最左端得到圖 3（a）。第1個時鐘周期內，各個頁面的R位分別為1，1，0，0，1，0，將其加到計數器的最左端得到圖3（b）。依此類推，如果圖3（e）時發生缺頁中斷，那么計數器值最小的頁面3將被置換。

圖3 老化算法示例

1.7.3 算法分析

這個算法解決了NFU的問題，如果一個頁面前期頻繁訪問，如值為11111111，但是后期不再被訪問，它的計數器值會越來越小，從01111111到00111111到00011111到00001111……；相反，如果一個頁面前期不被訪問，后期頻繁訪問，它的計數器值會越來越大，從00000000到10000000到11000000到11100000……。

一個在最近一個時鐘周期內被訪問的頁面獲得的計數器增量是最大的（左端加1，相當于給計數器加了10000000），由于頁面最近一次時鐘周期被訪問了，表示以后可能也要被訪問，這個信息的參考價值是最大的，應該提供最大的計數器增量，這是很合理的。而在前一個時鐘周期內被訪問的頁面獲得的計數器增量會慢慢變小，由于這個訪問記錄逐漸成為了歷史，可參考價值越變越低，這樣設計也是很正常的。這就是蘊含在算法背后的思想。

為什么說老化算法只是LRU的一個近似？下面用一個例子來說明。頁面A和頁面B的計數器分別為00100000和00101000。它們都是在最近的兩個時鐘周期內未被訪問，但是沒有精確的記錄。

LRU中是按指令而不是時鐘周期記錄的，老化算法中只知道它們都是在最近的兩個時鐘周期內未被訪問，但是不知道具體的先后順序（一個時鐘周期有多個指令，A，B總有一個更先被訪問）。因此在老化算法中只能看它們計數器值的大小來決定，不是真正的最近最少使用算法，僅僅是它的一個近似。

第二個與LRU的區別是，老化算法的計數器只有有限位數，限制了其對以往頁面訪問歷史的記錄。

2 系統顛簸的分析與解決

2.1 系統顛簸的概念

顛簸（Thrashing）（又稱抖動）就是指當內存中已無空閑空間而又發生缺頁中斷時，需要從內存中調出一頁程序或數據到磁盤的交換區中，如果算法不適當，剛被換出的頁面很快被訪問，需重新調入，因此需再選一頁調出，而此時被換出的頁面很快又要被訪問，因而又需將它調入，如此頻繁更換頁面，以致花費大量的CPU時間，極大地降低系統的效率，我們稱這種現象為“顛簸”（或“抖動”）。一般如果每執行幾條指令程序就會發生一次缺頁中斷，那么就可以稱這個程序發生了顛簸。

2.2 系統顛簸的產生

2.2.1 局部頁面置換算法與全局頁面置換算法

頁面置換算法可以分為兩大類，全局置換和局部置換。全局置換允許一個進程從所有頁幀集合中選擇一個頁幀置換，而不管該幀是否已經分配給其他進程，即一個進程可以從另一個進程中拿到幀。局部置換要求每個進程僅從自己的分配幀中進行選擇。局部置換和全局置換的一個示例如下：如圖4所示，三個進程A，B，C構成了可運行進程的集合。假設頁面置換算法是LRU算法，每個頁面的生存時間列在頁面的右邊。當進程A產生缺頁中斷時，如果采用全局置換算法，將選擇所有頁面中生存時間最少的頁面B3進行置換。如果采用局部替換算法，將選擇分配給A的所有頁面中生存時間最少的頁面A6進行置換。

2.2.2 因為物理內存不足而產生系統顛簸

采用全局頁面置換時容易產生系統顛簸，即使是使用最優頁面置換算法的全局頁面置換也不例外。因為當某個進程需要更多的頁幀時，為了增加該進程的頁幀數目，可能直接導致另一進程的頁幀數目減少。當整個系統的物理塊不能滿足所有進程的需要時，缺頁率將持續維持于一高水平值，意味著顛簸的產生。其具體表現形式如下：

（1）進程競爭臨界資源

考慮這樣的情況：系統中已不存在空閑物理塊，而進程A卻要求增加物理塊，于是，中斷處理程序只得將原屬于進程B的物理塊分配給進程A；同樣地，進程B又分配到原屬于進程C的物理塊，如此下去。在一定時候，各缺頁進程都將被阻塞，就緒隊列為空，顛簸從此形成。

（2）增加多道程序度

當CPU利用率處于低水平時，為提高多道程序度，調度程序要求從后備輸入隊列選擇進程加載到內存。圖5可清楚地說明這種情形下顛簸的形成原因。首先，隨著多道程序度的增加，CPU 利用率隨之增加而達到一個理論極值。但在極值點右邊，再增加多道程序度，因為進程事實上只能從已加載的進程處獲得頁幀，從而使得更多的進程因缺頁而阻塞，隨著更多的進程執行內外存的I/O操作，CPU利用率反而更低；為提高CPU利用率，調度程序又要求調入新進程.如此形成惡性循環，系統諸進程都將缺頁，顛簸形成。

2.2.3 因為頁面置換算法而產生顛簸

基于局部性原理，幾乎所有的頁面置換算法總是試圖從當前正在引用的頁面去”預測”將要引用的頁面，據此產生淘汰頁和置換頁。大多數情形下，這種預測的命中率可以很高。但對于特定的程序（如有大量的跳轉語句的程序），命中率將很低，其結果很可能是所選擇的淘汰頁卻是即將要引用的頁；而從磁盤置換到內存的頁面在最近很長時間卻不會被引用。不得已，繼續進行頁面置換，反反復復，顛簸形成。當然，不應用局部性原理的頁面置換算法在大多數的情形下都有可能產生顛簸。

2.3 系統顛簸的解決

解決系統顛簸主要有3個方式：好的頁面替換算法；減少運行的進程數；增大內存。

這里主要分析如何使用好的頁面替換算法盡量避免顛簸的發生。

（1）局部置換

采用局部置換算法，當某個進程產生缺頁中斷時，只允許從本進程分配的頁幀中選擇置換頁面，而不能從其他進程處拿到幀，就不會使其他進程也發生顛簸，可將顛簸框定在一個特定的、較小的范圍內。

當然，這種方法并不理想。全局置換提供了更好的性能，這與局部分配本身是矛盾的。另外，它并不能從根本上防止顛簸，只能局限其范圍。如果某個進程處于顛簸狀態，則其將長期處于阻塞隊列，不斷地進行內外存交換，又必然會影響其他進程進行缺頁處理。

（2）動態調整頁面置換算法

頁面置換算法與實際應用相關，對于大多數的進程，與置換算法同時吻合了局部性原理，從而缺頁率低。而其余少數進程因與局部性原理相背，而使”預測”失效，其缺頁率偏高可能引發顛簸。

因此，我們可以在一個系統中預備2種以上不同的選擇淘汰頁和置換頁策略的置換算法，并定義一個缺頁率的臨界值，在缺頁處理程序中設置一個判斷，當缺頁率大于臨界值時改用另一種頁面置換算法。

（3）跟蹤缺頁率

根據局部性原理，絕大多數時候，進程是從一個局部區域轉移到另一個局部區域執行。所以，必須有足夠的頁幀供使用，以減少缺頁，避免顛簸。到底應為每個進程分配多少頁幀呢，實際上，它是系統擁有總的頁幀數目與當前系統實際應用相關的一個經驗值。這從缺頁率與所分配的頁幀數關系曲線得到證實。（如圖6所示）在拐點附近，每增加（減少）進程的頁幀數目都能顯著地改變缺頁率。

而一定時間以后，即使再增加頁幀，缺頁率變化也不明顯。拐點左邊缺頁率非常高的區域就是本來的顛簸，拐點就是理想的頁幀數目。據此，可對系統中的進程定義其缺頁率的上限和下限閥值，此區間內的頁幀數是進程擁有的相對合理的頁幀數，缺頁率高于上限時說明其分配到的頁幀太少應當追加；而當缺頁率低于下限時說明該進程所擁有的頁幀數太多，可收回一部分。

3 算法間的關系

在頁面置換的過程中，選擇好的頁面置換算法是提高系統整體性能的關鍵。本文分析了常見的7種頁面置換算法的原理和思想，并對一些算法給出了實例。

另外作者對各個算法的本質提出了個人的見解，從為什么會有這樣的算法？算法解決了什么問題？算法的優點和問題是什么？算法和其他算法之間的聯系是什么？等多個方面剖析了頁面置換算法的方方面面。

圖7小結了各個頁面置換算法之間的關系。

4 結語

系統顛簸也是內存管理中的一個重要問題，本文詳細分析了系統顛簸產生的原因并闡述了如何使用好的頁面置換算法盡量避免顛簸的產生。

參考文獻

[1] [荷]TANENBAUM A S.現代操作系統[M].陳向群，馬洪兵，譯.北京：機械工業出版社，2009.

[2] 張堯學，史美林，張高.計算機操作系統教程[M].北京：清華大學出版社，2006.

[3] GALVIN P B，GAGNE G.操作系統概念[M].鄭扣根，譯.北京：高等教育出版社，2011.

[4] [美]BRYANT R E， O’HALLARON D R. 深入理解計算機系統[M].龔奕利，雷迎春，譯.北京：機械工業出版社，2010.

[5] 嚴蔚敏，吳偉民.數據結構（C語言版）[M].北京：清華大學出版社，1997.