Review

回顾在cache中，我们是如何降低miss rate的——set associative。核心在于设计一个合理的placement schema。在virtual memory中则遇到了相同的问题，如何减少page fault？简单来说，就是保证virtual address都能映射到physical address，而不是到disk中。

Page table的提出

为了减少page fault，这里想到的最极端的方式，就是之前的fully associative，当出现page fault时，可以将virtual page替换为任意的physical page。但是，前面也说到这种方法虽然可以很大程度上减少miss或page fault，但是当进行查找时，效率低下，需要比较cache中的每一个line，或者physical memory中的每一个page。

为了解决这个问题，在virtual memory中使用——page table：

该table通过virtual page number进行索引；
它保存virtual page和physical page的映射信息，将virtual page number映射到physical page number；
page table中的virtual page number不一定存在对应的physical page number，这时发生了page fault；
作为索引，这个table存储在memory中；

这里先假设，这个table存储在memory中的一段固定且连续的区域（其实实际上不是这样）。
每个程序（或者进程）有自己的page table；
为了定位page table中的数据，硬件中还有一个register来指向每个程序page table的起始位置，称为page table register。

到这里，我们解决了fully associative在查找时的问题，通过建立一个索引结构，从而可以减低page fault。

Page Table的组成

page table的组成示意图如下所示：

Page table的结构示意图

首先看一下page table register，直接指向page table的首地址，因此一个register可以直接确定page table的位置；
不同于fully associative中，需要使用virtual page number与physical page number直接对比，来确定是否page fault，这里在page table中存在一一映射关系；
与cache结构的异同：
- 也有valid bit，可以帮助快速判断是否存在page fault；
  - 当bit=1，virtual page有对应的physical page，无page fault；
  - bit=0，出现page fault；
  这里与cache有一点不同，在page table中，只要你找到virtual page number对应的entry，之后只需验证该valid bit就能知道有无page fault。但是，在cache中，当知道index对应的cache line时，即便验证了valid bit，还不能确定是否hit，还需要继续验证tag field，如果匹配，则hit，否则miss，因为cache中将memory的地址拆成了index和tag两个部分。
- 没有tag field，因为不同于cache中，一个cache line可以对应多个memory block（direct mapped cache），因此使用tag代表高位地址。在page table中，每个virtual page与physical page是一对一的，甚至是多对一的，因此不需要tag字段；
- 在page table中充当index的也不是memory的低位地址，而是直接使用virtual page number；
在上图中，page table中的entry共有 $2^{19}$ 个。即 virtual page number的位数减去valid bit的位数，但是实际中一般设计为32位。

进程之间的切换

多任务执行一直是一个吸引人的目标，在早期的单核时代，为了并行执行，需要将CPU的时钟切成小段的时间片，分配给不同的程序使用。这里就存在一个问题，当一个程序使用的时间片结束后，如何切换到另一个程序执行呢？

程序的执行需要指令和数据，当切换到另一个程序继续执行时，核心就是要找到该程序的指令和数据存储位置。在virtual memory中，我们知道CPU提出的指令中都是virtual address，因此切换程序中需要找到该程序对应的virtual address，来映射到physical address，也就是page table。

page table、program counter和相关的寄存器，指定了一个state，这个状态可以在切换程序执行时，用于恢复原来process的运行状态。操作系统通过加载该process对应的state，可以使该process变成active，从而继续执行。

操作系统不会加载process的完整的page table，而是加载page table register即可，就能定位整个page table，节省空间。

每个process都有自己的page table，因此不同的process可以用相同的virtual address。这些virtual address与physical address的映射，由操作系统来分配和更新，这样使得不同的process之间不会冲突。这样，page table的加入使得对于多个程序同时执行任务更加方便，而不会在访问内存时出现冲突。