Page Fault

课前准备

Xv6 对异常的响应非常简单：发生在用户空间则终止，发生在内核则崩溃。实际的系统比这更加复杂

COW fork

例如，可以利用异常 page fault 实现 COW fork：instead of 直接分配一块内存然后把父进程的内容完全复制到子进程，子进程可以和父进程共享完全相同的内存——但需要一些更多的操作

三种 Page Fault

Page Fault：CPU 试图访问内存时，vm无法找到合适的映射

• load
• store
• instruction：试图获取指令

scause 会告诉我们是哪种 Page Fault，stval 会存储无法转换的vm

COW fork 基本方案

父进程和子进程初始时共享所有物理页面，但将它们映射为只读。于是，试图进行写入时，会引发 Store Page Fault Exception

处理此异常时，为出现错误的页面分配一个副本，然后父子进程一个映射到新页并可读写，另一个映射到另一页并可读写，然后返回到原进程重新执行写入指令

COW fork 是透明的：应用程序不需要做任何修改就能从中受益。

exec 与 fork

子进程通常会在 fork 后立即调用 exec，用新的地址空间替换其现有的地址空间，在这种情况下可以完全避免多余的内存复制

lazy allocation

基于COW思想，自然衍生出另一个策略：延迟分配。应用程序通常要求比实际需要更多的内存，可以推迟这些内存的分配

程序调用 sbrk 时，grows the address space。新地址之一发生 page fault，为其分配物理空间并映射到PT中

内核可以透明地实现此功能。

paging from disk

同样地，如果应用程序需要的内存超过了可用的物理 RAM，内核可以逐出一些页面，将它们写入存储设备，并将其 PTE 标记为无效

如果应用程序尝试读写此页面，将会发生 Page Fault，内核随后检查这个页，如果存在磁盘上，则分配一页物理内存，将页面加载到内存中，并更新PTE。在这个过程中可能会删掉另一个PTE指向的页面

自动扩展堆栈和内存映射文件

Page Fault Basics

利用 page fault 可以实现：lazy allocation、copy-on-write fork、demand paging、memory mapped files

然而xv6一个都没实现

虚拟内存有两个优点：隔离性 & 抽象，其中利用抽象我们可以实现许多有趣的功能。目前内存映射基本都是直接映射，且内存地址映射相对来说比较静态，利用 page fault，我们可以动态更新PT

page fault 信息

产生 page fault 时肯定有 出错的虚拟地址 ，错误的vm会存储在 stval，错误的原因会存储在 scause ，产生异常的指令地址放在 sepc 和 trapframe->epc。

scause中，与 page fault 相关的为：8 instruction、13 load、15 store

这几个寄存器为我们分别提供了：产生错误的内存地址、错误原因、错误的指令，理想情况下，修复 page fault 后指令便可正常运行

Lazy page allocation

——sbrk，这是XV6提供的系统调用，它使得用户应用程序能扩大自己的heap。程序启动时sbrk指向heap的最底端，同时也是stack最顶端，通过进程结构体中的 sz 字段标识

sbrk 有一个参数n，代表申请字节数，它会改变 sz 的值。实际发生时，内核会分配一些物理内存，初始化为0，然后返回给sbrk。同时也可以传递负值，来减小内存 sz。我们主要关注扩大内存

sbrk：eager allocation

sbrk 的默认实现策略是 eager allocation，一旦申请就分配。然而应用程序倾向于多申请内存，会存在一定量的 内存浪费。原则上讲这不是什么大问题，但使用 page fault，我们可以使用一种更加聪明的策略，那就是 lazy allocation，使用时分配。

sbrk：lazy allocation

在此策略下，sbrk 只会将 p->sz 增加 n，不分配任何物理内存。在使用新内存时，也即访问一个大于旧的 p->sz，但是又小于新的 p->sz 的地址时，我们希望内核分配一个page，并重新执行原指令

通常情况下，如果进程确实已经用光了所有物理内存，也就是发生了 OOM（Out Of Memory），内核可以杀掉进程，也可以把一些page写入磁盘，需要时再取出——这是后文的内容了

sbrk：code

在 lazy 策略下，应该是这样：

再次执行程序时，就会触发page fault：

• pid = 3，这很可能是个 shell

查找这条指令，发现它位于 malloc 中，因为此时我们以为自己正在初始化已分配的内存：

