第二十二天 Virtual Memory(虛擬記憶體)--(二)

我們昨天提到demand paging，那如果我們想讓他能最佳化可以運用copy-on-write(COW，寫入時複製)。

copy-on-write讓parent和child process在記憶體能共用一個page，只有在child要寫入資料時，才會複製一個page出來，放到free page。所以說copy-on-write能讓多個process共用page，不用佔記憶體空間，提高process creation的效率。在這裡作業系統會提供一個pool來存放free page，如果需要free page時，按照zero-fill-on-demand分配。

複製時，運用vfork() system call，讓parent暫停，直到child執行exec() system call。下面有兩張例圖，顯示寫入前跟寫入後：


但我們要思考一個問題，如果pool裡沒有free frame怎麼辦？這時就會需要用到page replacement！

Page replacement：
page replacement裡會用到一個modify(dirty) bit來判斷page是否有被修改過，如果有被修改過，就會被swap到disk去，釋放空間給其他page。

page replacement的做法：

1. 在disk找需要用的page
2. 找一個free frame
   -> 有，直接使用
   ->沒有，就找一個victim frame(用dirty bit找)作page replacement
3. 將page載入free frame，更新page和frame table
4. 從剛剛中斷的地方開始執行
   這裡需要注意到，因為要把page搬上搬下，這會增加了有效應用時間(EAT)。
   以下是page replacement的例圖：
   
   Page and frame replacement演算法分成兩部分：frame-allocation algorithm(我們等等再談)和page-replacement algorithm：以最低的page fault rate為最高原則。

在演算法中，我們會運用reference string來表示page replacement，從哪個page換到那個page，數字就代表page number(例如：7,0,1,2,0,3,0,4)。

接下來談談page-replacement algorithm有哪幾種：

• First-In-First-Out(FIFO) Algorithm：
  先進先出，先進frame中的page會先被替換掉，這個雖然看似簡單，但是會有問題。以下有舉例：
  
  依照這個reference string，會發生15個page fault
  不知道有沒有人會認為，如果我給多一點的frame會不會減少page fault發生的次數呢？基本上是沒錯，但是總是會有例外發生，就叫做Belady’s Anomaly，給越多的frame越會發生page fault。

• Optimal Algorithm
  顧名思義，他是最好的演算法！會將長期用不到的page給交換出去，但這個演算法是很難做到的，因為必須要預測未來，才能決定要swap誰。以下是範例及運算：
  
  依照這個reference string，會發生9個page fault

• Least Recently Used(LRU) Algorithm
  這個演算法的效果也不錯，他是以最近不常使用的page交換掉，用過去推測未來。以下是範例及運算：
  
  依照這個reference string，會發生12個page fault，比FIFO好比Optimal差。

  LRU的實作分成兩種：counter和stack。

  • Counter：把時間記錄下來，當要交換時，把值最小的交換出去，但這個方法需要把整個table給瀏覽過一遍。
  • Stack：將用到的擺在最上面，運用double link。
    以下是範例及運算：
    
    LRU和Optimal都是用stack演算法，所以都不會發生Belady’s Anomaly的現象。

以下三個演算法，我們明天繼續！

• LRU Approximation Algorithms—Enhanced Second-Chance Algorithm
• Counting Algorithm
• Page-Buffering Algorithm