os頁(yè)面置換

1、評(píng)價(jià)一個(gè)算法的優(yōu)劣可通過(guò)在一個(gè)特定的存儲(chǔ)訪問(wèn)序列（頁(yè)面走向）上運(yùn)行它，并計(jì)算缺頁(yè)數(shù)量來(lái)實(shí)現(xiàn)。1先入先出法（FIFO）最簡(jiǎn)單的頁(yè)面置換算法是先入先出（FIFO）法。這種算法的實(shí)質(zhì)是，總是選擇在主存中停留時(shí)間最長(zhǎng)（即最老）的一頁(yè)置換，即先進(jìn)入內(nèi)存的頁(yè)，先退出內(nèi)存。理由是：最早調(diào)入內(nèi)存的頁(yè)，其不再被使用的可能性比剛調(diào)入內(nèi)存的可能性大。建立一個(gè)FIFO隊(duì)列，收容所有在內(nèi)存中的頁(yè)。被置換頁(yè)面總是在隊(duì)列頭上進(jìn)行。當(dāng)一個(gè)頁(yè)面被放入內(nèi)存時(shí)，就把它插在隊(duì)

2、尾上。這種算法只是在按線性順序訪問(wèn)地址空間時(shí)才是理想的，否則效率不高。因?yàn)槟切┏１辉L問(wèn)的頁(yè)，往往在主存中也停留得最久，結(jié)果它們因變“老”而不得不被置換出去。FIFO的另一個(gè)缺點(diǎn)是，它有一種異常現(xiàn)象，即在增加存儲(chǔ)塊的情況下，反而使缺頁(yè)中斷率增加了。當(dāng)然，導(dǎo)致這種異常現(xiàn)象的頁(yè)面走向?qū)嶋H上是很少見(jiàn)的?，F(xiàn)在來(lái)看下4塊的情況：0123213252362142【解答】剛開(kāi)始內(nèi)存并沒(méi)有這個(gè)作業(yè)，所以發(fā)生缺頁(yè)中斷一次。作業(yè)的0號(hào)頁(yè)進(jìn)入內(nèi)存。(1次缺頁(yè)中

3、斷)而頁(yè)1又不在內(nèi)存，又發(fā)生缺頁(yè)中斷一次。作業(yè)頁(yè)1進(jìn)入內(nèi)存。(2次缺頁(yè)中斷)頁(yè)2不在內(nèi)存，發(fā)生缺頁(yè)中斷。頁(yè)2進(jìn)入內(nèi)存。(3次缺頁(yè)中斷)頁(yè)3不在內(nèi)存，發(fā)生缺頁(yè)中斷。頁(yè)3進(jìn)入內(nèi)存。(4次缺頁(yè)中斷)接下來(lái)調(diào)入頁(yè)2，頁(yè)1，頁(yè)3，頁(yè)2。由于都在內(nèi)存中，并不發(fā)生缺頁(yè)中斷。頁(yè)5不在內(nèi)存，發(fā)生缺頁(yè)中斷。頁(yè)5進(jìn)入內(nèi)存，頁(yè)5置換頁(yè)0。(5次缺頁(yè)中斷)接下來(lái)調(diào)入頁(yè)2，頁(yè)3。由于都在內(nèi)存中，并不發(fā)生缺頁(yè)中斷。頁(yè)6不在內(nèi)存，發(fā)生缺頁(yè)中斷。頁(yè)6進(jìn)入內(nèi)存。頁(yè)6置換頁(yè)

4、1。(6次缺頁(yè)中斷)頁(yè)2在內(nèi)存，不發(fā)生缺頁(yè)中斷。頁(yè)1不在內(nèi)存(在發(fā)生第6次缺頁(yè)中斷時(shí)被置換了)，發(fā)生缺頁(yè)中斷。頁(yè)1進(jìn)入內(nèi)存，頁(yè)2被置換。(7次缺頁(yè)中斷)頁(yè)4置換頁(yè)3，頁(yè)4進(jìn)入內(nèi)存。(8次缺頁(yè)中斷)現(xiàn)在調(diào)入頁(yè)2，但頁(yè)2在發(fā)生第7次缺頁(yè)中斷時(shí)被置換掉了。現(xiàn)在頁(yè)2進(jìn)入內(nèi)存，其置換頁(yè)5。(因?yàn)檫@個(gè)時(shí)候是頁(yè)5最先進(jìn)入內(nèi)存。)(9次缺頁(yè)中斷)2最優(yōu)置換算法（OPT）最優(yōu)置換（OptimalReplacement）是在理論上提出的一種算法。其實(shí)質(zhì)是：

