virtual memory

background

执行一个只有部分大小在物理内存中的程序，好处是：

程序不受物理内存限制，用户能够随意地在虚拟内存中编写程序
因为用户程序使用了更少的物理内存，因此有更多程序同时运行，提高CPU利用率
I/O的操作更少了

虚拟内存允许文件共享：

系统库能被多个进程共享，尽管每个进程都视系统库为自己的部分，但实际上系统库是在物理内存上的一块空间中；
多个进程能够共享数据，某个进程能在真实的物理内存中开辟一块空间与其它进程共享；
pages在进程创建时能被共享，提高创建进程效率

demand paging

一个程序在被加载进内存时有两种方法：一个是整个装载进去，一个是当你有需要的时候再从disk读到memory，而后者就是demand paging。

为了实现这个方法，我们需要硬件来支持该页是否在内存中，因此可以在page table中设置一个有效位。

访问到一个标记为invalid的页，则叫page fault。此时系统中断，操作系统去从disk中加载该页进内存中。

performance of demand paging

p：page fault的概率
ma：访问内存的时间
pft：发生page fault需要处理的时间（主要是读取page）

有效访问时间 = (1-p) * ma + p*pft

copy-on-write

这个方法的提出是基于系统调用fork()导致的性能下降。在子进程fork一个父进程之后，如果直接将父进程的内存复制一份，考虑到子进程与父进程之间有不少数据内容是一样的，因此可以共享这部分数据，这就是copy-on-write。

步骤如下：

子进程从父进程fork出来，此时两个进程共享同一份内存；
当子进程要修改该共享内存的内容时，则先copy需要修改的页，接着修改复制出来的page；

如下图，当process1要修改pageC的内容时，会先复制一份pageC

由于copy-on-write需要找到一个可用的page，所以操作系统的做法是维护一个pool，随时取出来；

linux系统下提供了vfork()，这个系统调用并不会copy-on-write，而只是共享内存，因此要保证子系统不会轻易修改数据；

page replacement

当一个进程在执行时发生了page fault，当此时没有可用的内存，那么操作系统需要决定去替换一个页，至于替换方法有两种：

一种是直接terminate那个进程，但这不是一个好的方法，因为分页操作应该对用户是透明的（不懂？）

另一种则是交换进程，先把某个进程所有的frame释放了，降低cpu利用率

现在我们来考虑第三种方法page replacement

basic page replacement

发送basic page replacement时，操作系统会做以下操作：

在disk发现自己想要的page；
如果内存中没有可用frame，则用replacement 算法去置换一个frame；
将内存中选中的victim frame写进disk
修改page和frame的表内容
将disk中想要的page写进空出来的frame
重启进程

但这里会有一个问题：每次发生置换都需要两个pages的传送，需要大量的IO操作，因此为了提高效率，可以在page中增加一个modify bit(dirty page)

这个bit用来指示，该page在上一次从disk都出来之后有没有被修改过

因此就可以在replacement时检测这个bit，只有dirty的才会需要被写回disk，否则直接从disk读取想要的pages覆盖那个frame即可；

reference string

这个概念是用来评估replacement算法效率的（还需要知道内存的frame大小），用来记录每次对memory的引用
通常是page number
例如访问的地址为0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103, 0104, 0101, 0610, 0102, 0103, 0104, 0101, 0609, 0102, 0105
reference string就是1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1

FIFO page replacement

这是最基本的置换算法，很简单，就是维护一个队列，队列按时间连接，即最新的frame在队列尾。每次置换队列头的frame；

但这个算法有一个bug，具体可以参考Belady’s anomaly。即它可能会随着分配的内存即frame增多，它的page fault rate反而增大。

optimal page replacement

这是效率最高的算法，也是发送page fault可能性最小的一个算法。简单概括就是：

置换内存中某个frame，该frame在这时候很久才会被再次引用，这里的很久指的是相对其它frame要久

但这个算法不好实现，因为很难去判断未来在什么时候才会再次引用该frame

LRU page replacement

least recently used algorithm

这是综合以上两种算法的算法，往前追溯reference string，找到距离现在最久的frame，置换该frame

这里介绍两种实现方法：

counter
- 设置一个时钟，每次内存访问的时候，时钟就会加一；
- 所访问的page，就会在page table里面的time to use设置时钟值；
- 这样，只要每次遍历一下page table，即可找到最小的page，这就是我们要置换出去的frame；
stack
- 其实是一个双向列表。。
- 即维护这样一个stack，每次引用到page时，则从stack中抽取该page放到stack的顶部；
- 那样，最下面的page则是要置换出去的frame；

LRU-Approximate Page Replacement

多数硬件都会提供一个支持——reference bit，用来指示该page是否被使用过（读写）

Additional-Reference-Bits Algorithm

假设reference有8位，每个时钟周期该8位reference bit就右移一次，如果该周期内内存有被引用，则设最高位为1，否则设为0。这样，将8位reference bit转换成无符号整数，最小的page则为LRU page

second-chance algorithm

实现这个算法的基础是维护一个循环队列和一个指针，队列中的page都有一位reference bit，指针指向要替换的page

检查reference bit，如果该位为1；
指针下移，直到找到reference bit为0的page；
做替换

在最坏的情况下，指针会遍历一遍，将所有page的reference bit清零

enhanced second-chance algorithm

相对second-chance algorithm，这个算法添加了1bit，作为检查该bit是否被修改，即modified bit。

这样就将pages分为了四类：

(0, 0)：最好的选择，最近没有用过，并且没有修改过；
(0, 1)：次好的选择，最近没有用过，但修改过；
(1, 0)：次差选择；
(1, 1)：最差的选择

这种算法有一个好处，就是前面提过的modified bit的好处，减少了I/O的消耗。

counting-based page replacement

做一个计数，选择使用过最多次的/最少次的page。一个too expensive的算法~~

page buffering algorithm

系统维护一个free frames pool，在要被写出的帧写回disk之前，首先将想要的frame写进free frame，然后再把victim frame写回disk，据说？这样进程就能快速重启

allocation of frame

分配给每个进程的frame数量：

minimum number of frames：与计算机的体系结构有关
maximum number of frames：与内存呢大小有关

Allocation algorithm

主要是两种

平均分配
按权重分配：根据可用frame和进程大小和数量分配