Copy-on-Write

• 簡單來說，現在有parent process跟child process在共享一個page，但當child process想更改page裡的資料時就會變得很麻煩，所以這時就需要「複製」一份副本-frame給想childd process，如此一來parent process便不會受到影響，就能提高process的執行效率。
• 在這裡只會使用到系統呼叫中的fork()，並不會使用到vfork()，因為：

1. 使用fork()的原因是parent process會同時跟child process一起執行，但需要MMU的硬體支援。
2. 不使用vfork()的原因是它多在沒有MMU的OS中使用，且會促使parent process暫停執行，直到child process使用exec()語法才可以。

• 但如果沒有free frame可以使用的話就會造成演算法的不確定，且會讓相同的page一直被swap in記憶體許多次，就會拉低整體效率，並不是一個好現象。

Page Replacement

• 接下來討論page「取代」的基礎觀念。
• 其主要目的就是讓page在替換後可以減少page fault發生的機率，且機率降低，OS的壽命也越長同時硬體的使用壽命也能增加。
• 基本觀念就是先找尋想要的page所在位置，並查看是否有free frame的存在，如果有的話直接將要加入的直接覆蓋；若沒有free frame就選擇一個page當victim page，選擇方式為查看frame裡的資料有沒有被修改，有修改的稱為modify(dirty) bit，就必須寫進硬碟中。
• 以下為示意圖：
  

Page and Frame Replacement Algorithms
接下來會提到一些不同的演算法：

• page-replacement algorithm：在做page替換時，讓page fault的發生率下降，在之後的範例中我們會使用最簡單的表示法-reference string來表示記憶體內page替換的過程，如這個演算法的表示法就是「7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1」，有8個page在輪替。
• First-In-First-Out(FIFO) Algorithm：
  依先到先處理的觀念為基礎，而一個process一次最多能容納3個pages，所以第4順位要swap in時，就要將第1順位的swap out，才有空間可以容納，以此類推完成此演算法。
  但有時加入越多的pages不見得比較好，加入越多的page，就越容易發生page fault，也就是Belady's Anomaly現象產生。
  以下為示意圖：
  
  ==>一共發生15次的page fault，如果後面順位的page想進入page frame但跟裡面已存在的3個重複的話就沒有page fault，沒重複就表示page fault。
• Optimal Algorithm：
  簡單來說就是將未來最不常用的page當作victim page來取代，藉此提升整體效率
  以下為示意圖：
  
  ==>一共發生9次page fault。
  ==>前面5個順位的page都沒有問題，跟FIFO的概念相同，但到了第6順位的page 3時，接著後面的是page 0，因此將裡面的page 1給swap out出來，依此類推完成此演算法。
  ==>在所有演算法中是page fault發生率最少的。
• Least Recently Used(LRU) Algorithm：
  定義為依靠歷史的資料來進行推斷，也就是從過去到現在最不常使用的page作為victim page。
  以下為示意圖:
  
  ==>在這之中一共發生12次page fault。
  ==>一樣前5個順位的page都沒問題，在第6順位的page 3要swap in時，觀察到第2順位的page 0使用次數比第3順位的page 1還多，所以取代了page 1的位置，依此類推完成此演算法。
  ==>比FIFO演算法好卻也劣於Optimal演算法，但是最常被使用的好演算法。
• LRU Approximation：
  此演算法需要特別的硬體去支援。有兩種形式：
  1. Reference bit：每一個page都有個初始值為0的bit，如果被reference的話就更改為1，沒被reference的話，也就是bit = 0的就取代掉。
  2. Second-chance algorithm：以FIFO演算法為基礎，搭配著Reference bit一起使用。也就是說每個page的初始值為1，而被reference的就將bit改為0，然後再往下一個page前進，如果下一個bit = 0的話就將以替換。
     以下為示意圖：
     

剩下的演算法將會在明天繼續說明喔~!