內(nèi)存管理的頁面置換算法有哪些

看風(fēng)景D人 2014-09-14

展開全文

進程運行時，若其訪問的頁面不在內(nèi)存而需將其調(diào)入，但內(nèi)存已無空閑空間時，就需要從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)，送入磁盤的對換區(qū)。

選擇調(diào)出頁面的算法就稱為頁面置換算法。好的頁面置換算法應(yīng)有較低的頁面更換頻率，也就是說，應(yīng)將以后不會再訪問或者以后較長時間內(nèi)不會再訪問的頁面先調(diào)出。

常見的置換算法有以下四種。

1. 最佳置換算法(OPT)

最佳(Optimal, OPT)置換算法所選擇的被淘汰頁面將是以后永不使用的，或者是在最長時間內(nèi)不再被訪問的頁面,這樣可以保證獲得最低的缺頁率。但由于人們目前無法預(yù)知進程在內(nèi)存下的若千頁面中哪個是未來最長時間內(nèi)不再被訪問的，因而該算法無法實現(xiàn)。

最佳置換算法可以用來評價其他算法。假定系統(tǒng)為某進程分配了三個物理塊，并考慮有以下頁面號引用串：
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

進程運行時，先將7, 0, 1三個頁面依次裝入內(nèi)存。進程要訪問頁面2時，產(chǎn)生缺頁中斷，根據(jù)最佳置換算法，選擇第18次訪問才需調(diào)入的頁面7予以淘汰。然后，訪問頁面0時，因為已在內(nèi)存中所以不必產(chǎn)生缺頁中斷。訪問頁面3時又會根據(jù)最佳置換算法將頁面1淘汰……依此類推，如圖3-26所示。從圖中可以看出釆用最佳置換算法時的情況。

可以看到，發(fā)生缺頁中斷的次數(shù)為9，頁面置換的次數(shù)為6。

訪問頁面	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
物理塊1	7	7	7	2		2		2			2			2				7
物理塊2		0	0	0		0		4			0			0				0
物理塊3			1	1		3		3			3			1				1
缺頁否	√		√	√		√		√			√			√				√

圖3-26 利用最佳置換算法時的置換圖

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

優(yōu)先淘汰最早進入內(nèi)存的頁面，亦即在內(nèi)存中駐留時間最久的頁面。該算法實現(xiàn)簡單，只需把調(diào)入內(nèi)存的頁面根據(jù)先后次序鏈接成隊列，設(shè)置一個指針總指向最早的頁面。但該算法與進程實際運行時的規(guī)律不適應(yīng)，因為在進程中，有的頁面經(jīng)常被訪問。

訪問頁面	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
物理塊1	7	7	7	2		2	2	4	4	4	0			0	0			7	7	7
物理塊2		0	0	0		3	3	3	2	2	2			1	1			1	0	0
物理塊3			1	1		1	0	0	0	3	3			3	2			2	2	1
缺頁否	√	√	√	√		√	√	√	√	√	√			√	√			√	√	√

圖3-27 利用FIFO置換算法時的置換圖

這里仍用上面的實例，釆用FIFO算法進行頁面置換。進程訪問頁面2時，把最早進入內(nèi)存的頁面7換出。然后訪問頁面3時，再把2, 0, 1中最先進入內(nèi)存的頁換出。由圖 3-27可以看出，利用FIFO算法時進行了 12次頁面置換，比最佳置換算法正好多一倍。

FIFO算法還會產(chǎn)生當所分配的物理塊數(shù)增大而頁故障數(shù)不減反增的異?，F(xiàn)象，這是由 Belady于1969年發(fā)現(xiàn)，故稱為Belady異常，如圖3-28所示。只有FIFO算法可能出現(xiàn)Belady 異常，而LRU和OPT算法永遠不會出現(xiàn)Belady異常。

訪問頁面	1	2	3	4	1	2	5	1	2	3	4	5
物理塊1	1	1	1	4	4	4	5			,5'	5
物理塊2		2	2	2	1	1	1			3	3
物理塊3			3	3	3	2	2			2	4
缺頁否	√	√	√	√	√	√	√			√	√
		1	1	1			5	5	5	5	4	4
物理塊2*		2	2	2			2	1	1	1	1	5
物理塊3*			3	3			3	3	2	2	2	2
物理塊4*				4			4	4	4	3	3	3
缺頁否	√	√	√				√	√	√	√	√	√

圖 3-28 Belady 異常

3. 最近最久未使用(LRU)置換算法

