Arthals' ink

Back
26 min
中文
操作系统 /
xv6 /
pku

更适合北大宝宝体质的 xv6 OS Lab 踩坑记 - Part6

北京大学 2025 年秋季学期操作系统/OS Lab Part 6
views | comments

Part6 的核心是实现两种页面置换算法：

  • FIFO（先进先出）
  • LRU（最近最少使用）

助教给了两个对应的测例：

  • test_vm_fifo
  • test_vm_lru

我们要做的，是在 mmap 区域实现一个简化版的”虚拟内存”机制：当进程 mmap 区驻留的物理页数量超过限制时，需要按照指定的页面置换算法选择一个”受害者”页面换出到内存缓冲区（swap buffer），等到再次访问时再换入。

页面置换的核心在于为每个 mmap 页面维护状态追踪信息，包括页面当前状态 state（未分配、在内存中、已换出）、载入时间 load_time、最近访问时间 last_access 以及换出时保存数据的缓冲区指针 swap_data。当进程访问 mmap 区域触发缺页时，内核首先检查驻留页数是否已达上限，若是则需要执行换出操作。换出时根据 FIFO 或 LRU 策略选择受害者页面：

  • FIFO 选择 load_time 最小的页面，即最早载入的；
  • LRU 选择 last_access 最小的页面，即最久未访问的。

选定受害者后，将其内容复制到 swap 缓冲区，解除页表映射，释放物理页。换入时检查目标页面是否有 swap 数据，有则直接将缓冲区内容映射回页表，无则说明是首次访问，需要新分配物理页。

值得注意的是，FIFO 算法只需在页面载入时记录 load_time 即可，而 LRU 算法需要持续追踪页面的访问时间。由于 xv6 没有硬件 Access Bit 的支持，我们采用软件模拟的方式：用户态程序在每次访问页面后主动调用 lru_access_notify 系统调用来更新 last_access 时间戳。

这套实现与真实操作系统其实存在几点简化：

  1. 真实系统使用磁盘作为 swap 空间，而我们直接使用内存缓冲区，本质上只是在内存中腾挪数据而已
  2. 真实系统依赖硬件提供的 Access Bit 和 Dirty Bit 来追踪页面访问情况，而我们需要用户态程序显式通知内核
  3. 真实系统的页面置换通常是全局的，会在所有进程间选择受害者，而我们的实现仅针对当前进程的 mmap 区域

评测框架#

延续 Part4、Part5 的套路，Makefile 中新增了一组宏（简化版）：

含义：

  • ALGO=FIFO 时：
    • 编译器会看到 ALGO 和 ALGO_FIFO 两个宏
    • TEST_PROGRAM 被设置为 test_vm_fifo
  • ALGO=LRU 时：
    • 编译器会看到 ALGO 和 ALGO_LRU 两个宏
    • TEST_PROGRAM 被设置为 test_vm_lru

配合 Part4 中使用的 run_test 命令启动时注入的 ENABLE_JUDGER 宏，就可以类似这样跑评测：

make run_test ALGO=FIFO
make run_test ALGO=LRU
bash

init.c 和 judger.c 的逻辑与 Part4、Part5 类似，只是判断条件换成了：

#elif defined(ENABLE_JUDGER) && defined(ALGO)
c

Judger 判断测例通过的标准是输出里有：

FIFO Test PASSED
LRU Test PASSED
text

同时确保没有 ERROR 字样。

新增系统调用#

要在用户态测试页面置换，需要内核提供三个观测和控制接口。在 kernel/include/sysnum.h 里新增：

// kernel/include/sysnum.h
#define SYS_set_max_page_in_mem 600 // 设置最大物理页数
#define SYS_get_swap_count 601      // 获取交换次数
#define SYS_lru_access_notify 602   // 通知LRU页面替换算法
c

sys_set_max_page_in_mem#

设置当前进程 mmap 区域允许驻留的最大物理页数量。一旦超过这个限制，就必须触发页面置换。

sys_get_swap_count#

获取当前进程累计的 swap-out 次数。测例通过比较换出次数来验证页面置换算法是否正确。

// kernel/sysproc.c
/**
 * @brief 获取交换次数
 * @return 交换次数
 */
uint64 sys_get_swap_count(void) {
  struct proc* p = myproc();
  acquire(&p->lock);
  int count = p->swap_count;
  release(&p->lock);
  return count;
}
c

sys_lru_access_notify#

LRU 算法需要知道页面的访问时间。由于 xv6 没有硬件 Access Bit 的支持，我们让用户态程序在访问页面后主动调用这个系统调用来更新访问时间戳。

数据结构扩展#

要实现页面置换，首先需要扩展数据结构来追踪每个 mmap 页面的状态。

PCB 扩展#

在 PCB 中，我们需要记录三个信息：

  1. max_page_in_mem：mmap 区域允许驻留的最大物理页数量
  2. mmap_pages_in_mem：当前实际驻留的页数
  3. swap_count：swap-out 次数统计
// kernel/include/proc.h
struct proc {
  // ...
  #ifdef ALGO
  int max_page_in_mem;    // mmap 区域允许驻留的最大物理页数量
  int mmap_pages_in_mem;  // 当前 mmap 区域驻留物理页数量
  int swap_count;         // swap-out 次数统计
  #endif
  // ...
};
c

mmap 页面追踪结构#

然后，我们需要为每个 mmap 页面维护元数据。页面有三种状态：未分配（VMA_PAGE_UNUSED）、在内存中（VMA_PAGE_INMEM）、已换出到 swap 缓冲（VMA_PAGE_SWAPPED）。

