OS酱：“哎呀内存太小了，人家又缺页了！”
操作系統--虛頁面管理之頁面置換算法
?
系統的內存并不是無限大，操作系統會為每個程序分配內存，當訪問的地址塊不在內存中，就要從外存（即硬盤，U盤等）調入，這就是所說的缺頁異常。
當發生缺頁異常時，操作系統會選擇一個頁面進行換出從而為新進來的頁面騰出空間。對于被置換的頁面有以下情況：
如果要被換出的頁面只被訪問而沒被修改，那么直接將此頁面丟棄。
如果要被換出的頁面被修改，那么為了使得外存中的數據保證正確，先要將內存中的數據寫入外存，然后在丟棄。
雖然，被置換頁面的可以隨機選擇，但是不同的選擇，所導致后續系統訪存開銷是不一樣，甚至會出現很極端的情況，每次訪存都發生缺頁中斷，極大的增加系統額外的訪存開銷。
很多的頁面置換算法被提出用于操作系統，但是在其他各類應用，無論是數學還是經濟學都有類似的涉獵，今天我們就來討論一下這些算法。
OPT算法（最佳置換算法）
算法特點：
最佳置換算法是由 Belady 于1966年提出的一種理論上的算法。每次選擇以后永不使用的， 或許是在最長(未來)時間內不再被訪問的頁面的頁面被淘汰。顯然OPT算法是最優的，但是在實際操作往往無法預知未來，所以OPT只存在理論而不能真的實現，通常用于衡量其他置換算法的優劣。
算法流程：
在缺頁中斷發生時，首先從 主存中移出永遠不再需要的頁面；如無這樣的頁面存在，則選擇最長時間不需要訪問的頁面。
舉例如下：
?
?
缺頁9次，總訪問次數12次缺頁率：6/12 = 50%
FIFO算法（先進先出置換算法）
Belady異常：
采用FIFO算法時，如果對一個進程未分配它所要求的全部頁面，有時就會出現分配的頁面數增多但缺頁率反而提高的異常現象。
?
實現方法：
最簡單的頁面置換算法，每次淘汰最先調入內存的頁面。由操作系統維護一個所有在當前內存中的頁面的鏈表，最早進入的放在表頭，最新進入的頁面放在表尾，每次淘汰隊首頁面。因為先進入的頁面可能已經使用完畢，所以不會再被使用的概率可能性較大，優先淘汰。但是FIFO容易產生Belady異常。
?
該算法實現比較簡單，對具有線性順序訪問的程序比較合適，而對其他情況效率不高。因為經常被訪問的頁面，往往在內存中停留最久，結果這些常用的頁面卻因變老而被淘汰。
舉例如下：
?
?
缺頁9次，總訪問次數12次缺頁率：9/12 = 75%
LRU算法 (最近最久未使用算法)
利用局部性原理，根據一個作業在執行過程中過去的頁面訪問==歷史來推測未來==的行為。它認為過去一段時間里不曾被訪問過的頁面，在最近的將來可能也不會再被訪問。所以，這種算法的實質是：當需要淘汰一個頁面時，總是選擇在最近一段時間內最久不用的頁面予以淘汰。 即淘汰最近最長時間未訪問過的頁面。
LRU置換算法的硬件支持
-
寄存器為每個在內存中的頁面配置一個移位寄存器，用來記錄某進程在內存中各頁的使用情況。移位寄存器表示為R=Rn-1Rn-2Rn-3…R2R1R0當進程訪問某物理塊時，要將相應寄存器的Rn-1位置成1;同時，每隔一定時間將寄存器右移一位；如果把n位寄存器的數看作一個整數，那么具有最小數值的寄存器所對應的頁面，就是最近最久未使用的頁面。
-
棧利用一個特殊的棧來保存當前使用的各個頁面的頁面號。每當進程訪問某頁面時，便將該頁面的頁面號從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的編號，而棧底則是最近最久未使用頁面的頁面號。
?
舉例如下：
?
缺頁7次，總訪問次數12次缺頁率：7/12 = 58.3%
?
實際上，LRU算法根據各頁以前的情況，是“向前看”的，而最佳置換算法則根據各頁以后的使用情況，是“向后看”的。LRU性能較好，但需要寄存器和棧的硬件支持。
?
LRU是堆棧類的算法。理論上可以證明，堆棧類算法不可能出現Belady異常。
?
FIFO算法基于隊列實現，不是堆棧類算法。
?
LRU算法的性能接近于OPT，但是實現起來比較困難，且開銷大；FIFO算法實現簡單，但性能差。
Clock算法（時鐘置換算法）
也稱為NRU算法（最近未使用算法）是LRU和FIFO的折中算法。
?
實現：CLOCK算法是給每一個頁面設置一個訪問位，用來標識是否最近被訪問過，Clock維護的是內存中頁面組成的循環鏈表。當頁面被裝入內存時，或是內存中的頁面被訪問時，訪問位被置為1。若內存已被裝滿，那就需要淘汰一個頁面，于是指針就從上一個被淘汰的頁面的下一個位置開始，順序去遍歷這循環列表，訪問到訪問位為1的頁面時，就把該訪問位置0，繼續遍歷，只要遇到訪問位為0的頁面時，淘汰該頁面。其實調入內存也是訪問，那么上面就變成了：
?
訪問則置1
替換則遍歷
遍歷遇1置0，遇0替換。
?
舉例如下：
內存中共分配3個頁面資源
?
改進后的Clock算法(二次機會法）
由 訪問位A 和 修改位M 可以組合成下面四種類型的頁面：
?
最近既未被訪問，又未被修改(Visit=0, Modify=0) ：是最佳淘汰頁。
最近未被訪問，但已被修改(Visit=0, Modify=1)：并不是很好的淘汰頁。
最近已被訪問， 但未被修改(Visit=1, Modify=0)：該頁有可能再被訪問。
最近已被訪問且被修改(Visit=1, Modify=1)：該頁可能再被訪問。
?
執行過程：5. 查找00，有，淘汰，算法結束！繼續循環直到一圈結束，未找到則下一步；6. 查找01，有，淘汰，算法結束！未找到繼續循環遍歷直到一圈結束，在此過程中將Visit位置為“0”，未找到則下一步；7. 重復第一步。
?
優點：減少磁盤I/O；缺點：幾輪掃描，增加開銷！
總結
以上是生活随笔為你收集整理的OS酱：“哎呀内存太小了，人家又缺页了！”的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： html中select标签怎么用
- 下一篇： 证明：对于一棵二叉树，若度为2的结点有n