一、操作系统接口

介绍

操作系统的工作是为了多个程序共享一个计算机，并提供一个比硬件本身支持更有效的服务集。
一个操作系统管理、抽象低级硬件，例如：一个字处理器无需关心使用的是哪种类型的硬盘。
一个操作系统让多个程序共享硬件，让它们同时运行（或者说看起来像是同时运行）。
总之，操作系统为程序间相互作用提供控制方式，为了让它们可以共享数据或一起工作。
一个操作系统通过接口为用户程序提供服务。
设计一个好的接口结果发现是比较难的。
一方面，我们想让接口是简单而狭窄，因为那会让正确实现更简单。
另一方面，我们可能尝试给应用提供一些复杂特性。
解决这种紧张关系的诀窍是设计接口，这些接口依赖于一些可以组合以提供更多通用性的机制。
这本书使用一个单独的操作系统作为一个具体的例子，来阐述操作系统理念。
操作系统xv6，提供由Ken Thompson和Dennis Ritchie的Unix操作系统引入的基本接口，并模仿Unix的内部设计。
Unix提供了一个机制结合优秀的narrow接口，并且提供了很强的通用性。
该接口是相当成功的，以至于BSD、Linux、MacOs、Solaris、windows都有类Unix接口。
理解xv6是理解任一这些系统或其他系统的好开端。
正如图1.1所示，xv6采用传统的内核形式（一个为运行程序提供服务的特殊程序）。
每个运行程序，称为一个进程，拥有包含指令、数据、栈的内存。
指令实现程序的计算。数据是计算的变量。栈组织程序的过程调用。
现有的典型计算机拥有许多进程，但仅有一个kernel。

当一个进程需要调用内核服务，它调用一个system call（操作系统接口调用的一种）。
system call进入内核，内核执行服务并返回。
因此进程会在用户空间或内核空间之中执行。
内核使用cpu提供的硬件保护机制，来确保用户空间中执行的进程仅可以访问它自己的内存。
内核利用这些保护所需的硬件权利执行。
用户程序执行不需要这些权力。
当一个用户程序调用一个system call，硬件提升权力级别，并在内核中开始执行pre-arranged 函数。
内核提供的一系列system calls是用户程序所见的接口。
xv6内核提供了传统unix内核提供的system calls和服务的子集。
图1.2列出了xv6提供的所有system calls。

章节其余部分概括了xv6的服务：进程、内存、文件描述、pipes、文件系统，并且用代码段说明，而且讨论shell（Unix的命令行用户接口）如何使用它们。
shell的system calls使用，说明了这些system calls是如何被小心设计的。
shell是一个从用户读取命令行并执行的普通的程序。事实上，shell是一个用户程序，并非内核部分，阐述了system call接口的能力，shell没什么与众不同。
这也意味着shell是很容易取代的，结果是，unix系统有很多shell可供选择，每个都有它自己的用户接口和脚本特征。
xv6 shell是unix bourne shell本质的简单实现。
它的实现可以在user/sh.c:1处找到。

（一）进程和内存

一个xv6进程包含用户空间内存（指令、数据、栈），每个进程状态对内核是私有的。
所有xv6 time-shares进程：可用的cpu在一组等待执行的进程间透明地切换。
当一个进程不执行了，xv6保存它的cpu寄存器，并在再次运行时恢复。
内核与每个进程通过一个进程标识或pid来关联。
一个进程可以使用fork system call创建一个新的进程。
Fork创建的一个新进程，叫做子进程，它拥有和调用线程（父进程）一致的内存内容。
Fork在父子进程中都有返回。父进程：返回子进程的pid；子进程：返回0；例如考虑下面C语言写的代码段。

exit system call导致调用线程停止执行并释放资源（例如内存、打开文件）。
exit将一个整数作为参数，传统地0表明成功，1表明失败。
wait system call返回当前进程的exited、killed子进程pid，并且复制子进程exit状态给 传递给wait函数的地址。
如果没有个子进程exit，wait会一直等到一个子进程退出。
如果调用者没有子进程，wait立马返回-1.
如果父进程不关心子进程的退出状态，可以给wait传0。
在这个例子中输出行是：

也可能是其他输出顺序，这取决于父子进程水仙执行printf call。
在所有子进程exit后，父进程的wait返回，致使父进程打印parent: child 1234 is done。
尽管初始化时子进程和父进程有相同的内存内容，父子进程用不同的内存、寄存器执行：在一个进程改变变量，不会影响另外一个进程。
例如：父进程中wait的返回值存在pid中时，不会改变子进程中的pid。子进程中pid仍然是0。
exec system call用从文件系统中加载的文件的内存镜像，取代调用进程内存。
这个文件必须有一个特定的格式，表明哪里放着指令，哪里放着数据，从哪个指令开始执行等。
xv6使用ELF格式，第三章详细讨论。
当exec成功执行时，它不会给调用程序返回任何东西；另外从文件中加载的指令从ELF头声明的入口处执行。
Exec接受两个参数，可执行文件的名字和一组字符串参数。例如：

这个代码段用程序/bin/echo的运行实例（带有echo hello参数），取代调用程序。
绝大多数程序忽略参数组的第一个元素，传统上它是程序的名字。
xv6 shell使用上述calls运行用户程序。shell的主要结构很简单，看main（user/sh.c:145）。
主循环通过getcmd读取一行用户输入。
然后它调用fork，它将创建一个shell进程复制品。
当子进程执行命令时，父进程调用wait。
例如：如果一个用户输入echo hello到shell，runcmd将会把echo hello作为参数进行调用。
runcmd（user/sh.c:58）执行真正的命令。
对于echo hello，将会调用exec（user/sh.c:78）。
如果exec成功，子进程将会执行执行echo中的指令而不是runcmd。
在某个点上，echo将会调用exit，将导致父进程接收main（user/sh.c:145）中wait的返回值。
你可能会觉得奇怪，为什么fork和exec不结合成一条call，我们之后将看到：shell在io重定向时实现了分离。
为了避免创建重复线程的浪费，并立刻取代它（with exec） ，操作内核优化了fork（对这个使用情形）的实现，通过虚拟内存技术如copy-on-write(看4.6节)。
xv6隐晦地分配绝大多数用户空间内存：fork给子进程分配其父进程内存的拷贝，并且exec分配足够的内存来承载可执行文件。
一个在运行时需要更多内存（可能是执行malloc）的进程，可以调用sbrk(n)来给它的数据区增长n字节。sbrk返回新内存的地址。

（二）IO和文件描述

文件描述符是一个可以代表内核管理对象（线程可以读它、写它）的整数。
一个进程可以通过打开一个文件、目录、设备、创建pipe、复制一个已存在的描述符来获取一个文件描述符。
简单来讲，我们通常将文件描述符称为文件。文件描述符接口对文件、pipes和设备做出抽象，让他们都看起来像是字节流。我们将输入输出称为I/O。
内部地，xv6内核使用文件描述符作为一个索引（每个进程有一个table），所以每个进程中文件描述符都有私有空间。
公约中，读入（标准输入）：0，写出（标准输出）：1，写出错误信息（标准输出）：2。
就像我们将要看到的，shell利用公约实现了IO重定向和pipelines。
shell确保总是有3个文件描述符打开（user/sh.c:151），这是控制台默认的文件描述符。
read和write system calls从被文件描述符标识的打开文件中读字节、向其写字节。
read(fd, buf, n)最多从文件描述fd中读取n个字节，并把它们放到buf中，并返回读取到的字节数。
每个与文件相关的文件描述符有一个与之相关的偏移量。
read从当前文件偏移量开始读数据，然后通过读取字节的数量增加这个偏移量。一系列的read将返回第一次read之后的字节。当没有字节可读时，read返回0表明文件结束。
write(fd, buf, n)将buf数组中的n个字节写到文件描述符fd中，并且返回实际写入字节的数目。
仅当错误发生时，少于n个字节被写入。
像read，write在当前文件偏移量上写数据，并且通过写入字节的数目增加偏移量。每次写入从上次写完的位置开始。
下面的程序块（构成了cat程序的本质）从标准输入拷贝数据到标准输出。
如果一个错误发生，它将错误信息写入到标准错误。

代码中需要重点注意的是：cat不知道是在从文件、控制台、pipe中读入。
相似地，cat不知道是在向控制台、文件或者其他中打印。
文件描述符的使用和0表示输入、1表示输出的传统，允许cat一个简单的实现。
close system call会释放一个文件描述符，让它将来可被open、pipe、dup系统调用重用。
一个新分配的文件描述符总是当前线程中未被使用的最小整数文件描述符。
文件描述符和fork相互作用让I/O重定向很容易实现。
Fork通过拷贝父进程的内存将文件描述符拷贝过去，因此子进程拥有和父进程一样的打开文件。
exec system call取代调用线程的内存，但是保留它的文件表。
这个行为允许shell通过fork，在子进程中重新打开已选择的文件描述符，然后调用exec运行新的程序，实现IO重定向。
这是一个shell运行cat < input.txt的简化版代码。

在子进程关掉文件描述符0后，open保证去使用这个文件描述符关联新打开地input.txt：0将是最小的可被使用的文件描述符。
Cat用指向input.txt的文件描述符执行。
父进程的文件描述符不会改变，因为仅仅改变的是子进程中的文件描述符。
xv6shell中IO重定向的代码具体在user/sh.c:82。
调用此处时已经fork了子进程，并且runcmd将会调用exec去加载新程序。
open第二个参数包含一系列的标志位，用位表达，控制open函数干什么。
所有可能的值定义在kernel/fcntl.h:1-5：O_RDONLY-只读，O_WRONLY-写，O_RDWR-读写，O_CREATE-若文件不存在则创建，O_TRUNC-清空一个文件。
现在应该很清晰了，为什么fork和exec分开时有帮助的。在两个调用之间shell可以重定向子进程IO，不干扰main shell中设置的IO。
假想一个结合指令forkexec system call，但通过这进行IO重定向是尴尬的。
shell要在调用forkexec前更改它的IO设置（然后再改回来）；或者forkexec要把重定向作为参数；或者像cat一样自己重定向。
尽管fork复制文件描述符，但父子进程共享文件偏移。考虑下面例子：

在代码段最后，关联文件描述符1的文件将包含数据：hello world。
父进程中的write（由于wait，仅会在子进程结束后运行）从子进程写完的位置开始写。
这个行为帮助从序列shell命令中产生序列输出，像：(echo hello; echo world) >output.txt
dup system call复制一个已存在的文件描述符，返回一个指向相同IO对象的新文件描述符。
两个文件描述符共享一个偏移量，就像通过fork复制的文件描述符。
这是另一个将hello world写入一个文件的方式。

两个文件描述符共享一个偏移，如果它们都是通过fork和dup从同一个原始文件描述符派生的。
文件描述符不共享偏移量，即使它们是通过open打开的同一个文件。
dup允许shell实现这个命令ls existing-file non-existing-file > tmp1 2>&1。
2>&1通知shell文件描述符2是描述符1的复制。
已存在的文件名和不存在文件的错误信息将显示在tmp1中。
xv6shell不支持错误文件描述符的IO重定向，但现在知道了怎么实现它。
文件描述符是一个有力的抽象，因为它们隐藏了连接细节：一个向文件描述符1写的进程，可能正在向文件、设备（如控制台）、pipe中写。

（三）Pipes

一个pipe就是一个小的内核缓存（kernel buffer），它是对进程暴露的一对文件描述符，其中一个负责读，一个负责写。向pipe的一端写数据使得可以从pipe另一端读数据。Pipes提供了一种进程通信方式。
下面的示例代码运行程序wc，将标准输入连接到pipe的read端。

程序调用pipe函数，创建一个新pipe，并记录读、写文件描述符至数组p。fork执行后，父子进程都有指向pipe的文件描述符。子进程调用close和dup让文件描述符0指向pipe的读端，关掉p中的文件描述符，然后调exec来运行wc。当wc从它的标准输入读取时，它从pipe中读。父进程关掉pipe的读端，向pipe写数据，让后关闭写端。
如果无数据可用，一个pipe上的read端，要么等写端写数据，要么等写端的文件描述符都关闭。在这之后，read将返回0，就像达到一个文件的结尾一样。事实上read停止直到不会再有新数据写入。对子进程来说，要在执行wc之前关闭pipe写端。如果wc有文件描述符指向pipe写端的，那wc将一直不会停止。
xv6shell实现pipelines（例如：grep fork sh.c|wc -l）用了和上面代码相似的方式（user/sh.c:100）。子进程创建一个pipe连接pipeline的左端和右端。对pipeline的左端调用fork和runcmd，对右端调用fork和runcmd，子进程等这两个进程都结束。Pipeline的右端有可能是一个本身包含pipe的命令，它本身fork两个新的子进程（一个给b、一个给c）。因此，shell可能创建一个进程树。叶子节点是命令，内部节点是需要等待左右子节点完成的进程。
理论上，内部节点可以接入pipeline左端，但真成功实现会更复杂。考虑做出下面更改：修改sh.c，让它不为左节点创建进程，直接在内部节点执行runcmd(p->left)。然后，例如，echo hi|wc将不会产生输出，因为当echo hi从runcmd中exit时，内部进程exits，也就不会创建进程来绑定pipe的右端。这个不正确的行为可以通过不在内部进程runcmd中调用exit修复，但这让代码变复杂了：这时runcmd需要知道这是否是一个内部进程。复杂度也会提升当不调用runcmd(p->right)时。例如：sleep 10|echo hi将立刻打印“hi”而不是等待10s，因为echo立刻运行并退出，不会等到sleep结束。因此sh.c的目的就是尽量简单，它不会尝试去避免创建内部进程。
Pipes可能看起来不如临时文件有效。echo hello world | wc 可以不用pipe实现：
echo hello world >/tmp/xyz; wc </tmp/xyz。在这种情形下，Pipes比起临时文件至少有4个优点：1，pipes自动清理自身；2，对于文件重定向，结束时shell不得不小心的删除/tmp/xyz；3，pipes允许pipeline各阶段的并行执行，临时文件需要第一个程序执行结束，在第二个程序执行开始之前；4，如果你实现了内部进程通信，pipes的块级读写阅读比起文件的非块级更有效。

（四）文件系统

Xv6文件系统提供数据文件，包含未解释（uninterpreted）字节数组、目录（包含指向数据文件的命名索引和其他目录）。目录构成了一棵树，起始于一个名为root的特殊目录。一个像/a/b/c这样的路径，指向文件或目录c，在目录b中，在目录a中，在root目录下。那些不带“/”开始的路径，根据调用线程的当前目录（可以调用chdir system call改变）进行计算。下面这些代码端打开相同的文件（假设所有相关目录都存在）。

第一段改变进程的当前目录到/a/b；第二段既没有指向，也没有改变进程的当前目录。
有些system call创建新文件或目录：mkdir创建新目录，open函数传入O_CREATE标志来创建一个新数据文件，
mknod创建一个新的设备文件。这个例子阐述了上面3种情况：
mknod(“/console”, 1, 1);
Mknod创建一个指向device的特殊文件。与设备文件相关的是主要、次要设备编号（传给mknod的两个参数），这唯一标识了一个kernel device。当一个进程之后打开一个device文件，kernel转用read和write system call来实现，而不是通过file system。
一个文件的名字区别与文件本身。同一个潜在文件叫做 inode，可以有多个名字，叫做links。每个link包含一个入口在目录中。入口包含一个文件名字和一个inode的指向。一个inode保存着一个文件的元数据，包含它的类型（file、directory、device），它的长度，文件内容在硬盘的位置，指向此文件links的数量。
fstat system call可以从inode（一个文件描述符指向）获取信息。它这些信息可以用结构体stat表示，声明在stat.h(kernel/stat.h)：

link system call创建另外一个file system name指向与现有文件相同的inode。这个代码段创建了一个新文件命名为a和b。

从a中读或向a中写，从b中读或向b中写是一样的。每个inode由唯一一个inode number标识。执行完上面代码，通过检查fstat的结果，可以确定a和b指向相同的潜在内容：两个都会返回相同的inode number， nlink计数会变成2。
unlink system call将一个name从file system中移除。file inode和保存内容的硬盘空间，仅会在file link为0和无文件描述符指向时，才可以释放。因此添加unlink(“a”); ，文件内容仍然可以通过b访问。另外

是一个惯用语，来创建无名的临时目录，在进程调用close(fd)或exit时，会被clean up。
Unix提供从shell中可调用的文件工具（作为用户级别程序），例如mkdir、ln、rm。这个设计允许任何人去拓展命令行接口，通过添加新的用户级别程序。后来看来，这个打算是明智的，但unix同时期的其他系统设计通常将这些命令内置到了shell中（并把shell内置到内核中）。
cd是一个例外，它内置在shell中（user/sh.c:160）。cd会改变shell当前工作路径。如果cd被视作一个常规命令，那么shell将会fork一个子进程，子进程运行cd，cd将会改变子进程的工作目录。父进程（shell）的工作目录不会改变。

（五）现实世界

Unix结合了标准文件描述符、管道，以及方便操作他们的shell语法（shell在写通用目的可重复使用程序上是一个很大的进步）。这个想法鼓舞了 software tools 文化，对unix的流行起到了作用。shell也被称为脚本语言。unix system call存在于现在的系统（像BSD、Linux、MacOs）中。
unix system call接口已经通过 POSIX(portable operating system interface)标准形成了标准化。xv6不符合POSIX，
它缺少一些system calls（包括基础的例如lseek），并且其他一些系统调用不同于标准。我们xv6的主要目的是简化、清晰，提供一个简单的类unix system call接口。一些人已经用一些system calls拓展了xv6，并且提供了一个简单的C library，为了运行基本的unix程序。现代kernel比xv6提供更多system call和更多种类的kernel service。例如它们支持网络、窗口、用户级线程、许多设备驱动等等。现代kernel持续快速地进化中，并基于POSIX提供一些特性。
unix统一访问多种资源（文件、目录、device），用一组 file-name和file-descriptor接口。这个想法可以被拓展到更多类型的资源。一个好的例子如plan9，把资源即是文件的理念引用到网络、图形等等。然而，更多unix派生操作系统没有延续这个路线。
文件系统和文件描述符已经是很有力的抽象。即使是这样，也有其他操作系统接口模型。Multics（一个unix的先驱）抽象文件存储用一个类似内存的方式，产生了一种不同风格的接口。Multics复杂的设计对unix设计者（尝试构建地更简单）产生了直接的影响。
xv6没有提供一个用户概念，或者保护一个用户免受其他用户影响；用unix术语，所有xv6进程都是作为root的进程。
这本书核实了xv6如何实现它的类unix接口，但这些点子和理念不仅应用于unix。任一操作系统都让多个进程运行于潜在的硬件上，进程之间隔离，提供内部进程通信的控制机制。学完xv6后，你应该能够看其他更复杂的操作系统，并且会看到潜在于xv6中的理念也存于那些系统。

（六）练习

写一个程序，使用unix system calls在两个进程间”ping-pong“一个字节，使用一对pipe，一个pipe对应一个方向，另外一个pipe对应另外一个方向。
衡量程序的性能，看每秒交换多少次。

二、操作系统组织结构

介绍

操作系统一个关键的要求是支持同时刻多活动。例如：使用第一章描述的system call接口，一个进程可以通过fork开启新的进程。操作系统必须对计算机资源进行分时管理（在各个进程间）。例如：即使进程数量比cpu数量多，操作系统也可以保证所有进程都有机会执行。操作系统也必须保证进程间的隔离。如果一个进程有一个bug或者故障，它不应该影响那些不依赖它的进程。完全隔离是相当强大的，因为它可以让进程有意的相互作用。pipelines是一个例子。因此一个操作系统必须满足3点要求：多路复用、隔离、交互。
本章提供了一个操作系统如何组织实现这3点要求的概览。有很多方式实现，但本文聚焦于围绕monolithic kernel的主流设计，这被unix系统采用。这个章节也提供了xv6进程（这是xv6中的隔离单元）和xv6启动时第一个进程创建的概览。
xv6运行在多核risc-v微处理单元，它的许多低级功能（例如进程实现）是risc-v。risc-v是一个64位cpu，并且xv6用”LP64”（ L：long类型，P：pointer类型在c语言中是64位，int是32位）C写的。这本书假设读者已经完成了一些机器级别的编程（多种架构），将介绍risc-v的一些idea。一个有用的risc-v参考是“the risc-v reader：an open
architecture atlas”。用户级别ISA（instruction sets architecture）和privileged architecture是官方的声明。
完整电脑中的cpu被支持的硬件包围，它们中的大多数是IO接口。xv6基于qemu仿真的硬件写成。包括RAM，ROM（包含引导启动代码），一系列对用户键盘、屏幕的连接，硬盘存储。