对于在内存中的页面，需要记录载入时间供 FIFO 使用、记录最近访问时间供 LRU 使用；对于已换出的页面，需要保存指向 swap 缓冲区的指针：

VMA 结构扩展#

最后，我们还需要在 struct vma 中增加页面追踪数组的指针。每个 VMA 创建时会分配一个 mmap_vpage 数组，用于跟踪该 VMA 覆盖的所有页面：

// kernel/include/vm.h
struct vma {
    // 原有字段

    #ifdef ALGO
    int page_count;              // VMA 覆盖的页数量
    struct mmap_vpage *pages;    // 指向跟踪 mmap 页信息的数组
    #endif
};
c

mmap 系统调用改造#

原本 Part2 实现的 sys_mmap 只需要记录 VMA 元数据，并不真正分配物理页（懒分配）。现在还需要额外分配页面追踪数组。

改造的关键点是：在设置好 VMA 的基本信息后，用 kalloc() 分配一页内存作为 pages 数组（一页 4KB 可以容纳 4096 / sizeof(struct mmap_vpage) 个页面元数据，足够 128 页使用），然后初始化所有页面状态为 VMA_PAGE_UNUSED：

页面置换算法核心实现#

页面置换的核心逻辑都在 kernel/trap.c 里实现，因为它要和缺页处理紧密配合。

选择受害者页面#

我们首先需要一个选择受害者的函数。FIFO 和 LRU 的区别仅在于选择受害者的依据不同：

  • FIFO：选择 load_time 最小的页面（最早载入的）
  • LRU：选择 last_access 最小的页面（最久未访问的）

我们用一个统一的 select_victim_page 函数来实现，遍历所有 VMA 的所有驻留页，找出”度量值”最小的那个，这里使用条件编译区分：

换出页面#

选定受害者后，swap_out_one_page 负责执行换出操作。它先用 kalloc() 分配一页作为 swap 缓冲区，把受害者页面的内容 memmove 过去，然后解除用户页表和内核页表的映射（vmunmap），最后更新页面元数据和统计信息：

确保页面预算#

有了换出函数，还需要一个”预算检查”函数 ensure_mmap_budget，在分配新页面之前调用，确保驻留页数不超过限制。如果超了就持续换出，直到有空间为止：

VMA 缺页处理改造#

原本 Part2 的 vma_handler 只处理懒分配缺页，逻辑很简单：分配一页，映射到页表，如果是文件映射就从文件读取内容。现在需要加入页面置换逻辑，变成一个完整的换入/换出流程。

新的处理函数 handle_vma_fault_with_algo 首先计算缺页地址对应的页面索引，然后检查页面状态：如果已经在内存中就直接返回（可能是权限问题触发的 fault，不归我们管）；如果是首次访问（VMA_PAGE_UNUSED）或需要换入（VMA_PAGE_SWAPPED），就需要分配物理页。

分配之前先调用 ensure_mmap_budget 确保有空间。如果是换入，直接使用 swap_data 指向的缓冲区作为物理页（省去一次复制）；如果是首次访问，就 kalloc 新页并按需从文件读取内容。最后映射到用户页表和内核页表，更新页面元数据：

然后在原来的 vma_handler 中，用条件编译切换到新逻辑：

fork/clone 时的 VMA 复制#

原本 fork 只是简单地复制 VMA 元数据和文件引用计数，现在还需要额外处理页面追踪信息。这里有个设计决策：子进程的 mmap 页面应该处于什么状态？

我们选择把父进程所有的 mmap 页面（无论在内存中还是在 swap 中）都复制到子进程的 swap 缓冲区。这样做的好处是：子进程首次访问时会触发缺页，走正常的换入流程，不需要额外处理共享页面的问题。代价是 fork 时需要为每个已分配的页面分配一个 swap 缓冲区并复制内容。

然后在 fork() 和 clone() 中调用 copy_process_vmas，替换原有的简单循环：

int fork(void)
{
  // 复制进程状态

  // 复制 VMA（替换原有的简单循环）
  if (copy_process_vmas(np, p) < 0) {
    vma_free(np);
    freeproc(np);
    release(&np->lock);
    return -1;
  }

  // 复制文件描述符等
}
c

清理逻辑#

解除映射（munmap）或进程退出时，需要释放页面追踪数组和所有 swap 缓冲区。vma_reset_pages 遍历所有页面，释放 swap 缓冲区，更新驻留页计数，最后释放追踪数组本身：

在 sys_munmap 和 vma_free 中调用：

// sys_munmap 中
#ifdef ALGO
vma_reset_pages(p, v);
#endif
v->valid = 0;

// vma_free 中
#ifdef ALGO
vma_reset_pages(p, v);
#endif
v->valid = 0;
c

PCB 初始化与释放#

在 allocproc 和 freeproc 中处理新增字段：

在 fork 和 clone 中初始化子进程的字段：

#ifdef ALGO
np->max_page_in_mem = p->max_page_in_mem;  // 继承父进程的限制
np->mmap_pages_in_mem = 0;                  // 子进程初始没有驻留页
np->swap_count = 0;                         // 子进程重新计数
#endif
c

测试#

FIFO#

make run_test ALGO=FIFO
bash

得到输出：

LRU#

make run_test ALGO=LRU
bash

得到输出：

更适合北大宝宝体质的 xv6 OS Lab 踩坑记 - Part6
https://arthals.ink/blog/xv6-os-lab-part6
Author Arthals
Published at January 12, 2026
Copyright CC BY-NC-SA 4.0
Buy me a cup of coffee ☕.

更适合北大宝宝体质的 xv6 OS Lab 踩坑记 - Part8

如何降级 iOS / iPadOS App
Comment seems to stuck. Try to refresh?✨