xv6 book Chapter7 中文翻译

〇、前言

本文是 xv6 book 第七章的翻译，以下将开始翻译。

一、（翻译）第七章 调度

任何操作系统可能会运行比计算机 CPU 数量更多的进程，因此需要一个计划来在这些进程之间进行 CPU 的时间共享。理想情况下，共享对于用户进程应该是透明的。常见的方法是通过将进程复用到硬件 CPU 上，为每个进程提供其拥有独立虚拟 CPU 的假象。本章将解释 xv6 如何实现这种复用。

7.1 复用

xv6 通过在两种情况下将每个 CPU 从一个进程切换到另一个进程来进行复用。首先，在进程等待设备或管道 I/O 完成、等待子进程退出或在睡眠系统调用中等待时，xv6 的睡眠和唤醒机制会进行切换。其次，xv6 定期强制进行切换，以处理长时间计算而不休眠的进程。这种复用创建了每个进程拥有独立 CPU 的假象，就像 xv6 利用内存分配器和硬件页表创造了每个进程拥有独立内存的假象一样。

实现复用面临一些挑战。首先，如何从一个进程切换到另一个进程？尽管上下文切换的思想很简单，但实现起来是 xv6 中一些最不透明的代码。其次，如何以对用户进程透明的方式强制切换？xv6 使用标准技术，使用定时器中断驱动上下文切换。第三，许多 CPU 可能同时在进程之间进行切换，需要一种锁定计划来避免竞态条件。第四，进程退出时必须释放其内存和其他资源，但进程本身无法全部完成这些工作，因为（例如）它无法在仍在使用内核栈时释放自己的内核栈。第五，多核机器的每个核心必须记住它正在执行的进程，以便系统调用影响正确的进程的内核状态。最后，睡眠和唤醒允许进程放弃 CPU 并等待事件的发生，并允许另一个进程唤醒第一个进程。需要小心以避免导致唤醒通知丢失的竞态条件。xv6 试图尽可能简单地解决这些问题，但最终产生的代码仍然很棘手。

图 7.1：从一个用户进程切换到另一个用户进程。 在此示例中，xv6 使用一个 CPU 运行 （因此有一个调度程序线程）

7.2 代码：上下文切换

图 7.1 概述了从一个用户进程切换到另一个的步骤：从旧进程的内核线程进行用户-内核转换（系统调用或中断）、切换到当前 CPU 的调度器线程、切换到新进程的内核线程，最后返回到用户级进程的陷阱返回。xv6 的调度器每个 CPU 都有一个专用的线程（保存的寄存器和堆栈），因为调度器在旧进程的内核栈上执行是不安全的：其他核心可能唤醒该进程并运行它，如果在两个不同的核心上使用相同的栈将是灾难性的。本节将研究在内核线程和调度器线程之间进行切换的机制。

从一个线程切换到另一个涉及到保存旧线程的 CPU 寄存器，并恢复新线程先前保存的寄存器；保存和恢复堆栈指针和程序计数器意味着 CPU 将切换堆栈并切换执行的代码。

函数 swtch 执行了内核线程切换的保存和恢复工作。swtch 并不直接了解线程；它只是保存和恢复被称为上下文的寄存器集。当一个进程需要释放 CPU 时，该进程的内核线程调用 swtch 来保存自己的上下文并返回到先前保存在进程的 struct proc 或 CPU 的 struct cpu 中的调度器上下文中。每个上下文包含在一个结构体 context 中（kernel/proc.h:2）。swtch 接受两个参数：struct context *old 和 struct context *new。它将当前寄存器保存在 old 中，从 new 加载寄存器，并返回。

让我们跟踪一个进程通过 swtch 进入调度器。在第 4 章中我们看到，中断结束时的一种可能性是 usertrap 调用 yield。yield 反过来调用 sched，sched 又调用 swtch 来保存当前上下文在 p->context 中，并切换到先前保存在 cpu->scheduler（kernel/proc.c:509）中的调度器上下文。

