# 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`