5、當(dāng)調(diào)入新的一頁(yè)而必須預(yù)先置換某個(gè)老頁(yè)時(shí)，所選擇的老頁(yè)應(yīng)是將來(lái)不再被使用，或者是在最遠(yuǎn)的將來(lái)才被訪問(wèn)。采用這種頁(yè)面置換算法，保證有最少的缺頁(yè)率。但是最優(yōu)頁(yè)面置換算法的實(shí)現(xiàn)是困難的，因?yàn)樗枰藗冾A(yù)先就知道一個(gè)進(jìn)程整個(gè)運(yùn)行過(guò)程中頁(yè)面走向的全部情況。不過(guò)，這個(gè)算法可用來(lái)衡量（如通過(guò)模擬實(shí)驗(yàn)分析或理論分析）其他算法的優(yōu)劣。移走一項(xiàng)，所以要用具有頭尾指針的雙向鏈連起來(lái)。在最壞的情況下，移走一頁(yè)并把它放在棧頂上需要改動(dòng)6個(gè)指針。每次修改都要有開(kāi)銷，

6、但需要置換哪個(gè)頁(yè)面卻可直接得到，用不著查找，因?yàn)槲仓羔樦赶驐５?，其中有被置換頁(yè)。因?qū)崿F(xiàn)LRU算法必須有大量硬件支持，還需要一定的軟件開(kāi)銷。所以實(shí)際實(shí)現(xiàn)的都是一種簡(jiǎn)單有效的LRU近似算法。一種LRU近似算法是最近未使用算法（NotRecentlyUsed，NUR）。它在存儲(chǔ)分塊表的每一表項(xiàng)中增加一個(gè)引用位，操作系統(tǒng)定期地將它們置為0。當(dāng)某一頁(yè)被訪問(wèn)時(shí)，由硬件將該位置1。過(guò)一段時(shí)間后，通過(guò)檢查這些位可以確定哪些頁(yè)使用過(guò)，哪些頁(yè)自上次置0后還

7、未使用過(guò)。就可把該位是0的頁(yè)淘汰出去，因?yàn)樵谧罱欢螘r(shí)間里它未被訪問(wèn)過(guò)。4第二次機(jī)會(huì)算法（SCR）第二次機(jī)會(huì)算法的基本思想是與FIFO相同的，但是有所改進(jìn)，避免把經(jīng)常使用的頁(yè)面置換出去。當(dāng)選擇置換頁(yè)面時(shí)，檢查它的訪問(wèn)位。如果是0，就淘汰這頁(yè)；如果訪問(wèn)位是1，就給它第二次機(jī)會(huì)，并選擇下一個(gè)FIFO頁(yè)面。當(dāng)一個(gè)頁(yè)面得到第二次機(jī)會(huì)時(shí)，它的訪問(wèn)位就清為0，它的到達(dá)時(shí)間就置為當(dāng)前時(shí)間。如果該頁(yè)在此期間被訪問(wèn)過(guò)，則訪問(wèn)位置1。這樣給了第二次機(jī)會(huì)的頁(yè)

8、面將不被淘汰，直至所有其他頁(yè)面被淘汰過(guò)（或者也給了第二次機(jī)會(huì)）。因此，如果一個(gè)頁(yè)面經(jīng)常使用，它的訪問(wèn)位總保持為1，它就從來(lái)不會(huì)被淘汰出去。第二次機(jī)會(huì)算法可視為一個(gè)環(huán)形隊(duì)列。用一個(gè)指針指示哪一頁(yè)是下面要淘汰的。當(dāng)需要一個(gè)存儲(chǔ)塊時(shí)，指針就前進(jìn)，直至找到訪問(wèn)位是0的頁(yè)。隨著指針的前進(jìn)，把訪問(wèn)位就清為0。在最壞的情況下，所有的訪問(wèn)位都是1，指針要通過(guò)整個(gè)隊(duì)列一周，每個(gè)頁(yè)都給第二次機(jī)會(huì)。這時(shí)就退化成FIFO算法了。頁(yè)面置換算法還有很多變種，如考慮

9、到被置換頁(yè)是否修改過(guò)、按FIFO算法選中的頁(yè)正在使用等情況，都需要硬件、軟件協(xié)同實(shí)現(xiàn)。部分的頁(yè)面在虛擬內(nèi)存，部分在物理內(nèi)存，操作系統(tǒng)需要訪問(wèn)的頁(yè)面在物理內(nèi)存找不到則會(huì)把物理內(nèi)存的某個(gè)頁(yè)面置換下來(lái)，最佳置換算法的解決方法就是看物理內(nèi)存中的哪一個(gè)頁(yè)面在將來(lái)最遲需要訪問(wèn)，就置換它。如物理內(nèi)存里是0，7，6，訪問(wèn)到5時(shí)產(chǎn)生缺頁(yè)中斷，檢查物理內(nèi)存，發(fā)現(xiàn)0在將來(lái)第14個(gè)訪問(wèn)到，顯然置換0是最佳方案！usingnamespacestd#include