实现写时复制 (Copy-On-Write)

系统实验 (基于 xv6)

截止时间:2024年12月22日 23:59

提交内容

  1. 代码源文件 学号.zip: 请注意代码中应有必要的注释;
  2. 实验报告 学号.pdf:简要描述实验中遇到的关键问题及解决方案、印象最深的 bugs、或者额外实现的功能等即可 (1~2 页)。

提交方式:请参考实验页面的具体说明,本次实验 LAB ID3

# code
make package
make submit
# report
make report
# score
make score

*提交冷却时间 2 小时

在执行 fork() 系统调用时,操作系统需要将父进程地址空间复制一份副本给子进程。此时,如果父进程所使用的内存空间很大,复制会需要很长时间,并且这个复制开销很可能是无意义的 (例如,子进程在 fork() 返回后立即执行 execve())。为了降低 fork() 的执行开销并提高内存资源的利用率,现代操作系统会使用写时复制 (Copy-On-Write, COW)这一机制。 在本实验中,我们需要为 xv6 增加这一机制,以此来熟悉操作系统内存管理的一些相关概念和实现细节。

运行如下命令下载实验框架代码,并切换到 lab-cow 分支:

git clone https://git.nju.edu.cn/oslab/os-lab-2024fall.git
cd os-lab-2024fall
git checkout lab-cow

如果你在 Lab 2 的基础上进行实验,直接切换分支即可:

git fetch origin  # 拉取最新的远程更新
git checkout -b lab-cow origin/lab-cow  # 切换到 lab-cow 分支

🗒️ 实验内容

在本次实验中,我们需要为 xv6 实现基于写时复制的 fork() (COW Fork),从而将物理页的分配和复制推迟到实际需要的时候:即当父进程调用 fork() 时,子进程直接设置其 PTE 指向父进程的物理页 (父子进程共享物理页),并设置 PTE 为只读;随后,当其中一个进程需要对某个页进行写操作时,就会发生异常中断,此时在内核相应的 Interrupt Handler 中就可实际分配并复制相应物理页的内容,并将 PTE 更新为可写;最终,在异常中断返回后,进程就可以按正常方式写这个页。

在上述流程中,一个关键问题是在发生异常中断时,如何判断造成异常的原因是触发 COW 机制、还是访问了一个非法的虚拟地址? 为了解决这个问题,我们可以在 xv6 的 PTE 中添加一个标志位,用于标记该页面是否与 COW Fork 相关。另外,COW Fork 会导致同一个物理页被多个进程的页表引用,此时还需要记录每个物理页被引用的次数,以此来判断在进程结束时是否能释放对应的物理内存。

你可以参考以下流程来实现本次实验:

  1. 修改 kernel/vm.c 中的 uvmcopy() 函数,使其在 fork() 时不复制父进程的整个内存空间,而是让子进程共享。在这一过程中,需要修改父进程和子进程的 PTE,包括将页标记为只读 (擦除可写标志位 PTE_W),并设置 COW 标志位 (需要在合适的位置定义 PTE 的内容)。

  2. 修改 kernel/trap.c 中的 usertrap() 函数,使其在处理中断时,判断是否是 COW Fork 产生的中断异常。如果是,则分配和复制对应的物理页,并更新 PTE 为可写 (注意,如果该页面本来就是只读页面,则属于进程访问了非法地址,此时应杀死该进程)。

  3. 在合适的时机释放物理内存。为此,需要维护一个新的数据结构来记录各物理页的引用数,在此基础上,在第一次分配物理页时设置引用计数初始值 (kalloc())、在共享物理页时增加引用数、在进程从页表删除物理页时减少引用数 (kfree()、或者触发 COW 异常中断而导致页面复制时)、并最终当物理页引用数为 0 时释放物理内存。

  4. 修改 kernel/vm.c 中的 copyout() 函数,从内核复制页面到用户空间时,使用同样的方案处理 COW 页面。

在 COW Fork 实现正确的情况下,你应该可以通过 cowtest 测试:

$ make qemu
# ...
# in xv6
$ cowtest
simple: ok
simple: ok
three: ok
three: ok
three: ok
file: ok
ALL COW TESTS PASSED

在 xv6 上,添加 COW 标志位、引用计数等是相对简单的。然而,在实际的操作系统中,这些操作可能会变得复杂,例如:Patching until the COWs come home

其它需求说明

你可以采用不同的实现方式来完成本实验,但对 xv6 代码的修改应局限于以下文件:

  • kernel/defs.h
  • kernel/riscv.h
  • kernel/kalloc.c
  • kernel/trap.c
  • kernel/vm.c

💭 Tips

  • kernel/riscv.h 中包含了一些有用的宏定义;
  • COW 标志位的设置可以参考 PTE 中已有的 PET_W 等标志位的定义和修改方式;
  • 可以利用 xv6 中的一些已有函数来实现你需要的功能,阅读这些代码并在需要的时候使用:
    • kernel/vm.c/walk():获取虚拟地址对应的页表的页表项;
    • kernel/vm.c/mappages():映射虚拟地址到物理地址,创建页表项;
    • kernel/vm.c/uvmunmap():移除虚拟地址的映射;
    • kernel/string.c/memmove():复制一块内存;
  • 物理页引用数可以通过类似如下的 refcnt 结构来实现,其中通过物理地址除以 PGSIZE 来索引对应的物理页:
    struct {
      struct spinlock lock;
      int count[(PGROUNDUP(PHYSTOP) - KERNBASE)/PGSIZE];
    } refcnt;
    

    注意这里可能存在多个进程同时尝试修改 refcnt 的数据竞争情况,因此还需要使用 spinlock 来实现互斥,即在修改数据前需要使用 acquire() 来获取锁,并在修改结束后使用 release() 释放锁。

  • 如果一个 COW 页面需要被复制,但没有足够的空间,应该杀死该进程;
  • 产生中断异常时需要对地址的合法性进行检查,例如:是否超过虚拟地址的范围、是否请求了 Guard Page 内的地址等,如果地址不合法,应该杀死进程;
  • 根据 RISC-V 手册,页错误的 Supervisor Trap Cause (scause) 编号为 15

📊 结果评估

你可以使用以下测试用例在本地测试:

1) cowtest:包含不同难度的针对 COW Fork 的测试用例。

$ cowtest
simple: ok
simple: ok
three: ok
three: ok
three: ok
file: ok
ALL COW TESTS PASSED

2) usertests:该测试包含了一些 cowtest 不涉及的情况。你对 xv6 的修改应当不影响这些测试用例的正常执行,如果这里的一些测试用例执行失败 (即使 cowtest 执行通过),你的实现很有可能在已有功能上引入了新的 Bugs。

$ usertests -q
usertests starting
# ...
OK
# ...
OK
ALL TESTS PASSED