# Virtual Memory

###### tags: `IT鐵人`

跟上一篇有點關係的內容，我們會利用Disk來代替部分Memory的空間，這一篇一樣會講OS怎麼使用或是判斷有關Virtual Memory的事情。

## 複習

Virtual Memory的作用在於允許Process大小再超過Physical Memory可用空間大小時，仍能執行，即Logical Memory Size不受限於Physical Memory Size。

所以如果能夠不載入整個Process，而是載入需要用到的Page，就能提高Multiprogramming degree，並且可以減少I/O Transfer Time，不用把每個Process完整載入。

## Demand Paging

Demand Paging是一種執行的技術，從名字就可以理解他的做法，一個Process要執行的時候，我們可以只載入些許的Page，或者甚至不載入任何Page，等到需要用到某個Page時再把該Page拉進來Memory。

要做到這件事情，就要在Page Table中新增一個Valid bit，這個bit表示該Page在Memory中或是Disk中，這部分在前面計算機組織的Virtual Memory章節就有講到了，如果該Page在Disk的話，要把該Page load進Memory中，那麼OS負責的部分就是在Memory滿了情況下，決定哪個Page要被丟回去Disk，被抓回去Disk的Page稱為victim page。


## Page Replacement Algorithm

選擇Victim Page時有不同的選擇方法，那效果一樣有好有壞，以下一一介紹：

### FIFO

FIFO的做法是把最早載入的Page當作Victim Page。

他的效果差，Page Fault Ratio相當高、可能遭遇Belady Anomaly。不過簡單，易於製作。

舉例來說，如果Memory有三個Page空間(Frame)，一開始都是空的，然後依序出現了下列Page需求：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1，這時候三個Frame會有以下改變：

|需求Page|First|Second|Third|Page Fault?|
|-|-|-|-|-|
|7|7|||yes
|0|7|0||yes
|1|7|0|1|yes
|2|2|0|1|yes
|0|2|0|1|no
|3|2|3|1|yes
|0|2|3|0|yes
|4|4|3|0|yes
|2|4|2|0|yes
|3|4|2|3|yes
|0|0|2|3|yes
|3|0|2|3|no
|2|0|2|3|no
|1|0|1|3|yes
|2|0|1|2|yes
|0|0|1|2|no
|1|0|1|2|no
|7|7|1|2|yes
|0|7|0|2|yes
|1|7|0|1|yes

這18次的Page要求就發生了15次的Page Fault，效益非常差。

並且FIFO可能會發生一件異常現象，稱為Belady Anomaly，有時候Memory有較多的Frame，可以給Page塞進來，但發生Page Fault的次數可能會更高，底下直接幫各位找了一個例子說明：


### OPT

接下來介紹最好的做法，OPT的作法是挑未來長期不會使用的Page當作Victim Page。

OPT的Page Fault Ratio最低，不會發生Belady Anomaly。但是由於這個方法要預期未來，無法被實作，所以這只是作為理論跟其他的方法做比較。

### LRU

LRU是一個可行且不錯的概念，他選擇"最近最不常使用"的Page當作Victim Page，相當於反向的OPT作法。

他的效能不錯，不會發生Belady Anomaly。不過需要硬體支援，cost高。

它的實際做法有兩種，一種是用Counter，把Counter的值複製到每次需求的Page，就像是押上時間印一樣，我們只要找數字最小的當作Victim Page就好了。

另一種做法是Stack，每次把需求的Page push到Stack的最上面，那麼最底部的Page就準備要被當成Victim Page。


這邊直接幫大家找了一個例子了R，自己了解一下，不行再來問我。

### LRU變形

前面提到LRU成本比較高，所以我們就換個方法降低成本，比如說可以在Page Table新增一個Reference bit，當作近期是否有用到過，如此一來就不用擔心時間的過去會讓數字變得太大。加上Reference bit有三種作法，分別為Additional Reference Bits Usage, Second Chance, Enhanced Second Chance，不過解釋起來蠻花時間的，就不特別解釋了，有興趣的一樣自己查一下R~

### LFU & MFU

這兩個代表Least Frequently Usage以及Most Frequently Usage，字面上就代表誰最少用到或是誰最常用到的會變成Victim Page。

但這兩個的效果都不是很好，可能發生Belady Anomaly，而且製作cost又高。

沒什麼優點，缺點又一大堆，就不多說了。

## End of Replacement

那麼Replacement的部分就到這邊啦~快到結尾啦~(灑花(燦笑

| 上一篇 | 下一篇 |
|-|-|
|[Memory Management](https://hackmd.io/@dZfCcN4hT8aUuDPv3B8CWQ/HkrX_NsNF)|[Massive Storage Management](https://hackmd.io/@dZfCcN4hT8aUuDPv3B8CWQ/By5RsUpVF)