存儲管理的頁面置換算法

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

為什么要進行頁面置換

在請求分頁存儲管理系統(tǒng)中，由于使用了虛擬存儲管理技術，使得所有的進程頁面不是一次性地全部調入內存，而是部分頁面裝入。

這就有可能出現(xiàn)下面的情況：要訪問的頁面不在內存，這時系統(tǒng)產(chǎn)生缺頁中斷。操作系統(tǒng)在處理缺頁中斷時，要把所需頁面從外存調入到內存中。如果這時內存中有空閑塊，就可以直接調入該頁面；如果這時內存中沒有空閑塊，就必須先淘汰一個已經(jīng)在內存中的頁面，騰出空間，再把所需的頁面裝入，即進行頁面置換。

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

常用的頁面置換算法

教材中介紹的常用頁面置換算法有：先進先出法（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。當內存塊數(shù)量分別為3，5時，試問先進先出置換算法（FIFO）的缺頁次數(shù)是多少？（注意，所有內存塊最初都是空的，凡第一次用到的頁面都產(chǎn)生一次缺頁。）

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

頁面	1	2	3	4	2	1	5	6	2	1	2	3	7	6	3	2	1	2	3	6
塊1	1	1	1	4		4	4	6	6	6		3	3	3		2	2		2	6
塊2		2	2	2		1	1	1	2	2		2	7	7		7	1		1	1
塊3			3	3		3	5	5	5	1		1	1	6		6	6		3	3
缺頁	?	?	?	?		?	?	?	?	?		?	?	?		?	?		?	?

打叉的表示發(fā)生了缺頁，共缺頁16次。

提示：當FIFO算法執(zhí)行到藍色的4號頁面時，這時內存中有三個頁面，分別是1，2，3。按照FIFO算法，在內存中停留時間最長的頁面被淘汰。三個頁面在內存中的停留時間用綠色區(qū)域標記出來了，可見，1號頁面是停留時間最長的，因此要淘汰1號頁面。

當內存塊數(shù)量分別為5時，共缺頁10次。FIFO算法的執(zhí)行過程如下。

頁面	1	2	3	4	2	1	5	6	2	1	2	3	7	6	3	2	1	2	3	6
塊1	1	1	1	1	1			6		6	6	6	6
塊2		2	2	2	2			2		1	1	1	1
塊3			3	3	3			3		3	2	2	2
塊4				4	4			4		4	4	3	3
塊5					5			5		5	5	5	7
缺頁	?	?	?	?	?			?		?	?	?	?

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

最佳置換法（OPT）

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

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

考慮下述頁面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。當內存塊數(shù)量分別為3，5時，試問最佳置換法（OPT）的缺頁次數(shù)是多少？（注意，所有內存塊最初都是空的，凡第一次用到的頁面都產(chǎn)生一次缺頁。）

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

頁面	1	2	3	4	2	1	5	6	2	1	2	3	7	6	3	2	1	2	3	6
塊1	1	1	1	1			1	1				3	3			3	3			6
塊2		2	2	2			2	2				2	7			2	2			2
塊3			3	4			5	6				6	6			6	1			1
缺頁	?	?	?	?			?	?				?	?			?	?			?

打叉的表示發(fā)生了缺頁，共缺頁11次。

提示：當OPT算法執(zhí)行到藍色的4號頁面時，這時內存中有三個頁面，分別是1，2，3。按照OPT算法，在最遠的將來才被訪問的頁面先淘汰。這三個頁面在未來頁面走向序列的位置用綠色區(qū)域標記出來了，可見，3號頁面是最晚被訪問到的，因此要淘汰3號頁面。到了最后一個6號頁面時，由于沒有后續(xù)的頁面序列了，可以隨機選擇一個頁面淘汰。

當內存塊數(shù)量分別為5時，共缺頁7次。OPT算法的執(zhí)行過程如下。

頁面	1	2	3	4	2	1	5	6	2	1	2	3	7	6	3	2	1	2	3	6
塊1	1	1	1	1	1			1					1
塊2		2	2	2	2			2					2
塊3			3	3	3			3					3
塊4				4	4			6					6
塊5					5			5					7
缺頁	?	?	?	?	?			?					?

優(yōu)缺點：OPT算法因為要需要預先知道一個進程在整個運行過程中頁面走向的全部情況，因此只是一種理想狀態(tài)，實際是行不通的。一般用算法來衡量（如通過模擬實驗分析或理論分析）其他算法的優(yōu)劣。

最近最少使用置換法（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。當內存塊數(shù)量分別為3，5時，試問最近最少使用置換法（LRU）的缺頁次數(shù)是多少？（注意，所有內存塊最初都是空的，凡第一次用到的頁面都產(chǎn)生一次缺頁。）

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

頁面	1	2	3	4	2	1	5	6	2	1	2	3	7	6	3	2	1	2	3	6
塊1	1	1	1	4		4	5	5	5	1		1	7	7		2	2			2
塊2		2	2	2		2	2	6	6	6		3	3	3		3	3			3
塊3			3	3		1	1	1	2	2		2	2	6		6	1			1
缺頁	?	?	?	?		?	?	?	?	?		?	?	?		?	?			?

打叉的表示發(fā)生了缺頁，共缺頁15次。

提示：當LRU算法執(zhí)行到藍色的4號頁面時，這時內存中有三個頁面，分別是1，2，3。按照LRU算法，在最近一段時間里最久沒有使用過的頁面予以淘汰。這三個頁面在4號頁面之前的頁面走向序列中的位置用綠色區(qū)域標記出來了，可見，1號頁面是最久沒有被使用過的，因此要淘汰1號頁面。

當內存塊數(shù)量分別為5時，共缺頁8次。LRU算法的執(zhí)行過程如下。

頁面	1	2	3	4	2	1	5	6	2	1	2	3	7	6	3	2	1	2	3	6
塊1	1	1	1	1	1			1				1	1
塊2		2	2	2	2			2				2	2
塊3			3	3	3			6				6	6
塊4				4	4			4				3	3
塊5					5			5				5	7
缺頁	?	?	?	?	?			?				?	?

優(yōu)缺點：LRU算法是經(jīng)常采用的頁面置換算法。缺點是實現(xiàn)上需要大量的硬件支持。

3. 需要注意的問題

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

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

算法	FIFO	OPT	LRU
內存塊為3	16/20=80%	11/20=55%	15/20=75%
內存塊為5	10/20=50%	7/20=35%	8/20=40%

影響缺頁率的因素有分配給進程的內存塊數(shù)和頁面尺寸等。一般來說，內存塊數(shù)多，頁面增大，使得發(fā)生缺頁的可能性下降。但是這不是絕對的，還存在著Belady現(xiàn)象。

（3）衡量頁面置換算法好壞的標準是：好的算法能適當減少缺頁率，避免系統(tǒng)“抖動”。

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

總結

以上是生活随笔為你收集整理的存储管理的页面置换算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。