swtch（kernel/swtch.S:3）仅保存了被调用保存的寄存器；调用者保存的寄存器由调用的 C 代码保存在堆栈上（如果需要）。swtch 知道结构体 context 中每个寄存器字段的偏移量。它不保存程序计数器。相反，swtch 保存了 ra 寄存器，它保存了从中调用 swtch 的返回地址。现在 swtch 从新上下文中恢复寄存器值，这些值是由之前的 swtch 保存的。当 swtch 返回时，它返回到恢复的 ra 寄存器指向的指令，也就是新线程之前调用 swtch 的指令。另外，它返回到新线程的堆栈上。

在我们的例子中，sched 调用 swtch 切换到 cpu->scheduler，每个 CPU 的调度器上下文。该上下文是由 scheduler 的 swtch 调用（kernel/proc.c:475）保存的。当我们跟踪的 swtch 返回时，它返回到 scheduler 而不是 sched，并且其堆栈指针指向当前 CPU 的调度器堆栈。

7.3 代码：调度

上一节我们看了 swtch 的底层细节；现在让我们将 swtch 视作一个给定的函数，来研究从一个进程的内核线程通过调度器到另一个进程的切换。调度器以每个 CPU 一个特殊线程的形式存在，每个线程运行调度器函数。这个函数负责选择下一个要运行的进程。想要释放 CPU 的进程必须获取其自己的进程锁 p->lock，释放它持有的任何其他锁，更新自己的状态（p->state），然后调用 sched。遵循这一约定的有 yield（kernel/proc.c:515）以及稍后我们将要查看的 Sleep 和 Exit。sched 再次检查这些条件（kernel/proc.c:499-504），以及这些条件的含义：由于持有锁，中断应该被禁用。最后，sched 调用 swtch 将当前上下文保存在 p->context 中，并切换到 cpu->scheduler 中的调度器上下文。swtch 返回到调度器的堆栈，就像调度器的 swtch 已经返回一样。调度器继续 for 循环，找到一个要运行的进程，切换到它，循环重复。

我们刚刚看到，在调用 swtch 时 xv6 会持有 p->lock：调用 swtch 的调用者必须已经持有锁，并且控制权会传递给切换到的代码。这个约定在锁的使用上比较不寻常；通常获得锁的线程也负责释放锁，这样更容易推理正确性。对于上下文切换来说，必须打破这个约定，因为 p->lock 保护了进程状态和上下文字段上的不变量，而在 swtch 执行期间这些不变量是不成立的。如果在 swtch 执行期间没有持有 p->lock，可能会出现问题：在 swtch 使该进程停止使用自己的内核栈之前，另一个 CPU 可能会决定在 yield 将其状态设置为 RUNNABLE 之后运行该进程。结果将是两个 CPU 在同一个堆栈上运行，这是不正确的。

内核线程总是在 sched 释放 CPU，并始终切换到调度器中的同一个位置，这（几乎）总是切换到之前调用 sched 的某个内核线程。因此，如果打印出 xv6 切换线程的行号，会观察到以下简单的模式：(kernel/proc.c:475)，(kernel/proc.c:509)，(kernel/proc.c:475)，(kernel/proc.c:509)，以此类推。这种样式化地在两个线程之间切换的过程有时被称为协程；在这个例子中，sched 和 scheduler 是彼此的协程。

有一种情况下，调度器对 swtch 的调用并不会最终返回 sched。当首次调度一个新进程时，它会开始执行 forkret（kernel/proc.c:527）。forkret 的存在是为了释放 p->lock；否则，新进程可能会从 usertrapret 开始执行。

调度器（kernel/proc.c:457）运行一个简单的循环：寻找要运行的进程，运行它直到它放弃 CPU，然后重复这个过程。调度器遍历进程表，寻找一个可运行的进程，也就是具有 p->state == RUNNABLE 的进程。一旦找到一个进程，它设置每个 CPU 的当前进程变量 c->proc，将进程标记为 RUNNING，然后调用 swtch 开始运行它（kernel/proc.c:470-475）。

