实现写时复制 (Copy-On-Write)
系统实验 (基于 xv6)
截止时间:2024年12月22日 23:59
提交内容:
- 代码源文件
学号.zip
: 请注意代码中应有必要的注释;- 实验报告
学号.pdf
:简要描述实验中遇到的关键问题及解决方案、印象最深的 bugs、或者额外实现的功能等即可 (1~2 页)。提交方式:请参考实验页面的具体说明,本次实验
LAB ID
为3
。# 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 会导致同一个物理页被多个进程的页表引用,此时还需要记录每个物理页被引用的次数,以此来判断在进程结束时是否能释放对应的物理内存。
你可以参考以下流程来实现本次实验:
修改
kernel/vm.c
中的uvmcopy()
函数,使其在fork()
时不复制父进程的整个内存空间,而是让子进程共享。在这一过程中,需要修改父进程和子进程的 PTE,包括将页标记为只读 (擦除可写标志位PTE_W
),并设置 COW 标志位 (需要在合适的位置定义 PTE 的内容)。修改
kernel/trap.c
中的usertrap()
函数,使其在处理中断时,判断是否是 COW Fork 产生的中断异常。如果是,则分配和复制对应的物理页,并更新 PTE 为可写 (注意,如果该页面本来就是只读页面,则属于进程访问了非法地址,此时应杀死该进程)。在合适的时机释放物理内存。为此,需要维护一个新的数据结构来记录各物理页的引用数,在此基础上,在第一次分配物理页时设置引用计数初始值 (
kalloc()
)、在共享物理页时增加引用数、在进程从页表删除物理页时减少引用数 (kfree()
、或者触发 COW 异常中断而导致页面复制时)、并最终当物理页引用数为 0 时释放物理内存。修改
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