Lec7 Page Faults

COW fork, lazy allocation, demand page, mmap

Published

2024-03-20

Modified

2024-10-23

1 课前准备

Read Section 4.6.

任务最少的一集。

xv6 应对异常的方式比较无聊：如果是应用空间的异常，直接杀掉出错的进程；如果是内核里的异常，内核会 panic。真正的操作系统会有更有趣的方式应对异常。

一个示例是应用 page faults 实现的 copy-on-write (COW) fork。常规的 fork 会为子进程开辟相同的物理空间并将父进程的内容拷贝进去，如果能让父子进程共用一片内存将是非常高效的。但直接的实现方法是不可行的，因为这会导致父子进程会相互干扰对方的执行，因为它们共用了一个堆栈。

先来了解一下什么是 page-fault exception。当虚拟地址在页表中没有映射，或者对应的 PTE 标志位不符合当前操作所需的许可，就会引发 page-fault exception。RISC-V 区分三种 page fault：

load page fault：当 load 类指令无法翻译其虚拟地址；
store page fault：当 store 类指令无法翻译其虚拟地址；
instruction page fault：当 pc 无法翻译；

scause 寄存器会标示 page fault 的类型，stval 寄存器存有无法翻译的地址。

COW fork 的基本思想是父子进程在刚开始享有同一片物理内存，但是是只读的（PTE_W 未设置）。当任何一方要向某一页写入数据时，RISC-V CPU 会引发一个 page-fault exception。内核的 trap handler 会分配一个页的物理内存并复制引发异常的页的内容，并修改对应的 PTE 标识。此时恢复并重新执行刚才出错的命令，由于这次有了写权限，命令照常执行。COW fork 需要一个记事簿¹（book-keeping）来帮助决定哪个页面可以被释放，因为每个页都有可能被很多进程共享。

¹ 其实就是引用计数。

另一个广泛应用的是 lazy allocation。当进程通过 sbrk 申请更多空间时，内核注意到了空间的扩张，但并未真正分配内存。当新地址上出现了 page fault，内核才会真正分配内存并在页表上建立映射。

另一个广泛使用的是 demand page。在 exec 中，xv6 加载应用程序的所有文本和数据都 eagerly² 存入内存。由于应用程序可能很大并且从磁盘读取数据的成本很高，这种启动成本可能会引起用户的注意：当用户从 shell 启动大型应用程序，可能需要很长时间才能看到响应。现代内核为用户地址空间创建页表，但标记页面 PTE 无效。发生 page fault 时，内核从磁盘读取页面内容并将其映射到用户地址空间。

² 与 lazy 相对。

计算机上运行的程序可能需要比计算机 RAM 更多的内存。为了优雅地应对，操作系统可能会实现 paging on disk。这个想法是只将一小部分用户页存储在 RAM 中，并将其余部分存储在磁盘的 paging area 中。内核将与存储在 paging area（因此不在 RAM 中）的内存相对应的 PTE 标记为无效。如果应用程序尝试使用已 paged out 到磁盘的页面之一，则应用程序将引发 page fault，并且必须将页面 paged in：内核 trap handler 将分配物理 RAM 页面，从磁盘写入 RAM，并修改相关 PTE 指向 RAM。

如果一个页面需要被 paged in，但是没有空闲的物理内存怎么办？在这种情况下，内核必须首先释放一个物理页面，将其 paged out 或者逐出（evicting）到磁盘上的 paging area，并将指向该物理页面的 PTE 标记为无效。逐出操作是昂贵的，因此分页的性能最佳时是它不频繁发生。即，应用程序只使用其内存页面的子集，并且这些子集的并集能够适应内存。这种特性通常被称为具有良好的局部性。

2 Lecture

2.1 Memory Mapped Files

将完整或者部分文件加载到内存中，这样就可以通过内存地址相关的 load 或者 store 指令来操纵文件。为了支持这个功能，现代的操作系统会提供一个叫做 mmap 的系统调用，比如会长成这样：

mmap(va, len, protection, flags, fd, offset);

这里的语义就是，从文件描述符对应的文件的偏移量的位置开始，映射长度为 len 的内容到虚拟内存地址 va，同时我们需要加上一些保护，比如只读或者读写。flags 表示该文件是否可以在多个进程之间共享。

假设文件内容是读写并且内核实现 mmap 的方式是 eager 方式（不过大部分系统都不会这么做），内核会从文件的 offset 位置开始，将数据拷贝到内存，设置好 PTE 指向物理内存的位置。之后应用程序就可以使用 load 或者 store 指令来修改内存中对应的文件内容。当完成操作之后，会有一个对应的 unmap 系统调用，来表明应用程序已经完成了对文件的操作，在 unmap 时间点，我们需要将 dirty block 写回到文件中。我们可以很容易的找到哪些 block 是 dirty 的，因为它们在 PTE 中的 dirty bit 为 1。

当然，在任何聪明的内存管理机制中，所有的这些都是以 lazy 的方式实现。你不会立即将文件内容拷贝到内存中，而是先记录一下这个 PTE 属于这个文件描述符。相应的信息通常在 VMA (Virtual Memory Area) 结构体中保存。在 VMA 中我们会记录文件描述符，偏移量等等，这些信息用来表示对应的内存虚拟地址的实际内容在哪，这样当我们得到一个位于 VMA 地址范围的 page fault时，内核可以从磁盘中读数据，并加载到内存中。