思考调度代码结构的一种方式是，它强制执行有关每个进程的一组不变量，并在这些不变量不成立时持有 p->lock。其中一个不变量是，如果一个进程处于 RUNNING 状态，定时器中断的 yield 必须能够安全地切换出该进程；这意味着 CPU 寄存器必须保存进程的寄存器值（即 swtch 尚未将它们移动到上下文），并且 c->proc 必须引用该进程。另一个不变量是，如果一个进程是 RUNNABLE 的，空闲 CPU 的调度器必须能够安全地运行它；这意味着 p->context 必须保存进程的寄存器（即它们实际上并不在真正的寄存器中），没有 CPU 在执行进程的内核栈上的代码，并且没有 CPU 的 c->proc 指向该进程。请注意，这些属性通常在持有 p->lock 时是不成立的。

维护上述不变量是为什么 xv6 经常在一个线程中获取 p->lock 并在另一个线程中释放它的原因，例如在 yield 中获取，在 scheduler 中释放。一旦 yield 开始修改运行中进程的状态使其变为 RUNNABLE，锁必须保持持有状态直到这些不变量被恢复：最早正确的释放点是在 scheduler（在自己的堆栈上运行）清除 c->proc 之后。同样地，一旦 scheduler 开始将一个 RUNNABLE 进程转换为 RUNNING，直到内核线程完全运行（例如在 swtch 之后，比如在 yield 中）锁都不能被释放。

p->lock 还保护其他内容：exit 和 wait 之间的相互作用、避免丢失唤醒的机制（参见第 7.5 节）以及进程退出和其他进程读取或写入其状态之间的竞争（例如，exit 系统调用查看 p->pid 并设置 p->killed (kernel/proc.c:611)）。也许值得考虑是否可以分解 p->lock 的不同功能，以提高清晰度和性能。

7.4 代码: mycpu 和 myproc

在许多情况下，xv6 需要指向当前进程的 proc 结构的指针。在单处理器上，可以有一个指向当前 proc 的全局变量。但在多核机器上就行不通了，因为每个核心执行不同的进程。解决这个问题的方法是利用每个核心都有自己的一组寄存器这一事实；我们可以使用其中一个寄存器来帮助查找每个核心的信息。

xv6 为每个 CPU 维护一个 struct cpu 结构（kernel/proc.h:22），记录了当前在该 CPU 上运行的进程（如果有的话），CPU 调度器线程的保存寄存器，以及管理中断禁用所需的嵌套自旋锁计数。函数 mycpu（kernel/proc.c:60）返回当前 CPU 的 struct cpu 指针。RISC-V 对其 CPU 进行编号，每个 CPU 都有一个 hartid。xv6 确保每个 CPU 的 hartid 存储在该 CPU 的 tp 寄存器中，位于内核中。这允许 mycpu 使用 tp 来索引一个 cpu 结构数组，以找到正确的 CPU。

确保 CPU 的 tp 始终保存 CPU 的 hartid 有点复杂。mstart 在 CPU 的启动序列早期在机器模式下设置 tp 寄存器（kernel/start.c:46）。usertrapret 将 tp 保存在跳转页中，因为用户进程可能修改 tp。最后，uservec 在从用户空间进入内核时恢复了保存的 tp（kernel/trampoline.S:70）。

编译器保证永远不会使用 tp 寄存器。如果 RISC-V 允许 xv6 直接读取当前的 hartid，那将更方便，但这只允许在机器模式下，而不是在监管者模式下。
cpuid 和 mycpu 的返回值是不稳定的：如果计时器中断并导致线程放弃 CPU 并移动到另一个 CPU，先前返回的值将不再正确。为了避免这个问题，xv6 要求调用者禁用中断，并且仅在使用返回的 struct cpu 后才启用它们。

函数 myproc（kernel/proc.c:68）返回运行在当前 CPU 上的 struct proc 指针。myproc 禁用中断，调用 mycpu，从 struct cpu 中获取当前进程指针（c->proc），然后启用中断。即使启用了中断，myproc 的返回值也是安全的使用；如果计时器中断将调用进程移动到另一个 CPU，它的 struct proc 指针仍将保持不变。

