頁(yè)面替換算法是操作系統(tǒng)內(nèi)存管理中的一個(gè)重要問(wèn)題。為了研究不同頁(yè)面替換算法的差異和聯(lián)系及其對(duì)系統(tǒng)抖動(dòng)的影響，介紹了比較不同置換算法的方法，并闡述了幾種常見(jiàn)頁(yè)面替換算法的原理和思想，接下來(lái)小編簡(jiǎn)單介紹一篇優(yōu)秀計(jì)算機(jī)內(nèi)存論文。

　　0引言

　　在系統(tǒng)運(yùn)行過(guò)程中，若程序所要訪問(wèn)的頁(yè)面不在內(nèi)存而需要把他們調(diào)入內(nèi)存，但內(nèi)存已經(jīng)沒(méi)有空閑空間時(shí)，為了保證該進(jìn)程能正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)送到磁盤(pán)的交換區(qū)中，這個(gè)過(guò)程稱為頁(yè)面置換。決定將哪個(gè)頁(yè)面調(diào)出，需根據(jù)一定的算法來(lái)確定，通常，把選擇換出頁(yè)面的算法成為頁(yè)面置換算法。

　　置換算法的好壞，將直接影響到系統(tǒng)的性能。當(dāng)發(fā)生缺頁(yè)中斷時(shí)，雖然可以隨機(jī)地選擇一個(gè)頁(yè)面置換，但是如果一個(gè)被頻繁使用的頁(yè)面被置換出內(nèi)存，很可能它在很短時(shí)間內(nèi)又要被調(diào)入內(nèi)存，這會(huì)帶來(lái)不必要的開(kāi)銷。一個(gè)好的頁(yè)面置換算法，應(yīng)具有較低的頁(yè)面更換頻率。從理論上講，應(yīng)將那些以后不再會(huì)訪問(wèn)的頁(yè)面置換出，或者把那些在較長(zhǎng)時(shí)間內(nèi)不會(huì)再訪問(wèn)的頁(yè)面調(diào)出。這對(duì)提高系統(tǒng)性能極其重要。

　　1常見(jiàn)的頁(yè)面置換算法

　　1.1最優(yōu)頁(yè)面置換算法

　　1.1.1算法思想介紹

　　最佳頁(yè)面置換算法(OptimalPageReplacementAlgorithm，OPT)是一種理想情況下的頁(yè)面置換算法，它在所有頁(yè)面置換算法中產(chǎn)生的頁(yè)錯(cuò)誤率最低，但實(shí)際上該算法是不可能實(shí)現(xiàn)的。

　　該算法的基本思想是：發(fā)生缺頁(yè)時(shí)，有些頁(yè)面在內(nèi)存中，其中有一頁(yè)將很快被訪問(wèn)(也就是下一條指令要訪問(wèn)的那一頁(yè))，而其他頁(yè)面則可能要到10、100或者1000條指令后才會(huì)被訪問(wèn)，每個(gè)頁(yè)面都可以用在該頁(yè)面首次被訪問(wèn)前所要執(zhí)行的指令數(shù)進(jìn)行標(biāo)記。

　　最佳頁(yè)面置換算法規(guī)定：標(biāo)記最大的頁(yè)應(yīng)該被置換。例如，如果某頁(yè)在800萬(wàn)條指令內(nèi)不會(huì)被使用，另一頁(yè)在600萬(wàn)條指令內(nèi)不會(huì)被使用，則置換前一個(gè)頁(yè)面。這個(gè)算法惟一的一個(gè)問(wèn)題就是它無(wú)法實(shí)現(xiàn)，因?yàn)楫?dāng)缺頁(yè)發(fā)生時(shí)，操作系統(tǒng)無(wú)法知道各個(gè)頁(yè)面下一次是在什么時(shí)候被訪問(wèn)。雖然最佳頁(yè)面置換算法不可能實(shí)現(xiàn)，但是該算法可以用于對(duì)可實(shí)現(xiàn)算法的性能進(jìn)行衡量比較。如果一個(gè)頁(yè)面置換算法不是最優(yōu)的，但是它的性能與最優(yōu)置換相比相差不大(如僅有2%的性能差距)，那么就可以判定該算法是有實(shí)用價(jià)值的。

　　1.1.2算法分析

　　從理論上說(shuō)，當(dāng)置換一個(gè)頁(yè)面出內(nèi)存時(shí)，被置換出的頁(yè)面在將來(lái)仍然需要被訪問(wèn)，那個(gè)時(shí)候?qū)�發(fā)生缺頁(yè)中斷。既然不好的事情(缺頁(yè)中斷)總會(huì)發(fā)生，計(jì)算機(jī)也和人一樣，希望把不愉快的事情盡可能地向后拖延。一個(gè)最好的頁(yè)面置換算法應(yīng)該把因?yàn)樾枰�調(diào)入這個(gè)頁(yè)面而發(fā)生的缺頁(yè)中斷推遲到將來(lái)，越久越好。因此選擇最久之后才會(huì)被訪問(wèn)的頁(yè)面換出內(nèi)存是理論上最佳的，這也是這個(gè)算法被稱為最優(yōu)置換的原因。

　　1.2先進(jìn)先出頁(yè)面置換算法(FIFO)

　　1.2.1算法思想介紹

　　FIFO算法總是淘汰在內(nèi)存中停留得最久的那個(gè)頁(yè)面。具體實(shí)現(xiàn)方法是由操作系統(tǒng)維護(hù)一個(gè)所有當(dāng)前在內(nèi)存中的頁(yè)面的鏈表，最新進(jìn)入的頁(yè)面放在表尾，最久進(jìn)入的頁(yè)面放在表頭。當(dāng)發(fā)生缺頁(yè)中斷時(shí)，淘汰表頭頁(yè)面并把新調(diào)入的頁(yè)面加到表尾。FIFO頁(yè)面置換算法容易理解和實(shí)現(xiàn)，但是其性能并不總是很好。

