Operating System #9

Page Fault

• 當process在記憶體中找不到所需的page時，就會發生page fault。
• 它要怎麼知道那個page已經不是它的資料了？使用Valid-Invalid Bit。
  • 當page被移出時，它會把有使用到該page的地方的Valid-Invalid Bit都改為i，讓這些process知道之後不能直接使用該page。
• 發生page fault我們必須再找一個page移出去，並把我們需要的資料寫進來。這個動作非常耗時，因此我們要盡量降低page fault發生的機會。

Page Replacement

• 如何選擇移出去的page(又稱為victim)是很重要的事情，因為如果移出去馬上又要移進來就會很浪費時間。

FIFO

• 按照順序，最早進來的就移出去。
• 演算法簡單，但效果通常不好。
• Belady Anomaly - 當分配的page frame越多，反而page fault越多的情況。

Optimal

• 最佳演算法，用page fault最少的方式來移動。
• 問題是我們根本不知道接下來的process會需要什麼，因此只會出現在題目，實務上根本不會用到。

Least Recently Used (LRU)

• 使用最長時間沒有被使用到的當作victim。
• 實作時需要在每個page都放一個counter，選擇最小的那個移出。
• 不會有Belady’s Anomaly問題，因為是stack的演算法。

LRU Approximation

• LRU有兩個問題：
  • 因為要有counter，需要硬體支援
  • 運算太慢
• 改進方法：使用Additional-Reference bit支援。
  • 一開始為0。
  • 被存取時改為1。
  • 優先替換掉0的page。
• 根據Additional-Reference bit，又有了以下的方法。

Second-chance algorithm

• 基礎和FIFO一樣，但多了Reference bit。
  • 若Reference bit = 0，替換它。
  • 若Reference bit = 1，變為0。
• 如此一來就不用使用counter的裝置了。

Enhanced Second-Chance

• Second-chance algorithm的再強化版，再多一個modify bit。
• 根據(reference bit, modify bit)
  • (0,0)，最優先替換者。
  • (0,1)，有點不好，可能在替換後又需要寫入。
  • (1,0)，不好，很有可能馬上要再用到。
  • (1,1)，最差，可能馬上要寫入或是讀取。

Counting Algorithms

• Page被使用時，就一個count++，去記錄每個page被使用到的次數(之前的LRU是用時間)。
• 又分為LFU和MFU：
  • LFU: 換掉使用最少的
  • MFU: 換掉使用最多的(因為少的可能才剛被讀進來)

Page-Buffering Algorithms

• 算是一個加速的手段，總是放置一些空的frame。
• 讀page時都先放到這邊，等到空閒時才去找victim做交換。

Thrashing

• 正常來說，如果我們可以讓多個processes同時執行，應該執行越多，CPU的utilization就會越高。
• 但實際上太多的processes會讓page fault發生的機率大大上升，導致在process多到一個值之後，CPU utilization就會大大降低。
• 該現象稱做Thrashing。

Prepaging

• 為了提高效率，我們可以在page要被使用之前就預先將它們讀進來，降低page fault造成的低耗現象。
• 這個技巧稱做Prepaging。

tags: note