7.5 睡眠和唤醒

调度和锁有助于隐藏一个进程对另一个进程的存在，但到目前为止，我们还没有帮助进程有意识地相互交互的抽象。许多机制被发明来解决这个问题。xv6 使用了一种称为睡眠和唤醒的机制，它允许一个进程在等待事件发生时进入睡眠，另一个进程在事件发生后唤醒它。睡眠和唤醒通常被称为序列协调或条件同步机制。

举个例子，我们考虑一个称为信号量的同步机制 [4]，它用于协调生产者和消费者。信号量维护一个计数并提供两种操作。“V”操作（用于生产者）增加计数。“P”操作（用于消费者）等待直到计数不为零，然后将其减少并返回。如果只有一个生产者线程和一个消费者线程，并且它们在不同的 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 循环中自旋，希望 count 不为零。消费者的 CPU 可以找到比繁忙等待更有成效的工作，通过反复轮询 s->count。避免忙碌等待需要一种方法，让消费者能够让出 CPU，并且在 V 增加 count 后恢复运行。

以下是朝着这个方向迈出的一步，尽管我们会看到这还不够。让我们想象一对调用，sleep 和 wakeup，它们的工作方式如下。sleep(chan) 在任意值 chan（称为等待通道）上睡眠。sleep 使调用进程进入睡眠状态，释放 CPU 进行其他工作。wakeup(chan) 唤醒所有在 chan 上睡眠的进程（如果有的话），导致它们的 sleep 调用返回。如果没有进程在 chan 上等待，wakeup 什么都不做。我们可以改变信号量的实现以使用 sleep 和 wakeup（在下面黄色标出了更改的部分）：

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 而不是自旋，这很好。然而，设计带有这种接口的 sleep 和 wakeup 却并不直接，会出现被称为失去唤醒的问题。假设 P 在第 212 行发现 s->count == 0。在 P 处于第 212 行和第 213 行之间时，在另一个 CPU 上运行了 V：它将 s->count 更改为非零，并调用了 wakeup，但 wakeup 发现没有进程在睡眠，因此什么也没做。现在 P 继续执行第 213 行：它调用了 sleep 并进入了睡眠状态。这引发了一个问题：P 正在等待一个已经发生的 V 调用。除非我们很幸运并且生产者再次调用 V，否则即使计数是非零的，消费者也会永远等待。

问题的根源在于当 V 在恰到好处的时刻运行时，违反了只有当 s->count == 0 时 P 才会进入睡眠状态这个不变量。保护不变量的一个错误方法是将 P 中的锁获取操作（下面用黄色突出显示）移动，以便其对计数的检查和调用 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 看起来能避免丢失唤醒的问题，因为锁阻止了 V 在第 313 和 314 行之间执行。它确实做到了这一点，但也导致了死锁：P 在睡眠时持有了锁，所以 V 将永远阻塞，等待锁被释放。

我们将通过改变 sleep 的接口来修复上述方案：调用者必须将条件锁传递给 sleep，这样在调用进程被标记为睡眠并等待睡眠通道时，sleep 可以释放锁。这个锁会强制并发的 V 等待，直到 P 完成自己的休眠动作，以便唤醒可以找到正在睡眠的消费者并唤醒它。一旦消费者再次醒来，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 在检查 c->count 并调用 sleep 之间阻止了 V 尝试唤醒它。但是需要注意的是，我们需要 sleep 在原子性地释放 s->lock 并将消费进程置于睡眠状态。

7.6 代码：Sleep 和 Wakeup

让我们来看看 sleep 的实现（kernel/proc.c:548）和 wakeup 的实现（kernel/proc.c:582）。基本思想是让 sleep 标记当前进程为 SLEEPING，然后调用 sched 释放 CPU；wakeup 寻找在给定等待通道上睡眠的进程，并将其标记为 RUNNABLE。调用 sleep 和 wakeup 的程序可以使用任何彼此方便的数字作为通道。xv6 经常使用与等待相关的内核数据结构的地址。

