前一章提到虛擬記憶體需求分頁發生Page fault處理＆影響Page fault發生因素其中之一是頁面置換演算法

再複習一下Page fault處理步驟：

1. 發出page fault interrupt
2. 找一個暫時不用的frame(free frame)
3. 將所需的page從disk swap in
4. 更新page table

其中第2點，究竟要怎麼選frame，要翻誰的牌呢？以前會問問皇上，現代要講求公平！
而這就跟今天要講的演算法有關

1. FIFO(有 Belady's 異常)

先放入的frame先被換掉，你想像有一個３層的抽屜，每個抽屜都只放得下一個畫框(frame)，你總共有4個畫框要放，在一開始的時候抽屜是空的，依照指令開始放畫框進去
當第4個畫框要放進去的時候，就必須要把最先放進去的拿出來（淘汰），新的frame才能放進去

以上有兩個動作要釐清一下

• 把畫框放進抽屜(表示這個frameh從disk中要拿進memory) -> page fault
• 抽屜沒有位置要把舊的淘汰，給新的放 -> page replacement
  所以以上狀況總共有4次把畫框放進抽屜的行為(page fault) + 1次抽換畫框的行為(page replacement)

上一章有提到：frame數越多，表示一次可以載入的page數量較多，未來發生Page fault機率下降。
但看看下面的情況，怎麼不減反升？！這情況又叫Belady's異常

p.s. 有沒有覺得跟之前的短期排班演算法似曾相識? 原來也就這幾招~

2. OPT

當需要頁面置換的時候，算命預測一下未來，看現在抽屜哪一個frame會最晚再被拿進來用到，就先把它淘汰掉。如果有抽屜中兩個畫框未來同時用的次數一樣多的話，就回到樓上的FIFO。
但如果算命準的話，每個人都財富自由了，這種情況會遇到的困難就是未來難預料，因為會牽扯到你要觀察未來區間是多長，因此這種方式通常當理論值，只能嘴上說說，實作困難。

3. LRU

這種方式有點像你玩鋪克牌從最下面抽一張牌走，再蓋了一章牌在牌堆最上面；抽屜從下往上開始放畫框，放滿後要抽換時，最下面抽掉，一個一個往下移，新的放最上面。
不管抽屜裡有沒有當下需要的，只要被選到就是往上擺，擠掉最下面那個，如下圖：

但上面這種情況不算一次page fault，因為它沒有從disk中取frame，只是調整了一下位置(需要stack pop和push 1和2)，LRU最終目的就是把過去到現在最久時間未使用的那頁替換掉，占茅坑不拉屎的都走開。一開始我會有點跟FIFO搞混（先進來的就先出去），看看以下比較就能清楚明白：

4. LRU 近似法則(可能有 Belady's)

上面LRU的效果不錯，也不會有Belady's異常，但因為會需要用到大量硬體支援 (如:需要Stack知道被使用的先後次序) ，所以出現了這個近似法則，利用FIFO + 一個Reference Bit。
又分以下兩種:

• Second Chance
  每個 page 的初始值 reference bit 值設為 1，每次被指到的 page 其 reference bit 值就改為 0，然後指下一個 page，如果下一個被指到的 page 其 reference bit 值為 0 的話，則替換該 page。
  

• Enhance Second Chance
  FIFO + 一個Reference Bit + Modification Bit 配對值作為挑選 Victim Page 的依據。
  每個 page 近期有被修改 Modification bit 值設為 1，近期未被修改 Modification bit 值就改為 0
  這個改進 second chance 的方法是為了減少 I/O disk成本

  優先被替換的順序如下:
  (Reference Bit + Modification Bit)

  • (0,0)：最近沒被用到過也沒被修改過。
  • (0,1)：最近沒被用到過，但是有被修改過。
  • (1,0)：最近有被用到過，但是沒被修改過。
  • (1,1)：最近有被用到過，也有被修改過。

補充: 猛移現象Thrashing

分類會依照第一篇介紹的分類架構來進行
由於是將學習過程記錄下來，如果有任何錯誤歡迎糾正

以下參考連結在學習過程中覺得非常有幫助：
-Chapter3-作業系統-虛擬記憶體-part2
-虛擬記憶體 Virtual Memory