MIT 6.s081 Operating System Engineering
前言（Intro)
MIT 6.s081 作为著名的操作系统导论级课程，对于操作系统的设计和实现，以及它们作为系统编程基础的使用有着非常独到而易懂的讲解。在结束计算机体系结构基础的粗浅学习后，笔者毫不犹豫地选择了它开始了对作为计算机三大浪漫之一的OS的初步学习。
在Fall2020的版本中，lecture的主题包括虚拟内存、文件系统、线程、上下文切换、内核、中断、系统调用、进程间通信、软件和硬件之间的协调和交互等等；而对于lab，这门课专门开发了一个新的基于 RISC-V 的教学用多处理器操作系统 xv6，它是一个类似于 Unix v6 的操作系统，而不是最新最好版本的 Linux、Windows 或 BSD Unix，但 xv6足够大，足以说明操作系统中的基本设计和实现思想。另一方面，xv6 比任何现代生产操作系统都要小得多，因此也更容易理解。 xv6 具有与许多现代操作系统类似的结构，在探索xv6的过程中，也会发现 Linux 等内核内部有很多熟悉的内容。
简介(Synopsis)
Lab 指引
官方难度参考： 🟩 easy：小于 1 小时。通常是为后续练习的热身 🟧 moderate：1～2 小时。通常是添加一些较为独立的拓展 🟥 hard：大于 2 小时，通常这些功能的实现不需要写很多行代码， 但是debug的路途比较坎坷
“个人耗时”是我个人在做这个 lab 的时候所用的时间，包含了研究、阅读代码、编码与调试全过程。
Lab1 - Xv6 and Unix utilities｜Unix 实用工具：
目标简述： 实现几个用户态程序及 unix 实用工具，熟悉 xv6 的开发环境以及系统调用的使用。 实验难度： 🟩🟩 2 easy, 🟧🟧🟧🟧 4 moderate 个人耗时： 7 小时
Boot xv6 🟩
准备环境，编译编译器、QEMU，克隆仓库
$ git clone git://g.csail.mit.edu/xv6-labs-2020
$ cd xv6-labs-2020
$ git checkout util
$ make qemu
sleep 🟩
添加一个self-written的sleep.c文件执行用户级的进程，调用user.h中提供的syscall接口即可
pingpong 🟧
管道练手题，使用 fork() 复制父进程创建子进程，创建两个管道，分别用于父子之间两个方向的数据传输即可
primes 🟧
设计一个递归的filter，每一个 stage 以当前数集中最小的数字作为素数输出（每个 stage 中数集中最小的数一定是一个素数，因为它没有被任何比它小的数筛掉），并筛掉输入中该素数的所有倍数（必然不是素数），然后将剩下的数传递给下一 stage。最后会形成一条子进程链，而由于每一个进程都调用了wait(0)等待其子进程，所以会在最末端也就是最后一个 stage 完成的时候，沿着链条向上依次退出各个进程。
注意：由于每个stage 之间会有两个管道 pleft 和 pright，要注意关闭不需要用到的文件描述符
find 🟧
本质上就是在ls的基础上进行了选择，所以可以仿照ls.c进行改造，逻辑上先打开给定path的文件描述符，检查它的文件状态，是文件则检查与target是否相同，是目录则递归搜索内部文件
xargs 🟧
编写 xargs 工具，从标准输入读入数据，将每一行当作参数，加入到传给 xargs 的程序名和参数后面作为额外参数，然后执行。用内存池将储存调用xarg的参数以及从stdin读入的参数，对每个命令都fork出子进程exec即可
Lab2 - System calls｜系统调用：
目标简述： 添加 syscall 跟踪，以及添加新的系统调用 sysinfo，帮助加深对 xv6 内核的理解。 实验难度： 🟧🟧 2 moderate 个人耗时： 6 小时
System call tracing 🟧
为trace这个用户程序添加一个内核函数及其接口。首先在内核中的sysproc.c中实现内核调用，然后在syscall.h中加入新 sys_trace的序号，接着用 extern 全局声明新的内核调用函数，并且在 syscalls 映射表中，加入从前面定义的编号到系统调用函数指针的映射，此外还需要在 usys.pl 中加入用户态到内核态的跳板函数，最后在user.h中加入定义，即可使用户态程序找到这个跳板入口函数。
Sysinfo 🟧
添加一个系统调用，返回空闲的内存、以及已创建的进程数量。
xv6 中，空闲内存页的记录方式是，将空虚内存页本身直接用作链表节点，形成一个空闲页链表，每次需要分配，就把链表根部对应的页分配出去。每次需要回收，就把这个页作为新的根节点，把原来的 freelist 链表接到后面。所以计算空闲内存就只需要逐个检查freelist的结点然后加上pagesize即可
进程数目则可以直接通过内核栈上维护的proc数组，逐个查询proc->state的状态计数即可。剩下的syscall实现与上面一致
Lab3 - Page tables｜页表：
目标简述： 探索页表，为每个进程维护独立的内核页表；修改页表以简化从用户态拷贝数据到内核态的方法。 （难点：理解进程页表、内核页表概念） 实验难度： 🟩 1 easy, 🟥🟥 2 hard 个人耗时： 26 小时
Print a page table 🟩
添加一个打印页表的内核函数，按给定格式打印出传进的页表。
由于RISC-V 的逻辑地址寻址是采用三级页表的形式，9 bit 一级索引找到二级页表，9 bit 二级索引找到三级页表，9 bit 三级索引找到内存页，最低 12 bit 为页内偏移（即一个页 4096 bytes），所以要递归打印页表，只需要将递归释放页表的函数 freewalk()复制一份并将释放部分代码改为打印即可
A kernel page table per process🟥
xv6 原本的设计是，用户进程在用户态使用各自的用户态页表，但是一旦进入内核态（例如使用了系统调用），则切换到内核页表（通过修改 satp 寄存器，trampoline.S）。然而这个内核页表是全局共享的，也就是全部进程进入内核态都共用同一个内核态页表，本拓展则是要求让每一个进程进入内核态后，都能有自己的独立内核页表
首先在进程的结构体 proc 中，添加一个 kernelpgtbl，用于存储进程专享的内核态页表。接下来暴改 kvminit。内核需要依赖内核页表内一些固定的映射的存在才能正常工作，例如 UART 控制、硬盘界面、中断控制等。而 kvminit 原本只为全局内核页表 kernel_pagetable 添加这些映射。我们抽象出来一个可以为任何我们自己创建的内核页表添加这些映射的函数 kvm_map_pagetable()。
现在可以创建进程间相互独立的内核页表了，但是还有一个东西需要处理：内核栈。 原本的 xv6 设计中，所有处于内核态的进程都共享同一个页表，即意味着共享同一个地址空间。由于 xv6 支持多核/多进程调度，同一时间可能会有多个进程处于内核态，所以需要对所有处于内核态的进程创建其独立的内核态内的栈，也就是内核栈，供给其内核态代码执行过程。
xv6 在启动过程中，会在 procinit() 中为所有可能的 64 个进程位都预分配好内核栈 kstack，具体为在高地址空间里，每个进程使用一个页作为 kstack，并且两个不同 kstack 中间隔着一个无映射的 guard page 用于检测栈溢出错误。具体参考 xv6 book 的 Figure 3.3。
在 xv6 原来的设计中，内核页表本来是只有一个的，所有进程共用，所以需要为不同进程创建多个内核栈，并 map 到不同位置（见 procinit() 和 KSTACK 宏）。而我们的新设计中，每一个进程都会有自己独立的内核页表，并且每个进程也只需要访问自己的内核栈，而不需要能够访问所有 64 个进程的内核栈。所以可以将所有进程的内核栈 map 到其各自内核页表内的固定位置（不同页表内的同一逻辑地址，指向不同物理内存）。
然后，在创建进程的时候，为进程分配独立的内核页表，以及内核栈
到这里进程独立的内核页表就创建完成了，但是目前只是创建而已，用户进程进入内核态后依然会使用全局共享的内核页表，因此还需要在 scheduler() 中进行相关修改。在调度器将 CPU 交给进程执行之前，切换到该进程对应的内核页表：
到这里，每个进程执行的时候，就都会在内核态采用自己独立的内核页表了。最后需要做的事情就是在进程结束后，应该释放进程独享的页表以及内核栈，回收资源，否则会导致内存泄漏。
Simplify copyin/copyinstr 🟥
在上一个实验中，已经使得每一个进程都拥有独立的内核态页表了，这个实验的目标是，在进程的内核态页表中维护一个用户态页表映射的副本，这样使得内核态也可以对用户态传进来的指针（逻辑地址）进行解引用。这样做相比原来 copyin 的实现的优势是，原来的 copyin 是通过软件模拟访问页表的过程获取物理地址的，而在内核页表内维护映射副本的话，可以利用 CPU 的硬件寻址功能进行寻址，效率更高并且可以受快表加速。
要实现这样的效果，我们需要在每一处内核对用户页表进行修改的时候，将同样的修改也同步应用在进程的内核页表上，使得两个页表的程序段（0 到 PLIC 段）地址空间的映射同步。
首先实现一些工具方法，kvmcopymappings()将 src 页表的一部分页映射关系拷贝到 dst 页表中，并且只拷贝页表项，不拷贝实际的物理页内存；kvmdealloc()用于同步释放内存时内核页表内程序内存的映射和用户页表程序内存的映射，与 uvmdealloc 功能类似，将程序内存从 oldsz 缩减到 newsz。但区别在于不释放实际内存
接下来，为映射程序内存做准备。实验中提示内核启动后，能够用于映射程序内存的地址范围是 [0,PLIC)，我们将把进程程序内存映射到其内核页表的这个范围内，首先要确保这个范围没有和其他映射冲突。所以修改 kvm_map_pagetable()，去除 CLINT 的映射，这样进程内核页表就不会有 CLINT 与程序内存映射冲突的问题。但是由于全局内核页表也使用了 kvm_map_pagetable() 进行初始化，并且内核启动的时候需要 CLINT 映射存在，故在 kvminit() 中，另外单独给全局内核页表映射 CLINT。
后面的步骤就是在每个修改到进程用户页表的位置，都将相应的修改同步到进程内核页表中。一共要修改：fork()、exec()、growproc()、userinit()。最后替换copyin、copyinstr的实现即可
Lab4 - Traps｜中断陷阱：
目标简述： 探索中断以及中断处理机制（trap、trampoline、函数调用、现场保存、页表/特权切换、调用栈、栈指针及返回指针） （注：本 lab 并不非常难，重要的是理解 lecture5 与 lecture6 中的概念） 实验难度： 🟩 1 easy, 🟧 1 moderate, 🟥 1 hard 个人耗时： 4 小时
RISC-V assembly 🟩
阅读 call.asm，以及 RISC-V 指令集教程，回答问题
Backtrace 🟧
在内核中的sys_sleep函数调用中添加 backtrace 功能，打印出调用栈，用于调试。首先在在 defs.h 中添加声明，然后在 riscv.h 中添加获取当前 fp（frame pointer）寄存器的方法，接着在printf.c中实现 backtrace 函数，最后在 sys_sleep 的开头调用一次 backtrace()即可
关键是如何获取当前 fp（frame pointer）寄存器，关于寄存器、栈帧以及内存调用的细节，可以查看 lecture 5
Alarm 🟥
为 xv6 添加一项功能，在进程占用 CPU 时间时定期发出警报。这可能对希望限制占用 CPU 时间的计算绑定进程，或希望计算但也希望采取某些定期行动的进程很有用。更一般地说，它将实现一种原始形式的用户级中断/故障处理程序，例如，可以使用类似的方法来处理应用程序中的page fault
首先，在 proc 结构体的定义中，增加 alarm 相关字段：
- alarm_interval：时钟周期，0 为禁用
- alarm_handler：时钟回调处理函数
- alarm_ticks：下一次时钟响起前还剩下的 ticks 数
- alarm_trapframe：时钟中断时刻的 trapframe，用于中断处理完成后恢复原程序的正常执行
- alarm_goingoff：是否已经有一个时钟回调正在执行且还未返回（用于防止在 alarm_handler 中途闹钟到期再次调用 alarm_handler，导致 alarm_trapframe 被覆盖）
然后添加系统调用sys_sigalarm和sys_sigreturn，其中sigalarm设置 myproc 中的相关属性，sigreturn将trapframe恢复到时钟中断之前的状态，恢复原本正在执行的程序流。接着在 proc.c 中的allocproc和freeproc添加初始化与释放代码
最后在 usertrap() 函数中，实现时钟机制具体代码，这样，在每次时钟中断的时候，如果进程有已经设置的时钟（alarm_interval != 0），则进行 alarm_ticks 倒数。当 alarm_ticks 倒数到小于等于 0 的时候，如果没有正在处理的时钟，则尝试触发时钟，将原本的程序流保存起来（*alarm_trapframe = *trapframe），然后通过修改 pc 寄存器的值，将程序流转跳到 alarm_handler 中，alarm_handler 执行完毕后再恢复原本的执行流（*trapframe = *alarm_trapframe）。这样从原本程序执行流的视角，就是不可感知的中断了。
Lab5 - Lazy allocation｜内存页懒分配：
目标简述： 实现内存页懒分配机制，在调用 sbrk() 的时候，不立即分配内存，而是只作记录。在访问到这一部分内存页并触发缺页异常的时候才进行实际的物理内存分配。 实验难度： 🟩 1 easy, 🟧 2 moderate 个人耗时： 4 小时
Eliminate allocation from sbrk() 🟩
修改 sys_sbrk，使其不再调用 growproc()，而是只修改 p->sz 的值而不分配物理内存即可
Lazy allocation 🟧
修改 usertrap 用户态 trap 处理函数，为缺页异常添加检测，如果为缺页异常（(r_scause() == 13 || r_scause() == 15)），且发生异常的地址是由于懒分配而没有映射的话，就为其分配物理内存，并在页表建立映射
在实现uvmlazytouch函数来负责分配实际的物理内存并建立映射之前，还需要实现uvmshouldtouch用于检测一个虚拟地址是不是一个需要被 touch 的懒分配内存地址，具体检测的是：
- 处于
[0, p->sz)地址范围之中（进程申请的内存范围） - 不是栈的 guard page（具体见 xv6 book，栈页的低一页故意留成不映射，作为哨兵用于捕捉 stack overflow 错误。懒分配不应该给这个地址分配物理页和建立映射，而应该直接抛出异常） （解决 usertests 中的 stacktest 失败的问题）
- 页表项不存在
由于懒分配的页，在刚分配的时候是没有对应的映射的，所以要把一些原本在遇到无映射地址时会 panic 的函数的行为改为直接忽略这样的地址：
uvmummap()：取消虚拟地址映射
uvmcopy()：将父进程的页表以及内存拷贝到子进程
copyin() 和 copyout()：内核/用户态之间互相拷贝数据
由于这里可能会访问到懒分配但是还没实际分配的页，所以要加一个检测，确保 copy 之前，用户态地址对应的页都有被实际分配和映射。
Lazytests and Usertests 🟧
提供了一些特定的测试用例：
- Handle negative sbrk() arguments.
- Kill a process if it page-faults on a virtual memory address higher than any allocated with sbrk().
- Handle the parent-to-child memory copy in fork() correctly.
- Handle the case in which a process passes a valid address from sbrk() to a system call such as read or write, but the memory for that address has not yet been allocated.
- Handle out-of-memory correctly: if kalloc() fails in the page fault handler, kill the current process.
- Handle faults on the invalid page below the user stack.
Lab6 - Copy-on-write fork｜fork 懒拷贝：
目标简述： 实现 fork 懒复制机制，在进程 fork 后，与父进程共享物理内存页。在任一方尝试对内存页进行修改时，才对内存页进行复制。 实验难度： 🟥 1 hard 个人耗时： 5 小时
Implement copy-on write 🟥
实现 fork 懒复制机制，在进程 fork 后，不立刻复制内存页，而是将虚拟地址指向与父进程相同的物理地址。在父子任意一方尝试对内存页进行修改时，才对内存页进行复制。 物理内存页必须保证在所有引用都消失后才能被释放，这里需要有引用计数机制。
首先修改 uvmcopy()，在复制父进程的内存到子进程的时候，不立刻复制数据，而是建立指向原物理页的映射，并将父子两端的页表项都设置为不可写。然后与 lazy allocation lab 类似，在 usertrap() 中添加对 page fault 的检测，并在当前访问的地址符合懒复制页条件时，对懒复制页进行实复制操作；同时 copyout() 由于是软件访问页表，不会触发缺页异常，所以需要手动添加同样的监测代码（同 lab5），检测接收的页是否是一个懒复制页，若是，执行实复制操作。此外，还需要在vm.c中实现懒复制页的检测（uvmcheckcowpage()）与实复制（uvmcowcopy()）操作
到这里，就已经确定了大体的逻辑了：在 fork 的时候不复制数据只建立映射+标记，在进程尝试写入的时候进行实复制并重新映射为可写。接下来，还需要做页的生命周期管理，确保在所有进程都不使用一个页时才将其释放
在原本的 xv6 实现中，一个物理页的生命周期内，可以支持以下操作：
- kalloc(): 分配物理页
- kfree(): 释放回收物理页
而在支持了懒分配后，由于一个物理页可能被多个进程（多个虚拟地址）引用，并且必须在最后一个引用消失后才可以释放回收该物理页，所以一个物理页的生命周期内，现在需要支持以下操作：
- kalloc(): 分配物理页，将其引用计数置为 1
- krefpage(): 创建物理页的一个新引用，引用计数加 1
- kcopy_n_deref(): 将物理页的一个引用实复制到一个新物理页上（引用计数为 1），返回得到的副本页；并将本物理页的引用计数减 1
- kfree(): 释放物理页的一个引用，引用计数减 1；如果计数变为 0，则释放回收物理页
一个物理页 p 首先会被父进程使用 kalloc() 创建，fork 的时候，新创建的子进程会使用 krefpage() 声明自己对父进程物理页的引用。当尝试修改父进程或子进程中的页时，kcopy_n_deref() 负责将想要修改的页实复制到独立的副本，并记录解除旧的物理页的引用（引用计数减 1）。最后 kfree() 保证只有在所有的引用者都释放该物理页的引用时，才释放回收该物理页即可
Lab7 - Multithreading｜多线程：
目标简述： 实现一个用户态的线程库；尝试使用线程来为程序提速；实现一个同步屏障 实验难度： 🟧🟧🟧 3 moderate 个人耗时： 4 小时
Uthread: switching between threads 🟧
实现一个用户态的线程库，补全 uthread.c，完成用户态线程功能的实现。这个实验其实相当于在用户态重新实现一遍 xv6 kernel 中的 scheduler() 和 swtch() 的功能，所以大多数代码都是可以借鉴的。
uthread_switch.S 中需要实现上下文切换的代码，这里借鉴 swtch.S；从 proc.h 中借鉴一下 context 结构体，用于保存 ra、sp 以及 callee-saved registers；在 thread_schedule 中调用 thread_switch 进行上下文切换；再补齐 thread_create，添加的部分为设置上下文中 ra 指向的地址为线程函数的地址，这样在第一次调度到该线程，执行到 thread_switch 中的 ret 之后就可以跳转到线程函数从而开始执行了。设置 sp 使得线程拥有自己独有的栈，也就是独立的执行流。
Using threads 🟧
分析并解决一个哈希表操作的例子内，由于 race-condition 导致的数据丢失的问题
单纯在put和get中加锁后多线程的性能反而变得比单线程还要低了，虽然不会出现数据丢失，但是失去了多线程并行计算的意义：提升性能。这里的原因是，我们为整个操作加上了互斥锁，意味着每一时刻只能有一个线程在操作哈希表，这里实际上等同于将哈希表的操作变回单线程了，又由于锁操作（加锁、解锁、锁竞争）是有开销的，所以性能甚至不如单线程版本。
这里的优化思路，也是多线程效率的一个常见的优化思路，就是降低锁的粒度。由于哈希表中，不同的 bucket 是互不影响的，一个 bucket 处于修改未完全的状态并不影响 put 和 get 对其他 bucket 的操作，所以实际上只需要确保两个线程不会同时操作同一个 bucket 即可，并不需要确保不会同时操作整个哈希表。
所以可以将加锁的粒度，从整个哈希表一个锁降低到每个 bucket 一个锁即可
Barrier 🟧
利用 pthread 提供的条件变量方法，实现同步屏障机制。
线程进入同步屏障 barrier 时，将已进入屏障的线程数量增加 1，然后再判断是否已经达到总线程数。如果未达到，则进入睡眠，等待其他线程。如果已经达到，则唤醒所有在 barrier 中等待的线程，所有线程继续执行；屏障轮数 + 1；
「将已进入屏障的线程数量增加 1，然后再判断是否已经达到总线程数」这一步并不是原子操作，并且这一步和后面的两种情况中的操作「睡眠」和「唤醒」之间也不是原子的，如果在这里发生 race-condition，则会导致出现 「lost wake-up 问题」（线程 1 即将睡眠前，线程 2 调用了唤醒，然后线程 1 才进入睡眠，导致线程 1 本该被唤醒而没被唤醒，详见 xv6 book 中的第 72 页，Sleep and wakeup）
解决方法是，「屏障的线程数量增加 1；判断是否已经达到总线程数；进入睡眠」这三步必须原子。所以使用一个互斥锁 barrier_mutex 来保护这一部分代码。pthread_cond_wait 会在进入睡眠的时候原子性的释放 barrier_mutex，从而允许后续线程进入 barrier，防止死锁。
Lab8 - Parallelism/Locking｜并发与锁：
目标简述： 重新设计并发代码以降低锁竞争，提高在多核系统上的性能。 实验难度： 🟧 1 moderate, 🟥 1 hard 个人耗时： 8 小时
Memory allocator 🟧
通过拆分 kmem 中的空闲内存链表，降低 kalloc 实现中的 kmem 锁竞争。
kalloc 原本的实现中，使用 freelist 链表，将空闲物理页本身直接用作链表项（这样可以不使用额外空间）连接成一个链表，在分配的时候，将物理页从链表中移除，回收时将物理页放回链表中。在这里无论是分配物理页或释放物理页，都需要修改 freelist 链表。由于修改是多步操作，为了保持多线程一致性，必须加锁。但这样的设计也使得多线程无法并发申请内存，限制了并发效率。
这里解决性能热点的思路是「将共享资源变为不共享资源」。锁竞争优化一般有几个思路：
- 只在必须共享的时候共享（对应为将资源从 CPU 共享拆分为每个 CPU 独立）
- 必须共享时，尽量减少在关键区中停留的时间（对应“大锁化小锁”，降低锁的粒度）
该 lab 的实验目标，即是为每个 CPU 分配独立的 freelist，这样多个 CPU 并发分配物理页就不再会互相排斥了，提高了并行性。
但由于在一个 CPU freelist 中空闲页不足的情况下，仍需要从其他 CPU 的 freelist 中“偷”内存页，所以一个 CPU 的 freelist 并不是只会被其对应 CPU 访问，还可能在“偷”内存页的时候被其他 CPU 访问，故仍然需要使用单独的锁来保护每个 CPU 的 freelist。但一个 CPU freelist 中空闲页不足的情况相对来说是比较稀有的，所以总体性能依然比单独 kmem 大锁要快。在最佳情况下，也就是没有发生跨 CPU “偷”页的情况下，这些小锁不会发生任何锁竞争
Buffer cache 🟥
多个进程同时使用文件系统的时候，bcache.lock 上会发生严重的锁竞争。bcache.lock 锁用于保护磁盘区块缓存，在原本的设计中，由于该锁的存在，多个进程不能同时操作（申请、释放）磁盘缓存。
因为不像 kalloc 中一个物理页分配后就只归单个进程所管，bcache 中的区块缓存是会被多个进程（进一步地，被多个 CPU）共享的（由于多个进程可以同时访问同一个区块）。所以 kmem 中为每个 CPU 预先分割一部分专属的页的方法在这里是行不通的。在这里， bcache 属于“必须共享”的情况，所以需要用到第二个思路，降低锁的粒度，用更精细的锁 scheme 来降低出现竞争的概率。
原版 xv6 的设计中，使用双向链表存储所有的区块缓存，每次尝试获取一个区块 blockno 的时候，会遍历链表，如果目标区块已经存在缓存中则直接返回，如果不存在则选取一个最近最久未使用的，且引用计数为 0 的 buf 块作为其区块缓存，并返回。新的改进方案，可以建立一个从 blockno 到 buf 的哈希表，并为每个桶单独加锁。这样，仅有在两个进程同时访问的区块同时哈希到同一个桶的时候，才会发生锁竞争。当桶中的空闲 buf 不足的时候，从其他的桶中获取 buf。
Lab9 - File System｜文件系统：
目标简述： 为 xv6 的文件系统添加大文件以及符号链接支持。 实验难度： 🟧🟧 2 moderate 个人耗时： 2 小时
Large files 🟧
本 lab 的目标是通过为混合索引机制添加二级索引页，来扩大能够支持的最大文件大小。
与 FAT 文件系统类似，xv6 文件系统中的每一个 inode 结构体中，采用了混合索引的方式记录数据的所在具体盘块号。每个文件所占用的前 12 个盘块的盘块号是直接记录在 inode 中的（每个盘块 1024 字节），所以对于任何文件的前 12 KB 数据，都可以通过访问 inode 直接得到盘块号。这一部分称为直接记录盘块。对于大于 12 个盘块的文件，大于 12 个盘块的部分，会分配一个额外的一级索引表（一盘块大小，1024Byte），用于存储这部分数据的所在盘块号。
由于一级索引表可以包含 BSIZE(1024) / 4 = 256 个盘块号，加上 inode 中的 12 个盘块号，所以一个文件最多可以使用 12+256 = 268 个盘块，也就是 268KB。而这远远小于大文件的需求，故而需要添加二级索引页
首先修改 struct inode（内存中的 inode 副本结构体）以及 struct dinode（磁盘上的 inode 结构体），将 NDIRECT 直接索引的盘块号减少 1，腾出 inode 中的空间来存储二级索引的索引表盘块号。然后修改 bmap（获取 inode 中第 bn 个块的块号）和 itrunc（释放该 inode 所使用的所有数据块），让其能够识别二级索引即可。（基本上和复制粘贴一致，只是在查出一级块号后，需将一级块中的数据读入，然后再次查询）
Symbolic links 🟧
实现符号链接机制。首先实现 symlink 系统调用，用于创建符号链接。 符号链接与普通的文件一样，需要占用 inode 块。这里使用 inode 中的第一个 direct-mapped 块（1024字节）来存储符号链接指向的文件。然后修改 sys_open，使其在遇到符号链接的时候，可以递归跟随符号链接，直到跟随到非符号链接的 inode 为止。
Lab10 - Mmap | 文件内存映射：
目标简述： 实现 *nix 系统调用 mmap 的简单版：支持将文件映射到一片用户虚拟内存区域内，并且支持将对其的修改写回磁盘。 实验难度： 🟥 1 hard 个人耗时： 6 小时
实现 *nix 系统调用 mmap 的简单版：支持将文件映射到一片用户虚拟内存区域内，并且支持将对其的修改写回磁盘。
这里涉及的操作系统基本概念是「虚存」，mmap 指令除了可以用来将文件映射到内存上，还可以用来将创建的进程间共享内存映射到当前进程的地址空间内。本 lab 只需实现前一功能即可。
首先需要在用户的地址空间内，找到一片空闲的区域，用于映射 mmap 页。为了尽量使得 map 的文件使用的地址空间不要和进程所使用的地址空间产生冲突，我们选择将 mmap 映射进来的文件 map 到尽可能高的位置，也就是刚好在 trapframe 下面。并且若有多个 mmap 的文件，则向下生长。接下来定义 vma 结构体，其中包含了 mmap 映射的内存区域的各种必要信息，比如开始地址、大小、所映射文件、文件内偏移以及权限等。此外，记得在 proc 结构体末尾为每个进程加上 16 个 vma 空槽。
实现 mmap 系统调用。函数的功能是在进程的 16 个 vma 槽中，找到可用的空槽，并且顺便计算所有 vma 中使用到的最低的虚拟地址（作为新 vma 的结尾地址 vaend，开区间），然后将当前文件映射到该最低地址下面的位置（vastart = vaend - sz）。最后记得使用 filedup(v->f);，将文件的引用计数增加一。
映射之前，需要注意文件权限的问题，如果尝试将一个只读打开的文件映射为可写，并且开启了回盘（MAP_SHARED），则 mmap 应该失败。否则回盘的时候会出现回盘到一个只读文件的错误情况。
由于需要对映射的页实行懒加载，仅在访问到的时候才从磁盘中加载出来，故而下面实现 munmap 调用，将一个 vma 所分配的所有页释放，并在必要的情况下，将已经修改的页写回磁盘。
这里首先通过传入的地址找到对应的 vma 结构体（通过前面定义的 findvma 方法），然后检测了一下在 vma 区域中间“挖洞”释放的错误情况，计算出应该开始释放的内存地址以及应该释放的内存字节数量（由于页有可能不是完整释放，如果 addr 处于一个页的中间，则那个页的后半部分释放，但是前半部分不释放，此时该页整体不应该被释放）。
计算出来释放内存页的开始地址以及释放的个数后，调用自定义的 vmaunmap 方法（vm.c）对物理内存页进行释放，并在需要的时候将数据写回磁盘。将该方法独立出来并写到 vm.c 中的理由是方便调用 vm.c 中的 walk 方法。
在调用 vmaunmap 释放内存页之后，对 v->offset、v->vastart 以及 v->sz 作相应的修改，并在所有页释放完毕之后，关闭对文件的引用，并完全释放该 vma。这里的实现大致上和 uvmunmap 相似，查找范围内的每一个页，检测其 dirty bit (D) 是否被设置，如果被设置，则代表该页被修改过，需要将其写回磁盘。注意不是每一个页都需要完整的写回，这里需要处理开头页不完整、结尾页不完整以及中间完整页的情况。
最后需要做的，是在 proc.c 中添加处理进程 vma 的各部分代码。
- 让 allocproc 初始化进程的时候，将 vma 槽都清空
- freeproc 释放进程时，调用 vmaunmap 将所有 vma 的内存都释放，并在需要的时候写回磁盘
- fork 时，拷贝父进程的所有 vma，但是不拷贝物理页
Lab11 - Network stack：
目标简述： 熟悉系统驱动与外围设备的交互、内存映射寄存器与 DMA 数据传输，实现与 E1000 网卡交互的核心方法：transmit 与 recv。 （本 lab 的难度主要在于阅读文档以及理解 CPU 与操作系统是如何与外围设备交互的。换言之，更重要的是理解概念以及 lab 已经写好的模版代码的作用。） 实验难度： 🟥 1 hard 个人耗时： 3 小时
操作系统想要发送数据的时候，将数据放入环形缓冲区数组 tx_ring 内，然后递增 E1000_TDT，网卡会自动将数据发出。当网卡收到数据的时候，网卡首先使用 direct memory access，将数据放入 rx_ring 环形缓冲区数组中，然后向 CPU 发起一个硬件中断，CPU 在收到中断后，直接读取 rx_ring 中的数据即可。
感想(Summary)
在通过最后一个net的测试时，一种前所未有的轻松感顿时席卷了我的全身，那种深入了解计算机系统内部是如何与用户进行交互，与硬件进行通信以及在程序间进行调度的感觉简直无与伦比。还记得第一次接触Unix中用二进制文件来表示一切的抽象时，那种巧妙而又神奇的设计给了我巨大的震撼。
在整个lab的完成过程中，可以清晰地看到，有些代码行体现了主要思想的本质（例如，上下文切换、用户/内核边界、锁等），并且每一行都很重要；其他代码行提供了如何实现特定操作系统想法的说明，并且可以通过不同的方式轻松完成（例如，更好的调度算法、更好的磁盘数据结构来表示文件、更好的日志记录以允许并发事务等等）。所有的想法都是在一个特定的、非常成功的系统调用接口（Unix 接口）的背景下阐述的，但这些想法也延续到了其他操作系统的设计中。
当然，操作系统的内容还很多，我的路也还很长，xv6虽然精巧但也不过是很简易的系统内核，现代OS的很多思想和算法也等着我去探索，所以，少年：
所谓无底深渊，走下去，也是前程万里
—— 木心
附录(Appendix)
6.S081: Operating System Engineering/schedule