sleep 获取了 p->lock（kernel/proc.c: 559）。现在要进入睡眠状态的进程同时持有 p->lock 和 lk。在调用者中（例如 P）持有 lk 是必要的：它确保没有其他进程（例如运行 V 的进程）可以开始调用 wakeup(chan)。现在 sleep 持有 p->lock，释放 lk 是安全的：其他进程可能开始调用 wakeup(chan)，但 wakeup 将等待获取 p->lock，因此将等到 sleep 完成将进程置于睡眠状态，防止 wakeup 错过 sleep。

有一个小的复杂性：如果 lk 和 p->lock 是同一个锁，那么如果试图获取 p->lock，sleep 就会与自身发生死锁。但是如果调用 sleep 的进程已经持有 p->lock，则它不需要做任何额外的操作以防止错过并发的 wakeup。这种情况发生在 wait（kernel/proc.c:582）调用 sleep 时使用 p->lock。

现在 sleep 持有 p->lock 且没有其他锁，它可以通过记录睡眠通道、将进程状态更改为 SLEEPING 并调用 sched 将进程置于睡眠状态（kernel/proc.c:564-567）。很快就会明白为什么在标记进程为 SLEEPING 之后才释放 p->lock 是至关重要的。

在某个时候，一个进程将获取条件锁，设置睡眠进程正在等待的条件，并调用 wakeup(chan)。重要的是 wakeup 在持有条件锁的情况下被调用。wakeup 遍历进程表（kernel/proc.c:582）。它获取每个它检查的进程的 p->lock，因为它可能会操纵该进程的状态，并且 p->lock 确保 sleep 和 wakeup 不会错过彼此。当 wakeup 找到处于 SLEEPING 状态且通道匹配的进程时，它将该进程的状态更改为 RUNNABLE。下次调度器运行时，它将看到该进程已准备好运行。

为什么 sleep 和 wakeup 的锁定规则确保睡眠进程不会错过唤醒？在睡眠进程检查条件之前，它持有条件锁或自己的 p->lock，或者两者都持有，直到它被标记为 SLEEPING 之后。调用 wakeup 的进程在其循环中同时持有这两个锁。因此，唤醒者要么在消费线程检查条件之前使条件为真；要么唤醒的 wakeup 严格在被标记为 SLEEPING 之后检查睡眠线程。然后 wakeup 将看到睡眠进程并唤醒它（除非有其他事件先唤醒它）。

有时会出现多个进程在同一个通道上睡眠的情况；例如，从管道中读取的多个进程。一次 wakeup 调用会将它们全部唤醒。其中一个将首先运行并获取使用 sleep 时调用的锁，并且（在管道的情况下）读取管道中等待的任何数据。其他进程将发现，尽管被唤醒，但没有数据可读取。从它们的角度来看，唤醒是“虚假的”，它们必须再次进入睡眠状态。因此，sleep 总是在循环中调用以检查条件。

如果两个 sleep/wakeup 的使用意外地选择了相同的通道，也不会造成任何损害：它们会看到虚假的唤醒，但如上所述的循环将容忍这个问题。sleep/wakeup 的很多魅力在于它既轻量化（不需要创建特殊的数据结构作为睡眠通道），又提供了一层间接性（调用者不需要知道与哪个特定的进程进行交互）。

7.7 代码：管道

一个更复杂的例子是 xv6 使用 sleep 和 wakeup 来同步生产者和消费者的管道实现。我们在第一章看到了管道的接口：写入管道一端的字节被复制到内核缓冲区，然后可以从管道的另一端进行读取。未来的章节将审查围绕管道的文件描述符支持，但现在让我们来看一下 pipewrite 和 piperead 的实现。