（一）抽象物理资源

当遇到一个操作系统时，第一个可能问的问题是：为什么要有它？利用library实现system calls（程序可链接link）。
用这种方式，每个应用甚至可以裁剪成它需要的库。应用可以直接和硬件资源交互，并用最适合应用的方式使用资源（实现高可用）。一些嵌入式设备的操作系统或者实时操作系统用这种组织方式。
库方案的缺点是：如果不止一个应用在运行，这些应用必须是表现良好的。例如，每个应用必须间歇性地放弃cpu，以致于其它应用可以运行。这种协作-分时方式可能不错，如果所有应用互相信任且无bug。对于应用来说更典型的情况是不信任其他进程，且有bug，因此一个进程通常想要更强的隔离比起协作方案。
实现强隔离，对禁止应用直接访问硬件敏感资源改为抽象资源为服务 有帮助。例如，unix应用与内存交互仅通过文件系统的open、read、write、close system call，而不是直接读写硬盘。system call给应用提供了方便的路径名，并允许操作系统管理硬盘。即使不关心隔离，那些有意交互的程序也会发现，文件系统是一个比直接访问硬盘更方便的抽象。
相似地，unix透明地在进程间切换硬件cpu，根据需要保存、恢复寄存器状态，因此应用无需知道分时。这个透明性允许操作系统分享cpu，即使一些应用是无限循环。
另外一个例子，unix进程使用exec来构建他们的内存镜像，而不是直接与物理内存交互。这允许操作系统决定一个进程该在内存中的哪个位置。如果内存紧张，操作系统甚至可能将进程的一些数据存储到硬盘上。exec也给用户提供了一些文件系统的便利来存储可执行程序的镜像。
许多形式的unix进程间交互通过文件描述符发生。文件描述符不仅与细节（数据可能在pipe或文件中存储）抽离，而且简化了交互。例如：如果pipeline的一个应用挂了，kernel生成文件结束信号给pipeline中的下一个进程。
system call接口小心地设计，提供程序便利和强隔离可能。unix interface并非仅有的抽象资源方式，但它被证实是一个好的抽象。

（二）user mode、supervisor mode、system calls

强隔离需要一个坚固的边界（在程序和操作系统之间）。如果程序出错，我们不想让操作系统失败，或其他应用失败。操作系统应该能够清理失败应用，并继续运行其他应用。为了实现强隔离，操作系统必须这么安排：应用不能更改（甚至读）操作系统的数据结构和指令，应用不能访问其他进程的内存。
cpu为强隔离提供硬件支持。例如：risc-v有3种cpu执行指令的模式：machine mode、supervisor mode、user mode。在machine mode下执行的指令有全部权限。cpu从machine mode开始启动。machine mode绝大多数用于配置一台电脑。xv6在machine mode下执行几行代码，然后切换到supervisor mode。
在supervisor mode中，cpu被允许执行权限指令：例如，启用、禁用中断，读写寄存器（保存页表地址）等等。
如果一个应用在user mode下尝试执行权限指令，cpu不会执行这个指令，而是切换到supervisor mode下终止应用，因为这个应用做了它不该做的事。图1.1阐述了这个组织。一个应用仅可以执行user-mode指令，在用户空间运行；而在supervisor mode下运行的软件也可以执行权限指令，在kernel空间运行。在kernel space（或in supervisor mode）中运行的软件称作kernel。
一个想调用kernel函数（read system call）的应用必须transition到kernel。cpus提供一个特殊的指令，将cpu从user mode切换到supervisor mode，从kernel声明的入口点处进入kernel（risc-v提供ecall指令达到这个目的）。一旦cpu切换到supervisor mode，kernel会校验system call参数，决定应用是否被允许执行请求操作，然后拒绝它或者执行它。kernel控制过渡到supervisor mode的入口是很重要的事；如果一个应用可以决定kernel入口，一个恶意程序可以进入到kernel中逃脱参数校验的点。

（三）kernel组织

设计问题的关键是：操作系统的哪部分应该运行在supervisor mode下。一种可能是整个操作系统搁置在kernel中，因此所有system calls的实现运行在supervisor mode下。这个组织叫做monolithic kernel。
在这种组织中，整个操作系统运行有所有的硬件权利。这个组织是便利的，因为os设计者无需决定操作系统的哪部分不需要全部硬件权利。另外，操作系统各部分之间协作更容易。例如：一个操作系统可能有一个buffer cache，它可以被file system和virtual memory system共享。
monolithic组织的一个缺点是：操作系统不同部分间的接口通常是复杂的（我们将在之后文中看到），因此操作系统开发人员很容易犯错。在monolithic kernel中，一个错误是致命的，因为一个supervisor mode下的错误通常将导致kernel挂掉。如果kernel挂掉了，计算机停止工作，因此所有应用也挂掉。计算机必须重启。
为了减少kernel错误风险，os设计者会最小化操作系统代码（运行在supervisor mode下）的体积，并在用户mode下执行操作系统块。这个kernel组织称作microkernel。
图2.1阐述了微内核设计。在这个图中，文件系统作为一个用户级别的进程运行。os服务作为进程运行称作servers。为了允许应用和file server交互，kernel提供一个内部进程交互机制来让用户进程之间发送消息。例如：如果一个像shell这样的应用想读写文件，它向file server发消息并等待响应。
在微内核中，kernel接口包含一些低级别函数来启动应用，发消息，访问硬件设备等等。这种组织允许内核尽量简单，将操作系统大多数搁置在用户级别servers
xv6作为一个monolithic kernel实现，像绝大多数unix os。因此xv6 kernel接口（对应于os接口），并且kernel实现了完整的os。因为xv6不提供一些服务，它的内核比一些微内核小，但xv6的理念是monolithic。

（四）代码：xv6组织

xv6 kernel源码在kernel子目录中。资源被分成多个文件，跟随了模块化理念。图2.2列出了这些文件。内部模块接口定义在defs.h（kernel/defs）中。

（五）进程概览

xv6中的隔离单元是进程（正如其他unix中一样）。进程抽象阻止一个进程破坏、侦测另外一个进程的内存、cpu、文件描述符等等。也阻止一个进程破坏kernel本身，因此一个进程不能推翻kernel隔离机制。kernel必须小心实现进程抽象，因为一个有bug或恶意的应用可能会欺骗kernel或硬件做一些错误的事情（环境隔离）。kernel实现进程的机制包括user/supervisor模式标志位、地址空间、线程时间分片。
为了帮助强制隔离，进程抽象为程序提供了阐述（进程有自己私有的机器）。进程为程序提供一个私有内存系统或者地址空间（看起来是），其他进程不能读写。进程也给程序提供它自己的cpu（看起来是）来执行程序的指令。
xv6使用页表（硬件实现）来给每个进程分配自己的地址空间。risc-v页表翻译一个虚拟地址（risc-v指令操作的地址）到物理地址（cpu分配给主存的地址）。

xv6为每个进程保留一个独立的页表（定义了进程的地址空间）。正如图2.3阐述的那样，一个地址空间包括进程的用户内存（起始于虚拟内存地址0）。首先是指令，紧跟全局变量，然后栈，最后是一个堆（进程可以根据需要拓展）。一些因素限制进程地址空间的最大尺寸：risc-v上面的指针是64位的；在页表中查找虚拟地址时，硬件仅使用低39位；xv6仅使用39位中的38位。因此最大地址是238-1=0x3fffffffff，这是最大虚拟地址（MAXVA max virtual address， kernel/riscv.h:348）。在xv6地址空间顶部保留一个page用作trampoline和一个page匹配进程的trapframe来切换到kernel，正如我们将在第四章解释的那样。
xv6 kernel给每个进程保留了许多个state，这些state集合在一起组成一个结构体struct_proc（kernel/proc.h）。
一个进程最重要的kernel state是page table，kernel stack，它的运行状态。我们将使用p->xxx来引用proc结构中的元素；例如p->pagetable是一个指向进程页表的指针。
每个进程有一个执行线程，执行进程指令。一个线程可能会被挂起，然后再唤醒。在两个进程之间透明地切换，kernel挂起当前运行线程，并且唤醒另外一个进程的线程。thread的多个state（本地变量、函数调用返回地址）被存储在线程栈中。每个进程有两个栈：一个用户栈，一个kernel栈。当进程正在执行用户指令，仅它的用户栈在使用，它的内核栈是空的。当进程进入kernel（system call或interrupt），kernel代码在进程kernel stack；当进程在kernel中时，它的用户栈仍然保留存储的数据，但不会被使用。进程的线程可选择的在使用用户栈和kernel栈之间切换。kernel stack是单独的（保护用户code），因此kernel仍然可以执行，即使进程已经毁坏了它的用户stack。
一个进程可以做一个system call通过执行risc-v的ecall指令。这个指令提升硬件权利，改变程序计数器到一个kernel定义的入口。代码在入口处切换到kernel stack，并执行system call实现的kernel指令。当system call完成后，kernel切换回用户栈，通过调用sret指令返回到用户空间，这个指令拉低了硬件权利级别，并在system call指令之后恢复执行用户指令。一个进程的线程会block在kernel来等待io，并在io结束时恢复。
p->state表明进程是被分配了，准备好去执行，正在执行，等待io，退出状态。
p->pagetable保留了进程的页表，用一种risc-v硬件期望的格式。xv6引发paging硬件来使用一个进程的p->pagetable，当执行进程在用户空间中时。一个进程的页表也作为一个地址（存储进程内存的物理页）记录。

（六）代码：启动xv6和第一个进程

为了让xv6更具体，我们将概述kernel启动，启动第一个进程。之后的章节将描述这个机制，展示更多的细节。
当risc-v计算机上电时，它自身初始化，并运行一个引导加载器（存储在rom中）。引导加载器装载xv6kernel到内存。然后在machine mode下，cpu从_entry处（kernel/entry.s:6）执行xv6。risc-v启动时paging硬件是禁用的：虚拟地址直接映射到物理地址。
加载器将xv6 kernel加载到内存（物理地址：0x80000000）。不从0x0开始是因为0~0x80000000之间包含IO设备。
_entry处的指令设置一个stack以便执行C代码。Xv6为初始化栈stack0声明空间，在start.c(kernel/start.c:11)。
_entry处的代码加载地址stack0+4096（栈顶）到栈指针寄存器sp，因为risc-v的栈向下增长。现在kernel有一个栈，_entry在start(kernel/start.c:21)处调用C。
函数start运行一些配置（仅允许在机器模式下），然后切换到supervisor mode。为了进入supervisor mode，risc-v提供指令mret。这个指令绝大多数被用作从supervisor mode上个调用到机器模式。start没有从这个调用返回，而是设置things up就像已经有一个：它通过mstatus设置之前的权利模式到supervisor；它通过写main的地址到寄存器mepc来给main设置返回地址；通过设置页表寄存器satp为0，可以在supervisor mode下禁用虚拟地址翻译。委派所有中断和异常到supervisor mode。
在进入supervisor mode之间，start运行另外的任务：执行时钟片来生成计时中断。通过这种方式，start通过调用mret进入supervisor mode。这导致程序计数器改变到main(kernel/main.c:11)。
main(kernel/main.c)初始化设备和子系统后，通过调用userinit(kernel/proc:212)创建第一个进程。第一个进程执行一个汇编（risc-v）小程序，initcode.s(user/initcode.s:1)（通过调用exec system call重入kernel）。正如第一章看到的，exec用新程序替换当前进程的内存和寄存器。一旦内核完成exec，它返回到用户空间。init(user/init.c:15)创建一个新控制台设备文件（如果需要），然后作为文件描述符0、1、2打开它。然后在console启动一个shell，系统启动。

（七）现实世界

在现实世界，既有monolithic kernel和microkernel。一些unix kernel是monolithic。例如：linux有monolithic kernel，尽管一些os功能作为用户级别服务运行（例如windowing system）。kernel例如L4、Minix、QNX是microkernel（附带一些server），并且已经广泛部署在嵌入式中。
大多数操作系统已经采用了进程理念，并且大多数进程和xv6类似。现代操作系统支持一个进程中多个线程，让一个进程利用多个cpu。进程支持多线程的机器（xv6不支持）有很多，包含潜在的接口改变（例如：linux的clone、fork变形），来控制进程（多线程共享）的各方面。

（八）练习

你可以使用gdb来观测首个kernel到user的过渡。运行make qemu-gdb。在另外的窗口中，相同目录下，运行gdb-multiarch。输入gdb指令break *0x3ffffff10e，在kernel sret指令（跳转到user space）处设置断点。输入continue命令。gdb应该在断点处停止，将会执行sret。输入stepi，gdb应该表明正在0x0处（在user space，initcode.S的起始处）执行。

三、page tables

介绍

页表是一种机制（操作系统通过这种机制为每个进程提供自己的私有地址空间和内存）。页表决定了内存地址的含义，物理内存的哪部分可以被访问。页表允许xv6隔离不同进程的地址空间、复用页表到单个物理内存。页表也提供一种迂回（允许xv6做几种把戏）：映射同一内存到几个地址空间，用无映射绑定的页来保护内核、用户栈。
其余章节解释页表（risc-v硬件提供）、xv6如何使用他们。

（一）分页硬件

作为提醒，risc-v指令（用户、内核）操作虚拟地址。机器的RAM或者物理内存被物理地址索引。Risc-v页表硬件将这两种地址关联，通过将一个虚拟地址映射到物理地址。
xv6运行在Sv39 RISC-V，意味着64位虚拟地址中仅低39位被使用。高25位没被使用。在这种Sv39配置中，一个Risc-V页表逻辑上来说是一个数组（有227个page table entries-PTE）。每个PTE包含一个44位物理页号（physical Page Number-PPN）和一些标志位。分页硬件通过使用39位中的高27位翻译一个虚拟地址，来定位到页表进而找到一个PTE，一个56位物理地址（其高44位来自PTE中的PPN，低12位从原始虚拟地址拷贝）。图3.1用一个逻辑页表（作为一个简单的PTE数组）视图展示了这个进程。一个页表给操作系统控制，通过虚拟地址到物理地址翻译，在一个4096字节（对齐的块）的粒度。这个块称为页。
在Sv39 Risc-V，虚拟地址高25位没有用作翻译；未来Risc-v可能使用这些位来定义更多级别的翻译。物理地址也有增长空间：在PTE格式中的PPN也有另外10位可以增长。

如图3.2所示，真正的翻译发生在3步。一个页表作为一个三级树被存在物理内存中。树的根节点是一个4096字节的页表页（存放页表信息的页，包含512个PTEs），包含树下一级别页表页的物理地址。那些页表中的每一个包含512个PTE用作树的最后一级。分页硬件使用27位中的高9位来选择一个根页表页PTE，中9位选择下一级别页表页中的PTE，低9位选择最后的PTE。
如果三个PTE中的任意一个需要被翻译成一个不存在的地址，分页硬件提出一个页错误异常，扔到kernel来解决这个异常。通常情况下（大范围虚拟地址无映射），这种三级结构允许一个页表省略整个页表页
每个PTE包含标志位（告知分页硬件相关虚拟地址被允许如何使用）。PTE_V表明此PTE是否存在：如果不设置，指向此页导致一个异常（例如：不被允许）。PTE_R控制指令是否允许读此页。PTE_W控制指令是否允许写此页。PTE_X控制CPU是否解释此页内容作为指令并执行他们。PTE_U控制用户模式下指令允许访问此页；若PTE_U没设置，此PTE仅能在supervisor mode下使用。图3.2展示它如何工作。标志位和所有其他硬件相关结构页被定义在（kernel/riscv.h）。
为了告知硬件使用页表，kernel必须把根页表页的物理地址写到satp（Supervisor Address Translation and Protection）寄存器。每个CPU有自己的satp寄存器。一个cpu将使用satp指向的页表翻译所有地址（由一系列指令生成）。每个cpu有自己的satp以至于不同cpu可以运行不同的进程，每个进程有自己的私有地址空间（自己页表描述）。
一些相关点。物理内存指的是DRAM中的存储单元。一个字节的物理内存有一个地址，称为物理地址。指令仅使用虚拟地址，页硬件翻译成物理地址，发送到DRAM去读写存储。不像物理内存和虚拟地址，虚拟内存不是一个物理对象，而是指内核提供管理物理内存和虚拟地址的机制、抽象的集合。

（二）kernel地址空间

xv6位每个进程保留一个页表，描述每个进程的用户地址空间，加一个单独的页表来描述kernel地址空间。kernel配置地址空间的布局来让它可以访问物理内存和多种硬件资源用可预测的虚拟地址。图3.3展示这个布局如何映射kernel虚拟地址到物理地址。文件(kernel/memlayout.h)定义了xv6 kernel内存布局的常量。
qemu模拟一个计算机（包含RAM-物理内存，起始于物理地址0x80000000，至少到0x86400000，xv6称之为PHYSTOP）。qemu仿真也包含I/O设备例如硬盘接口。qemu将设备接口作为一个内存映射控制寄存器（位于物理地址空间0x80000000之下）向软件暴露。kernel可以通过读写这些特殊物理地址与设备交互；这些读写交互是和硬件设备而不是RAM。第四章解释xv6如何与设备交互。

kernel在RAM和内存映射设备寄存器处使用直接映射。意味着，映射资源虚拟地址等同于物理地址。例如kernel本身位于KERNBASE=0x80000000在虚拟地址空间和物理内存中。例如，当fork分配用户内存给子进程，分配器返回内存物理地址。fork直接使用这个地址作为一个虚拟地址，当fork拷贝父级用户内存到子级。
一些没有直接映射的kernel虚拟地址：
trampoline page。位于虚拟地址空间的顶部；用户页表有相同的映射。第四章讨论trampoline page的角色，我们在此处仅看作一个有趣的页表使用例子。一个物理页（保存trampoline code）在kernel虚拟地址空间中被映射两次：一次在虚拟地址空间顶部；一次是直接映射。
kernel stack page。每个进程有自己的kernel stack，它被映射在高位，以至于在它下面xv6可以留下一个无映射的guard page。guard page的PTE是无效的（例如PTE_V没设置），以致于如果kernel stack溢出，将可能引发一个异常，并且kernel将panic。没有guard page的栈溢出将覆盖掉其他kernel内存，导致错误操作。一个panic崩溃是更好的。
当kernel通过高内存映射使用它的栈时，kernel也可以通过直接映射地址访问。一个可选择的设计可能是只有直接映射，使用直接映射地址访问栈。在这种安排下，提供guard pages将取消映射虚拟地址，否则这些虚拟地址将指向物理地址，这样就很难使用。
kernel映射trampoline和kernel text中的pages带有PTE_R和PTE_X。kernel读取、执行这些页中的指令。kernel映射其他页带有PTE_R和PTE_W，以至于它可以读写那些页中的内存。guard pages的映射是无效的。

（三）创建一个地址空间