新页的另一个佐证就是，我们的Shell通常是有5个page，但此时试图访问 5008，也就是第六个 page

usertrap：page fault 处理

触发写 page fault 时，分配内存，注意要对 va 取整，并对其映射

此时有另一个错：

我们在尝试 ummap 一些本就没有 map 的页，而sbrk本就没有做任何事，因此这实际上是我们的预期行为，所以：

——我们这里仍有很多需要修改的地方，比如判断sz范围，这是下一个实验的内容

Zero Fill On Demand

一个简单但是使用的非常频繁的功能

bss 放未初始化或初始化为0的全局变量，或许包含多个 page。通常可以调优的地方在于，将这些 vm 全部映射到一个page上，这样就可以避免大量的物理内存分配：

但我们不允许对它进行写，我们期望这全都是0，所以在写时需要另外分配一个可读可写0页，重新映射，然后重新执行指令

有什么好处？

更加充分得利用内存，且exec需要做的工作更少

page fault的代价

page fault并不是没有代价的，切换地址空间需要巨量的 store

COW Fork

shell 运行程序时，会fork一个副本，然后立马exec，丢弃副本——这很浪费。所以一个优化策略就是，子进程与父进程共享内存，但修改需要对父进程不可见——这利用 page fault 实现：

将父子进程共享的PTE设为只读，写时触发page fault。在page fault中，为要写的页分配一个副本，本进程映射到这个页，另一个进程还是映射到原来的页，并把权限均设为可读可写

如何分辨COW与写错误？

可以将保留位中的第8位设为 COW，标识当前是一个copy-on-write page。

也可以由内核维护这些信息，这些实现都很灵活

共享page带来的问题

什么时候释放一个page？我们需要对每个page维护一个计数信息

Demand Paging

exec 对于text，data区域也是以eager的方式进行加载，为什么不延迟分配？程序的二进制文件可能非常巨大

可以为 text 和 data 分配好PTE，但是其不对应任何物理内存，也就是PTE_V 为0

优点

如果我们幸运的话，用户程序并没有使用所有的text区域或者data区域，那么我们一方面可以节省一些物理内存，另一方面我们可以让exec运行的更快

worst case

在最坏的情况下，程序使用了text和data中的所有内容，而这个程序又比较大，我们会遇到超级多的page fault——不仅如此，这还包含从磁盘加载文件的时间，我们的程序会变得很慢

一种策略：程序给操作系统提示，说哪部分一定会用到，这部分一定加载进来，其他可能用可能不用的部分统统延迟加载

内存还是耗尽了怎么办？

我们将要读取的文件，它的text和data区域可能大于物理内存的容量。又或者多个应用程序按照demand paging的方式启动，它们二进制文件的和大于实际物理内存的容量。对于demand paging来说，假设内存已经耗尽了或者说OOM了，这个时候如果得到了一个page fault，需要从文件系统拷贝中拷贝一些内容到内存中，但这时你又没有任何可用的物理内存page，这其实回到了之前的一个问题：在lazy allocation中，如果内存耗尽了该如何办？

一个选择是撤回page（evict page），写回文件系统并标记PTE为non-valid

可能的撤回策略有：LRU，以及优先撤回 non-dirty page 中的未访问 page

如果先撤回dirty page，它之后再被修改，现在你或许需要把它再次加载回内存，然后再次写回文件系统

需要定时清除Access bit。clock algorithm，就是一种实现方式。

Memory Mapped Files

将完整或者部分文件加载到内存中，这样就可以通过内存地址相关的load或者store指令来操纵文件。这通过函数 mmap 实现

mmap 的实现方式也分 eager 和 lazy

1

void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);

从文件描述符对应的文件的偏移量的位置开始，映射长度为len的内容到虚拟内存地址VA，同时我们需要加上一些保护，比如只读或者读写。

flag：读写；prot：私有还是共享

eager mmap

分配物理内存，设置PTE，从fd指定偏移开始复制到指定va。然后就可以开始对内存进行操作

unmap

将dirty block写回到文件中。

lazy mmap

不立即分配内存，只分配PTE。记录一下这个PTE属于这个文件描述符，相应的信息通常在VMA（Virtual Memory Area）结构体中保存

多进程读写同一个文件

存在同步问题，可以使用锁。

共享的情形下，如果修改了文件，需要同步到内存中