每个管道由一个 struct pipe 表示，其中包含一个锁和一个数据缓冲区。字段 nread 和 nwrite 计算从缓冲区读取的字节总数和写入的总数。缓冲区是循环的：在 buf[PIPESIZE-1] 之后写入的下一个字节是 buf[0]。计数不是循环的。这个约定让实现能够区分满缓冲区（nwrite == nread+PIPESIZE）和空缓冲区（nwrite == nread），但这意味着索引到缓冲区必须使用 buf[nread % PIPESIZE] 而不是仅仅是 buf[nread]（对于 nwrite 也是类似）。

假设在两个不同的 CPU 上同时调用 piperead 和 pipewrite。pipewrite（kernel/pipe.c:77）首先获取管道的锁，该锁保护计数、数据和它们相关的不变量。然后 piperead（kernel/pipe.c:103）尝试获取锁，但无法获取。它在 acquire（kernel/spinlock.c:22）中旋转等待锁。在 piperead 等待时，pipewrite 循环处理被写入的字节（addr[0..n-1]），依次将每个字节添加到管道中（kernel/pipe.c:95）。在此循环期间，可能发生缓冲区填满的情况（kernel/pipe.c:85）。在这种情况下，pipewrite 调用 wakeup 来通知任何正在睡眠的读取器有数据在缓冲区中等待，并且然后在 &pi->nwrite 上睡眠等待读取器将一些字节从缓冲区中取出。sleep 在将 pipewrite 进程置于睡眠状态时释放了 pi->lock。

现在 pi->lock 可用了，piperead 设法获取它并进入了临界区：它发现 pi->nread != pi->nwrite（kernel/pipe.c:110）（因为 pipewrite 进入睡眠是因为 pi->nwrite == pi->nread+PIPESIZE（kernel/pipe.c:85）），所以它继续执行 for 循环，从管道中复制数据（kernel/pipe.c:117），并将 nread 增加复制的字节数。现在有了这么多字节可供写入，因此 piperead 在返回之前调用 wakeup（kernel/pipe.c:124）唤醒任何正在睡眠的写入器。wakeup 找到了在 &pi->nwrite 上睡眠的进程，这个进程在管道填满时停止了。它将该进程标记为 RUNNABLE。

管道代码为读取器和写入器使用了单独的睡眠通道（pi->nread 和 pi->nwrite）；在极少出现大量读取器和写入器等待同一管道的情况下，这可能使系统更加高效。管道代码在一个循环中睡眠检查睡眠条件；如果有多个读取器或写入器，除了第一个唤醒的进程外，其余的都会发现条件仍然为 false，并再次进入睡眠状态。

7.8 代码：等待、退出和终止

sleep 和 wakeup 可用于许多种等待方式。一个有趣的例子，介绍于第一章，是子进程的退出与其父进程的等待之间的交互。在子进程死亡时，父进程可能已经在等待中，或者正在执行其他操作；在后一种情况下，后续对 wait 的调用必须观察到子进程的死亡，也许是在调用 exit 之后相当长的时间。xv6 记录子进程的终止状态直到 wait 观察到它时，是通过 exit 将调用者置于 ZOMBIE 状态，保持在那里，直到父进程的 wait 发现它，将子进程状态更改为 UNUSED，复制子进程的退出状态，并将子进程的进程 ID 返回给父进程。如果父进程在子进程之前退出，则父进程将子进程交给 init 进程，后者永远调用 wait；因此每个子进程都有一个父进程来清理它的残留。

主要的实现挑战在于父子进程的 wait 和 exit 之间以及 exit 与 exit 之间的竞争和死锁可能性。wait 使用调用进程的 p->lock 作为条件锁以避免丢失唤醒，并在开始时获取该锁（kernel/proc.c:398）。然后它扫描进程表。如果找到 ZOMBIE 状态的子进程，它将释放该子进程的资源和其 proc 结构，将子进程的退出状态复制到 wait 提供的地址（如果不为 0），然后返回子进程的进程 ID。如果 wait 找到子进程但没有任何子进程已退出，则它调用 sleep 等待其中一个退出（kernel/proc.c:445），然后再次扫描。这里，条件锁在 sleep 中被释放是等待进程的 p->lock，即上述提到的特殊情况。注意，wait 经常持有两个锁；在尝试获取任何子进程的锁之前，它会先获取自己的锁；因此，为了避免死锁，整个 xv6 必须遵守相同的锁定顺序（父进程，然后子进程）。