绝大多数操作地址空间和页表的代码放在vm.c（kernel/vm.c）。核心数据结构是pagetable_t，这是一个指向risc-v根页表页的指针；一个pagetable_t要么是kernel page table，要么是一个进程page table。核心函数是walk，找出虚拟地址的PTE；mappages，安置PTE到新的映射。以kvm开头的函数操控kernel page table；以uvm开头的函数操控user page table；其他函数是公用的。copyout和copyin 拷贝数据到/从用户虚拟地址（作为system call参数提供）；它们在vm.c，因为它们需要明确地翻译这些地址，为了找到对应物理内存。
早先在boot序列中，main调用kvminit（kernel/vm.c:22）来创建kernel page table。这个调用发生在xv6启用Risc-V paging之前，所以地址直接指向物理地址。Kvminit首先分配一页物理内存来保存根页表页（page-table page）。然后它调用kvmmap来安置翻译（kernel需要）。翻译包含kernel指令和数据、物理内存（到PHYSTOP）、以及表示真实设备的内存。
kvmmap（kernel/vm.c:118）调用mappages（kernel/vm.c:149），它把映射放到页表中（一批虚拟地址对应一批物理地址）。mappages函数每次只建立一个绑定关系，绑定粒度为页。对每个要映射的虚拟地址，mappages调用walk去找到该虚拟地址对应的PTE。然后初始化PTE来保存相关物理页号（physical page number）、所需权限（PTE_W，PTE_X、PTE_R）、PTE_V（标志PTE是有效的，kernel/vm.c:161）。
walk（kernel/vm.c）模仿risc-v分页硬件，正如为一个虚拟地址找PTE（见图3.2）。walk下降3级页表（每次9位）。每级别9位虚拟地址来找到一个PTE（要么是下一级页表、要么是最终页，kernel/vm.c:78）。如果PTE不是有效的，那么需要的page尚未被分配；如果alloc参数设置了，walk分配一个新页表页，并把它的物理地址放到PTE。它返回树最低层PTE的地址（kernel/vm.c:88）。
以上代码基于物理地址直接映射到kernel虚拟地址空间。例如，walk依赖多级页表，它从PTE拿到下一级别page table的物理地址（kernel/vm:80），然后使用这个地址作为一个虚拟地址去获取下一级PTE（kernel/vm:78）。
main调用kvminithart(kernel/vm.c:53)来安置kernel page table。它将根页表页的物理地址写入satp。在此之后，cpu将使用kernel page table翻译地址。因为kernel使用一个明确的映射，下个指令的虚拟地址将能映射到正确的物理地址。
procinit(kernel/proc.c:26)，由main调用，为每个进程分配一个kernel stack。将每个stack放到KSTACK生成的地址处，并为invalid stack-guard page留下空间。kvmmap添加PTE映射到kernel page table。kvminithart重新加载kernel page table到satp，以致于硬件知道新的PTE。
每个RISC-V CPU缓存page table entries到Translation Look-aside Buffer(TLB)，当xv6修改一个page table，它必须告诉CPU去无效化对应缓存的TLB entries。如果不这么做，在某些时候，TLB可能会使用一个旧的缓存映射，指向一个物理页（此时这个物理页已经被分配到另一个进程），结果一个进程就会乱写其他进程的内存。RISC-V有一个指令sfence.vma，可以flush当前CPU TLB的缓存。在kvminithart中重新加载satp寄存器后、trampoline代码中（在返回到用户空间之前（kernel/trampoline.S:79）），xv6执行sfence.vma。

（四）物理内存分配

在运行时kernel必须为page tables、user memory、kernel stacks、pipe buffer分配和释放物理内存。
xv6使用“kernel末尾”到PHYSTOP作为运行时分配。它每次分配和释放4096个字节。通过一个链表跟踪哪个页是空闲的。分配：从链表中删除一个page；释放：在链表中添加一个page。

（五）物理内存分配器

分配器在kalloc.c（kernel/kalloc.c:1）。分配器的数据结构是一个物理内存页（可以用于分配）的空闲list。每个空闲page list的元素是一个结构体run（kernel/kalloc.c:17）。分配器从哪获取内存来保存数据结构？存储空闲页的run结构在空闲页本身中，因为没有其他地方存储它。空闲list由一个spin lock（kernel/kalloc:21-24）保护。list和lock被包裹在一个结构体中，使得锁保护结构体中成员变得清晰。现在忽略lock和acquire、release调用。第六章将详细检验锁。
main函数调用kinit来初始化分配器（kernel/kalloc.c:27）。kinit初始化空闲list来保存kernel末尾到PHYSTOP之间的每个page。xv6应该决定多少物理页可用（通过转换硬件提供的配置信息）。xv6假设机器有238MB RAM。kinit调用freerange来向free list添加内存，通过每页调用kfree。一个PTE仅仅可以指一个物理地址（对齐到4096字节边界，4096的倍数），因此freerange使用PGROUNDUP来保证它只会释放对齐的物理地址。分配器始于无内存，这些对kfree的调用让它有一些内存可用管理。
分配器有时将地址视为一个整数（为了对它们执行算数运算，如遍历freerange中所有page），有时将地址视作一个指针来读写内存（操作存储在每个page中的run数据结构）。地址的双重使用是分配器代码都是C类型转换的主要原因。另外一个原因，释放、分配固有地改变了内存类型。
kfree函数（kernel/kalloc.c:47）起始于设置内存中被释放的每个字节值为1。这将导致使用内存（释放后）的代码，会读取垃圾而不是旧的有效内容。希望更快地破坏这些代码。kfree预置页到空闲list：它转换pa为一个struct run指针，记录之前free list的起始位置到r->next，设置free list等于r。kalloc移除并且返回freelist的第一个元素。

（六）进程地址空间

每个进程有一个单独的页表，当xv6在进程之间切换时，它也需要改变页表。正如图2.3所示，一个进程的用户空间起始于虚拟地址0，并且能增长到MAXVA（kernel/risc.h:348），允许一个进程规则上定位256GB内存。
当一个进程向xv6索取更多用户内存时，xv6首先使用kalloc去分配一个物理页。然后添加PTE到进程的页表（指向新的物理页）。xv6在这些PTE中设置PTE_W、PTE_X、PTE_R、PTE_U、PTE_V标志位。绝大多数进程不会使用整个用户地址空间；xv6使用PTE_V来清除不使用的PTE。
我们看一些使用页表的好例子。首先，不同进程的页表，翻译用户地址到不同页表的物理内存，因此每个进程有私有的用户内存。第二，每个进程看待内存都是从0开始的连续虚拟地址，然而进程的物理地址可以是非连续的。第三，kernel在用户地址空间顶部，将一个page与trampoline代码映射，因此一个单独的物理内存页出现在所有地址空间。
图3.4展示了xv6一个正在执行进程的用户内存布局的更多细节。stack是一个单独的page，并且显示了由exec创建的初始化内容。字符串包含命令行参数，以及一组指向它们的指针，在栈顶。在那之后是一些值（允许一个程序从main开始，就像main函数已经被调用）。

为了检测一个用户栈溢出了已分配的栈内存，xv6在stack下面设置一个无效的保护页。如果用户栈溢出，并且进程尝试去使用一个栈下面的地址，硬件将生成一个page-fault异常，因为映射是无效的。一个实际操作系统中，用户栈溢出时，可能会自动分配更多内存。

（七）sbrk

Sbrk是一个system call，进程用来缩小或增长它的内存。这个system call由函数growproc（kernel/proc.c:239）实现。growproc调用uvmalloc或uvmdealloc，取决于n是正数还是负数。uvmalloc（kernel/vm.c:229）用kalloc分配物理内存，并且用mappages添加PTE到用户页表。uvmdealloc调用uvmunmap（kernel/vm.c:174），使用walk来找到PTE，并用kfree来释放它们指代的物理内存。
xv6使用一个进程的页表，不只是告诉硬件如何映射用户虚拟地址，也记录了哪些物理页分配给了该进程。这就是释放用户空间（uvmunmap）需要检测用户页表的原因。

（八）exec

exec是一个system call，创建用户地址空间。它用一个存储在文件系统中的文件，来创建一个用户地址空间。exec（kernel/exec.c:13）使用namei（kernel/exec.c:26，第8章解释）打开命名的二进制路径。然后，它读ELF header。xv6应用被描述为广泛使用的ELF格式，定义在（kernel/elf.h）。一个ELF二进制包含一个ELF header，struct elfhdr（kernel/elf.h:6），跟着一系列程序section header，struct proghdr（kernel/elf.h:25）。每个proghdr描述一段必须加载到内存中的应用；xv6程序仅有一个程序section header，但其他系统可能有单独的指令、数据sections。
第一步是快速查验：文件可能包含一个ELF二进制。一个ELF二进制起始于四个字节魔力数字：0x7F、’E’、’L’、’F’或ELF_MAGIC（kernel/elf.h）。如果ELFheader有正确的magic数字，exec假定这个二进制是格式正确的。
Exec通过proc_pagetable（kernel/exec.c:38）分配一个无用户映射的新页表，通过uvmalloc（kernel/exec.c:52）为每个ELF段分配内存，通过loadseg（kernel/exec.c:10）加载每个segment到内存。loadseg使用walkaddr来找到分配内存的物理地址（每个ELF段的页写到了此内存），readi从file中读。
init（exec创建的第一个用户程序）的程序section header看起来如下：

程序section header的filesz可能小于memsz，表明它们之间的间隔应该被填充上0（用于C全局变量）而不是从文件中读取。init的filesz是2112字节，memsz是2136字节，因此uvmalloc分配足够的物理内存来保存2136字节，但只从init文件中读取2112字节。
现在exec分配、初始化用户栈。它分配一个stack page。exec复制参数字符串到栈顶，记录指向它们的字符串指针到ustack。设置一个空指针在（传到main的argv list）末尾。ustack的前三个entry是假的return PC、argc、argv指针。
exec设置一个不可访问的page，放在stack page下面，因此那些尝试使用不止1页的程序将失败。这个不可访问的page允许exec去处理那些非常大的参数。在那种情况下，copyout（kernel/vm.c:355）函数（exec用来拷贝参数到stack）将通知目标page不可访问，并且返回-1。
在新内存镜像的准备期间，如果exec检测到一个error（像一个无效program segment），它跳到label bad，释放新镜像，并且返回-1。exec必须等待，直到确保system call调用成功，才能释放老镜像。如果老镜像消失，那么system call不会是返回-1。exec仅有的错误例子发生在镜像创建期间。一旦镜像完成，exec可以提交到新page table（kernel/exec.c:113），并且释放旧的（kernel/exec.c:117）。
exec加载elf文件字节到内存，放到elf明确的地址处。用户或者进程可以放置任何他们想要的地址到elf文件。
因此exec是危险的、意外的、有意的。因为elf文件中的地址可能指向kernel。粗心kernel的结果可能会从崩溃到蓄意地破坏内核隔离机制（例如安全利用）。xv6做一些检查来避免这些风险。例如
if(ph.vaddr + ph.memsz < ph.vaddr)检测是否sum溢出了64位整数。一个用户可以构造一个elf二进制文件（带有一个ph.vaddr，指向一个用户选择地址），ph.memsz足够大，sum溢出到0x1000，看起来是有效的。在旧版xv6中，用户地址空间页包含kernel（但在用户模式下不可读写），用户可以选择一个对应内核内存的地址，因此从elf二进制到kernel copy data。在risc-v版本的xv6中，这不会发生，因为kernel有自己的独立page table；loadseg加载到进程的page table，不在kernel的page table。
kernel开发人员很容易忽略一个至关重要的检查，实际的kernel很长一段时间缺失检查，这个缺失可以被用户程序利用来获取kernel权利。一个恶意的用户程序可能利用此来绕过xv6的隔离。

（九）现实世界

像绝大多数操作系统，xv6使用分页硬件做内存保护和映射。大多数操作系统比xv6更复杂地利用分页，通过结合分页和page-fault exception，我们将在第四章讨论。
xv6通过kernel的虚拟、物理内存直接映射使用，通过假设物理RAM在地址0x8000000（kernel期望被加载到的位置）进行简化。这对QEMU是起作用的，但在现实的硬件上，这是一个坏主意。真实硬件放置RAM和设备在不可预测的物理位置，因此RAM可能不在0x8000000（xv6期望能够存储kernel的地方）。更多严格的kernel设计利用页表把任意硬件物理地址布局，编程可预测的kernel虚拟地址布局。
risc-v支持物理地址级别的保护，但xv6不使用这个特性。
在有大量内存的机器上，使用risc-v的 super pages可能更好一些。当物理内存小时，小pages合适，允许分配和硬盘调出页采用合适粒度。例如，如果一个程序仅仅使用8KB内存，给它一个4MB的物理页是浪费的。更大的页适合有大量RAM的机器，可以减少页表管理的经费。
xv6 kernel缺少malloc类似的分配器（为小对象提供内存，阻止kernel使用复杂数据结构（那些需要动态分配的））。内存分配是一个长久的热点话题，基本问题是高效利用有限内存、为未来未知请求做准备。比起空间效率，现在人们更关心速度效率。另外，一个更复杂的kernel可以分配不同尺寸的小块，不只是4096字节块；一个真正的kernel分配器需要解决小的和大的分配。

四、traps和system calls

介绍

3种事件导致CPU搁置原始的指令执行，强制转移到处理事件的特殊代码。一种场景是system call，用户程序执行ecall指令告知kernel做些什么。另外的场景是一个异常：一个指令（user 或 kernel）做了某些非法的事，例如除以0或使用一个无效的虚拟地址。第三个场景是一个设备中断，需要关心的设备信号，例如硬盘结束读写请求。
本书对这些情景使用trap作为一个通用术语。典型地，在trap发生时无论什么代码正在执行，待会都要恢复，而且也不需要知道任何发生过的特殊事情。我们通常想让traps是透明的，这对中断来说特别重要，中断代码通常不希望如此。通常顺序是trap强制控制转移到kernel；kernel保存寄存器和其他state，为了执行可被恢复；kernel执行对应的handler代码（例如，一个system call实现或设备驱动）；kernel恢复存储的state，并从trap返回；原先代码从离开的地方恢复。
xv6 kernel处理所有traps。对system call来说这是很自然的。对中断来说是可以理解的，因为隔离需要用户进程不直接使用设备，并且因为只有kernel有device handling需要的state。对异常来说也是可以理解的，因为xv6对所有来自用户空间的异常，通过杀掉违法程序作出响应。
xv6 trap handling过程有四个阶段：risc-v cpu采取硬件动作，一个汇编vector（为kernel C code铺路），c trap handler决定对trap、system call或者设备驱动服务程序做什么。虽然三种trap类型的共性表明，kernel可用一个单独代码路径处理所有traps，但结果发现，对于三种不同情况使用单独汇编vector和c trap handler是便利的：用户空间traps、内核空间traps、定时器中断。

（一）risc-v陷阱机制

每个risc-v cpu有一组控制寄存器（kernel对这些寄存器赋值）来告知cpu如何处理陷阱，kernel也可以读取来找出已经发生的陷阱。risc-v文档包含完整信息。riscv.h（kernel/riscv.h）包含xv6使用的定义。这是大多数重要寄存器的概览：
stvec：kernel把trap handler地址写到这；risc-v跳到这来处理一个trap。
sepc：当一个trap发生时，risc-v在这保存程序计数器（因为pc会被stvec重写）。sret指令复制sepc到pc。kernel可以写sepc来控制sret跳转到哪。
scause：risc-v在这放一个数来描述trap原因。
sscratch：kernel在这放置一个值，在trap handler一开始就会派上用场
sstatus：sstatus中的SIE位控制中断是否可用。如果kernel清除SIE，risc-v将推迟设备中断直到kernel设置SIE。SPP位表明一个trap来自user模式或者supervisor模式，并控制sret返回到哪种模式。
以上traps相关寄存器在supervisor模式中处理，他们不能在user模式读写。一组等价的traps 控制寄存器在机器模式下处理；xv6仅会在定时器中断的特殊情景下使用。
多核芯片的每个cpu有它自己的这些寄存器集，任意时刻，可能不止一个cpu在处理一个trap。
当发生一个trap，risc-v硬件对所有trap类型（除了timer中断外）做下面步骤：
1， 若trap是一个设备中断，sstatus SIE位被清除，不会做下面任意步骤
2， 通过清除SIE禁用中断
3， 复制pc到sepc
4， 保存当前模式（user 或者supervisor）在sstatus中的SPP位中
5， 设置scause反映trap的原因
6， 设置模式为supervisor
7， 复制stvec到pc
8， 开始从新pc执行
注意cpu不会切换到kernel page table，不会切换到kernel stack，不会保存任何寄存器（除了pc）。kernel软件必须执行这些任务。cpu最小化trap期间工作的原因是为软件提供便携性。例如，一些操作系统在一些场景中不需要页表切换，这可以提升性能。
你可能觉得奇怪是否cpu硬件的trap handling顺序可以更简单。例如，假设cpu不会切换程序计数器。trap可以切换到supervisor mode，却仍执行用户指令。那些用户指令会打破user/kernel隔离，例如更改satp寄存器来指向一个物理页（允许访问所有物理内存）。因此非常重要：cpu切换到一个kernel特定指令地址（也就是stvec）。

（二）用户空间traps

在用户空间执行时，用户程序做system call（ecall指令）、非法操作或设备中断，trap可能发生。用户空间trap的高级路径是uservec（kernel/trampoline.S:16），然后是usertrap（kernel/trap.c:37）；当返回时，usertrapret（kernel/trap.c:90），然后userret(kernel/trampoline.S:16)。
用户代码traps比kernel的更具挑战，因为satp指向一个用户页表（不匹配kernel），并且stack指针可能包含一个无效、甚至恶意的值。
因为risc-v硬件不会在trap期间切换页表，user page table必须包含一个uservec的映射（stvec指向的 trap vector指令）。uservec必须切换satp来指向kernel page table；为了切换后可以继续执行指令，uservec必须被映射到kernel page table中用户页表同一地址。
xv6通过trampoline page（包含uservec）满足这些限制。xv6映射trampoline page在每个用户页表和内核页表相同虚拟地址上。虚拟地址是TRAMPOLINE（正如我们在图2.3和3.3看到的）。trampoline内容放在trampoline.S中，执行用户代码时，stvec被设置为uservec(kernel/trampoline.S:16)。
当uservec开始时，所有32个寄存器包含由中断代码拥有的值。但uservec需要能够更改一些寄存器来设置satp并生成保存寄存器的地址。risc-v以sscratch寄存器形式提供帮助。csrrw指令在uservec开始处，交换a0和sscratch的值。用户code的a0被保存；uservec有一个寄存器a0可以使用；a0包含kernel之前放在sscratch中的值。
uservec的下个任务是保存用户寄存器。在进入用户空间之前，kernel设置sscratch来指向每个进程的trapframe（有空间保存所有用户寄存器kernel/proc.h:44）。因为satp仍然指向用户页表，uservec需要trapframe映射到用户地址空间。当创建每个进程时，xv6分配一个页给进程的trapframe，总是安排它映射到用户虚拟地址TRAPFRAME（仅位于TRAMPOLINE之下）。进程的p->trapframe指向trapframe，因为是指向物理地址，因此kernel可以通过kernel page table使用它。
因此交换a0和sscratch后，a0有一个指向当前进程trapframe的指针。uservec现在保存所有用户寄存器在trapframe，包括用户的a0（从sscratch读取的）。
trapframe包含指向当前进程kernel stack的指针，当前cpu的hartid，usertrap地址，内核页表地址。uservec获取这些值，切换satp到kernel page table，然后调用usertrap。
usertrap的任务是决定引发trap的原因然后处理它，并且返回kernel/trap.c:37。正如上面提到的，它先改变stvec以至于kernel trap将被kernelvec解决。保存sepc（saved user program counter），因为可能有一个进程切换在usertrap（会导致sepc被重写）。如果trap是一个system call，syscall处理它；如果是一个device interrupt，devintr；否则是一个异常，kernel杀掉错误进程。system call path加4到已保存的user pc，因为risc-v在system call时，保留程序指针指向ecall指令 。此后，usertrap检查进程是否已经被杀掉或yield cpu（如果trap是一个定时器中断）。
返回到用户空间的第一步是调用usertrapret（kernel/trap.c:90）。这个函数设置risc-v控制寄存器，来准备用户空间未来的trap。这包括改变stvec指向uservec，准备trapframe fileds（uservec依赖的），设置sepc为之前保存的user program counter。最后，usertrapret调用trampoline page的userret（在kernel/user page table上都有映射）；原因是userret汇编代码将切换页表。
usertrapret对userret的调用传一个指针到进程user page table在a0，TRAPFRAME在a1（kernel/trampoline.S:88）。userret切换satp到进程页表。用户页表映射trampoline page和TRAPFRAME，但没有映射kernel其他page。事实是trampoline page被映射在user/kernel page table同样的虚拟地址，这允许uservec在修改satp后继续执行。userret复制trapframe保存的user a0到sscratch准备之后TRAPFRAME的交换。从这点出发，userret仅可以使用的数据是寄存器内容和trapframe的内容。接下来userret恢复trapframe保存的用户寄存器，做最后的a0和ssscratch交换，来恢复user a0，并为下次trap保存TRAPFRAME，并使用sret返回到用户空间。

（三）调用system call

