電子職稱論文刊發(fā)頁面置換算法的分析

來源：職稱那點(diǎn)事作者：職稱論文時間：2015-04-17 13:39

　　摘要：頁面置換算法是操作系統(tǒng)內(nèi)存管理中的一個重要問題。為了研究不同頁面置換算法的區(qū)別與聯(lián)系以及它們對系統(tǒng)顛簸的影響，在此采用了將不同置換算法對比介紹的方法，闡釋了幾種常見的頁面置換算法的原理和思想，并通過它們對系統(tǒng)顛簸影響的分析實(shí)驗(yàn)，得到了通過改進(jìn)頁面置換算法解決系統(tǒng)顛簸的三個途徑。通過采用局部頁面置換算法，動態(tài)調(diào)整的頁面置換算法和跟蹤缺頁率，可以有效地實(shí)現(xiàn)系統(tǒng)顛簸的控制。

　　關(guān)鍵詞：頁面置換算法;系統(tǒng)顛簸;缺頁中斷;內(nèi)存管理;操作系統(tǒng);虛擬內(nèi)存

　　0引言

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

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

　　1常見的頁面置換算法

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

　　1.1.1算法思想介紹

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

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

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

　　1.1.2算法分析

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

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

　　1.2.1算法思想介紹

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

　　1.2.2算法分析

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

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

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

　　1.3.1算法思想介紹

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

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

　　1.3.2算法示例

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

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

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

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

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

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

　　1.3.3算法分析

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

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

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

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

　　