--- title: "Lec7 Page Faults" order: 7 date: 2024-3-20 date-modified: last-modified description: "COW fork, lazy allocation, demand page, mmap" --- ## 课前准备 > Read Section 4.6. 任务最少的一集。 xv6 应对异常的方式比较无聊：如果是应用空间的异常，直接杀掉出错的进程；如果是内核里的异常，内核会 panic。真正的操作系统会有更有趣的方式应对异常。一个示例是应用 page faults 实现的 copy-on-write (COW) fork。常规的 `fork` 会为子进程开辟相同的物理空间并将父进程的内容拷贝进去，如果能让父子进程共用一片内存将是非常高效的。但直接的实现方法是不可行的，因为这会导致父子进程会相互干扰对方的执行，因为它们共用了一个堆栈。先来了解一下什么是 page-fault exception。当虚拟地址在页表中没有映射，或者对应的 PTE 标志位不符合当前操作所需的许可，就会引发 page-fault exception。RISC-V 区分三种 page fault： 1. load page fault：当 load 类指令无法翻译其虚拟地址； 2. store page fault：当 store 类指令无法翻译其虚拟地址； 3. instruction page fault：当 `pc` 无法翻译； `scause` 寄存器会标示 page fault 的类型，`stval` 寄存器存有无法翻译的地址。 COW fork 的基本思想是父子进程在刚开始享有同一片物理内存，但是是只读的（`PTE_W` 未设置）。当任何一方要向某一页写入数据时，RISC-V CPU 会引发一个 page-fault exception。内核的 trap handler 会分配一个页的物理内存并复制引发异常的页的内容，并修改对应的 PTE 标识。此时恢复并重新执行刚才出错的命令，由于这次有了写权限，命令照常执行。COW fork 需要一个记事簿[^1]（book-keeping）来帮助决定哪个页面可以被释放，因为每个页都有可能被很多进程共享。 [^1]: 其实就是引用计数。另一个广泛应用的是 lazy allocation。当进程通过 `sbrk` 申请更多空间时，内核注意到了空间的扩张，但并未真正分配内存。当新地址上出现了 page fault，内核才会真正分配内存并在页表上建立映射。另一个广泛使用的是 demand page。在 `exec` 中，xv6 加载应用程序的所有文本和数据都 eagerly[^2] 存入内存。由于应用程序可能很大并且从磁盘读取数据的成本很高，这种启动成本可能会引起用户的注意：当用户从 shell 启动大型应用程序，可能需要很长时间才能看到响应。现代内核为用户地址空间创建页表，但标记页面 PTE 无效。发生 page fault 时，内核从磁盘读取页面内容并将其映射到用户地址空间。 [^2]: 与 lazy 相对。计算机上运行的程序可能需要比计算机 RAM 更多的内存。为了优雅地应对，操作系统可能会实现 **paging on disk**。这个想法是只将一小部分用户页存储在 RAM 中，并将其余部分存储在磁盘的 **paging area** 中。内核将与存储在 paging area（因此不在 RAM 中）的内存相对应的 PTE 标记为无效。如果应用程序尝试使用已 **paged out** 到磁盘的页面之一，则应用程序将引发 page fault，并且必须将页面 **paged in**：内核 trap handler 将分配物理 RAM 页面，从磁盘写入 RAM，并修改相关 PTE 指向 RAM。如果一个页面需要被 paged in，但是没有空闲的物理内存怎么办？在这种情况下，内核必须首先释放一个物理页面，将其 paged out 或者逐出（evicting）到磁盘上的 paging area，并将指向该物理页面的 PTE 标记为无效。逐出操作是昂贵的，因此分页的性能最佳时是它不频繁发生。即，应用程序只使用其内存页面的子集，并且这些子集的并集能够适应内存。这种特性通常被称为具有良好的局部性。 ## Lecture ### Memory Mapped Files 将完整或者部分文件加载到内存中，这样就可以通过内存地址相关的 load 或者 store 指令来操纵文件。为了支持这个功能，现代的操作系统会提供一个叫做 `mmap` 的系统调用，比如会长成这样： ``` c mmap(va, len, protection, flags, fd, offset); ``` 这里的语义就是，从文件描述符对应的文件的偏移量的位置开始，映射长度为 `len` 的内容到虚拟内存地址 `va`，同时我们需要加上一些保护，比如只读或者读写。`flags` 表示该文件是否可以在多个进程之间共享。假设文件内容是读写并且内核实现 `mmap` 的方式是 eager 方式（不过大部分系统都不会这么做），内核会从文件的 offset 位置开始，将数据拷贝到内存，设置好 PTE 指向物理内存的位置。之后应用程序就可以使用 load 或者 store 指令来修改内存中对应的文件内容。当完成操作之后，会有一个对应的 `unmap` 系统调用，来表明应用程序已经完成了对文件的操作，在 `unmap` 时间点，我们需要将 dirty block 写回到文件中。我们可以很容易的找到哪些 block 是 dirty 的，因为它们在 PTE 中的 dirty bit 为 1。当然，在任何聪明的内存管理机制中，所有的这些都是以 lazy 的方式实现。你不会立即将文件内容拷贝到内存中，而是先记录一下这个 PTE 属于这个文件描述符。相应的信息通常在 VMA (Virtual Memory Area) 结构体中保存。在 VMA 中我们会记录文件描述符，偏移量等等，这些信息用来表示对应的内存虚拟地址的实际内容在哪，这样当我们得到一个位于 VMA 地址范围的 page fault时，内核可以从磁盘中读数据，并加载到内存中。