wait 查看每个进程的 np->parent 来查找其子进程。它在不持有 np->lock 的情况下使用 np->parent，这违反了通常的共享变量必须由锁保护的规则。可能 np 是当前进程的祖先，在这种情况下，获取 np->lock 可能导致死锁，因为那将违反上述的顺序。在这种情况下，在没有锁的情况下检查 np->parent 似乎是安全的；进程的 parent 字段只能由其父进程更改，因此如果 np->parent==p 成立，除非当前进程更改它，否则值不会改变。

exit（kernel/proc.c:333）记录退出状态，释放一些资源，将任何子进程交给 init 进程，唤醒等待中的父进程，将调用者标记为僵尸进程，并永久性地让出 CPU。最后的顺序有点棘手。退出进程必须在将其状态设置为 ZOMBIE 并唤醒父进程之前持有其父进程的锁，因为父进程的锁是 wait 中防止丢失唤醒的条件锁。子进程也必须持有自己的 p->lock，否则父进程可能在其仍在运行时看到它处于 ZOMBIE 状态并将其释放。锁获取顺序对于避免死锁非常重要：因为 wait 在获取父进程的锁之前先获取子进程的锁，所以 exit 必须使用相同的顺序。

exit 调用了一个专门的 wakeup 函数，wakeup1，它只唤醒父进程，仅在其处于 wait 状态时才唤醒（kernel/proc.c:598）。在子进程将状态设置为 ZOMBIE 之前唤醒父进程可能看起来不正确，但是是安全的：虽然 wakeup1 可能导致父进程运行，但是 wait 中的循环不能检查子进程，直到子进程的 p->lock 被 scheduler 释放，因此 wait 不能在 exit 将其状态设置为 ZOMBIE 之后很久之前查看退出进程（kernel/proc.c:386）。

虽然 exit 允许进程终止自身，但是 kill（kernel/proc.c:611）允许一个进程请求另一个进程终止。直接摧毁受害者进程对 kill 来说太复杂了，因为受害者可能正在另一个 CPU 上执行，也许正在执行对内核数据结构敏感的一系列更新。因此 kill 做的很少：它只是设置受害者的 p->killed，并且如果其正在睡眠，则唤醒它。最终，受害者将进入或离开内核，此时 usertrap 中的代码将根据 p->killed 的设置调用 exit。如果受害者在用户空间运行，它将很快通过发出系统调用或者因为计时器（或其他设备）中断而进入内核。

如果受害者进程处于睡眠状态，kill 的调用将导致受害者从睡眠中返回。这可能是危险的，因为正在等待的条件可能不为真。但是，xv6 对 sleep 的调用始终包裹在一个 while 循环中，在 sleep 返回后重新测试条件。一些对 sleep 的调用也在循环中测试 p->killed，如果设置了就放弃当前活动。这只有在放弃时是正确的情况下才会这样做。例如，管道读取和写入代码在 killed 标志被设置时返回；最终代码会返回到 trap，再次检查标志并退出。

一些 xv6 的 sleep 循环不检查 p->killed，因为代码处于多步系统调用的中间，应该是原子的。virtio 驱动程序（kernel/virtio_disk.c:242）就是一个例子：它不检查 p->killed，因为磁盘操作可能是一组必须按顺序完成的写操作之一，以便文件系统处于正确的状态。等待磁盘 I/O 的进程直到完成当前系统调用并且 usertrap 看到 killed 标志时才会退出。

7.9 现实情况

