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是一種執行的技術,從名字就可以理解他的做法,一個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。
選擇Victim Page時有不同的選擇方法,那效果一樣有好有壞,以下一一介紹:
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的作法是挑未來長期不會使用的Page當作Victim Page。
OPT的Page Fault Ratio最低,不會發生Belady Anomaly。但是由於這個方法要預期未來,無法被實作,所以這只是作為理論跟其他的方法做比較。
LRU是一個可行且不錯的概念,他選擇"最近最不常使用"的Page當作Victim Page,相當於反向的OPT作法。
他的效能不錯,不會發生Belady Anomaly。不過需要硬體支援,cost高。
它的實際做法有兩種,一種是用Counter,把Counter的值複製到每次需求的Page,就像是押上時間印一樣,我們只要找數字最小的當作Victim Page就好了。
另一種做法是Stack,每次把需求的Page push到Stack的最上面,那麼最底部的Page就準備要被當成Victim Page。
這邊直接幫大家找了一個例子了R,自己了解一下,不行再來問我。
前面提到LRU成本比較高,所以我們就換個方法降低成本,比如說可以在Page Table新增一個Reference bit,當作近期是否有用到過,如此一來就不用擔心時間的過去會讓數字變得太大。加上Reference bit有三種作法,分別為Additional Reference Bits Usage, Second Chance, Enhanced Second Chance,不過解釋起來蠻花時間的,就不特別解釋了,有興趣的一樣自己查一下R~
這兩個代表Least Frequently Usage以及Most Frequently Usage,字面上就代表誰最少用到或是誰最常用到的會變成Victim Page。
但這兩個的效果都不是很好,可能發生Belady Anomaly,而且製作cost又高。
沒什麼優點,缺點又一大堆,就不多說了。
那麼Replacement的部分就到這邊啦~快到結尾啦~(灑花(燦笑
上一篇 | 下一篇 |
---|---|
Memory Management | Massive Storage Management |