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会有以下改变：

这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的部分就到这边啦~快到结尾啦~(洒花(灿笑