6. Page fault

1. Lazy page allocation
2. Zero fill on demand
3. Copy on write fork（写时复制）
4. Demand paging
5. Memory mapped files

这里主要记录课程中讲述到的一些关于 Page fault 的 trick，分别为：

Lazy page allocation
Zero fill on demand
Copy on write fork
Demand paging

Memory mapped files

1. Lazy page allocation

xv6 中用户分配内存使用的是 sbrk 接口，其实际上调用了 growproc 接口，该接口实现如下：

int growproc(int n)
{
  uint sz;
  struct proc *p = myproc();
  sz = p->sz; // 1. 增加进程大小
  // 2. 用户进程页表增加 page。
  if(n > 0){
      if((sz = uvmalloc(p->pagetable, sz, sz + n)) == 0) {
          return -1;
      }
  } else if(n < 0){
      sz = uvmdealloc(p->pagetable, sz, sz + n);
  }
  p->sz = sz;
  return 0;
}

该接口可以分配/回收用户进程内存，用户进程的 malloc 接口实际上分配内存便是使用这个接口。主要做了两件事情：

增加进程大小 struct proc.sz
增加/回收进程页表对应的虚拟页，并建立对应物理地址与虚拟地址的映射。

这种方式实际上是 Eager allocation，通常来说，应用程序会申请多于自己所需要的内存，往往会有很多内存并不被使用，这会造成很多浪费，因此有一种更聪明的方式：Lazy allocation 。如果将上述的 Eager allocation 方式替换成 Lazy allocation，那么在用户进程申请内存时，只需要执行一步：

增加进程大小 struct proc.sz

当用户进程真正访问这块区域的内存时，会触发缺页异常，此时我们只需要：

检查虚拟地址是否正确（vaddr < proc.sz），触发缺页异常的虚拟地址存放在 stval寄存器中
满足条件，则执行分配内存，即建立页表映射

2. Zero fill on demand
在一个正常的操作系统中，如果执行 exec，exec会申请地址空间，里面会存放 text 和 data。因为 BSS 里面保存了未被初始化的全局变量，这里或许有许多个 page，但是所有的 page 内容都为0。 Zero fill on demand 的策略是，申请一个物理 page（PTE 的权限需要为只读），清空为 0，然后将所有为 0 的数据虚拟地址都映射向这个 Page，如下所示：

这种方式的优势显而易见：
只需要为这些为零的数据分配一个物理 Page
当只需要读 BSS 段的数据时，丝毫不影响性能
exec 可以更快的执行，原来可能需要分配 N 个 Page，执行 N 次页面映射，现在只需要分配 1 个。

当需要写数据时，触发 Page fault ，则再另行分配一个新的物理 Page，重新写入即可。

3. Copy on write fork（写时复制）

当 Shell 处理指令时，它会通过 fork 创建一个子进程。fork 会创建一个Shell进程的拷贝，所以这时我们有一个父进程（原来的Shell）和一个子进程。Shell 的子进程执行的第一件事情就是调用 exec 运行一些其他程序，比如运行echo。现在的情况是，fork 创建了Shell地址空间的一个完整的拷贝，而 exec 做的第一件事情就是丢弃这个地址空间，取而代之的是一个包含了echo 的地址空间。这里看起来有点浪费。
因此引入了 Copy on write fork 策略，简单来说就是父进程的物理页共享给子进程，子进程和父进程映射相同的物理页，并且父子进程的 PTE 都需要标记为只读，如下所示
6. Page fault - 图2
当发现写操作时，只需要将对应物理页的数据 Copy 到新的物理页，然后将对应执行写操作的进程的 PTE 重新映射到新的物理页，加上写权限即可，如下：
6. Page fault - 图3
这里还有一些隐藏的问题：

发生缺页异常时，需要知道是因为 Copy on write fork 引起的还是进程自身不安全操作引起的（比如读野指针，空指针）

xv6 选择在 PTE 中加入一个标记，PTE 为 64 位，其中有两位保留位（RSW），如下所示：
6. Page fault - 图4
当当前 Page 为 Copy on write page 时，则 RSW 标记为 1，即可区分缺页异常是否由 Copy on write 触发。

一个物理页可能有多个虚拟页引用，因此需要在分配物理页时，加上引用技术，如果没有该操作，可能会释放还在使用的物理页。
详细的实现参考 Lab: Copy-on-Write Fork for xv6

4. Demand paging
这里有点类似第二点 Zero fill on demand，对于 exec，在虚拟地址空间中，我们为 text 和 data 分配好地址段，但是相应的 PTE 并不对应任何物理内存 page。对于这些 PTE，我们只需要将 valid bit 位设置为 0 即可。当触发 Page fault 的时候（理论上是执行第一条语句的时候），将对应程序文件加载到内存中，然后映射到用户进程的 Page table，最后重新执行指令。
这样做的优势是：
exec 更快加载
大量节约内存空间
允许我们加载比内存更大的进程

但是在最坏的情况下，进程使用了 text 和 data 中的所有内容，那么会触发很多 page fault，引发额外的消耗。此外，当进程所需的空间大于内存时，通常会采用撤回某些物理 Page，Page 的选择最经典的算法就是 LRU。然后将对应空闲出来的物理页重新分配，也可以根据 PTE 的 dirty flag 和 accessed flag 来选择 page。

5. Memory mapped files

这里的核心思想是，将完整或者部分文件加载到内存中，这样就可以通过内存地址相关的 load 或者 store 指令来操纵文件。linux 中该实现为 mmap 调用，也可以利用该接口实现共享内存，相同的物理 Page 映射到不同的进程的虚拟 Page Table 中。

1. Lazy page allocation

2. Zero fill on demand

3. Copy on write fork（写时复制）

4. Demand paging

5. Memory mapped files