計算機操作系統中幾種頁面置換算法的比較

【摘要】在計算機操作系統的進程運行過程中，若被訪問的頁面不在內存時，就產生缺頁中斷。所以，計算機操作系統中頁面置換算法的好壞會直接影響系統的性能。本文對幾種典型的置換算法通過實例計算中斷次數來進行了比較。

【關鍵詞】計算機操作系統 置換算法 缺頁

【中圖分類號】TP316【文獻標識碼】A 【文章編號】2095-3089（2014）11-0220-02

在操作系統的進程運行過程中，若被訪問的頁面不在內存時，就產生缺頁中斷。這時，操作系統進行中斷處理，把該頁從外存調入內存。那么新調進的頁到底放在什么地方呢？如果內存中有空閑塊，則可把該頁裝入任何空閑塊中。那么，內存中沒有空閑空間時，怎么辦？那么必須先淘汰已在內存的一頁，騰出空間，再把所需頁面裝入。但是這要有一定的策略，這也是“算法”。我們叫做頁面置換算法。置換算法的好壞直接影響系統的性能。若采用的算法不適當，會產生“抖動”現象。即：剛被換出的頁，很快又被訪問，又需將它調入而將另一頁換出；而剛被換出的另一頁不久又被訪問，還需把它調入。以致系統的大部分時間花費在頁面的調度和傳輸上。這時，實際上系統的效率很低，只是在“白忙活”。

一、操作系統中常用的幾種置換算法

（一）先進先出法（FIFO）

它是最簡單的頁面置換算法。這種算法總是淘汰在內存中停留時間最長的一頁，即先進入內存的頁，先被換出。這種算法把一個進程所有在內存中的頁按進入內存的次序排序，淘汰頁面總是在隊首進行。剛被調入內存的那一頁插在隊尾。

舉個例子：

比如有下述頁面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，

3，6。當內存塊數量分別為3時，我們算一算使有此方法時產生的缺頁次情況。（注意，所有內存塊最初都是空的，凡第一次用到的頁面都產生一次缺頁。）

解：當內存塊數量分別為3時，FIFO算法的執行過程如下圖所示。

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

隨便一個內存塊時，比如說當內存塊數量為5時，同樣方法計算出共缺頁10次。算法的執行過程如下。

（二）最佳置換法（OPT）

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

舉例說明一下：

還是使用上述頁面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，

1，2，3，6。當內存塊數量分別為3時，看一看最佳置換法（OPT）的缺頁次數是多少？（注意，所有內存塊最初都是空的，凡第一次用到的頁面都產生一次缺頁。）

解：當內存塊數量分別為3時，OPT算法的執行過程如下圖所示。

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

再看看比如當內存塊數量為5時，同樣方法算出共缺頁7次。OPT算法的執行過程如下。

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

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

還是拿同樣頁面走向來舉例說明一下：1，2，3，4，2，1，5，6，2，

1，2，3，7，6，3，2，1，2，3，6。當內存塊數量分別為3時，看一看最近最少使用置換法（LRU）的缺頁次數。（注意，所有內存塊最初都是空的，凡第一次用到的頁面都產生一次缺頁。）

解：當內存塊數量分別為3時，LRU算法的執行過程如下圖所示。

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

再當內存塊數量為5，可算出共產生缺頁8次。LRU算法的執行過程如下。

二、幾種算法的比較

（一）先進先出法（FIFO）

先進先出置換算法簡單易于實現、容易理解和進行程序設計，但是性能不好，拿上述例子來看：存在Belady現象。這種算法僅當按線性順序訪問地址空間時才是理想的；否則，效率不高。因為那些常被訪問的頁，往往在內存中也停留得最久，結果它們因變“老”而不得不被淘汰出去。

（二）最佳置換法（OPT）

同樣的頁面走向來看，當內存塊為3時，產生了11次。比使用先進先出法（FIFO）時，缺頁率減少了25%。減少了缺頁率固然是好的算法，但是實際中由于OPT算法需要預先知道一個進程在整個運行過程中頁面走向的全部情況，因此只是一種理想狀態，實際是行不通的。不過這個算法可用來衡量（如通過模擬實驗分析或理論分析）其他算法的優劣。

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

最佳置換算法在實際中行不通，于是我們找到了與它接近的算法——就是最近最少使用置換法。FIFO算法與OPT算法之間的主要差別是：FIFO算法將頁面進入內存后的時間長短作為淘汰依據，而OPT算法是依據今后使用頁面的時間。那么LRU就是將以“最近的過去”作為“不久的將來”的近似，把最近最長一段時間里不曾被使用的頁面進行淘汰。所以，LRU算法是經常采用的頁面置換算法。但是，實現LRU算法需要實際硬件的支持。這需要一定的開銷。所以，如果我們想減少開銷的話，也可以設計一個最近未使用算法。它是LRU的近似算法。它比較易于實現，開銷也比較小。

總之，一個好的置換算法會影響到系統的性能。所以選擇一個好的算法是很重要的。

參考文獻：

[1]孟慶昌主編：操作系統 中央廣播電視大學出版社，2008.

[2]吳企淵：計算機操作系統 清華大學出版社，2006.

[3]侯炳輝：信息管理系統 中央廣播電視大學出版社 2001.