os頁面置換

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

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

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

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

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

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

7、未使用過。就可把該位是0的頁淘汰出去，因為在最近一段時間里它未被訪問過。4第二次機會算法（SCR）第二次機會算法的基本思想是與FIFO相同的，但是有所改進，避免把經(jīng)常使用的頁面置換出去。當選擇置換頁面時，檢查它的訪問位。如果是0，就淘汰這頁；如果訪問位是1，就給它第二次機會，并選擇下一個FIFO頁面。當一個頁面得到第二次機會時，它的訪問位就清為0，它的到達時間就置為當前時間。如果該頁在此期間被訪問過，則訪問位置1。這樣給了第二次機會的頁

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

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