第二章以initcode.S调用exec system call（user/initcode.S:11）结束。让我们看用户调用如何用它的方式到exec system call内核实现。
用户代码为exec在寄存器a0和a1放置参数，并把system call序号放到a7。system call序号匹配入口在syscalls数组，一个函数指针表（kernel/syscall.c:108）。ecall指令traps into kernel并执行uservec、usertrap，然后syscall，正如我们上面看到的。
syscall（kernel/syscall.c:133）从trapframe存的a7取得system call序号，并用它在system calls中找出。对于第一个system call，a7包含SYS_exec（kernel/syscall.h:8），结果是调用system call 实现函数sys_exec。
当system call实现函数返回，syscall记录它的返回值在p->trapframe->a0。这将导致原始用户空间call exec()返回该值，因为risc-v的c调用约定是将返回值放到a0。system call约定返回负值来表明错误，0或正值表明成功。如果system call序号无效，syscall打印一个错误，并返回-1。

（四）system call参数

system call kernel实现需要找出user code传递的参数。因为user code调用system call包装函数，参数被初始化在RISC-V c调用约定放置他们的地方：寄存器。kernel trap代码保存用户寄存器到当前进程的trap frame，kernel code可以访问。函数argint，argaddr，和argfd， 从trap fraame获取第n个system call参数，作为整数、指针、文件描述符。他们都调用argraw来获取对应保存参数的寄存器。
一些system call传递指针作为参数，并且kernel必须使用那些指针来读取或写user内存。exec system call，传递kernel一个指针数组，来标识用户空间的字符串参数。这些指针有两个挑战。首先用户程序可能是有bug或恶意的，并且可能传给kernel一个无效指针或一个欺骗kernel访问kernel 内存（而不是user内存）的指针。第二，xv6 kernel page table映射不同于user page table映射，因此kernel不会使用原始指令来加载或存储用户提供地址。
kernel实现到/从用户提供地址安全转移数据的函数。fetchstr是一个例子（kernel/syscall.c:25）。file system calls例如exec使用fetchstr从用户空间来获取字符串文件名参数。fetchstr调用copyinstr来做这个工作。
copyinstr（kernel/vm.c:406）复制至多max字节，从user pagetable虚拟地址srcva到dst。它使用walkaddr（调用walk）来遍历软件page table，决定srcva的物理地址pa0。因为kernel映射所有物理RAM地址到相同kernel虚拟地址，copyinstr可以直接从pa0复制字符串到dst。walkaddr(kernel/vm.c:95)检测用户提供的虚拟地址是进程用户地址空间的一部分，因此程序不会欺骗kernel去读取其他内存。一个相似的函数，copyout，从kernel复制数据到用户提供地址。

（五）kernel空间traps

xv6配置cpu trap寄存器有些不同，取决于正在执行的是user还是kernel代码。当kernel正在cpu上执行时，kernel把stvec指向汇编代码kernelvec(kernel/kernelvec.S:10)。因为xv6已经在kernel中，kernelvec可以依靠satp（被设置成kernel page table），并且栈指针指向一个有效kernel stack。kernelvec保存所有寄存器，以便于中断的代码可以恢复，不会紊乱。
kernelvec保存寄存器在中断kernel 线程的栈上，这可以理解，因为寄存器值属于该线程。这是特别重要的，如果trap导致切换到不同线程，在这种情况下，trap将真正地返回到新线程的栈，让中断线程的安全地保留寄存器在它的栈上。
在保存完寄存器后kernelvec跳转到kerneltrap（kernel/trap.c:134）。kerneltrap为两种trap准备：设备中断和异常。它调用devintr（kernel/trap.c:177）来检查、处理设备中断。如果trap不是一个设备中断，它一定是一个异常，并且总会是一个严重错误，如果它发生在xv6 kernel中。kernel调用panic并且停止执行。
如果kerneltrap由于定时器中断被调用，进程的kernel thread正在运行（而不是一个调度线程），kerneltrap调用yield来给其他线程一个机会运行。在某些时候，那些线程中的某一个将会yield，并让我们的线程和它的kerneltrap再次恢复。章节7解释yield中发生了什么。
当kerneltrap的工作完成后，它需要返回到被trap中断的代码处。因为一个yield可能已经扰乱了保存的sepc，保存在sstatus中的previous mode，kerneltrap在开始时保存他们。它现在恢复那些控制寄存器，并且返回到kernelvec（kernel/kernelvec.S:48）。kernelvec 从栈中pop出保存的寄存器，并且执行sret，复制sepc到pc，并且恢复中断的kernel code。
这是值得思考的：trap如何返回，如果kerneltrap调用yield由于一个定时器中断。
xv6设置cpu的stvec到kernelvec，当cpu从用户空间进入kernel；你可以看到这在usertrap（kernel/trap.c:29）。有一个时间窗口：当kernel正在执行时stvec被设置为uservec，这是重要的：设备中断在这个窗口被禁用。幸运地，risc-v总是禁用中断，当它开始进入trap。xv6不会启用它们，直到设置完stvec之后。

（六）page-fault异常

xv6对异常的响应是十分无聊的：如果一个异常发生在用户空间，kernel杀掉这个错误的进程。如果一个异常发生在kernel，kernel panic。真正的操作系统通常用更有趣的方式响应。
举个例子，一些kernel使用page faults来实现copy-on-write(COW) fork。解释copy-on-write fork，考虑xv6的fork，在第三章描述。fork导致child拥有与parent一样的内存内容，通过调用uvmcopy（kernel/vm.c:309）来为child分配物理内存，并且拷贝parent的memory到child。如果child和parent可以共享parent的物理内存会是更高效的。基于此的一个直接实现不会起作用，然而，因为它导致parent和child写共享stack和heap扰乱各自的执行。
parent和child可以使用copy-on-write fork安全地分享物理内存，由page faults驱动。当cpu不能翻译一个虚拟地址到物理地址，cpu生成一个page-fault异常。risc-v由三种不同的page fault：load page faults（当一个load指令不能翻译它的虚拟地址），store page faults（当一个store指令不能翻译它的虚拟地址），instruction page faults（当指令地址不能翻译）。scause寄存器的值表明page fault类型，stval寄存器包含不能被翻译的地址。
COW fork基本的计划是：对于parent和child初始化共享所有物理内存，但映射它们为只读。因此，当child或parent执行一个store instruction，risc-v cpu抛出一个page-fault异常。kernel做一个page的拷贝（包含faulted address）来响应这个异常。它映射一个拷贝在子进程的地址空间read/write，并且映射另外一个copy在父进程地址空间read/write。在更新页表后，kernel在引发fault的指令处恢复faulting进程。因为kernel已经更新相关PTE允许写，faulting指令将可以执行，不会产生fault。
这个COW计划对于fork很有效，因为通常child在fork后立即调用exec，用一个新的地址空间替代原先地址空间。在通常情况下，child将仅会经历几种page faults，并且kernel可以避免做一个完全的copy。另外，COW fork是显然的：在应用无更改情况下，让它们受益是必需的。
page tables和page faults的结合打开了一个除COW fork之外的大范围有趣可能。另外一个广泛使用的特性叫做lazy allocation，分为两部分。首先，当一个应用调用sbrk，kernel增长地址空间，但将新地址空间标记为在页表无效。第二，当那些新地址中的一个，发生一个page fault时，kernel分配物理内存，并且在页表映射它。因为应用通常比它们需要的索取更多内存，懒分配是成功的：kernel仅在应用真正使用时再分配内存。像COW fork，kernel可以实现这个特性而对应用透明。
另外一个广泛使用的利用page faults特性：paging from disk。如果应用需要更多内存比起可用的物理RAM，kernel可以去除一些pages：把它们写到一个存储设备例如硬盘，并且标记它们的PTE为无效。如果一个应用读/写一个去除的页，cpu将得到一个page fault。kernel会检查faulting地址。如果地址属于硬盘上的页，kernel分配一个物理内存page，将硬盘上的page读到物理内存page中，更新PTE为有效并指向该内存，然后恢复应用。为page制造room，kernel可能不得不去除另外的页。这个特性需要对应用无改变，若应用有索引局部性会较好生效（在任意给定时间，它们仅使用内存的子集）。
另外特性：结合paging和page-fault异常包括自动拓展栈和内存映射文件。

（七）现实世界

对特殊trampoline页的需要可以被消除，如果kernel内存被映射到每个进程用户页表（有准确的PTE权限标志位）。也会消除页表切换的需要，当从user space过度到kernel。允许在kernel实现system call来利用当前进程被映射的用户内存，允许kernel code直接利用用户指针。一些操作系统已经使用这些想法来提高效率。xv6避免它们，减少了kernel安全bug的可能（由于疏忽利用用户指针），并且减少了一些复杂度（需要确保user和kernel虚拟内存地址不重叠）。

五、interrupts和device drivers

介绍

驱动是操作系统中管理某个特定设备的代码：它配置设备硬件，告诉设备执行操作，解决结果中断，与进程（可能正在等待设备IO）交互。驱动代码可能是棘手的，因为驱动与它管理的设备并行执行。另外，驱动必须理解设备硬件接口（这是复杂、记录不充分的）。
需要操作系统关注的设备通常被配置为生成中断，这是一种trap。当设备抛出中断时，kernel trap handling代码识别出，然后调用驱动中断handler。在 xv6，这个分发发生在devintr(kernel/trap.c:177)。
一些设备驱动在两种场景下执行代码：上半部分发生在进程kernel线程，下半部分在中断时执行。上半部分通过system call被调用，例如read、write（想要设备执行I/O）。这个代码可能让硬件开始一个操作（例如让硬盘读一个block）；然后代码等待操作完成。最后设备完成该操作，并抛出一个中断。驱动的interrupt handler（扮演下半部分）找出什么操作已经完成，唤醒等待进程，然后告诉硬件开始处理任一等待的下个操作。

（一）Code：Console input

console驱动（console.c）是一个简单的驱动结构描述。console驱动通过连接到RISC-V的UART硬件串口接收人输入的字符。console驱动一次积累一行输入，处理特殊输入字符例如退格和ctrl+u。用户进程，例如shell，使用read system call来获取控制台多行输入。当你打字输入给qemu的xv6，你按击键盘通过qemu仿真UART硬件的方式传递给xv6 。
驱动交互的UART硬件是qemu仿真的16550芯片。在真正电脑上，16550管理连接到一个终端或其他电脑的RS232串行连接。当运行qemu，他被连接到你的键盘和显示上。
UART硬件表现在软件上为一组内存映射控制寄存器。有一些物理地址（risc-v连接UART设备），因此加载存储这些地址是与设备硬件交互而不是RAM。UART的内存映射地址起始于0x10000000，或UART0（kernel/memlayout.h:21）。有些有帮助的UART控制寄存器，每个一字节宽。它们对于UART0的偏移定义在kernel/uart.c:22。例如，LSR寄存器包含位（表明是否有输入字符等着被软件读）。这些字符可以从RHR寄存器读取。每次一个字符被读取，UART硬件将它从内部等待字节FIFO中删除，并且在FIFO空时清除LSR的ready标志位。UART传送硬件独立于接收硬件；如果软件向THR中写一个字节，UART传递该字节。
xv6 main调用consoleinit（kernel/console.c:184）来初始化UART硬件。这个代码配置UART在接收到每个字节输入时，生成一个接收中断，以及每次UART完成发送一个字节输出时（kernel/uart.c:53），生成一个传递完成中断。
xv6 shell从控制台通过init.c(user/init.c:19)打开的文件描述符读取输入。read system call调用通过kernel进入consoleread(kernel/console.c:82)。consoleread通过中断等待输入到达，缓存在cons.buf，拷贝输入到用户空间，在一整行到达后返回给用户进程。如果用户没有输入完一整行，读取进程将在sleep调用中等待（kernel/console.c）。
当用户输入一个字符，UART硬件让RISC-V抛出一个中断，这会激活xv6的trap handler。trap handler调用devintr（kernel/trap.c:177），它查看RISC-V的scause寄存器发现来自拓展设备的中断。然后它让硬件单元PLIC来告诉它哪个设备中断了（kernel/trap.c:186）。如果是UART，devintr调用uartintr。
uartintr（kernel/uart.c:180）从UART硬件读取一些等待输入字符，将它们传到consoleintr（kernel/console.c:138）;不会等待字符，因为未来输入将会抛出一个中断。consoleintr的任务是累计输入字符到cons.buf，直到一整行。consoleintr特殊对待backtrace和一些其他字符。当到一行时，consoleintr唤醒一个等待的consoleread（如果有一个）。
一旦唤醒，consoleread将从cons.buf读取一整行，把它拷贝到用户空间，然后返回到用户空间（通过system call 机制）。

思考：
system call通过指令ecall触发，page fault可以通过MMU监测到触发，自动将stvec寄存器的值加载到pc寄存器， 那中断如何监测到？
暂时猜测，cpu收到uart引脚某种信号，将其视作中断。

（二）Code：Console output

write system call（对连接到console的文件描述符）最终到达uartputc(kernel/uart.c:87)。这个设备驱动持有一个output buffer（uart_tx_buf），因此写进程无需等UART结束发送；uartputc拼接每个字符到buffer，调用uartstart来开始设备传输，然后返回。uartputc等待的唯一场景是buffer已经满了。
每次UART结束发送一个字节，它生成一个中断。uartintr调用uartstart，它检查设备已经结束发送，且处理设备下个缓冲输出字符。因此如果一个进程写多个字节到console，通常，第一个字节将通过uartputc调用uartstart被发送，随着传送完成中断抵达，剩下的缓存字节将通过uartstart调用（来自uartintr）被发送。
一个需要关注的通用模式为：通过buffering和interrupt分离设备活动与进程活动。console驱动可以处理输入，即使没有进程等待读入。接下来的读将看到这个输入。相似地，进程可以发送输出，而无需等待设备。分离通过允许进程与设备I/O并发执行来提升性能，当设备很慢（就像UART）或需要立刻关注（就像回显输入字符），这是特别重要的。这个主意有时也称为I/O concurrency。

（三）Concurrency in drivers

你可能注意到consoleread和consoleintr中的acquire调用。这些调用需要一个锁，它保证console driver的数据结构不会并发访问。三个并发危险是：两个不同CPU上的进程可能同时调用consoleread；硬件可能让CPU传递一个console （实际上是UART）interrupt，在CPU执行consoleread期间；当consoleread正在执行时，硬件可能传递一个console interrupt到一个不同CPU。第六章探索锁如何在这些场景下起作用。
另外一个驱动中需要并发关注的是，一个进程可能等待一个设备的输入，但输入中断信号到达时，另外一个进程可能正在运行。interrupt handlers不会考虑它们打断的进程或代码。例如，一个interrupt handler不会安全的调用copyout（用当前进程page table）。Interrupt handlers通常做较少工作（只是拷贝输入数据到buffer），然后唤醒top-half代码做剩下的。

（四）timer interrupts

xv6使用timer interrupt来保持它的时钟，并且启用它来在各进程间切换；yield在usertrap和kerneltrap中调用导致进程切换。timer interrupt来源于每个绑定在risc-v cpu上的时钟硬件。xv6对这个时钟硬件编程来周期性地中断每个cpu。
risc-v需要timer interrupt在机器模式下采用，不是supervisor模式。risc-v机器模式执行没有分页，并且有一组单独的控制寄存器，所以在机器模式下执行原始xv6 kernel代码是不切实际的。结果是，xv6处理timer interrupts完全独立于上面提到的trap机制。
执行在机器模式下的代码在start.c，main函数之前，设置接收timer interrupts（kernel/start.c:57）。工作的一部分是编程CLINT硬件（core-local interruptor）来在某个延时后生成一个中断。另外一部分是设置一个scratch area，和trapframe相似，帮助timer interrupt handler保存寄存器和CLINT寄存器地址。最终，start设置mtvec到timervec并且启用timer interrupts。
timer interrupt会发生在user或kernel代码执行的任意时刻；在关键操作期间kernel没法禁用timer interrupt。因此timer interrupt handler必须采取某种方式保证不会扰乱中断的kernel code。handler基本策略是让risc-v抛出一个软件中断并立即返回。risc-v用基本trap机制传递软件中断到kernel，允许kernel禁用它们。处理由timer interrupt生成的软件中断代码可以在devintr（kernel/trap.c:204）中看到。
机器模式timer interrupt vector是timervec（kernel/kernelvec.S:93）。它保存少量寄存器在scratch area（start准备），告诉CLINT何时生成下一个timer interrupt，让risc-v抛出一个软件中断，恢复寄存器，然后return。没有c代码在timer interrupt handler。

（五）现实世界

当在kernel和用户程序中执行时，xv6允许设备和timer中断。在timer中断handler中，定时器中断处理器的timer中断强制一个线程切换（调用yield），即使在kernel中执行。在kernel线程之间公平地对CPU时间分片的能力是有用的，如果kernel threads有时花费大量时间计算，而不返回用户空间。然而kernel code需要小心：可能被挂起（因为timer中断），然后在不同的CPU上恢复，这是xv6复杂的源头。kernel可以被弄得更简单，如果设备和timer中断仅发生在执行用户代码期间。
支持一个通用计算机的所有设备是一项艰巨的工作，因为有许多设备，设备有许多特性，设备和驱动间的协议是复杂和缺少文档的。在一些操作系统中，驱动比core kernel需要更多代码。
通过读取UART控制寄存器，UART驱动每次获取一个字节；这个模式称为programmed I/O，因为软件驱动数据移动。Programmed I/O是简单的，但太慢了，不能在大量数据时使用。需要高速移动大量数据的设备通常使用direct memory access（DMA）。DMA设备硬件直接写输入数据到RAM，直接从RAM读输出数据。现代硬盘和网络设备都使用DMA。DMA设备驱动在RAM准备数据，然后用一个写到控制寄存器，告知设备处理准备好的数据。
中断解释了，设备在不可预测时间需要关注，且不会太频繁。但中断有高CPU开销。因此高速设备，例如网络和硬盘控制器，使用技巧来减少中断需要。一个技巧是为一批输入/输出请求抛出一个中断。另外的驱动技巧是禁用整个设备中断，周期性检查设备来看它是否需要被关注。这个技术叫做polling。如果设备执行操作较快那么polling起作用，但如果设备大部分时间是空闲的，它浪费CPU时间。一些驱动动态的切换polling和interrupt取决于当前设备负载。
UART驱动复制输入数据到kernel buffer，然后到用户空间。这使得低数据效率，对于快速生成、消费数据的设备，双拷贝显著减少性能。一些操作系统能直接在用户空间buffer和设备硬件之间移动数据，通常是DMA。

六、locking

介绍

绝大多数kernels，包括xv6，交叉执行多个活动。交叉的一个原因是多处理器硬件：电脑有多个CPUS独立执行，例如xv6的RISC-V。多个CPU共享物理RAM，xv6利用共享来保存所有CPUS读写的数据结构。这个共享提供了一种可能：一个CPU正在读一个数据结构，而另外一个CPU正在更新它，或多个CPU同时更新同一个数据。不小心设计这种并发访问可能导致错误结果或一个被破坏的数据结构。即使在单处理器上，kernel可能让CPU在多个线程间切换，导致交替执行。最终，如果一个中断恰好发生在错误时间，那么一个设备中断处理器（更改的数据，与一些被中断代码更改的数据相同）会破坏数据。单词 concurrency指的是，由于多处理器并行、线程切换或中断，多指令流交叉的场景。
Kernel都是并发访问数据。例如，两个CPU可以同时调用kalloc，因此并发地从free list的头部popping。Kernel设计者喜欢允许大量并发，因为它可以通过parallelism导致提升的性能和提升的响应能力。然而结果是kernel设计者花费大量精力确保它们的正确性，无论如何并发。有一些方式达到正确的代码，有些比其他更容易推理。为了并发正确性的策略以及支持它们的抽象，称为并发控制技术。
根据场景，xv6使用一些并发控制技术。本章节聚焦于广泛使用的技术：锁。锁提供相互地排斥，确保某一时刻只有一个CPU持有锁。如果程序员将一个锁与一个共享数据项关联，那么在使用该数据项时代码总是持有相关的锁，那么某一时刻，数据项仅被一个CPU使用。在这种场景中，我们说锁保护数据项。尽管锁是易于理解的并发控制机制，锁的缺点是它们会杀掉性能，因为它们串行并发操作。
章节其余部分解释为什么xv6需要锁，xv6如何实现它们，以及如何使用它们。

（一）Race conditions

一个为什么我们需要锁的例子，考虑两个进程在不同CPU上调用wait。wait释放child的内存。因此在每个CPU上，kernel将调用kfree来释放children的页。kernel allocator保存一个链表：kalloc()(kernel/kalloc.c:69)从free page list中pop一个内存page，kfree()(kernel/kalloc.c:47)push一个page到free list。为了最好的性能，我们可能希望两个parent进程的kfree可以并行的执行，任意一个无需等另外一个，但考虑到xv6的实现，这是不正确的。
图6.1解释了设置的更多细节：链表在内存中被两个CPU共享，使用load、store指令操作链表。（实际上，处理器有缓存，但概念上讲，多处理器系统表现的就像只有一个共享内存）。如果没有并发请求，你可能实现一个链表push操作如下：

