Virtual Memory（3）：Page fault

Page fault的基本内容

是什么

回顾cache中的miss，page fault表示的是同样的含义，只不过page fault一般是在main memory中miss，从而需要访问disk。这其中的时间差远远高于cache和main memory之间的时间差。

如何判断发生了page fault

在page table中有一个valid bit，当GPU发出的指令中，使用的virtual address中的virtual page number，用来定位page table中的一个entry时，检查该entry的valid bit，如果为1，则发生了page fault。

Page fault时发生了啥

如何处理page fault

发生page fault后，virtual page number找不到对应的physical page number，此时触发异常。操作系统接过控制权，需要完成两件事：

1. 到memory的下层存储disk中找到对应于virtual page number的page；
2. 将来自disk的page放到main memory中；

2个问题

这里自然遇到了2个问题？

1. 如何找到virtual page number在disk中对应的page？
2. 如何替换physical memory中的page以放置来自disk的page？

针对问题1

到目前为止，不管是virtual address与physical address直接映射，还是通过page table加快映射，都不涉及disk。但是现在出现了page fault，为了找到virtual page number对应的来自disk的page，因此需要记录两者之间的映射关系，如下图所示。

这里通过page table分别维护了两种映射关系：

• virtual page number 到 physical page number；
• virtual page number 到page address in disk；

有时，这两种映射关系是两个数据结构分别维护的，但是逻辑上看是一张表。

在这里要澄清一个问题，在page table中，如果不出现page fault(valid bit=1)时，是否不需要维护virtual page number到page address in disk的关系？仍然需要，即需要对于所有的virtual page维护一个page address in disk的映射关系，无论它们当时是否page fault，因为我们不知道后续的执行中，哪个virtual page又会出现page fault（比如别的程序把main memory都占满了）。

这种操作通过操作系统在创建process时，同时在disk中创建swap space实现。此时，把virtual page number映射到disk的关系也全部记录下来。

针对问题2

我们知道在memory hierarchy中，只有相邻的两个level之间才能传递数据，因此，即便virtual page number映射到page address in disk，也不能访问，需要将disk中的page放到physical memory中，进行访问。

前面介绍page table时提到，为了减少page fault，我们允许将virtual page映射到任意的physical page。当需要将disk中的page加载到physical memory时，有两种情况：

1. physical memory未满，可以直接将disk中的page选择一个放入其中，因为是fully associative；
2. physical memory已满（很多程序同时运行时），操作系统需要在physical memory中选择一个page进行替换。

第一种情况很简单，直接将disk中的page写入即可。

第二种情况则比较复杂，为了最大程度上减少page fault的发生，应该尽量保证替换的physical page后续不会被访问，这里又用到了之前replacement policy中提到的LRU。因此，在这个过程中发生两步：

1. 操作系统基于replacement policy（如LRU）替换虚选择的physical page；
2. 同时，这个选择的physical page中的数据也要写回到disk中对应的swap space，以保证数据不会丢失；

virtual memory中的replacement policy

前面也提到过，实现LRU很昂贵，因为每访问一次memory，都需要更新一次数据结构。面对这种问题，这里使用一种近似的方法来解决。

在physical page中设置一个reference bit(use bit)，当该physical page被访问，这个标识被设置为1。但是，操作系统在固定的时间段内不断地清除该bit，之后继续记录每个page的reference bit。

这种操作有什么用？举例说明，当第一次访问该page时，reference bit=1，之后被操作系统清0，之后在替换page时，发现该page的reference bit还是1，说明该page最近被访问了，它最好不要替换。这里边对于清0的时间间隔决定该page被访问的“有多近”。

参考资料

1. Computer Organization and Design - 5.7 - Page faults