# 7.3 代码：调度

上一节介绍了`swtch`的底层细节；现在，让我们以`swtch`为给定对象，检查从一个进程的内核线程通过调度程序切换到另一个进程的情况。调度器（scheduler）以每个CPU上一个特殊线程的形式存在，每个线程都运行`scheduler`函数。此函数负责选择下一个要运行的进程。想要放弃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`在调度程序的栈上返回，就像是`scheduler`的`swtch`返回一样。`scheduler`继续`for`循环，找到要运行的进程，切换到该进程，重复循环。

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

内核线程总是在`sched`中放弃其CPU，并总是切换到调度程序中的同一位置，而调度程序（几乎）总是切换到以前调用`sched`的某个内核线程。因此，如果要打印xv6切换线程处的行号，将观察到以下简单模式：（***kernel/proc.c***:475），（***kernel/proc.c***:509），（***kernel/proc.c***:475），（***kernel/proc.c***:509）等等。在两个线程之间进行这种样式化切换的过程有时被称为协程（coroutines）；在本例中，`sched`和`scheduler`是彼此的协同程序。

存在一种情况使得调度程序对`swtch`的调用没有以`sched`结束。一个新进程第一次被调度时，它从`forkret`（***kernel/proc.c***:527）开始。`Forkret`存在以释放`p->lock`；否则，新进程可以从`usertrapret`开始。

`scheduler`（***kernel/proc.c***:457）运行一个简单的循环：找到要运行的进程，运行它直到它让步，然后重复循环。`scheduler`在进程表上循环查找可运行的进程，该进程具有`p->state == RUNNABLE`。一旦找到一个进程，它将设置CPU当前进程变量`c->proc`，将该进程标记为`RUNINING`，然后调用`swtch`开始运行它（***kernel/proc.c***:470-475）。

考虑调度代码结构的一种方法是，它为每个进程强制维持一个不变量的集合，并在这些不变量不成立时持有`p->lock`。其中一个不变量是：如果进程是`RUNNING`状态，计时器中断的`yield`必须能够安全地从进程中切换出去；这意味着CPU寄存器必须保存进程的寄存器值（即`swtch`没有将它们移动到`context`中），并且`c->proc`必须指向进程。另一个不变量是：如果进程是`RUNNABLE`状态，空闲CPU的调度程序必须安全地运行它；这意味着`p->context`必须保存进程的寄存器（即，它们实际上不在实际寄存器中），没有CPU在进程的内核栈上执行，并且没有CPU的`c->proc`引用进程。请注意，在保持`p->lock`时，这些属性通常不成立。

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

`p->lock`还保护其他东西：`exit`和`wait`之间的相互作用，避免丢失`wakeup`的机制（参见第7.5节），以及避免一个进程退出和其他进程读写其状态之间的争用（例如，`exit`系统调用查看`p->pid`并设置`p->killed`(***kernel/proc.c***:611)）。为了清晰起见，也许为了性能起见，有必要考虑一下`p->lock`的不同功能是否可以拆分。