struct element{
	int data;
	sturct element *next;	
};
struct element *list=0;
void push(int data){
	struct element *l;
	
	l = malloc(sizeof *l);
	l->data = data;
	l->next = list;
}

如果隔离执行，这个实现是正确的。然而如果不止一个拷贝并发执行，代码并不正确。如果两个CPUS同时执行push，可能都在执行图6.1的15行，在执行16行之前，会导致一个错误的结果（由图6.2描述）。两个list元素的next设置为之前的list值。当两个list赋值发生在16行时，第二个将覆盖掉第一个；第一个赋值中的相关元素将会丢失。
16行丢失的更新是一个race condition的例子。race condition是一种场景：一个内存位置被并发地访问，至少一个访问是写。race通常是bug的标志，要么是lost update（如果访问都是写），要么a read of an incompletely-updated数据结构。race导致的结果取决于两个相关CPU具体的时序，以及它们的内存操作如何被内存系统排序，这会让race诱发的错误难以重现和调试。例如，在调试push时添加打印语句，可能会改变执行时序而让race消失。
避免race的通常方式是使用一个锁。锁确保相互排斥，因此某一时刻仅一个CPU可以执行push的相关行；这让上述场景不可能。上面代码正确地加锁版本仅会添加几行（黄色高亮）。

struct element *list=0;
struct lock listlock;

void push (int data){
  struct element *l;
  l = malloc(sizeof *l);
  l->data = data;
  acquire(&listlock);
  l->next = list;
  release(&listlock);
}

acquire和release之间的一系列指令通常称为critical section。锁通常被看作保护list。
当我们说锁保护数据，我们真正地意思是，锁保护一些应用于数据的不变关系集合。不变性是跨操作维护地数据结构属性。通常，操作的正确行为取决于操作开始时，不变量为真。操作可能临时违反不变性，但必须在结束前重新建立它们。例如，在链表场景中，不变性是：list指向链表的首个元素，而且每个元素的next属性指向下个元素。push的实现临时违反了不变性（在17行），l指向下个链表元素，但list还没有指向l（在18行重建）。我们上面检查的race condition之所以发生，是因为第二个CPU执行的代码，依赖list不变性，然而它们被临时违反了。
锁的正确使用保证了某一时刻只有一个CPU可以在critical section中操作数据结构，因此当数据结构的不变性不成立时，没有CPU会执行数据结构操作。
你可以考虑一个锁，例如串行化并发critical section，因此它们某一时刻执行一个，因此保证了不变性（假设critical sections单独时是正确的）。你也可以将被同一锁保护的critical sections视作是原子的（与其他critical section相比），因此每个critical section仅会看到来自上个critical section的完整改变，不会看到partially-completely updates。
虽然正确使用锁让错误代码正确了，但锁限制了性能。例如，两个进程并发地调用kfree，锁将串行化两个调用，我们不能从 不同CPU运行中 获得好处。如果某一时刻多进程想要同一锁，我们称之为多进程冲突或lock experiences contention。kernel设计的主要挑战是避免锁争用。xv6做的不多，但复杂的kernel组织数据结构和特定算法来避免锁争用。在链表的例子中，kernel可以让每个CPU持有一个free list，仅会在一个CPU的list为空，需要从另外CPU窃取内存时，才会接触另外CPU的free list。其他使用场景可能需要更复杂的设计。
锁放置的地方对性能也很重要。例如，将acquire移动到push中更早的地方也是正确的：将对acquire的调用提到13行之前也是对的。这会降低性能，因为对malloc的调用也是串行了。下面Using Locks章节提供一些指导（在哪插入acquire和release调用）。

（二）Code：Locks

xv6有两种类型的锁：spinlocks和sleep-locks。我们将开始于spinlocks。
xv6将spinlock表示为一个struct spinlock(kernel/spinlock.h:2)。
结构中重要的属性是locked，当锁可用时为0，当它被持有时为非0。
逻辑上，xv6应该可以通过执行像下面代码来获取锁。

void acquire(struct spinlock *lk){
  for(;;){
	if(lk->locked == 0){
  		lk->locked=1;
  		break;
	}
  }
}

不幸地是，这个实现不能保证在多处理器上的互相排斥。两个CPU同时到达25行，看到lk->locked是0，然后都通过执行26行获取锁。基于这点，两个不同的CPU持有该锁，违反了相互排斥属性。我们需要的是一个方式：让25和26行像一个原子（密不可分）步骤一样执行。
因为锁是广泛使用的，多核处理器通常提供指令实现一个25行和26行的原子版本。在RISC-V上这个指令是amoswap r,a。amoswap读取内存地址a的值，将寄存器r的内容写到该地址，然后将把从地址读到的值放到寄存器r。它交换寄存器和内存地址的内容。它原子地执行这些，使用特殊硬件来阻止任何其他CPU在读写期间使用该内存地址。
xv6的acquire(kernel/spinlock.c:22)使用portable C库调用_sync_lock_test_and_set，它归结为amoswap指令；返回值是lk->locked旧值。acquire函数将swap包装在循环中，重试（自旋）直到它获取到锁。每次迭代交换一个值到lk->locked并且检查之前的值。如果之前的值为0，那么我们获取到了锁，swap将设置lk->locked为1。如果之前值为1，那么一些其他CPU持有该锁，事实是：我们原子地交换值1到lk->locked没有改变它的值。
一旦获取到锁，acquire记录（为了调试）获取到锁的CPU。lk->cpu属性被锁保护，只有持有该锁时才能被改变。
函数release（kernel/spinlock.c:47）是acquire的对立：它清除lk->cpu属性，然后释放锁。理论上，release仅需要将0赋值到lk->locked。C标准允许编译器用多个store指令来实现赋值，所以一个C赋值对并发代码来说并不是原子的。release使用C库函数_sync_lock_release执行一个原子赋值。这个函数也归结为一个RISC-V amoswap指令。

（三）Code：Using locks

xv6在一些地方使用锁来避免race conditions。正如上面描述的，kalloc(kernel/kalloc.c:69)和kfree(kernel/kalloc.c:47)构成了一个好例子。尝试练习1和2，当那些函数忽略琐时会发生什么。你将可能发现触发不正确的行为是困难的，表明可靠地测试代码是否可以免于锁错误和竞争是困难的。xv6不太可能出现竞争。
关于使用锁的一个难点是：决定使用多少锁，以及每个锁应该保护哪些数据和不变性。有少量基本原则。首先，任意时刻，一个变量被一个CPU写，同一时刻另外一个CPU写或读，锁应该被用来保证两个操作免于重叠。第二，记住：锁保护不变性：如果一个不变性包括多个内存位置，通常它们所有都需要被一个锁保护起来，从而保证不变性被持有。
以上原则表明何时锁是必须的，但没有说明何时锁是不必须的，为了效率不锁太多是重要的，因为锁减少并行。如果并行不重要，那么可以只安排一个线程，无需担心锁。一个简单kernel可以在一个多处理器上做到这点，通过持有一个单独的锁（在进入内核时持有，退出内核时释放）（尽管system calls例如pipe read或wait会暴露问题）。一些单处理器操作系统已经使用这种方式转为在多处理器上运行，有时称作”big kernel lock”，但这种方式牺牲并行：某时刻仅一个CPU在kernel执行。如果kernel做一些重度计算，使用大量更细粒度的锁是更有效的，因此kernel可以同时执行在多个CPU上。
一个粗粒度锁的例子，xv6的kalloc.c分配器有一个单独的free list被一个锁保护。如果不同CPU上的多个进程尝试同时分配页，每个将必须等着轮到它，通过在acquire中自旋。自旋降低性能，因为它不是有用的工作。如果这个锁的争用浪费了大量CPU时间，可能性能可以通过改变分配器（设计为有多个free list）来提升，每个有它自己的锁，允许真正的并行分配。
一个细粒度锁的例子，xv6对每个文件有一个单独的锁，因此操作不同文件的进程通常可以（无需等待其他锁）执行。如果需要允许多进程同时写同一文件的不同区域，文件锁方案要被做的更细粒度，最终，锁粒度决定需要被性能衡量和复杂度考量所驱动。
正如随后的章节解释xv6的每部分，它们将提到xv6使用锁应对并发的例子。作为一个预览，图6.3列出了xv6中所有的锁。

（四）Deadlock and lock ordering

如果通过kernel的代码必须同时持有多个锁，所有代码以相同顺序获取那些锁是重要的。如果它们没那么做，就有死锁的风险。xv6代码需要锁A和B，但path 1需要锁的顺序是先A后B，另外的path以先B后A 的顺序获取它们。假设线程T1执行代码path 1，获取锁A，线程T2执行代码path2，获取锁B。接下来，T1将尝试获取锁B，T2将尝试获取锁A。两个获取将永远阻塞，因为每个线程都持有另外线程需要的锁，不会释放它直到acquire返回。为了避免这个死锁，所有code paths必须以相同顺序获取锁。全局锁获取顺序的需要意味着锁实际上是每个函数声明的一部分：调用方必须调用函数以（锁约定顺序被获取）这种方式 。
由于sleep的工作方式（看章节7），xv6有一些长度为2的锁顺序链，涉及每个进程的锁（在每个struct proc中的锁）。例如，consoleintr(kernel/console.c:138)是处理输入字符的中断方式。当新行到达时，任意等待console input的进程应该被唤醒。为了做到这，当调用wakeup时consoleintr持有cons.lock，需要等待进程的锁来唤醒它。结论是，全局死锁避免 锁顺序包含 cons.lock必须在进程锁获取之前被获取 的规则。文件系统代码包含xv6最长的锁链。例如，创建一个文件需要同时持有该目录的锁，新文件inode的锁，disk block buffer锁，disk driver的vdisk_lock，调用进程的p->lock。为了避免死锁，文件系统代码总是以之前句子中提到的顺序获取锁。
遵循global deadlock-avoiding order会出人意料的困难。有时锁顺序与逻辑的程序结构冲突，例如，可能代码模块M1调用模块M2，但锁顺序需要M2中的锁获取在M1中锁获取之前。有时锁标识不能提前知道，可能因为一个锁必须被持有来发现下个被获取的锁标识。这种场景出现在文件系统中，当它在路径名中查找连续组件时，也会出现在wait和exit代码中，当它们查看进程表查找子进程时。最终，死锁的危险性通常是锁机制何种粒度的限制，因为更多锁通常意味着更多机会产生死锁。避免死锁的需要通常是kernel实现的主要因素。

（五）Locks and interrupt handlers

