iT邦幫忙

2021 iThome 鐵人賽

DAY 28
0
自我挑戰組

杰哥的考研紀錄系列 第 28

Day-28 Virtual Memory

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 Massive Storage Management


上一篇
Day-27 Memory Management
下一篇
Day-29 Massive Storage Management
系列文
杰哥的考研紀錄30

尚未有邦友留言

立即登入留言