xv6的调度器实现了一种简单的调度策略，即逐个运行每个进程。这个策略被称为循环轮转。真实的操作系统实现了更复杂的策略，例如，允许进程具有优先级。其想法是，一个可运行的高优先级进程将被调度程序优先于可运行的低优先级进程。这些策略可能会很快变得复杂，因为通常存在着竞争的目标：例如，操作系统可能还想要保证公平性和高吞吐量。此外，复杂的策略可能会导致意想不到的交互，比如优先级反转和车队现象。优先级反转可能会发生在低优先级和高优先级进程共享一个锁时，当低优先级进程获取该锁时，会阻止高优先级进程取得进展。当许多高优先级进程等待获取共享锁的低优先级进程时，长时间的等待进程车队可能形成；一旦车队形成，它可以持续很长时间。为了避免这类问题，在复杂的调度器中需要额外的机制。

sleep和wakeup是一种简单有效的同步方法，但还有许多其他方法。所有这些方法中的第一个挑战是避免我们在本章开头看到的“丢失唤醒”问题。原始的Unix内核的sleep只是禁用了中断，这足够因为Unix运行在单CPU系统上。因为xv6运行在多处理器上，它在sleep中添加了一个显式的锁。FreeBSD的msleep采用相同的方法。Plan 9的sleep使用了一个回调函数，在进入睡眠之前在持有调度锁的情况下运行；该函数作为睡眠条件的最后一次检查，以避免丢失唤醒。Linux内核的sleep使用了一个名为等待队列的显式进程队列，而不是等待通道；该队列有自己的内部锁。

在wakeup中扫描整个进程列表以查找具有匹配chan的进程是低效的。更好的解决方案是在sleep和wakeup中将chan替换为一个数据结构，该数据结构保存在该结构上睡眠的进程列表，例如Linux的等待队列。Plan 9的sleep和wakeup将该结构称为会面点或Rendez。许多线程库将相同的结构称为条件变量；在那种情况下，操作sleep和wakeup称为wait和signal。所有这些机制都具有相同的特点：睡眠条件由某种在睡眠期间原子地丢弃的锁保护。

wakeup的实现唤醒所有在特定通道上等待的进程，可能会有许多进程在等待特定通道。操作系统将调度所有这些进程，它们将竞争检查睡眠条件。像这样行为的进程有时被称为雷鸣般的群体，最好避免。大多数条件变量对唤醒有两个原语：signal，唤醒一个进程，和broadcast，唤醒所有等待的进程。

信号量通常用于同步。计数通常对应于管道缓冲区中可用字节数或进程拥有的僵尸子进程数量之类的东西。在抽象的一部分中使用显式计数避免了“丢失唤醒”问题：有明确的唤醒次数计数。计数还避免了虚假唤醒和雷鸣般的群体问题。

终止进程并清理它们在 xv6 中引入了很多复杂性。在大多数操作系统中，这更加复杂，因为例如，受害进程可能深深地睡眠在内核中，解开它的堆栈需要非常小心的编程。许多操作系统使用显式的异常处理机制，如 longjmp 来解开堆栈。此外，还有其他事件可能导致正在睡眠的进程被唤醒，即使它等待的事件尚未发生。例如，当Unix进程正在睡眠时，另一个进程可能向其发送信号。在这种情况下，进程将从被中断的系统调用返回，值为**-1，并将错误代码设置为EINTR**。应用程序可以检查这些值并决定如何处理。xv6不支持信号，因此不会出现这种复杂性。

xv6对 kill 的支持并不完全令人满意：有一些sleep循环可能应该检查 p->killed 。一个相关的问题是，即使对于检查 p->killed的 sleep 循环，也存在sleep和kill之间的竞争；后者可能设置 p->killed ，并在受害者的循环检查p->killed之后但在调用sleep之前尝试唤醒受害者。如果出现这个问题，受害者直到它等待的条件发生时才会注意到 p->killed 。这可能会相当晚（例如，当virtio驱动程序返回受害者正在等待的磁盘块时）或永远不会发生（例如，如果受害者正在等待来自控制台的输入，但用户没有输入任何内容）。

真实的操作系统会在常数时间内使用显式的空闲进程结构体列表而不是在 allocproc 中进行线性搜索来找到空闲的进程结构体。xv6 出于简单起见使用线性扫描。