一些xv6自旋锁保护被多线程和中断handlers使用的数据。例如clockintr定时器中断handler有可能：提升ticks（kernel/trap.c:163）的时间与kernel线程在sys_sleep(kernel/sysproc.c:64)读取ticks的时间一致。tickslock锁串行化两个操作。
自旋锁和中断的相互影响引发一个潜在危险。假如sys_sleep持有tickslock，且它的CPU被timer interrupt中断。clockintr会尝试获取tickslock，看到它被持有，等它被释放。在这种场景，tickslock将不会被释放：仅sys_sleep可以释放它，但sys_sleep不会继续执行直到clockintr返回。因此CPU将会死锁，那些代码需要锁的代码也会僵住。
为了避免这种情形，如果一个自旋锁被一个中断handler使用，CPU必须在中断启用时从没有持有该锁。xv6时更保守的：当CPU需要任何锁时，xv6总是禁用该CPU中断。中断可能仍然会发生在其他CPU上，因此一个中断的获取会等待线程释放一个自旋锁；只是不在同一个CPU。
当一个CPU没有持有自旋锁时，xv6重新启用中断；它必须做一点记录来应对嵌套的critical section。acquire调用push_off((kernel/spinlock.c:89)和release调用pop_off(kernel/spinlock.c:100)来在当前CPU上追踪嵌套级别的锁。当计数到0时，pop_off恢复中断启用state（在最外层critical section起始处存在）。intr_off和intr_on函数执行RISC-V指令来禁用、启用中断。
这是重要的：在设置lk->locked(kernel/spinlock.c:28)之前，acquire直接调用push_off。如果两个反转，那么有一个简短的窗口，中断启用时，持有锁，一个不幸的定时中断会deadlock系统。相似地，release只会在释放掉锁后调用pop_off(kernel/spinlock.c:66)。

（六）Instruction and memory ordering

以源码出现的顺序考虑程序执行是自然的。一些编译器和CPU为实现更高性能不按顺序执行代码。如果一个指令花费多个cycles来完成，CPU可能提前发出指令，以便能够与其他指令重叠，避免CPU暂停。例如，CPU可能注意到，在一个串行指令中A和B不互相依赖。CPU可能先开始指令B，要么因为它的输入比A的输入先准备好，要么为了重叠执行A和B。一个编译器可能执行一个类似的重排序，通过发一个语句的指令在某个语句（在源码里先处理）指令之前。
编译器和CPU遵循原则：何时重排序来确保它们不会改变结果（正确写入串行代码）。然而，允许重排序的规则改变并发代码结果，而且容易在多处理器上引起不正确的行为。CPU的排序规则称为内存模型。
例如，在push的代码中，这会是一个灾难，如果编译器或CPU移动存储（对应第4行）到release（第6行）之后。

l = malloc(sizeof *l);
l ->data = data;
acquire(&listlock);
l->next = list;
list = l;
release(&listlock);
如果这个重排序发生，会有一个窗口期：另外的CPU可以获取锁，然后看到更新后的list，但看到一个没有初始化的list->next。
为了告诉硬件和编译器不执行这个重排序，xv6在acquire(kernel/spinlock.c:22)和release(kernel/spinlock.c:47)使用_syn_synchroniez()。_syn_synchronize()是一个memory barrier：它告诉编译器和CPU不重排序lord和store穿过barrier。xv6 acquire和release的barriers强制所有相关场景中的顺序，因为xv6使用锁访问共享数据。章节9讨论一些异常。

（七）Sleep locks

有时xv6需要长时间持有一个锁。例如文件系统保持一个文件锁定，当读写磁盘上它的内容时，这些磁盘操作会花费几十毫秒。长时间持有一个自旋锁会导致浪费，如果另外的进程想获取它，因为获取进程会在自旋时浪费CPU很长时间。自旋锁另外的缺点是，在持有自旋锁时进程不会yield CPU；当有锁进程等待磁盘时，我们喜欢这么做，以至于其他进程可以使用CPU。持有自旋锁时yield是不合法的，因为它可能导致死锁，如果第二个线程尝试获取自旋锁；因为acquire不会yield CPU，第二个线程的自旋可能阻止第一个线程执行、释放锁。持有锁时yield也会违反要求（中断必须在持有spinlock期间关闭）。因此我们想要一种锁（在等待获取期间可以yield CPU），并且允许持有锁期间yield和中断。
xv6以sleep-lock的形式提供这种锁。acquresleep（kernel/sleeplock.c:22）在等待时yield CPU，使用的技术会在章节7解释。sleep-lock有一个locked属性（由spinlock保护），acquiresleep的调用到sleep原子地yieldCPU和释放spinlock。结果是：另外的线程会在acquiresleep等待时执行。
因为sleep-lock让中断启用，它们不会被用在中断处理器。因为acquiresleep会yieldCPU，sleep-lock不会用在spinlock critical sections（尽管spinlocks可以被用在sleep-lock critical sections期间）。
spinlock最适用于短critical sections，因为等待它们消耗CPU时间；sleep-lock对长期操作表现良好。

（八）现实世界

有锁编程仍然是个挑战，不管研究多少年并发和并行。用高级结构例如synchronized queue明确锁通常好一些，尽管xv6没有这么做。如果你有锁编程，使用一个工具（尝试明确race conditions）是明智的，因为很容易忘记需要锁的不变性。
大多数操作系统支持POSIX线程（Pthreads），这允许一个用户进程有多个线程在不同CPU上并行执行。Pthreads也支持用户级别锁，barriers等等。支持Pthreads需要操作系统支持。例如，如果一个pthread阻塞在system call中，同一进程的另外一个pthread应该能够在该CPU上运行。例外一个例子，如果一个pthread改变其进程地址空间（例如maps或unmaps内存），kernel必须安排其他CPU（运行着同一进程其他多线程）更新它们的硬件页表来反映地址空间的改变。
不用原子指令实现锁也是可以的，但这是昂贵的，且绝大多数操作系统使用原子指令。
如果多个CPU要在同一时刻获取同一锁，那么锁时昂贵的。如果某个CPU有一个锁缓存在它的本地cache中，另外CPU必须获取该锁，那么原子指令更新缓存line（含有锁），就必须从一个CPU cahe到其他CPU cache移动line，可能会无效化一些其他cache line拷贝。从另外CPU cache获取cache line比从本地cache中获取昂贵几个数量级。
为了避免锁消耗，一些操作系统使用 lock-free 数据结构和算法。例如，实现一个像章节开始处那样（在list查找期间无需锁）的链表是可能的。lock-free编程比有锁编程更复杂；例如，必须考虑指令和内存重排序。有锁编程已经够难了，因此xv6避免额外的lock-free编程复杂度。

七、Scheduling

介绍

任何操作系统，都可能以 多于计算机拥有的CPU数 的进程数运行，因此在多进程之间time-share CPU的方案是需要的。理想地，共享对用户进程来说是透明的。常见的方案是给每个进程一个错觉（它有自己的CPU），通过多进程复用CPU硬件。本章节解释xv6如何实现多路复用。

（一）Multiplexing

xv6通过将每个CPU从一个进程切换到另一个进程来实现多路复用（有两个情形）。第一，当一个进程等待设备或pipe I/O完成、或等待child exit、或等待sleep system call时，xv6的sleep和wakeup机制switches。第二，xv6周期性地，强制对长期计算不会睡眠的进程进行一个切换。这个多路复用制造一个假象（每个进程有它自己的CPU），就像xv6使用内存分配器和硬件page tables制造一个假象（每个进程有它自己的内存）。
实现多路复用有一些挑战。首先，如何从一个进程切换到另外一个？尽管上下文切换的想法是简单的，实现是xv6绝大多数难懂代码的一部分。第二，如何以一种对用户进程透明的方式强制切换？xv6使用标准技术：用timer interrupt驱动上下文切换。第三，一些CPU可能并发地在多个进程间切换，加锁方式对避免竞争是必要的。第四，进程退出时，一个进程的内存和其他资源必须释放，但它不能自己做所有工作，因为它不能在仍使用时释放它的kernel stack。第五，多核机器的每个核必须记着哪个进程正在执行，为了system call影响正确进程的kernel state。

最后，sleep和wakeup允许一个进程放弃CPU，然后sleep等待一个event，允许另外的进程唤醒第一个进程。需要小心来避免（会导致wakeup通知丢失的）竞争。xv6尽可能简单地尝试解决这些问题，但最终代码是棘手的。

（二）Code：Context switching

图7.1概括了从一个用户进程切换到另外一个进程的相关步骤：一个到旧进程kernel thread的user-kernel过度（system call or interrupt），上下文切换到当前CPU scheduler thread，上下文切换到新进程kernel thread，一个返回到user-level进程的trap。xv6 scheduler每个CPU有一个定义好的thread（保存寄存器和栈），因为在旧进程kernel stack上执行，对scheduler来说是不安全的：一些其他核可能唤醒进程并执行它，两个不同核上使用同一stack是灾难的。在本节中，我们将检验kernel线程和scheduler线程的切换机制。
从一个线程切换到另外一个，包括保存旧线程的CPU寄存器，恢复新线程之前保存的寄存器；事实（栈指针和程序计数器被保存和恢复）意味着CPU将切换栈、切换正在执行的代码。
函数swtch为kernel thread切换执行保存和恢复。swtch没有直接了解线程；只是保存和恢复寄存器集（称为context）。当一个进程准备好放弃CPU时，进程kernel thread调用swtch来保存它自己的context，并返回到scheduler context。每个context保存在一个context结构体中（kernel/proc.h:2），它本身包含在进程的结构体proc或CPU的结构体cpu中。Swtch接收两个参数：struct context *old和struct context *new。它保存当前寄存器到old，加载new中的寄存器，然后返回。
让我们跟着一个进程穿过swtch到scheduler。我们看到在章节4中，中断结尾处的一个可能是usertrap调用yield。yield转为调用sched，然后调用swtch保存当前context到p->context，然后切换为之前保存在cpu->scheduler（kernel/proc.c:509）中的scheduler context。
Swtch(kernel/swtch.S:3)仅保存callee-saved寄存器；caller-saved寄存器通过调用C代码保存在栈上。swtch知道struct context中每个成员的偏移量。没有保存程序计数器。swtch保存ra寄存器，它存了返回地址（swtch被从此处调用）。现在swtch从新context中恢复寄存器，它保留了寄存器的值（由上个swtch保存的）。当swtch返回时，它返回到由恢复的ra寄存器指向的指令，这个指令是新线程之前调用swtch的地方。另外，它返回到新线程的栈。
在我们的例子中，sched调用swtch来切换到cpu->scheduler（每个CPU scheduler context）。context已经通过scheduler调用swtch(kernel/proc.c:475)保存。当我们跟踪的swtch返回时，它不是返回到sched而是scheduler，而且它的栈指针指向当前CPU的scheduler stack。

（三）Code：Scheduling

最后一节来看swtch低级细节；现在我们将swtch看作一个给定的、校验的switching（从一个进程的kernel thread通过scheduler到另外一个进程）。scheduler以每个CPU一个特殊线程的形式存在，每个执行scheduler函数。此函数掌管选择哪个进程下个运行。一个想放弃CPU的进程必须获取它自己的进程锁p->lock，release任何其他正在持有的锁，更新它自己的状态（p->state），然后调用sched。Yield（kernel/proc.c:515）遵循这个约定，就像sleep和exit，我们待会校验。sched double-checks那些条件（kernel/proc.c:499-504），那些条件的含义：因为锁被持有，中断应该被禁用。最后，sched调用swtch保存当前context到p->context，并切换到scheduler context（cpu->scheduler）。

Swtch返回到scheduler stack，就像scheduler swtch返回一样，scheduler继续for循环，找到一个进程来执行，切换到它，重复这个循环。
我们刚刚看到xv6持有p->lock对swtch调用：swtch的调用者必须已经持有该锁，锁的控制传递到切换后的代码。这个习惯对锁不常见；通常获取锁的线程，也对释放该锁负责，这让推断正确性更容易。对于context切换，打破这个习惯是必要的，因为在执行swtch时，p->lock保护进程状态和context属性的不变性。可以发现问题的一个例子：如果p->lock在swtch期间没持有：一个不同CPU可能在yield设置其状态为RUNNABLE后决定执行进程，但之前的swtch导致它停止使用它自己的kernel stack。结果是两个CPU运行在同一个栈上，这是不对的。
一个kernel线程总是在sched放弃它的CPU，总是切换到scheduler中相同位置，总是切换回之前调用sched的kernel thread。因此，如果在xv6切换线程处打印行号，可以看到下面简单形式：（kernel/proc.c:475），（kernel/proc.c509），（kernel/proc.c:475），（kernel/proc.c509）等等。两个线程之间样式化切换所在的程序有时称为coroutines；在本例中，sched和scheduler彼此互为coroutines。
有一种情况，scheduler对swtch调用后不会到sched。当新进程首次被调度时，它开始于forket(kernel/proc.c:527)。Forket存在是为了释放p->lock，否则新进程将起始于usertrapret。
scheduler（kernel/proc.c:457）执行一个简单循环：找一个进程执行，执行直到它yield。scheduler循环进程表找一个可以执行的进程，即p->state==RUNNABLE。一旦找到一个进程，它设置每个CPU当前进程变量c->proc，标记该进程为RUNNING，然后调用swtch来开始执行它（kernel/proc.c:470-475）。
考虑调度代码结构的一种方式是：它enforce一组进程的不变量，那些不变量not true时要持有p->lock。一个不变量是：如果一个进程是RUNNING，定时器中断的yield必须能够安全地从该进程切换。这意味着CPU寄存器必须持有进程的寄存器值（swtch还没有将他们移到context），c->proc必须指向该进程。另外一个不变性是：如果进程是RUNNABLE，一个idle CPU scheduler执行它必须是安全的。这意味着：p->context必须持有进程的寄存器（它们并非真正的寄存器），没有CPU在该进程kernel栈上执行，没有CPU的c->proc指向该进程。当持有p->lock时，看到这些属性通常是变化的。
保持上述不变性的原因是：xv6经常在一个线程中获取p->lock，然后再另外线程中释放，例如在yield中获取、在scheduler中释放。一旦yield已经开始更改执行进程的状态，让其为RUNNABLE，锁必须一直持有，直到不变性恢复：最早的正确释放点在scheduler（执行在它自己的栈上）清除c->proc之后。相似地，一旦scheduler开始转换一个RUNNABLE进程为RUNNING，锁不能被释放直到kernel thread执行完毕（swtch之后，例如yield）。
p->lock也保护其他：exit和wait之间相互作用，避免lost wakeups机制，避免一个进程退出和另外进程读写它的状态的竞争（例如，exit system call看p->pid并设置p->killed(kernel/proc.c:611)）。值得考虑：是否p->lock不同功能可以分开，为了清晰，也可能为了性能。

（四）Code：mycpu and myproc

xv6通常需要一个指针指向当前进程proc结构。在单处理器上，我们可以有一个全局变量指向当前proc。但这对多核机器不起作用，因为每个核执行一个不同的进程。解决此问题的方式是利用事实：每个核有它自己的一组寄存器；我们可以使用其中一个寄存器来帮我们找到每个核的信息。
xv6为每个CPU持有一个struct cpu（kernel/proc.h:22），记录进程当前运行所在CPU，为每个CPU scheduler thread保存寄存器，嵌入自旋锁（用来管理中断禁用）的数量。mycpu函数（kernel/proc.c:60）返回一个指针到当前CPU的struct cpu。RISC-V对每个CPU编定一个hartid。在kernel时，xv6确保每个CPU的hartid存在CPU的tp寄存器。

这允许mycpu使用tp寄存器来索引一个cpu结构数组来找到正确的那个。
确保一个CPU的tp总是持有CPU的hartid有一点牵扯。mstart早在CPU启用时设置tp寄存器，处于机器模式（kernel/start.c:46）。usertrapret保存tp到trampoline page，因为用户进程可能更改tp。最终，从用户空间进入kernel时（kernel/trampoline.S:70），uservec恢复保存的tp。编译器保证从不使用tp寄存器。如果RISC-V允许xv6直接读取当前hartid是更方便的，但这仅在机器模式下被允许，不是在supervisor mode。
cpuid和mycpu的返回值是fragile：如果timer中断，导致线程yield，转移到一个不同的CPU，之前的返回值不再正确。为了避免这个问题，xv6需要调用者禁用中断，仅在使用完返回的struct cpu后才启用。
函数myproc（kernel/proc.c:68）返回struct proc指针（指向当前CPU上运行的进程）。myproc禁用中断，调用mycpu，从struct cpu获取当前进程指针（c->proc），然后开启中断。myproc的返回值是可以安全使用的，即使中断启用了：如果定时器中断将调用进程转移到不同的CPU上，struct proc指针仍然是同一个。

（五）Sleep and wakeup

调度和锁帮助明确了一个进程与另外一个进程的存在，但至今为止我们没有抽象（有意地帮助进程交互）。一些机制已经创造出来用于解决这个问题。xv6使用sleep和wakeup，允许一个进程sleep等待一个event，一旦event发生另外一个进程来唤醒等待进程。sleep和wakeup通常称作sequence coordination或conditional synchronization机制。
为了解释，让我们考虑一个同步机制称为semaphore（协调生产者和消费者）。一个semaphore有一个计数和两个操作。V操作（生产者）增加计数。P操作（消费者）等待直到计数非0，然后减少它并返回。如果仅有一个生产者thread、一个消费者线程，它们在不同CPU上执行，编译器不会过分激进地优化，这个实现是正确的：

struct semaphore{
struct spinlock lock;
int count;
}

void V(struct semaphore *s){
acquire(&s->lock);
s->count += 1;
release(&s->lock);
}

void P(struct semaphore *s){
while(s->count == 0);
acquire(&s->lock);
s->count -= 1;
release(&s->lock);
}
上面的实现是昂贵的。如果生产者很少执行，消费者将花费大量时间在while循环中自旋，希望得到一个非0的计数。消费者的CPU可以找到更有效的工作方式，比起busy waiting（通过重复地polling s->count）。避免busy waiting需要一个方式（yield CPU、仅在V提升计数时恢复）用于消费者。
在该方向上有一个方法，尽管我们将发现它还不够。让我们想象一对调用，sleep和wakeup，它们如下工作。sleep(chan)在某个专门的值chan上sleep，称为wait channel。sleep让调用进程sleep，释放CPU来处理其他工作。wakeup(chan)唤醒在chan上sleeping的所有进程，致使它们的sleep调用返回。如果没有进程等在chan上，wakeup什么都不做。我们可以使用sleep和wakeup改变semaphore实现（改变黄色高亮）。
void V(struct semaphore *s){
acquire(&s->lock);
s->count += 1;
wakeup(s);
release(&s->lock);
}
void P(struct semaphore *s){
while(s->count == 0)
sleep(s);
acquire(&s->lock);
s->count -= 1;
release(&s->lock);
}
P现在放弃CPU而不是spinning，这很不错。然而结果是：使用这个接口设计sleep和wakeup并不容易，因为会遇到一个叫做lost wake-up问题。假设P发现s->count==0（在212行），当P处于212行和213行之间，V在另外一个CPU上执行：它改变s->count为非0，然后调用wakeup，发现没有进程sleeping，因此什么都不做。现在P继续执行213行：他调用sleep，然后sleep。这导致一个问题：P sleep等待一个V调用（他已经发生）。除非我们足够幸运，生产者再次调用V，否则消费者将一直等，尽管count是非0的。
问题的根源是：不变性（P仅会在s->count == 0时陷入sleep）被V恰好在某个错误时刻执行打破了。不正确的方式（保护不变性）改为移动锁获取（下面黄色高亮），以便于计数校验和它的sleep调用原子化。
void V(struct semaphore *s){
acquire(&s->lock);
s->count += 1;
wakeup(s);
release(&s->lock);
}
void P(struct semaphore *s){
acquire(&s->lock);
while(s->count == 0)
sleep(s);
s->count -= 1;
release(&s->lock);
}
一种期望是：这个版本的P可以避免lost wakeup，因为锁阻止V在313和314行之间执行。这实现了，但也死锁了：在sleep时P持有锁，因此V将一直阻塞等着获取锁。
我们将修复之前的方案，通过修改sleep的接口：调用方必须传递condition lock到sleep，因此它可以在调用进程被标记为sleep、等在sleep channel上 后释放锁。这个锁将强制并发V等待直到P已经结束 使其自身陷入睡眠，因此wakeup将找到sleeping消费者并唤醒它。一旦消费者再次唤醒，sleep在返回前重新获取锁。我们新的、正确的sleep/wakeup方案如下被使用（改变用黄色高亮）：
void V(struct semaphore *s){
acquire(&s->lock);
s->count += 1;
wakeup(s);
release(&s->lock);
}
void P(struct semaphore *s){
acquire(&s->lock);
while(s->count == 0)
sleep(s, &s->lock);
s->count -= 1;
release(&s->lock);
}
事实是：P持有s->lock阻止V尝试 在P校验c->count和调用sleep期间 唤醒它。注意，我们需要sleep自动释放s->lock并把消费进程sleep。

（六）Code：Sleep and wakeup

让我们看sleep的实现（kernel/proc.c:548）和wakeup(kernel/proc.c:582)。基本想法是：让sleep标记当前进程为SLEEPING，然后调用sched释放CPU；wakeup找到一个在给定wait channel上sleep的进程，将它标记为RUNNABLE。sleep和wakeup的调用者可以使用任意彼此方便的数字作为channel。xv6经常使用kernel数据结构（与等待相关）地址。
sleep获取p->lock（kernel/proc.c:559）。现在将要sleep的进程持有p->lock和lk。在调用者中持有lk是必要（例子中为P）：它确保没有其他进程（例子中，一个执行的V）可以调用wakeup(chan)。现在sleep持有p->lock，释放lk便是安全的：一些其他进程可能开始一个调用wakeup(chan)，但wakeup将等着获取p->lock，因此将等着直到sleep将进程置为sleep状态，保证wakeup不会错过sleep。
有一点复杂的地方：如果lk与p->lock是同一把锁，那么sleep会与其本身产生死锁（如果它尝试获取p->lock）。但如果调用sleep的进程已经持有p->lock，就无需做任何更多事来避免丢失一个并发的wakeup。当wait(kernel/proc.c:582)用p->lock调用sleep时，这种情况出现。
现在sleep持有p->lock，且没持有其他锁，可以通过记录sleep channel来让进程sleep，改变进程状态为SLEEPING，调用sched（kernel/proc.c:564-567）。这是清晰的：为什么p->lock不被release（通过scheduler）直到进程被标为SLEEPING后 是重要的。
在一些点，进程将获取condition lock，设置condition（sleeper正在等），并调用wakeup(chan)。当持有condition lock时wakeup被调用是重要的。wakeup循环基于进程表（kernel/proc.c:582）。它获取每个进程的p->lock，既因为可能操作进程的状态，也因为p->lock保证sleep和wakeup不会互相丢失。当wakeup发现一个进程处于SLEEPING状态，且有匹配的chan，它改变进程状态为RUNNABLE。下次scheduler执行，将会看到进程已经准备好运行了。
为什么sleep和wakeup的锁规则保证一个sleeping进程不会错过wakeup？sleeping进程要么持有condition lock，要么持有它自己的p->lock或两者都有，从检查condition之前的一个点到标记为SLEEPING之后的一个点。调用wakeup的进程在wakeup的循环里持有condition lock和process lock。因此waker要么在消费线程检查condition之前让condition为true；要么在标记为SLEEPING之后wakeup直接校验sleeping线程。wakeup将看到sleeping进程并唤醒它（除非其他线程先唤醒它）。
有时也有这种情况：多个进程在相同channel上执行；例如，不止一个进程从pipe上读。一个对wakeup的调用将把它们都唤醒。它们中的其中一个将首先执行，并获取锁（sleep使用的），在pipe的场景中，读取等在pipe中的任何数据。其他进程将发现，无论哪个被唤醒，没有数据会被读取。

如果sleep/wakeup意外地选择同一channel则无害：他们将看到虚假的wakeup，但上面描述的循环将容忍这个问题。sleep/wakeup的一些迷人之处为：轻量级（无需为sleep channel创建特殊数据结构）和提供一层间接（调用者无需知道它们在与哪个进程交互）。

（七）Code：Pipes

一个更复杂的、使用sleep和wakeup同步producers和consumers的例子是xv6 pipe的实现。我们在第一章看到pipes接口：被写到pipe一端的字节拷贝到kernel buffer中，然后可以从pipe另一端读出。未来章节将检查文件描述符（支持surrounding pipes），但现在让我们看pipewrite和piperead的实现。
每个pipe由一个结构体pipe表示，他包含一个lock和一个data buffer。属性nread和nwrite对读取、写入buffer的字节进行计数。buffer wraps around：buf[PIPESIZE-1]写入之后，下个字节写入到buf[0]。计数不会wrap。这个习惯让full buffer(nwritenread+PIPESIZE)和空buffer(nwritenread)区分开，但这意味着：buffer中的索引必须使用buf[nread%PIPESIZE]而不是buf[nread]（nwrite也相似）。
我们假设piperead和pipewrite调用同时发生在不同CPU上。Pipewrite(kernel/pipe.c:77)通过获取pipe锁开始，它保护计数、数据、以及相关不变性。Piperead（kernel/pipe.c:103）也尝试获取锁，但获取不到。它在acquire(kernel/spinlock.c:22)中自旋等待锁。当piperead等待时，pipewrite循环等待被写入的字节（addr[0…n-1]），轮流添加每个到pipe（kernel/pipe.c:95）。在这个循环中，buffer full会发生（kernel/pipe.c:85）。在这个情形，pipewrite调用wakeup来提醒任意sleeping readers，有数据等在buffer中或sleeps on &pi->nwrite，等待reader把一些字节从buffer中取出。Sleep释放pi->lock作为使pipewrite进程进入睡眠的一部分。
现在pi->lock是可用的，piperead获取它，进入它的critical section：它发现pi->nread != pi->nwrite(kernel/pipe.c:110)（pipewrite因为pi->nwrite == pi->nread+PIPESIZE(kernel/pipe.c:85)进入睡眠），它进入循环，从pipe拷贝数据（kernel/pipe.c:117），通过拷贝字节数提升nread。现在一些字节可用于写，因此piperead在它返回前调用wakeup(kernel/pipe.c:124)来唤醒任意sleeping writers。wakeup找到一个等在&pi->nwrite上的进程，正在执行pipewrite但因buffer满了而停止的进程。将该进程标记为RUNNABLE。
pipe代码为reader和writer使用单独的sleep channel（pi->nread和pi->nwrite）；这可能让系统在不可能事件（大量reader和writer在同一pipe上等待）更有效。pipe代码在循环中sleep，检查sleep condition；如果有多个reader或writer，但除了第一个进程外的进程会wakup看到condition false，再次进入sleep。

（八）Code：Wait，exit，and kill

Sleep和wakeup可以被用于多种等待。一个有趣的例子，在第一章中介绍的，child exit和parent wait之间的交互。当child消亡时，parent可能已经在wait中sleeping，或可能正在做其他事；在之后的场景中，之后对wait的调用必须看到child的消亡，可能是调用exit很久之后。xv6记录child的消亡直到wait看到exit让调用者陷入ZOMBIE状态，它保留直到parent的wait注意到它，改变child的状态为UNUSED，拷贝child的exit status，返回child的进程id到parent。如果parent在child之前退出，parent将child交给init进程，它永远调用wait；因此每个child有一个parent来clean up。主要实现挑战是：竞争可能、parent wait和child exit之间的死锁，以及exit和exit。
wait使用调用进程的p->lock作为condition lock来避免丢失wakeup，并且它在开始时获取该锁（kernel/proc.c:398）。然后它扫描进程表。如果它找到一个child是ZOMBIE状态，它释放该child的资源和它的proc结构，拷贝child的exit状态到wait提供的地址（如果值非0），返回child的进程id。如果wait找到children但都没有exit，那么调用sleep等待它们中的某个exit（kernel/proc.c:445），然后再次扫描。此处sleep中释放的condition lock是等待进程的p->lock，上面提到的特殊场景。注意，wait通常持有两个锁；在尝试获取child锁之前，它获取自己的锁；因此所有xv6必须遵从相同锁顺序（先parent后child），来避免死锁。
wait看每个进程的np->parent来发现它的children。它使用np->parent而没有持有np->lock，这违反通用规则，共享变量必须被锁保护。有可能np是当前进程的祖先，这种情况下获取np->lock可能导致死锁，因为违反上面提到的顺序。无锁检查np->parent在这种情况下看起来是安全的；一个进程的parent属性仅会被它的parent改变，因此如果np->parent==p是true，那么这个值不会改变，除非当前进程改变它。
exit(kernel/proc.c:333)记录exit status，释放一些资源，把children进程交给init进程，唤醒wait parent，标记调用者为zombie，永久yield CPU。最终序列有点棘手。当把它的状态设为ZOMBIE、唤醒parent时，exiting进程必须持有其parent的锁，因为parent lock是condition lock（保证wait不丢失wakeup）。child必须也持有它自己的p->lock，因为parent可能看到它的状态为ZOMBIE，在它正在执行时释放它。lock获取顺序对避免死锁是重要的：因为wait获取parent lock在child lock之前，exit必须以相同的顺序。
exit调用一个特殊的wakup函数，wakeup1，它仅唤醒parent，仅当parent在wait sleeping时（kernel/proc.c:598）。这可能看起来不正确：child在设置它的状态为ZOMBIE前唤醒parent，但这是安全的。尽管那wakeup1可能导致parent执行，但wait中的loop不能监测child，直到child的p->lock被scheduler释放，因此wait不能看到exiting进程，直到exit已经设置它的状态为ZOMBIE之后（kernel/proc.c:386）。
exit允许一个进程终止其本身，kill（kernel/proc.c:611）让一个进程请求另外进程终止。让kill直接销毁victim进程太过复杂，因为victim可能正在另外CPU上执行，可能处于敏感序列：更新kernel数据结构之中。因此kill做地非常少：它仅仅设置victim的p->killed然后唤醒它（若它正在sleeping）。最终victimi将进入或离开kernel，在该代码处若p->killed被设置，则usertrap将调用exit。如果victim运行在用户空间，它将很快通过system call或因为timer（或其他）中断进入kernel。
如果victim进程是sleep状态，kill对wakeup的调用将导致victim从sleep中返回。有个潜在危险：因为等待的条件可能非true。xv6对sleep的调用总是包裹在while循环中，在sleep返回后重新测试条件。一些对sleep的调用也在循环中测试p->killed，如果它被设置了则放弃当前活动。只有在这种放弃是正确的情况下才会这么做。例如：若killed标志位设置了，pipe读、写代码返回；最终代码将返回到trap，将再次检测flag并退出。
一些xv6 sleep循环没有检测p->killed，因为代码在多步system call（应该是原子的）之中。virtio驱动（kernel/virtio_disk.c:242）是一个例子：它没有检查p->killed，因为disk操作可能是一组写（都需要以一个顺序，来保证文件系统以正确状态存在）中的一个。一个等待disk I/O的被killed进程不会exit，直到它完成当前system call，usertrap看到killed标志位。

（九）现实世界

xv6 scheduler实现一个简单的调度策略，轮流执行每个进程。这个策略称为round robin。实际操作系统实现更复杂的策略，例如，允许进程有优先级。这个主意是：一个可执行高优先级进程比一个可执行低优先级进程被scheduler更倾向。这些策略会很快变得复杂，因为通常有计算目的：例如，操作可能想保证公平和高吞吐。另外，复杂策略可能导致无意识地交互，例如优先级反转和convoys。当低优先级和高优先级进程共享一个锁时，优先级反转会发生，低优先级进程获取到锁会阻止高优先级进程执行。当一些高优先级进程等待低优先级进程（获取到一个共享锁）时，一个等待进程long convoy会形成。一旦convoy形成，它会存在很长时间。为了避免这些问题，额外机制在复杂scheduler中是必须的。
sleep和wakeup是一个简单、有效的同步方法，但也有一些其他方法。它们中的首个挑战是：章节开始看到的避免lost wakeup问题，。原始Unix kernel的sleep简单地禁用中断，它是足够的，因为unix运行在单CPU系统上。因为xv6运行在多处理器上，它添加一个明确的锁到sleep。FreeBSD的msleep采取同样方法。Plan 9的sleep用一个回调函数（在进入sleep前，持有scheduling lock执行）；该函数可作为sleep condition的最后一分钟检查，来避免lost wakeup。linux kernel的sleep使用一个明确的进程队列，称为等待队列，而不是一个wait channel；队列有它自己内部的锁。
wakeup扫描整个进程表找一个匹配chan是低效的。更好的方案是：用一个数据结构（持有睡在该结构上的进程表）取代sleep和wakeup中的chan，例如linux的等待队列。Plan 9的sleep和wakeup称该结构为rendezvous point或Rendez。一些线程库参考同样的结构作为一个condition变量；在该场景中，操作sleep和wakeup称为wait和signal。所有这些机制共享同一个观点：sleep condition被一些锁保护，在sleep中原子删除。
wakup实现唤醒所有进程（等待在特殊channel），也可能是：一些进程等待该特殊channel。操作系统将schedule所有这些进程，然后它们将竞争检查sleep condition。以这种方式表现的进程有时称为thundering herd，且它最好被避免。绝大多数condition变量对wakeup有两个原始属性：signal，唤醒一个进程，broadcast，唤醒所有等待进程。
semaphore通常被用作同步。计数通常根据类似pipe buffer的可用字节数目或进程拥有的僵尸children数量。使用一个明确的计数作为抽象的一部分，避免lost wakeup问题：有一个明确的计数：已经发生wakeup的次数。计数也避免spurious wakeup和thundering herd问题。
终止进程和清理它们给xv6引入了一些复杂性。在绝大多数操作系统，这是更复杂，因为，例如，victim进程可能陷入kernel处于sleeping，解开它的栈需要更小心的编程。一些操作系统使用明确的异常处理机制解开栈，例如longjmp。另外，有另外一些事可用让一个sleeping进程被唤醒，即使等待的事件还没发生。例如，当unix进程正在sleeping，另外一个进程可能向它发送一个signal。在这种情况下，进程将从被中断的system call处返回-1，并把该错误码设到EINTR。应用可以检测这些值，决定做什么。xv6不支持signal，这个复杂性不会出现。
xv6对kill的支持并非完全满足：有些sleep循环可能应该检查p->killed。一个相关问题是：即使是sleep循环检查p->killed，sleep和kill之间也会有竞争；设置p->killed、尝试唤醒victim，在victim循环检查p->killed之后、调用sleep之前。如果这个问题发生，victim将不会注意到p->killed直到等待的condition发生。这可能是相当久之后（例如，当virtio驱动返回一个victim正在等待的disk block），或者从不（例如，如果victim等待控制台输入，但用户不会敲任何输入）。
一个实际操作系统会用一个明确的free list，以常量时间而非线性时间在allocproc中查找，找到free proc结构；xv6使用简单使用线性扫描。

八、File system

介绍

文件系统的目的是组织和存储数据。文件系统通常支持用户之间、应用之间共享数据，以及持久化（数据在重启后仍然可用）。
xv6文件系统提供类Unix文件、目录、路径（见章节一），并在virtio硬盘上存储其数据用于持久化（见章节四）。文件系统解决了几个挑战：
文件系统需要磁盘数据结构，用于代表命名目录和文件树，用于记录block（持有每个文件的内容）标识，用于记录硬盘哪块区域是空闲的。
文件系统必须支持crash recovery。如果crash（例如断电）发生，重启后文件系统必须仍然正常工作。风险是：crash可能中断更新序列，导致磁盘数据结构不能保持一致性（例如，一个block既被用在一个file中，又被标记为空闲的）。
不同进程可以同时操作文件系统，因此文件系统代码必须协调保证不变性。
访问磁盘比访问内存慢很多，因此文件系统必须保持常用block的内存缓存。
本章节其余部分解释，xv6如何应对这些挑战。

（一）总览

xv6文件系统实现以7层组织起来，如图8.1所示。disk层基于virtio hard drive读写block。buffer cache层缓存硬盘block、同步访问它们，确保对于任意给定block：同一时刻仅有一个内核进程可以更改数据存储。logging层允许更高的层将多个block的更新放到一个事务里，确保面对crash时blocks会原子更新（例如，所有都被更新或都没被更新）。inode层提供单个文件，每个被表示为拥有唯一数字i的inode，且一些blocks持有文件数据。directory层实现每个目录作为一个特殊类型的inode（其内容是一系列目录入口，每个包含一个文件名和数字i）。pathname层提供层级路径名，如/usr/rtm/xv6/fs.c，并用递归查询解析它们。file descriptor层用文件系统接口对一些Unix资源（例如pipes、devices、files等等）进行抽象，简化应用程序员使用。

文件系统必须有计划：在磁盘哪里存inodes和content blocks。为了做到，xv6将磁盘分为几段，如图8.2所示。文件系统不会使用block0（它持有boot sector）。block 1称为superblock；它包含文件系统的metadata（文件系统有多少blocks，数据blocks数量、inodes数量、log中blocks数量）。持有log的blocks从2开始。在log后是inodes，每个block有多个inodes。之后是bitmap blocks，跟踪正在使用的数据block。剩下的blocks是数据block；每个要么在bitmap block中被标记为空闲的，要么持有一个文件或目录的内容。superblock通过一个单独的程序填充，称为mkfs，它构建一个初始化文件系统。

（二）Buffer cache layer

Buffer cache有两个任务：（1）同步访问磁盘块来确保内存中只有一个block拷贝，且某一时刻，仅有一个内核线程在使用该拷贝；（2）缓存常用block，以致于它们无需从slow硬盘中再次读取。代码在bio.c。
buffer cache输出的主要接口包括bread和bwrite；前一个获取一个buf（包含一个block拷贝，可以在内存中读、改），后者写一个更改的buffer到磁盘对应的block。当使用完buffer时，内核线程必须通过调用brelse释放buffer。buffer cache使用一个per-buffer sleep-lock来确保，某一时刻只有一个线程使用每个buffer（每个disk block）；bread返回一个加锁的buffer，brelse释放该锁。
让我们回到buffer cache，buffer cache有固定数量的buffer来保存disk blocks，这意味着如果文件系统请求一个不在cache中的block，buffer cache必须回收当前持有其他block的一个buffer。buffer cache回收least recently used buffer用于新block。假设是：least recently used buffer是最不可能在短期内再次被使用的。

（三）Code：Buffer cache

buffer cache是一个buffer双向链表。函数binit，由main调用（kernel/main.c:27），用静态数组buf中NBUF个buffers初始化这个链表（kernel/bio.c:43-52）。所有其他对buffer cache（指向链表）的访问通过bcache.head，并非buf array。
buffer有两个与其相关的状态字段。字段valid表示buffer包含一个block拷贝。字段disk表明buffer内容已经传递给磁盘，这会改变buffer（例如，写磁盘数据到data）。
bread（kernel/bio.c:93）调用bget对给定sector给一个buffer（kernel/bio.c:97）。如果buffer需要从磁盘读取，在返回buffer之前，bread调用virtio_disk_rw来实现。
bget(kernel/bio.c:59)扫描buffer list，找到一个是给定设备和sector编号的buffer（kernel/bio.c:65-73）。如果有这么一个buffer，bget对该buffer获取sleep-lock。bget返回locked buffer。
如果对于给定sector没有cached buffer，bget必须制作一个，可能重用一个buffer（持有一个不同的sector）。再度扫描buffer list，找到一个没在使用的buffer（b->refcnt = 0）；任何这种buffer都可以被使用。bget编辑buffer metadata来记录新设备、sector编号、并获取它的sleep-lock。注意：赋值语句b->valid = 0，确保bread将从磁盘读取block数据，而不会错误地使用buffer之前的内容。
这是很重要的：每个磁盘sector最多一个cached buffer，为了确保读者看到writes，也因为文件系统使用buffer上的锁进行同步。bget通过持有bache.lock确保不变性，从第一个循环：检验block是否被缓存，第二个循环：block被缓存（通过设置dev，blockno，refcnt）。这使得block存在的校验、让buffer持有block的设计是原子的。
在bcache.lock critical section之外获取buffer的sleep-lock对bget来说是安全的，因为b->refcnt非0阻止buffer因一个不同的disk block被重用。sleep-lock保护块缓存内容的读、写，而bcache.lock保护有关缓存哪些blocks的信息。
如果所有buffers是繁忙的，那么过多进程同时执行文件系统调用；bget崩溃。一个更优雅的响应可能是：sleep直到一个buffer变为free，尽管有死锁可能。
一旦bread已经读了disk，并返回buffer到它的调用者，调用者单独使用buffer、并可以读写数据字节。如果调用者更改buffer，必须在释放buffer之前，调用bwrite来把改变的数据写到磁盘。bwrite（kernel/bio.c:107）调用virtio_disk_rw来与磁盘硬件通信。
当调用者处理完buffer时，必须调用brelse来释放它。（brelse，是b-release的缩写，它是神秘但值得学习的：它起源于Unix、也用于BSD、Linux、Solaris）。brelse（kernel/bio.c:117）释放sleep-lock，将buffer移到链表最前端（kernel/bio.c:128-133）。移动buffer，导致链表因buffer被使用（意味着释放）而排序：链表第一个buffer是最近被使用的，最后一个是最久被使用的。bget中的两个循环利用这个：扫描一个已存在的buffer，最坏情况下必须处理整个list；当有好的参考位置时，检查最近被使用的buffers（始于bcache.head，跟着next指针）会减少扫描时间。扫描抓取一个buffer来重新使用，通过从后向前扫描（跟着prev指针），抓取最久被使用的buffer。

（四）Logging layer

文件系统设计中最感兴趣的问题之一是：crash recovery。因为一些文件系统操作包括对磁盘多写，会出现问题，一部分写之后的崩溃会让磁盘文件系统处于不一致状态。例如，假设崩溃在文件删除时发生（设置文件长度为0，释放它的内容blocks）。根据磁盘写的顺序，崩溃要么会让一个inode指向一个content block（被标记为free），要么留下一个已分配但没有被引用的content block。
后者是相对和善的，但一个指向freed block的inode，可能在重启后导致严重问题。重启后，kernel可能分配该block给另外的文件，现在我们有两个不同的文件，非有意地指向同一个block。如果xv6支持多用户，这个情况会是一个安全问题，因为旧文件的拥有者可以读写新文件（另外一个用户拥有）的blocks。
xv6解决文件系统操作期间的崩溃问题，用一个简单的形式logging。xv6 system call不会直接写磁盘文件系统数据结构。取而代之，它将所有期望的磁盘写入描述放到磁盘的一个log中。一旦system call已经记录了它的所有写入，它写一个特殊的commit记录到磁盘，表明：log包括一个完整的操作。此后system call拷贝写入到磁盘文件系统数据结构。在那些写入完成后，system call擦除掉磁盘上的log。
如果系统应该崩溃并重启，文件系统代码从崩溃中恢复如下，在执行任意进程之前。如果log被标记为包含一个完整的操作，那么恢复代码会把写入拷贝到磁盘文件系统中它们所属的地方。如果log没有被标记为包含一个完整操作，恢复代码会忽略这个log。恢复代码通过擦除这个log结束。
为什么xv6的log解决了文件系统操作之间的崩溃问题？如果崩溃在操作提交之前发生，那么磁盘上的log不会被标记为完成，那么恢复代码将会忽略它，磁盘状态将会就像操作还没开始。如果crash发生在提交操作后，那么recovery将replay所有写入操作，可能重复，如果操作已经开始写它们到磁盘数据结构。另外一个情况，log让操作对于crash原子化：recovery后，要么所有写入操作出现在磁盘上，要么都不会出现。

（五）Log design

log搁置在一个已知的固定位置，明确在superblock中。它包含一个header block，跟着一系列updated block（“logged blocks”）。header block包含一组sector编号（每个logged block一个编号）和log blocks的数量。磁盘上header block中的数量要么是0，表明log中无事务，要么非0，表明log包含一个完整的已提交事务（有logged blocks的明确编号）。当一个事务提交时（而非提交之前），xv6写header block，拷贝logged blocks到文件系统后，将计数设为0。因此一个crash发生在事务期间将导致log header block中计数为0；crash发生在提交之后，将导致计数非0。
每个system call代码都表明写入序列的开始和结束，对于崩溃，写入序列必须是原子的。为了允许不同进程并发执行文件系统操作，logging system可以累计多个system call写入到一个事务。因此单个提交可以包含多个完整system call写入。为了避免一个system call分离在多事务中，logging system仅会在无文件系统system call在执行时提交。
一次提交多个事务的想法被称为group commit。group commit减少磁盘操作次数，因为它将一次commit的开销分摊到多个操作上。group commit也让磁盘可以同时处理更多并发写入，可能允许硬盘在一次硬盘rotation期间全部写入。xv6的virtio驱动不支持这种批处理，但xv6的文件系统设计允许。
xv6指明磁盘上固定量的空间来保存log。一个事务中system calls写入的blocks总数必须适合该空间。这有两个结果。单个system call不被允许写 比log空间 更多的blocks。这对绝大多数system call不算问题，但有两个可能潜在地写多个blocks：write和unlink。一个大文件写可能写多个data blocks、多个bimap blocks、一个inode block；unlinking一个大文件，可能写多个bitmap blocks和一个inode。xv6的写system call将large writes分为多个更小的写（适合log），unlink不会引发问题，因为实际中，xv6文件系统仅使用一个bitmap block。其他有限log空间结果是：logging系统不会允许一个system call开始，除非system call的写入适合log中剩余的空间。

（六）Code:logging

在system call中通常使用log方式为：

begin_op();
…
bp = bread(…);
bp->data[…] = …;
log_write(bp);
…
end_op();
begin_op(kernel/log.c:126)等待，直到logging system当前没有提交，直到有足够unreserved log space来保存此次调用的写入。log.outstanding对已经预留log space的system call进行计数；所有reserved space是log.outstanding 乘 MAXOPBLOCKS。提升log.outstanding既提升reserve space，也阻止提交在此system call期间发生。代码保守地假设每个system call可能写MAXOPBLOCKS个blocks。
log_write(kernel/log.c:214)作为一个bwrite代理。它在内存中记录block的sector编号，在磁盘log上预留一个slot，钉住block cache中的buffer，防止被从block cache中删除。block必须放在cache中直到提交：到那时，缓存的拷贝是仅有的更改记录；它不会被写到磁盘的位置上，直到commit之后；同一事务中的其它读必须能看到更改。
log_write注意到：一个事务中，一个block中被写多次时，给该block在log上分配同一slot。这个优化，通常被称作absorption。这是常见的，例如，某个磁盘block包含多个文件的inodes，一个事务中被写多次。通过吸收多个磁盘写到一个，文件系统可以节省log空间，可以实现更好的性能，因为只有一个dick block拷贝被写到磁盘。
end_op(kernel/log.c:146)首先减少outstanding system calls计数。如果计数现在是0，它通过调用commit()提交当前事务。这个过程有四步。write_log()(kernel/log.c:178)拷贝每个block（事务中更改过）从buffer cache到磁盘log的slot上。write_head()(kernel/log.c:102)将header block写到磁盘；这是一个提交点，写入之后崩溃会导致recovery 对log中的事务写进行replay。install_trans(kernel/log.c:69)从log读取每个block，并把它写到文件系统正确位置。最终end_op将log header的计数设为0；这发生在下个事务开始写logged blocks之前，因此崩溃不会导致recovery使用这种事务的header（仅有事务部分logged blocks）。
recovery_from_log(kernel/log.c:116)由initlog（kernel/log.c:55）调用，initlog由fsinit(kernel/fs.c:42)调用（在重启期间，第一个用户进程执行之前（kernel/proc.c:539））。它读取log header，如果header表明log包含一个已提交的事务，那么它会模拟end_op方法。
一个使用log的例子，发生在filewrite(kernel/file.c:135)。事务看起来如下：
begin_op();
ilock(f->ip);
r = writei(f->ip, …);
iunlock(f->ip);
end_op();
此代码包裹在循环中，将large write打断为单个事务（每次只有几个sectors），避免了log溢出。writei调用写多个blocks作为此事务的一部分：文件inode，一个或多个bitmap blocks，一些data blocks。

（七）Code:Block allocator

文件和目录内容存储在disk blocks，这必须从一个free pool中被分配。xv6的block分配器在disk上持有一个free bitmap，每个block一个bit。0 bit表明对应block是free；1 bit表明block被使用着。程序mkfs设置boot sector、superblock、log blocks、bitmap blocks对应的bits。
block分配器提供两个函数：balloc分配一个新disk block，bfree释放一个block。balloc循环consider每个block，起始于block 0到sb.size，文件系统中blocks编号。它查找一个block，看其bitmap bit为0，表明它是空闲的。如果balloc找到这么一个block，它更新bitmap、并返回该block。为了效率，循环被分为两部分。外循环读取每个block的bitmap bits。内循环检查单个bitmap block中所有BPB位。如果两个进程尝试同时分配一个block，竞争可能发生会被此事实阻止：buffer cache某一时刻仅让一个进程使用某个bitmap block。
bfree(kernel/fs.c:90)找到对应的bitmap block，并将对应bit清0。再次，bread和brelse隐式声明的互斥使用避免了明确锁的需要。
正如描述在本章其余代码中的一样，balloc和bfree必须被在一个事务中调用。

（八）Inode:layer

术语inode可以有两个相关含义之一。它可能指磁盘数据结构（包含一个文件的尺寸和data block编号列表）。或者，inode可能指一个内存inode，包含一个磁盘inode的拷贝以及kernel需要的额外信息。
磁盘inodes被打包在一个连续磁盘区域，称为inode blocks。每个inode同样尺寸，所以它是简单的，给定一个序号n，找出磁盘第n个inode。实际上，这个序号n，被称为inode编号或i-number，是inode标识的实现。
磁盘inode定义为struct dinode(kernel/fs.h:32)。type属性区分文件、目录、特殊文件（设备）。type为0表明磁盘inode为空闲的。nlink属性记录指向此inode的目录入口数量，为了标明磁盘inode和它的data blocks何时该被释放。size属性记录此文件内容字节数。addrs数组记录 持有文件内容的磁盘block的block编号。
kernel将一组活跃inodes放在内存中；struct inode（kernel/file.h:17）是磁盘struct dinode在内存中的拷贝。kernel存储一个inode在内存，仅当有C指针指向该inode。ref属性记录C指针指向内存inode的数量，kernel在reference计数降到0时，从内存中丢弃inode。iget和iput函数获取和释放一个inode的指针，更改reference计数。到某个inode的指针可以来自文件描述符，当前工作目录，暂存kernel code例如exec。
在xv6 inode代码中有四个锁或类锁机制。icache.lock保护不变性：一个inode在cache中最多只有一个；缓存inode ref属性，记录内存中指向缓存inode的指针数量。每个内存inode有一个lock属性，保护一个sleep-lock，确保互斥访问inode的属性（例如文件长度）、inode文件或目录内容blocks。一个inode ref，如果它大于0，导致系统在cache中持有inode，并且不会重用该cache entry为一个不同的inode。最终，每个inode包含一个nlink属性（在磁盘上，如果它被缓存则拷贝在内存中），记录指向该文件的directory entries数量；xv6不会释放该inode，如果它的link计数大于0。
struct inode指针由iget返回，保证有效直到对应调用iput。inode不会被删除，且该指针指向的内存不会被一个不同的inode重用。iget()提供一个非互斥访问某inode，因此可以有多个指针指向同一inode。文件系统代码许多部分依赖iget()行为，既长期持有inode引用（如打开文件和当前目录），阻止竞争，避免操作多inodes引发的死锁（例如pathname查询）。
iget返回的struct inode可能没有任何有用的内容。为了确保它持有磁盘inode拷贝，代码必须调用ilock。这锁住该inode（因此没有其他进程可以ilock它），并从磁盘读取该inode，如果它尚未被读取。iunlock释放该inode的锁。从locking中单独获取inode指针帮助避免一些情况下的死锁，例如在目录查找期间。多进程可以通过iget返回，持有一个指向inode的C指针，但某一时刻仅一个进程可以锁住该inode。
inode cache仅会缓存inodes。它的主要工作是同步多进程访问；缓存是次要的。如果一个inode被经常使用，bufffer cache将可能把它保存在内存中，如果它没有被inode cache持有。inode cache是write-through，意味着：更改cached inode的代码，必须立即用iupdate写到磁盘。

（九）Code:inodes

分配一个新inode（例如，创建一个文件），xv6调用ialloc(kernel/fs.c:196)。ialloc与balloc相似：它循环磁盘inode结构，一次一个block，查看标记为free的block。当找到一个后，它通过写新type到disk来认领，调用iget（kernel/fs.c:210）从inode cache中返回一个entry。ialloc正确操作依赖事实：某一时刻只有一个进程持有bp的引用，ialloc可以确保，其他进程不能同时看到该inode可用并认领它。
iget（kernel/fs.c:243）遍历inode cache找一个可用entry（ip->ref>0），有一致的device和inode编号。如果找到了，返回一个指向该inode的新引用（kernel/fs.c:252-256）。正如iget扫描，它记录第一个空slot位置（kernel/fs.c:257-258），如果需要分配一个cache entry，它会被使用。
在读/写inode元数据或内容之前，代码必须使用ilock锁住它。为了这个目的，ilock（kernel/fs.c:289）使用一个sleep-lock。一旦ilock互斥访问该inode，如果需要的话，它从磁盘读取inode（更可能是buffer cache）。函数iunlock（kernel/fs.c:317）释放sleep-lock，可以导致睡眠进程被唤醒。
iput（kernel/fs.c:333）通过减少引用数量（kernel/fs.c:356），释放一个指向inode的C指针。如果这是最后的引用，inode cache中inode的slot现在是空闲的，可以被一个不同inode重用。
如果iput看到：没有C指针指向某个inode，没有links指向该inode（发生在无目录），那么inode和它的数据blocks必须被释放。iput调用itrunc来截取文件到0字节，释放data blocks；设置inode type为0（未分配）；并写inode到磁盘（kernel/fs.c:338）。
iput中的锁协议（释放inode）值得仔细看看。一个风险是：一个并发线程可能正等在ilock中，为了使用这个inode（例如，读文件或list目录），并且不会发现该inode不再是已分配。这不会发生，因为system call无法获取一个指针指向cached inode，如果没有links指向它、ip->ref为1。该引用被调用iput的线程拥有。其他主要风险：一个ialloc并发调用可能选择一个，与iput正在释放的同一inode。这仅会在iupdate写磁盘后发生，因此inode有type 0。这个竞争是善良的；分配线程将礼貌地等待获取inode的sleep-lock，在读写inode之前，此时iput已经处理完了。

（十）Code:Inode content

磁盘inode结构，struct dinode，包含一个尺寸和一个block编号数组（见图8.3）。inode data可以在dinode addrs数组列出的block中找到。前面NDIRECT个数据blocks列在数组NDIRECT个入口中。这些blocks称为direct blocks。接下来NINDIRECT个数据blocks并非列在inode中，而是在一个数据块中，称为indirect block。数组addrs中最后一个入口给出indirect block的地址。因此文件前12KB（NDIRECTBSIZE）可以从inode中列出的blocks中加载。然而下个256KB（NINDIRECTBSIZE）字节仅可以在consulting indirect block之后加载。这是一个好的磁盘代表，但对clients来说却是复杂的。函数bmap管理代表，以便于高级方式，例如readi和writei，我们很快会看到。bmap返回inode ip第bn个数据块的磁盘块号。如果ip尚没有这个block，bmap分配一个。

函数bmap（kernel/fs.c:378）首先瞄准简单情形：首先NDIRECT个blocks列在inode自身中（kernel/fs.c:383-387）。然后NINDIRECT blocks列在indirect block(写在ip->addrs[NDIRECT])。bmap读取indirect block（kernel/fs.c:394），然后从block正确位置读取block编号（kernel/fs.c:395）。如果block编号超出NDIRECT+NINDIRECT，bmap崩溃；writei包括这个检查，防止这个发生（kernel/fs.c:490）。

bmap按需分配blocks。ip->addrs[]或indirect entry为0表明没分配block。当bmap遇到0时，它用新blocks取代它们，有需要就分配（kernel/fs.c:384-385）（kernel/fs.c:392-393）。

itrunc释放文件的blocks，重置inode的尺寸为0。itrunc（kernel/fs.c:410）以释放direct blocks开始（kernel/416-421），然后是列在indirect block（kernel/fs.c:426-429）中的，最后是indirect block本身（kernel/fs.c:431-432）。

bmap让readi和writei获取inode数据变得简单。readi（kernel/fs.c:456）通过确认偏移和计数没有超过文件末尾开始。起始位置超过文件末尾的read返回一个错误（kernel/fs.c:461-462），然而结束位置超过文件末尾的读比请求返回更少的字节（kernel/fs.c:463-464）。主循环处理文件每个block，从buffer复制数据到dst（kernel/fs.c:466-474）。writei（kernel/fs.c:483）与readi相同，有三个异常：起始于或穿过文件末尾的写增长文件，直到最大文件尺寸（kernel/fs.c:490-491）；循环拷贝数据到buffer而不是out；如果写拓展了文件，writei必须更新它的尺寸（kernel/fs.c:504-511）。

readi和writei都是通过检查ip->type == T_DEV起始。这种情况处理特殊设备（它的数据不在文件系统）；我们将在文件描述符layer返回到这种情形。

函数stati（kernel/fs.c:442）复制inode元数据到stat结构，它通过stat system call暴露给用户程序。

（十一）Code:directory layer

目录内部实现，犹如文件。它的inode有类型T_DIR，且它的数据是一系列目录入口。每个入口是struct dirent（kernel/fs.h:56），它包含一个name和一个inode编号。name最多DIRSIZ（14）个字符；如果更短，它以NULL（0）字节结尾。inode编号为0的目录入口表示空闲。

函数dirlookup(kernel/fs.c:527)在目录中找一个 给定名称 入口。如果它找到一个，它返回一个对应inode指针，解锁，设置poff为该目录中入口偏移字节数，在这种情况下调用者想编辑它。如果dirlookup发现一个有对应名称的入口，它更新poff并通过iget返回一个未解锁的inode。dirlookup是iget返回未解锁inode的原因。调用者已经锁住dp，因此如果lookup是.，当前目录别名，在返回前尝试锁住inode，会尝试重新锁dp并产生死锁。（有更复杂的包括多进程的死锁场景，…是父级目录的别名；.并非仅有的问题。）调用者可以解锁dp，然后锁住ip，确保某一时刻仅持有一把锁。

函数dirlink（kernel/fs.c:554）用给定名称和inode编号，在目录dp写一个新目录入口。如果明长城已经存在，dirlink返回一个错误（kernel/fs.c:560-564）。主循环读取目录入口，查找一个未分配的入口。当它找到一个，它早早地停止循环（kernel/fs.c:538-539），将off设置为可用入口的偏移量。否则，循环以off设置为dp->size结束。dirlink接下来添加一个新入口到目录，通过在偏移量off处写（kernel/fs.c:574-577）。

（十二）Code:Path names

路径名称查询包含连续的dirlookup调用，每次调用对应每个路径组件。namei（kernel/fs.c:661）评估path，并返回对应inode。函数nameiparent是一个变种：它在最后一个元素之前停止，返回父级目录的inode，并拷贝最后元素到name。都调用通用函数namex来处理真正的工作。

namex（kernel/fs.c:626）首先决定路径求值开始的位置。如果路径以一个/起始，求值从根开始；否则，当前目录（kernel/fs.c:630-633）。然后它用skipelem来轮流考虑路径中每个元素。每次循环的迭代必须在当前inode ip中查看name。每次迭代开始，锁ip、检查它是否为一个目录。如果不是目录，查询失败（kernel/fs.c:636-640）。锁ip是必要的，并非因为ip->type会更改（它不会更改），而是因为ilock执行前，ip->type不能保证已经从磁盘加载。如果调用是nameiparent，且这是最后的路径元素，循环提前停止，正如nameiparent的定义；最终路径元素已经拷贝到了name，因此namex仅需要返回未锁定的ip（kernel/fs.c:641-645）。最终，循环通过使用dirlookup查找路径元素，通过设置ip=next(kernel/fs.c:646-651)为下次迭代做准备。当循环用尽path元素，它返回ip。

程序namex可能花费大量时间完成：它可能包含多个磁盘操作来读取inodes和目录blocks，用来pathname的目录遍历（如果它们不在buffer cache）。xv6小心地设计，以便于如果一个内核线程的namex调用被阻塞在磁盘I/O，另外一个内核线程查找一个不同的pathname可以并发处理。namex单独锁住路径中的每个目录，以便于不同目录的查询可以并行处理。

这个并发引入了一些挑战。例如，当一个内核线程正在查找一个pathname，另外一个内核线程可能正在通过unlink目录改变目录树。一个潜在的风险是，查询可能正在查找一个被另外内核线程删除的目录，且它的blocks已经被另外的目录或文件重用。

xv6避免这些竞争。例如，当在namex中执行dirlookup时，lookup线程持有目录的锁，且dirlookup返回一个使用iget获取的inode。iget提升inode的引用数量。仅在dirlookup接收到inode之后，namex才会释放目录的锁。
现在另外的线程可以从目录中unlink inode，但xv6不会删除inode，因为inode的引用数量仍然大于0。

另外的风险是死锁。例如，查询”.”时，next指向与ip一致的inode。在释放ip lock前锁next会导致死锁。为了避免这个死锁，namex在获取next锁之前，解锁目录。此处我们再次看到，为什么iget与ilock分离如此重要。

（十三）File descriptor layer

Unix接口一个较酷的方面是：Unix中绝大多数资源被表示为文件，包括设备，例如控制台、pipes、真正的文件。文件描述层是实现这种统一的层。

xv6给每个进程它自己打开的文件表，或文件描述符表，正如第一章看到的。每个打开文件被表示为struct file(kernel/file.h:1)，包含一个inode或pipe，加一个I/O偏移。每个open调用创建一个新打开文件（一个新struct file）：如果多进程各自打开相同文件，不同实例将有不同的IO偏移量。另一方面，一个单独的打开文件（相同struct file）可以在一个进程的文件表中出现多次，也可以出现在多进程的文件表中。当一个进程使用open打开文件，然后使用dup创建别名或使用fork与child共享它，这会发生。引用计数跟踪某个打开文件的引用数量。文件可以被打开用于读或写，或读写。readable和writable属性跟踪这。

系统中所有打开文件保存在一个全局文件表，ftable。文件表有函数用于分配一个文件（filealloc），创建一个引用复制（filedup），释放一个引用（fileclose），读写数据（fileread和filewrite）。

前三个是现在熟悉的形式。filealloc(kernel/file.c:30)扫描文件表，找一个无引用的文件（f->ref==0），然后返回一个新引用；filedup(kernel/file.c:48)提升引用计数；fileclose(kernel/file.c:60)减少计数。当文件计数到0时，fileclose根据type释放潜在pipe或inode。

函数filestat，fileread，filewrite实现文件stat，读和写操作。filestat(kernel/file.c:88)仅允许inodes调用stati。fileread和filewrite检查：操作被打开模式所允许，然后传递调用到pipe或inode实现。如果文件代表inode，fileread和filewrite使用I/O偏移作为操作偏移，然后提升它（kernel/file.c:122-123）(kernel/file.c:153-154)。pipes没有偏移概念。重新调用inode函数需要调用方处理锁（kernel/file.c:94-96）(kernel/file.c:121-124)(kernel/file.c:163-166)。inode锁有方便的副作用：读写偏移被自动更新，因此同一文件同时多写不能覆盖另外的数据，即使它们的写是交错的。

（十四）Code:System calls

低层提供的绝大多数system call实现是琐碎的（kernel/sysfile.c）。有少部分调用值得仔细看看。

函数sys_link和sys_unlink编辑目录，创建或移除inodes引用。它们是另外一个使用事务很好的例子。sys_link(kernel/sysfile.c:120)通过获取它的参数开始，两个字符串old和new（kernel/sysfile.c:125）。假设old存在且并非一个目录（kernel/sysfile.c:129-132），sys_link提升它的ip->nlink计数。然后sys_link调用nameiparent来找父级目录和new的最终path元素（kernel/sysfile.c:145），创建一个新目录entry指向旧inode（kernel/sysfile.c:148）。new的父级目录必须存在，且和已存在inode在同一设备：inode编号在某个磁盘上仅有一个单独的含义。如果这种错误发生，sys_link必须返回、减少ip->nlink。

事务简化实现，因为它需要更新多个磁盘block，但我们不得不考虑处理顺序。它们要么都成功，要么都失败。例如，没有事务，在创建link前更新ip->nlink，会让文件系统临时处于一个非安全状态，在两个操作期间发生崩溃会导致灾难。带有事务，我们无需担心这。

sys_link为一个已存在inode创建一个新名称。函数create(kernel/sysfile.c:242)为一个新inode创建一个新名称。它是三个文件创建system call的概括：带有O_CREATE标志位的open创建一个新原始file，mkdir创建一个新目录，mkdev创建一个新设备文件。像sys_link，create从调用nameiparent（获取父级目录的inode）开始。然后调用dirlookup检查是否名称已存在（kernel/sysfile.c:252）。如果名称存在，create的行为取决于哪个system call正在被使用：open在mkdir和mkdev有不同的语义。如果create是代表open（type==T_FILE）被使用的，并且存在的名称本身是一个常规文件，那么open把这当作成功，因此create does too（kernel/sysfile.c:256）。否则这是一个错误（kernel/sysfile.c:257-258）。如果名称不存在，create用ialloc（kernel/sysfile.c:261）分配一个新inode。如果新inode是一个目录，create用 . 和… 入口初始化它。最终，现在数据被正确初始化，create会把它link到父级目录（kernel/sysfile.c:274）。create，像sys_link，同时持有两个inode锁：ip和dp。不会产生死锁，因为inode ip是新分配的：系统中没有其他进程将持有ip的锁，然后尝试锁dp。

使用create，易于实现sys_open，sys_mkdir，sys_mknod。sys_open(kernel/sysfile.c:287)是最复杂的，因为创建一个新文件仅是它要做的一个小环节。如果open被传入O_CREATE标志位，它调用create(kernel/sysfile.c:301)。否则，它调用namei（kernel/sysfile.c:307）。create返回一个锁住的inode，但namei不会，因此sys_open必须锁住inode本身。这提供一个方便的地方来检查：目录仅被打开用于读，而没有写。假设inode是以这样那样的方式获取，sys_open分配一个file和file描述符（kernel/sysfile.c:325），然后填充到文件（kernel/sysfile.c:337-342）。注意，没有其他进程可以访问部分初始化的文件，因为它仅在当前进程表中。

在我们有文件系统之前，章节7检查pipes的实现。函数sys_pipe通过提供一个方式创建pipe对，连接文件系统实现。它的参数是一个指向两个整数空间的指针，它将记录两个新文件描述符。然后分配pipe，安装文件描述符。

（十五）Real world

现实操作系统中的buffer cache比xv6的复杂的多，但它服务相同的两个目的：缓存和同步访问磁盘。xv6的buffer cache类似unix v6的，用一个简单的LRU去除策略；有一些更复杂的可实现策略，每个适用于一些场景，但并非适用于其他场景。一个更有效的LRU缓存会去除链表，取而代之使用一个哈希表用于查找和一个堆用于URU移除。现代buffer cache通常和虚拟内存系统集成，来支持内存映射文件。

xv6的记录系统是低效的。提交不能用文件系统system calls并发进行。系统记录整个blocks，即使某个block中仅有几个字节被改变。它执行同步log写，每次一个block，每次可能需要一整个磁盘rotation time。真正的记录系统解决所有这些问题。

logging并非提供崩溃恢复仅有的方式。早期文件系统在重启期间使用一个scavenger（清理工）（例如unix fsck程序），来检查每个文件、目录、block、inode free list，查找且解析不一致性。对于大文件系统来说，清理会花费数小时，而且在某些情况下，无法以导致system call原子性保证解决不一致性。从log中恢复是更快的，并且让system call面对崩溃时是原子的。

xv6使用与早期UNIX，同样的基本磁盘层（inodes和directories）。这个方案多年来非常持久。BSD的UFS/FFS，以及linux的ext2/ext3使用同样的数据结构。文件系统层中最低效的部分是目录，再每次查询期间，它需要线性的扫描所有磁盘blocks。当目录仅仅几个磁盘块时，这是可行的，但对持有多文件的目录来说，这是昂贵的。微软windows的NTFS、MAC OS的HFS、Solaris的ZFS，只说这几个，实现目录作为blocks的磁盘平衡树。这是复杂的。但保证了log时间复杂度的目录查询。

xv6对于磁盘失败是单纯的：如果磁盘操作失败，xv6崩溃。这是否合理取决于硬件：如果操作系统位于特殊硬件（使用冗余掩盖磁盘失败）之上，可能操作系统很少看到错误，因此崩溃是合理的。另一方面，操作系统使用平常磁盘应该考虑失败，并更优雅地处理，因此某个文件中block的缺失不该影响其余文件系统的使用。

xv6需要文件系统安装在一个磁盘设备上，且不改变尺寸。大数据库和多媒体文件驱动存储要求更高，操作系统正在寻找方法：去除瓶颈：每个文件系统一个硬盘。这个基本方式是结合多个磁盘到一个逻辑磁盘。硬件方案如RAID仍然广受欢迎，但当前趋势是：尽可能以软件实现这个逻辑。这些软件实现通常有丰富的功能，通过匆忙地添加或移除磁盘，来扩展或缩小逻辑设备。当然，可以匆忙增长或缩小的存储层，需要可以同样做到的文件系统：xv6使用的inode blocks固定尺寸的数组，不能在这种环境下好好工作。将磁盘管理从文件系统中剥离可能是最简洁的设计，但两者之间最复杂的接口已经衍生出一些系统，如Sun的ZFS，用于结合它们。

xv6文件系统缺乏一些其他现代文件系统的特性；例如：它缺乏快照和增量备份。

现代Unix系统允许多种资源关联同一system call作为磁盘存储：named pipes、network connections、远程访问网络文件系统、监控和控制接口例如/proc。xv6并非在fileread和filewrie中使用if语句，调用函数指针来调用inode的调用实现。网络文件系统和用户级文件系统提供函数：把那些调用转为网络RPC、在返回前等待响应。