HackMD
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。
