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

• LRU Approximation Algorithms—Enhanced Second-Chance Algorithm
  因為LRU需要特別的硬體支援，而且使用後還是很慢，所以產生LRU近似演算法，Second-Chance Algorithm跟Enhanced Second-Chance Algorithm。它添加了一個reference bit來帶表page有沒有被用過，1代表有0代表沒有，初始值皆設為0。

  • Second-Chance Algorithm：
    又稱為clock algorithm，以FIFO為基礎，如果在找victim 時，找到的reference bit為1，會將reference bit改為0，給他一次機會，下次再找到他時，就會被交換掉。以下有例圖：
    
  • Enhanced Second-Chance Algorithm：
    加強版的演算法，多增加一個dirty bit來判斷。
    以下有四種模式，越上方的越會先被交換掉：
    (reference bit , dirty bit)
    (0,0) ->最近沒有被使用也沒有被修改
    (0,1) ->最近沒有被使用，但有被修改
    (1,0) ->最近有被使用，但沒被修改
    (1,1) ->最近有被使用而且也有修改
    運用此方法可能要在queue內搜尋很多次

• Counting Algorithms：
  這種演算法很少用，他是計算被用到的次數來決定，有兩種方式：

  1. Lease frequently used algorithm：
     將最少運用到的page交換掉
  2. Most frequently used algorithm：
     運用次數少的page可能才剛交換近來，所以交換已經運用次數多的，因為可能不會再用到它。

• Page-Buffering Algorithms：
  當page被修改過後，一段時間未被使用，則將被修改的page移入磁碟內，dirty bit重設為0。然後使用一個free frame記錄是哪些page被修改過，當需要再用到時，可以直接取出重新使用。
  這個演算法是為了要減少把victim page swap out出去的時間。

說完page replacement的演算法，我們來說說frame的分配。每個process都有最多跟最少frame的數量限制，而分配的方啊有兩種：

1. Fixed allocation(固定分配)：又分為兩種

• Equal allocation：
  每個process分配到的frame是一樣多的，可以分配一些frame或是分配不均的可以當成free frame使用。
• Proportional allocation：
  按照每個process的大小比例，進行分配。

2. Priority allocation：
   按照優先順序的比例進行分配，如果發生page fault，會從process中的frame找一個低優先的取代掉。

Frame的配置還分為global跟local：

• Global allocation – global replacement：
  Process要找一個frame來替換時，可以考慮到所有process的frame。
• Local allocation：
  Process找frame替換時，只能找自己的frame。
  global replacement有較好的throughput，所以經常使用。

當process分配到的frame不夠多時，就有可能會發生thrashing 現象！至於thrashing現象是什麼，我們明天來說明吧！