存儲管理的頁面置換算法

存儲管理的頁面置換算法

轉自：http://blog.csdn.net/pbymw8iwm/article/details/6799247

存儲管理的頁面置換算法在考試中常常會考到，作業系統教材中主要介紹了3種常用的頁面置換算法，分别是：先進先出法（FIFO）、最佳置換法（OPT）和最近最少使用置換法（LRU）。大家要了解3種置換算法的含義，然後能熟練地運用在具體的練習中就可以了。

為什麼要進行頁面置換

在請求分頁存儲管理系統中，由于使用了虛拟存儲管理技術，使得所有的程序頁面不是一次性地全部調入記憶體，而是部分頁面裝入。

這就有可能出現下面的情況：要通路的頁面不在記憶體，這時系統産生缺頁中斷。作業系統在處理缺頁中斷時，要把所需頁面從外存調入到記憶體中。如果這時記憶體中有空閑塊，就可以直接調入該頁面；如果這時記憶體中沒有空閑塊，就必須先淘汰一個已經在記憶體中的頁面，騰出空間，再把所需的頁面裝入，即進行頁面置換。

有助于了解的關鍵詞有：請求分頁、虛拟存儲、缺頁中斷、頁面置換。

常用的頁面置換算法

教材中介紹的常用頁面置換算法有：先進先出法（FIFO）、最佳置換法（OPT）和最近最少使用置換法（LRU）。

先進先出法（FIFO）

算法描述：由于認為最早調入記憶體的頁不再被使用的可能性要大于剛調入記憶體的頁，是以，先進先出法總是淘汰在記憶體中停留時間最長的一頁，即先進入記憶體的頁，先被換出。先進先出法把一個程序所有在記憶體中的頁按進入記憶體的次序排隊，淘汰頁面總是在隊首進行。如果一個頁面剛被放入記憶體，就把它插在隊尾。

【例1】教材第4章課後習題。

考慮下述頁面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。當記憶體塊數量分别為3，5時，試問先進先出置換算法（FIFO）的缺頁次數是多少？（注意，所有記憶體塊最初都是空的，凡第一次用到的頁面都産生一次缺頁。）

解：當記憶體塊數量分别為3時，FIFO算法的執行過程如下圖所示。

頁面

1

2

3

4

5

6

7

塊1

塊2

塊3

缺頁



打叉的表示發生了缺頁，共缺頁16次。

提示：當FIFO算法執行到藍色的4号頁面時，這時記憶體中有三個頁面，分别是1，2，3。按照FIFO算法，在記憶體中停留時間最長的頁面被淘汰。三個頁面在記憶體中的停留時間用綠色區域标記出來了，可見，1号頁面是停留時間最長的，是以要淘汰1号頁面。

當記憶體塊數量分别為5時，共缺頁10次。FIFO算法的執行過程如下。

塊4

塊5

優缺點：先進先出法（FIFO）簡單易于實作，但是性能不好，存在Belady現象。例如對于以下頁面：1，2，3，4，1，2，5，1，2，3，4，5，當記憶體塊為3時，出現9次缺頁中斷；當記憶體塊為4時，出現10次缺頁中斷。缺頁率随着記憶體塊增加而增加的現象，稱為Belady現象。有興趣的同學可以試一試，看看是不是這樣的。

最佳置換法（OPT）

算法描述：最佳置換算法（OPT）在為調入新頁面而必須預先淘汰某個老頁面時，所選擇的老頁面應在将來不被使用，或者是在最遠的将來才被通路。采用這種算法，能保證有最小缺頁率。

【例2】教材第4章課後習題。

考慮下述頁面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。當記憶體塊數量分别為3，5時，試問最佳置換法（OPT）的缺頁次數是多少？（注意，所有記憶體塊最初都是空的，凡第一次用到的頁面都産生一次缺頁。）

解：當記憶體塊數量分别為3時，OPT算法的執行過程如下圖所示。

打叉的表示發生了缺頁，共缺頁11次。

提示：當OPT算法執行到藍色的4号頁面時，這時記憶體中有三個頁面，分别是1，2，3。按照OPT算法，在最遠的将來才被通路的頁面先淘汰。這三個頁面在未來頁面走向序列的位置用綠色區域标記出來了，可見，3号頁面是最晚被通路到的，是以要淘汰3号頁面。到了最後一個6号頁面時，由于沒有後續的頁面序列了，可以随機選擇一個頁面淘汰。

當記憶體塊數量分别為5時，共缺頁7次。OPT算法的執行過程如下。

優缺點：OPT算法因為要需要預先知道一個程序在整個運作過程中頁面走向的全部情況，是以隻是一種理想狀态，實際是行不通的。一般用算法來衡量（如通過模拟實驗分析或理論分析）其他算法的優劣。

最近最少使用置換法（LRU）

算法描述：最近最少使用置換法（LRU）是選擇在最近一段時間裡最久沒有使用過的頁面予以淘汰。借鑒FIFO算法和OPT算法，以“最近的過去”作為“不久将來”的近似。

【例3】教材第4章課後習題。

考慮下述頁面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。當記憶體塊數量分别為3，5時，試問最近最少使用置換法（LRU）的缺頁次數是多少？（注意，所有記憶體塊最初都是空的，凡第一次用到的頁面都産生一次缺頁。）

解：當記憶體塊數量分别為3時，LRU算法的執行過程如下圖所示。

打叉的表示發生了缺頁，共缺頁15次。

提示：當LRU算法執行到藍色的4号頁面時，這時記憶體中有三個頁面，分别是1，2，3。按照LRU算法，在最近一段時間裡最久沒有使用過的頁面予以淘汰。這三個頁面在4号頁面之前的頁面走向序列中的位置用綠色區域标記出來了，可見，1号頁面是最久沒有被使用過的，是以要淘汰1号頁面。

當記憶體塊數量分别為5時，共缺頁8次。LRU算法的執行過程如下。

優缺點：LRU算法是經常采用的頁面置換算法。缺點是實作上需要大量的硬體支援。

3. 需要注意的問題

不要把存儲管理的頁面置換算法與處理機排程算法混淆。有的同學可能會将FIFO和FCFS弄混，FIFO是先進先出頁面置換算法，FCFS是先來先服務的作業調動算法，雖然道理相似，卻用在不同的地方。

缺頁率。教材中提到了缺頁率，沒有給出它的概念。缺頁率=缺頁次數/頁面總數。以上面3個例題為例，缺頁率如下：

算法

FIFO

OPT

LRU

記憶體塊為3

16/20=80%

11/20=55%

15/20=75%

記憶體塊為5

10/20=50%

7/20=35%

8/20=40%

影響缺頁率的因素有配置設定給程序的記憶體塊數和頁面尺寸等。一般來說，記憶體塊數多，頁面增大，使得發生缺頁的可能性下降。但是這不是絕對的，還存在着Belady現象。

（3）衡量頁面置換算法好壞的标準是：好的算法能适當減少缺頁率，避免系統“抖動”。

說明：以上内容僅作為教學輔導材料，不作為考核内容。