　　1.2.2算法分析

　　FIFO算法僅僅考慮到在內(nèi)存中滯留了很久的頁(yè)面的需求性可能比新進(jìn)入的頁(yè)面更小。就像在超級(jí)市場(chǎng)中，新引進(jìn)的商品往往比已經(jīng)庫(kù)存了很久的商品更容易被購(gòu)買(mǎi)，因此當(dāng)新引進(jìn)商品時(shí)，通常淘汰那個(gè)庫(kù)存了最久的商品。

　　但是這種考慮顯然不太準(zhǔn)確，誰(shuí)說(shuō)新上架的東西一定比庫(kù)存很久的東西更有用呢?考慮一個(gè)頁(yè)面，它在很早的時(shí)候被調(diào)入內(nèi)存，之后被頻繁的引用，這個(gè)頁(yè)面很容易被FIFO算法當(dāng)作沒(méi)用的頁(yè)面從而被淘汰。因此純粹的FIFO算法很容易淘汰重要的頁(yè)面，實(shí)際很少使用。

　　1.3第二次機(jī)會(huì)頁(yè)面置換算法

　　1.3.1算法思想介紹

　　第二次機(jī)會(huì)頁(yè)面置換算法是對(duì)FIFO算法的改進(jìn)。它在FIFO的基礎(chǔ)上進(jìn)行了修改，其性能較FIFO有了很大的提高，避免了把經(jīng)常使用的頁(yè)面置換出去。

　　和FIFO算法一樣，操作系統(tǒng)維護(hù)一個(gè)所有當(dāng)前在內(nèi)存中的頁(yè)面的鏈表，最新進(jìn)入的頁(yè)面放在表尾，最久進(jìn)入的頁(yè)面放在表頭。當(dāng)需要置換頁(yè)面是，檢查最老頁(yè)面的R位，如果它為0，表示它最近未被使用，也就是說(shuō)，它又老又沒(méi)用，可以立即置換。如果是1，則把R位置為0，并把該頁(yè)面放在鏈表尾端(即把它作為剛裝入的頁(yè)面一樣)，然后繼續(xù)搜索。

　　1.3.2算法示例

　　如圖1(a)所示，頁(yè)面A到頁(yè)面H按照進(jìn)入內(nèi)存的時(shí)間先后順序保存在鏈表中。頁(yè)面上的數(shù)字是該頁(yè)面進(jìn)入內(nèi)存時(shí)的時(shí)間。第二次機(jī)會(huì)算法的一個(gè)執(zhí)行示例過(guò)程如下：

　　(1)在時(shí)間20發(fā)生了一次缺頁(yè)中斷;

　　(2)檢查最老的頁(yè)面A，如果A的R位為0，則將它淘汰出內(nèi)存;

　　(3)現(xiàn)在頁(yè)面A的R位為1，則將A放到鏈表的尾部，并且重新設(shè)置頁(yè)面的進(jìn)入時(shí)間為當(dāng)前時(shí)刻，并置A的R位為0。即讓A頁(yè)面好像是剛剛調(diào)入內(nèi)存一樣;

　　(4)檢查當(dāng)前最老的頁(yè)面B，重復(fù)以上過(guò)程。

　　可以看出在上面的過(guò)程中，如果A到H頁(yè)面都被訪問(wèn)過(guò)了，那么在遍歷了一次之后，仍然是頁(yè)面A被淘汰，此算法就變成了純粹的FIFO算法。

　　1.3.3算法分析

　　該算法的思想是找到一個(gè)最近的時(shí)鐘滴答中從來(lái)沒(méi)有被訪問(wèn)過(guò)的頁(yè)面，而且這個(gè)頁(yè)面是最老的(最先調(diào)入內(nèi)存)，這樣綜合了兩個(gè)方面的考慮：

　　(1)老的頁(yè)面比新的頁(yè)面需求量小(FIFO算法的想法)

　　(2)局部性：最近未被訪問(wèn)的頁(yè)面今后也可能不被訪問(wèn)

　　并且算法優(yōu)先考慮局部性，例如在上面的過(guò)程中，如果A～H頁(yè)面都被訪問(wèn)過(guò)了，那么在遍歷了一次之后，仍然是最老的頁(yè)面A被淘汰，此算法就變成了純粹的FIFO算法。

　　閱讀期刊：軟件

　　《軟件》(月刊)創(chuàng)刊于1979年，由中國(guó)科協(xié)主管，中國(guó)電子學(xué)會(huì)、天津電子學(xué)會(huì)主辦，天津電子儀表信息所與中科鼎盛科技發(fā)展(北京)中心協(xié)辦的首屆中文核心國(guó)際發(fā)行期刊，是首批中文核心期刊，被《中國(guó)學(xué)術(shù)期刊綜合評(píng)價(jià)數(shù)據(jù)庫(kù)來(lái)源期刊》、《中國(guó)核心期刊(遴選)數(shù)據(jù)庫(kù)收錄期刊》、《萬(wàn)方數(shù)據(jù)—數(shù)字化期刊群全文收錄期刊》、《中文科技期刊數(shù)據(jù)庫(kù)(全文版)收錄期刊》、美國(guó)《劍橋科學(xué)文摘》、波蘭《哥白尼索引》收錄期刊、美國(guó)《烏利希國(guó)際期刊指南》等國(guó)內(nèi)外數(shù)據(jù)庫(kù)收錄。