引入
MIT 6.828 实验使用 xv6 作为基础内核，要么探索内核原理，要么扩展内核功能。涉及系统调用、页表机制、中断机制、内存分配、调度机制、驱动、锁同步和文件系统。但是，xv6 只解决了有没有的问题，并没有解决好不好用的问题。举个例子，xv6 不支持广义的多线程，xv6 虽然支持并发多个线程，但不支持一个线程分多个逻辑段送入不同的 CPU 核心协作进行；xv6 只支持大锁（coarse-grained lock），这使得线程的并发效率降低。xv6 实验除了探索上面的原理，更多的是负责优化内核功能，也即是解决好不好用的问题
第一个实验
环境搭建 略过
读 xv6-handout，ch1，完成 lab: xv6 and unix utilities，耗时 28h28m
作为第一个实验，其实总体来说是比较简单的（可能是第一次接触，所以我这个完成时长非常感人）：
- 首先是介绍了 lab 打分脚本、如何使用
- 大多数任务是基于 xv6 提供的系统调用来实现的
- 所有任务都是以 shell 命令形式运行的，主要目的是让我们熟悉如何为 xv6 添加命令
- 有两个任务需要熟悉管道的思想，要知道管道读阻塞的特性，要知道管道读返回的条件
- 最后两个任务是复现 UNIX 系统调用，当然 xv6 只要求很简单的那部分功能，这个过程中可以了解 find、xargs 命令的实现细节
第二个实验
读 xv6-handout，ch2，完成 lab: system calls，耗时 7h56m
通过这个实验可以了解：
- 知道系统调用到底是怎么回事。事实上用户进程发起一个系统调用如
read()，并不是直观上的内核帮你找到这个函数，让你跳入执行。从用户进程发起系统调用，到内核执行真正的函数这中间是个山路十八弯的过程。具体的原理在 lab trap 里可以看到，目前这个 lab 的目的是让我们熟悉 xv6 系统调用 - xv6 安装系统调用的过程。这里就是一个非常曲折的过程，事实上 xv6 提供给用户进程的只是一个系统调用数组。用户进程发起的系统调用，最终会转化为系统调用号。内核利用系统调用号作为索引，从数组中找到对应的函数指针，这才得以调用实际的内核函数。为什么需要这么复杂的过程？这是为了保证内核隔离性，也即是用户进程不允许直接访问内核数据
第三个实验
读 xv6-handout，ch3，完成 lab: page tables，耗时 15h6m
这个实验和优化内核功能有关，前提是你需要熟悉 risc-v 页表机制
- 了解虚拟地址翻译过程。risc-v 是三级页表，因此翻译过程也是三级迭代进行，第二个任务需要利用这个思想将翻译过程中的页表项内容打印出来
- 了解虚拟地址与其页表项的关系。某个页面是否刚才被访问过其实硬件是会记录下来的，这就是垃圾收集机制（GC）可以利用的硬件设施。这通过页表项标志位可以获悉，所以第三个任务的问题就变成了，给定一个虚拟地址，如何得到它的页表项
第四个实验
读 xv6-handout，ch4，完成 lab: traps，耗时 15h26m
这个实验是为数不多的属于内核原理方面的内容：
- 第二个任务让我们了解栈帧结构、了解函数调用过程底层的程序流。从本质来说，其实并没有什么内核栈、用户栈，都是内存某个区域上的数据而已。只是说，一开始只有内核自己的栈，而在内核运行过程中，开始运行其他用户进程后，内核会在自己的栈分一部分出去（其实还是将栈顶分出去）供用户进程使用，这便称为栈帧。所以每调用一个函数，最初那个内核栈便多分出一部分空间用作栈帧，因此可以逐个栈帧逐个栈帧地，根据返回地址往回访问，最终形成一系列系统调用过程序列
- 第三个任务让我们了解系统调用原理，这是利用 risc-v 中断机制实现的。xv6 实现了一个函数叫做
trampoline()，由于这个函数所在的页，在用户空间和内核空间都是同一个映射，所以这是一个横跨用户态和内核态两个状态的函数（过渡函数）。这是整个中断故事开始的地方，用户进程在这里保护现场，并在 sepc 寄存器留下返回地址（这是非常关键的一步）。然后进入usertrap()，这个函数会分辨 trap 到底是中断、异常还是系统调用，分别交给不同的函数执行。执行结束便调用usertrapret()完成收尾，然后又回到过渡函数userret()恢复现场，最后通过 spec 的返回地址返回用户空间。这就是中断机制的思想，如下图所示
第五个实验
读 xv6-handout，ch5，完成 lab: Copy-on-Write Fork for xv6，耗时 12h13m
这又是属于内核功能优化的实验：
- 内存分配思想主要分为两种：一种是 eager allocation，这种思想是用户进程要多少内存就分配多少；另一种是 lazy allocation，这种思想是不分配内存，只建立页表映射。只有当内核抛出缺页异常时，才实际分配。可以看出后者是非常优秀的思想，按需分配，可惜的是 xv6 只实现了 eager allocation
- page-fault 异常。可以说这是现代操作系统非常非常非常重要的思想，内存分配既可以兼顾效率（因为只安装了页表映射，没有分配物理内存），又可以使用比实际内存条大得多得多的空间（因为是按需分配）
- 写时拷贝思想。
fork()大家都知道是用来复制子进程的，但一般是用在什么场景呢？答案是 shell，当我们在 shell 敲入命令比如ls后，此时父进程是 shell，子进程先是 shell，之后马上被替换成ls进程。可以说子进程拷贝了一大片内存，然后用都没用，就被替换成另一个进程（从磁盘将另一个文件加载上来）。这就造成了巨大的浪费，写时拷贝思想就是fork()并不分配内存，而是子进程和父进程共享同一个物理页，但该物理页属性要修改为 “只读”，这样，只有父、子进程其中一个想写入时，就会抛出异常，之后内核再重新分配一个物理页，并修改相应属性，从而达到减少开销的目的
第六个实验
读 xv6-handout，ch6 和 ch7，完成 lab: Multithreading，耗时 11h25m
这个实验可以算得上是内核原理部分的探索，但又不全是。这是因为实验要求实现的是用户级线程系统，但是如果你不了解 xv6 调度机制又不可能会完成：
- 首先要注意的是 xv6 没有实现广义上的多线程。xv6 是一个进程只包含一个线程，所以 xv6 里面你既可以说进程切换，也可以说是线程切换。它的确可以多个线程并发执行，但这些线程只是各做各的事情，你想让一个程序分为不同的逻辑段，每一段送去不同的核心执行，这种多线程之间协作在 xv6 里面是不可能的
- 调度机制：上图所示是线程切换的例子（从 CC 命令切换到 LS 命令，详见原文）。xv6 用户线程只要陷入内核态，就变成了内核线程（这里并不是同一个程序逻辑，只要变成内核线程，程序逻辑就改变了），同时要注意陷入也是通过 trap 机制实现的。之后为了实现调度，内核会保护两个现场，分别是内核线程现场和调度器现场。内核线程和用户线程关联，调度器和 CPU 关联。然后调度的逻辑，就是和系统调用差不多了
- 锁：这个实现只是让我们熟悉锁，后面锁那个实验才真正涉及原理。由于线程的推进速度是随机的，因此需要一种机制来确保多个线程的执行保证正确性，锁机制就应用于此，这个实验仅使用 POSIX 接口的锁，相对来说还算简单
第七个实验
有 xv6-handout ch5 基础即可，完成 lab: networking，耗时 12h42m
这个实验属于内核功能的扩展，为 xv6 添加网卡驱动。网络栈由 qemu 模拟，所以相对来说比较简单，只需负责 E1000 网卡发送和接收模块
第八个实验
有 xv6-handout ch6 基础以及 ch8 部分章节，完成 lab: locks，耗时 32h27m
这个实验属于内核功能的优化，难度比较大，主要涉及锁同步方面内容：
- 大锁低效率，小锁易死锁：假设当前并发 10 个进程，使用大锁会使这 10 个进程串行起来，即一个一个地执行，这保证了程序正确性，但牺牲了效率；使用小锁可以使 10 个进程并发进行，但进程间却容易产生竞争条件（比如两个进程同时争抢一个资源），甚至形成死锁（比如两个进程互相持有自己的资源，却又同时请求对方的资源）。xv6 只使用大锁处理同步，第二个任务就是把大锁优化为多个小锁，提升并发效率，但在这个过程里面需要注意竞争与死锁
- 磁盘调度算法（LRU 算法）其他实现思路：LRU 全名最近最久未使用，说的是上一次释放的磁盘块很可能会接着使用，所以淘汰策略最先考虑那些很久没使用的块。xv6 原生提供由循环双链表组织的磁盘块链非常巧妙，链头指针往前是最近最久未使用的块，往后是使用得最频繁得块。所以 xv6 寻找磁盘块直接往后找，淘汰磁盘块直接往前找，这样就可以保证效率。第二个任务让我们放弃这种算法，改成根据时间片数值的大小进行淘汰，使用频繁的块时间片最大，所以此时只需淘汰时间片最小的块
第九个实验
阅读 xv6-handout ch8，完成 lab: file system，耗时 9h18m
这个实验也是属于内核功能的优化：
- 为 xv6 添加大文件支持：文件尺寸是由 inode 决定的，xv6 只支持一级索引，所以单个文件大小限制较大。第一个实验通过修改 inode 为新增二级索引，从而扩大文件尺寸
- 为 xv6 添加符号链接（软连接）：相当于 Windows 的快捷方式，底层原理只是拷贝了一份文件路径，并增加了文件引用
第十个实验
有 xv6-handout ch3 以及 ch8 基础，完成 lab: file system，耗时 25h35m
这个实验属于内核功能的优化，涉及虚拟内存系统和文件系统两大部分，难度比较大：
- mmap 技术：这也是一种文件系统操作，区别于常规
read()/write()，mmap 技术能支持更大的文件读写。另外，mmap 技术也使用了 page-fault 这种按需分配的思想，所以在性能上也会比常规读写更优 - 内存映射文件和 VMA：内存映射文件逻辑上和常规文件读写一样，也是需要经过两次拷贝（磁盘文件到内核 block cache，再到用户进程缓冲区），不同的是这种技术是通过 VMA 结构管理的。VMA 结构包含了文件和该文件对应的虚拟地址，可以引入 page-fault 实现按需分配，为 mmap 技术支持比物理内存大得多的文件提供基础支撑
写在最后
我知道 fall-2021 已经改名，但我还是喜欢称之为 MIT 6.828，不单单因为更经典。更是因为，我手边有个烂尾 x86 kernel，这些年来我一直从入门到放弃，从放弃到入门，bootloader 已经改了五六版，但其他的进度却一直停滞。对于烂尾，我感到很遗憾，我真的十分渴望有朝一日可以真真正正完成，这也是我执着 x86 的原因
在完成整个系列的过程中，我是先阅读 handout，再来到 对应的 lec 跟着课堂笔记理解，最后才是动手做实验
困难是有的，由于是国外的课程，所以 lab 是英文描述，阅读理解自然是必须要做的。其实有很多时候我也会因为题目描述是英文而感到迷惑，我的策略是先翻译题目（我没有逐字逐句翻译，我只会翻译修饰结构多的句子），然后从头开始读一遍题意，这一次一并整理思路（我会把关键的句子用红色荧光笔画出来）。对于后面那几个实验，是优化内核功能的，非常难。有时候我读实验提示就读了好几次，还需要参考网上优化技术的原理，之后才能推出实验逻辑到底是怎样的
所以如果觉得某个实验难，千万不要放弃，都是这么过来的
另一个不得不说的是调试，可能也因为我不会 GDB，所以不知道 GDB 调试到底好在哪。我是用非常蠢的办法调试的，就是 printf()：
我会在关键函数里面，执行完某些语句后写上 printf() 打印执行后变量的变化情况，从而推出函数逻辑是否和我想得一样。其实 GDB 也可以用 C 代码来调试，只要你玩得溜的话（我在 LEC 里见过教授这么用）
总的来说，课程质量很高，也很有趣。但实验只是捡出了操作系统里面最重要的几个部分来巩固。其实也不可能面面俱到把所有内容都设计成实验供我们探索，像管道、文件系统崩溃恢复、shell 实现之类的，这些实验没包括的内容但仍然很重要的内容，还是需要我们回到 xv6 源码里面才能知道它的原理到底是怎样的。如果你是想探索操作系统里面最基础最重要的（比如中断机制、页表机制等等）那么经过整个系列的实验你会收获很多，但如果你是想从零开始自己实现一个内核，那么光靠实验是远远不够的