選擇最近最長時間未訪問過的頁面予以淘汰，它認為過去一段時間內(nèi)未訪問過的頁面，在最近的將來可能也不會被訪問。該算法為每個頁面設(shè)置一個訪問字段，來記錄頁面自上次被訪問以來所經(jīng)歷的時間，淘汰頁面時選擇現(xiàn)有頁面中值最大的予以淘汰。

再對上面的實例釆用LRU算法進行頁面置換，如圖3-29所示。進程第一次對頁面2訪問時，將最近最久未被訪問的頁面7置換出去。然后訪問頁面3時，將最近最久未使用的頁面1換出。

訪問頁面	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
物理塊1	7	7	7	2		2		4	4	4	0			1		1		1
物理塊2		0	0	0		0		0	0	3	3			3		0		0
物理塊3			1	1		3		3	2	2	2			2		2		7
缺頁否	√	√	√	√		√		√	√	√	√			√		√		√

圖3-29 LRU頁面置換算法時的置換圖

在圖3-29中，前5次置換的情況與最佳置換算法相同，但兩種算法并無必然聯(lián)系。實際上，LRU算法根據(jù)各頁以前的情況，是“向前看”的，而最佳置換算法則根據(jù)各頁以后的使用情況，是“向后看”的。

LRU性能較好，但需要寄存器和棧的硬件支持。LRU是堆棧類的算法。理論上可以證明，堆棧類算法不可能出現(xiàn)Belady異常。FIFO算法基于隊列實現(xiàn)，不是堆棧類算法。

4. 時鐘(CLOCK)置換算法

LRU算法的性能接近于OPT,但是實現(xiàn)起來比較困難，且開銷大；FIFO算法實現(xiàn)簡單，但性能差。所以操作系統(tǒng)的設(shè)計者嘗試了很多算法，試圖用比較小的開銷接近LRU的性能，這類算法都是CLOCK算法的變體。

簡單的CLOCK算法是給每一幀關(guān)聯(lián)一個附加位，稱為使用位。當某一頁首次裝入主存時，該幀的使用位設(shè)置為1;當該頁隨后再被訪問到時，它的使用位也被置為1。對于頁替換算法，用于替換的候選幀集合看做一個循環(huán)緩沖區(qū)，并且有一個指針與之相關(guān)聯(lián)。當某一頁被替換時，該指針被設(shè)置成指向緩沖區(qū)中的下一幀。當需要替換一頁時，操作系統(tǒng)掃描緩沖區(qū)，以查找使用位被置為0的一幀。每當遇到一個使用位為1的幀時，操作系統(tǒng)就將該位重新置為0；如果在這個過程開始時，緩沖區(qū)中所有幀的使用位均為0，則選擇遇到的第一個幀替換；如果所有幀的使用位均為1,則指針在緩沖區(qū)中完整地循環(huán)一周，把所有使用位都置為0，并且停留在最初的位置上，替換該幀中的頁。由于該算法循環(huán)地檢查各頁面的情況，故稱為CLOCK算法，又稱為最近未用(Not Recently Used, NRU)算法。

CLOCK算法的性能比較接近LRU，而通過增加使用的位數(shù)目，可以使得CLOCK算法更加高效。在使用位的基礎(chǔ)上再增加一個修改位，則得到改進型的CLOCK置換算法。這樣，每一幀都處于以下四種情況之一：

最近未被訪問，也未被修改(u=0, m=0)。
最近被訪問，但未被修改(u=1, m=0)。
最近未被訪問，但被修改(u=0, m=1)。
最近被訪問，被修改(u=1, m=1)。

算法執(zhí)行如下操作步驟：

從指針的當前位置開始，掃描幀緩沖區(qū)。在這次掃描過程中，對使用位不做任何修改。選擇遇到的第一個幀(u=0, m=0)用于替換。
如果第1)步失敗，則重新掃描，查找(u=0, m=1)的幀。選擇遇到的第一個這樣的幀用于替換。在這個掃描過程中，對每個跳過的幀，把它的使用位設(shè)置成0。
如果第2)步失敗，指針將回到它的最初位置，并且集合中所有幀的使用位均為0。重復(fù)第1步，并且如果有必要，重復(fù)第2步。這樣將可以找到供替換的幀。

改進型的CLOCK算法優(yōu)于簡單CLOCK算法之處在于替換時首選沒有變化的頁。由于修改過的頁在被替換之前必須寫回，因而這樣做會節(jié)省時間。