# 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。 ![](https://i.imgur.com/6agymxY.png) ## 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的次數可能會更高,底下直接幫各位找了一個例子說明: ![](https://i.imgur.com/CXq0CdA.png) ### 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。 ![](https://i.imgur.com/A1eP0NP.png) 這邊直接幫大家找了一個例子了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) ![](https://i.imgur.com/gPPXBdP.png)