任何操作系统的进程都可能比CPU多，所以进程需要分时共享(time-share)CPU。理想状态下，共享对用户进程应当是透明的。常用的方式的把进程多路复用到硬件CPU上，使每个进程产生拥有自己的虚拟CPU的假象。本章描述xv6如何实现的多路复用。
多路复用
xv6的多路复用是让进程在所有CPU之间切换，它分两种情况。一，当进程等待设备或管道I/O的完成，或等待子进程退出，或在sleep系统调用中等待，使用sleep和wakeup机制切换。二，定时强制切换进程。多路复用使得每个进程看上去都拥有自己的CPU，就像内存分配器和硬件页表的使用使得每个进程看上去都拥有自己的内存一样。
实现多路复用会有一些挑战。一，怎么来让进程切换呢？虽然上下文切换的想法很简单，它的实现却是xv6里最不透明的代码。二，如何让强制切换对用户进程透明？xv6使用计时器中断驱动上下文切换，这是标准技术。三，多个CPU并发地在进程间切换，需要锁来避免竞争。四，进程退出时它的内存和其它资源必须被释放，但它不能自己完成全部的过程，比如它不能在运行的时候释放自己的内核栈。五，多核系统的每个核都必须记住它运行的是哪个进程，这样系统调用才能影响正确进程的内核状态。最后，sleep和wakeup允许放弃CPU并睡眠以等待一个事件，并允许其它的进程唤醒先前的进程。要小心避免竞争，否则会导致唤醒通知的丢失。xv6尝试尽可能简单地解决这些问题，但最后的代码依然很复杂。
代码：上下文切换
从一个进程切换到另一个进程的步骤是：用户进程通过系统调用或中断进入内核态，通过上下文切换进到当前CPU的调度线程，再通过上下文切换进入到新进程的内核线程，返回到用户态的进程。xv6调度器在每个CPU上都有一个专用的线程(保存的寄存器和栈)，因为它运行在任何进程的内核栈上都是不安全的。本节中将研究内核线程和调度器线程之间的切换机制。
从一个线程切换到另一个包含了保存旧线程的寄存器，和恢复新线程的寄存器。切换sp寄存器意味着要切换栈，切换pc寄存器意味着切换要执行的代码。
函数swtch实现了线程切换时保存和恢复两个过程。swtch并不知道线程，它只是保存和恢复寄存器的集合，这个寄存器的集合叫做上下文。当进程要让出CPU的时候，进程的内核线程调用swtch来保存它自己的上下文并返回到调度器的上下文。每个上个文都包含在struct context里，而它自己又被包含在进程的struct proc里或CPU的struct cpu里。swtch有两个参数：struct context *old指当前的寄存器组，struct context *new指要载入的寄存器组。
我们来看看一个进程是怎么通过swtch进到调度器的。中断导致usertrap执行，usertrap调用yield。yield再调用sched，sched调用swtch将当前上下文保存在p->context，并切换到之前保存在cpu->scheduler的调度器上下文。
swtch只保存被调用者要保存的寄存器，调用者的的寄存器由调用的C代码保存在栈上(如果需要的话)。swtch知道struct context里每个寄存器字段的位置。它不保存pc寄存器。相反，swtch保存ra寄存器，这个寄存器保存着调用swtch的返回值。现在swtch从新上下文里恢复寄存器，新上下文里保存的是上一个swtch的寄存器。当swtch返回，它返回到ra所指向的指令处，也就是新线程之前调用swtch的指令。除此之外，它返回到新线程的栈上。
在我们的例子里，sched调用swtch以切换到cpu->scheduler。上下文通过scheduler对swtch的调用而得以保存。当我们追踪的swtch返回时，它返回到scheduler而不是sched，并且它的sp寄存器将指向当前CPU的调度器的栈。
代码：调度
上一节讨论了swtch的底层细节，本节研究一个进程是怎么通过调度器切换到另一个进程的。调度器就是每个CPU上运行的scheduler函数。这个函数的任务就是选择下一个要运行的进程。一个进程要让出CPU首先要获取它自己的进程锁p->lock，释放它持有的其它锁，更新它自己的状态p->state，然后调用sched。当我们在做sleep和exit的时候，yield就遵循了这个约定。sched再次检查了这些条件，并检查这些条件隐含的结果：如果持有锁，中断应当是关闭的。最后，sched调用swtch保存p->context的上下文并切换到cpu->scheduler里调度器的上下文。swtch返回到调度器的栈，就像scheduler的swtch已经返回了。调度器继续for循环，找到一个进程来运行，切换到它，重复这个过程。
我们在调用swtch的过程中xv6持有了p->lock：swtch的调用者必须持有锁，并且对锁的控制传递给了要切换过去的代码。这个约定在锁上是不常见的，通常哪个线程获取锁，哪个线程就负责释放锁，这有利于判断正确性。对于上下文切换来说，则要打破这个约定，因为p->lock保护的是进程的state和context字段的不变量，那些字段在执行swtch的时候是不正确的。如果在swtch期间不持有p->lock可能会有这样的问题：对于在yield之后已经把自己的状态设置为RUNNABLE的进程，可能会有其它CPU决定运行它，但此时swtch可能还没有使它停止使用它自己的内核栈。这导致两个CPU运行在同样的栈上，这是错误的。
内核线程总是在sched里让出CPU，并且总是在调度器里切换到同样的位置，调度器几乎总是切换到之前调用sched的内核线程上。线程切换实际上就是scheduler和sched的swtch交替执行的过程。这种在两个线程间程式化切换的过程叫做协程(coroutines)。sched和scheduler就互为协程。
在一种情况下，调度器调用swtch但不在sched中结束。当一个新的进程第一次调度的时候，它在forkret开始。forkret的存在就是为了释放p->lock，否则新进程就应从usertrapret开始。
scheduler运行的是一个简单的循环：找到一个进程来运行，直到这个进程让出CPU，然后一直重复这样的过程。调度器在进程表里找到一个可运行的进程，那个进程是p->state==RUNNABLE。一旦它找到这样的进程，它就设置当前CPU的当前进程c->proc，将进程标记为RUNNING，然后调用swtch。
可以把调度代码的结构认为是强制每个进程的一组不变量，一旦这些不变量是不正确的就持有p->lock。一个不变量是，如果一个进程是RUNNING的，中断计时器的yield必须可以安全地切换出去；这意味着CPU的寄存器必须保留着进程寄存器的值(如swtch没有把它们移动到一个context)，且c->proc必须指向这个进程。另一个不变量是，如果一个进程是RUNNABLE的，它必须是安全的以便一个空闲CPU的scheduler可以运行它；这意味着p->context必须保留进程的寄存器(如，它们不是在真实的寄存器里)，没有CPU运行在进程的内核栈上，没有CPU的c->proc指向此进程。显然当持有p->lock这些特性都不正确。
xv6之所以在一个线程里请求p->lock而在另一个线程里释放它，就是为了保持上面所提的不变量，比如在yield请求而在scheduler释放。一旦yield开始一个运行进程的状态使它RUNNABLE，必须持有锁直到不变量被恢复：最早的正确的释放点在scheduler清空c->proc之后，那时scheduler运行在它自己的栈上。同样地，一旦scheduler开始把一个可运行的进程转换为RUNNING，直到内核线程完全运行的时候才可以释放锁(对于yield来说就是在swtch之后)。
p->lock也保护了其它的东西：exit和wait的相互作用，避免唤醒(wakeup)的缺失，避免一个进程退出时其它进程读写它的状态的竞争(如，exit系统调用查找p->pid并设置p->killed)。出于清晰和性能的考虑，也许应该把p->lock的不同功能分开。
代码：mycpu和myproc
xv6经常需要一个指针来指向当前进程的proc结构体。单处理器上可以用一个全局变量来指向当前proc。然而在多核机器上却不行，因为每个核都在执行不同的进程。解决这个问题的方法是利用每个核自己的寄存器；可以利用其中的一个寄存器来查询那个核的信息。
xv6为每个CPU维护了一个struct cpu，它记录了在那个CPU上正在运行的进程(如果存在的话)，为CPU的调度器线程保存的寄存器，用于管理中断关闭的自旋锁嵌套层数。函数mycpu返回当前CPU的struct cpu的指针。RISC-V给所有CPU进行了编号，即hartid。xv6确保每个CPU的hartid保存在那个CPU的tp寄存器里。这使得mycpu可以使用tp来索引cpu结构体的数组以找到正确的那个。
确保一个CPU的tp总是保存着这个CPU的hartid有点复杂。在CPU启动的初期start设置了tp寄存器，当时仍在机器模式。usertrapret把tp保存在trampoline页，因为用户进程可能修改tp。最后，当从用户空间进到内核的时候uservec恢复已保存的tp。编译器保证绝不使用tp寄存器。如果RISC-V允许xv6直接读取当前hardid会更方便，但只能是在机器模式，在管理员模式是不允许的。
cpuid和mycpu的返回值是脆弱的：如果发生计时器中断使得线程让出CPU，返回值将不再正确。为避免这个问题，xv6需要调用者关闭中断，只有在使用完返回的struct cpu后才可以开启中断。
函数myproc返回struct proc，它指向的是在当前CPU正在运行的进程。myproc关闭中断，调用mycpu，从struct cpu获取当前进程的指针c->proc，然后使能中断。即使开启中断myproc的返回值也是安全的：如果记时器中断把调用的进程移动了其它CPU，它的struct proc指针仍然是不变的。
睡眠与唤醒
调度和锁有助于一个进程相对于其它进程隐藏自己的存在性，但到目前为止还没有抽象方式可以帮助进程之间的交互。许多机制被发明出来解决这个问题。xv6使用的机制叫睡眠和唤醒，这允许一个进程睡眠以等待一个事件，一旦这个事件发生其它进程会把这个进程唤醒。睡眠和唤醒被称为序列协调(sequence coordination)或条件同步(conditional synchronization)。
为了说明我们的意思，考虑一个简单的同步机制信号量(semaphore)，它被用来协调生产者和消费者。信号量包含了一个记数，并提供了两个操作。V操作递增记数(用于生产者)，P操作等待记数为0，然后递减记数并返回(用于消费者)。如果生产者线程和消费者线程都只有一个，且它们在不同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循环里自旋。相对于忙等，消费者的CPU应该去做一些更有意义的工作。要想避免忙等，就需要消费者让出CPU且只在V操作后恢复。
让我们来考虑一对调用sleep和wakeup。sleep(chan)睡在任意值chan上，被等待频道(wait channel)调用。sleep让调用的进程睡眠，释放CPU来干其它的事情。wakeup唤醒所有睡眠在chan上的进程(如果存在的话)，引发它们的sleep调用返回。如果没有进程等待在chan上，wakeup就什么也不做。可以把wakeup加到V操作，且把sleep加到P操作，来改变信号量的实现。
P操作不再自旋而是放弃了CPU，这很好。但是，设计sleep和wakeup这样的接口并不容易，因为它会带来所谓的唤醒丢失(lost wake-up)问题。假定P操作发现s->count == 0。当P操作还没有执行sleep的时候，V运行在了其它CPU上：它改变了s->count为非0的值并调用了wakeup，它发现没有睡眠的进程所以什么都没有做。现在P操作继续执行sleep并进程睡眠。这就引发了一个问题：P进入睡眠等待一个已经发生了的V操作。除非我们很幸运生产者又调用了V操作，否则消费者将永远等待(被死锁了)即使记数是非0的。
问题的根源在于，当s->count == 0时P才能睡眠的不变量被破坏了，因为V运行在错误的时候。可以在P里使用自旋锁让计数检查和sleep调用是原子的。这样的P确实可以避免唤醒丢失，但它依然会死锁：P在睡眠的时候持有锁，导致V等待这个锁而被永远阻塞。
我们通过修改sleep接口修复之前的方案：调用者必须把锁传递给sleep，这样在调用进程被标记为睡眠且等待在睡眠频道之后，sleep就可以把锁释放。锁将强制并发的V等待直到P完成自己的睡眠，这样wakeup将发现睡眠的消费者并把它唤醒。一旦消费者被再次唤醒，sleep在返回前会请求锁。
P持有s->lock避免了P在检查c->count和调用sleep期间，V唤醒它的尝试。我们需要sleep来原子性地释放锁并让消费者进程睡眠。
代码：睡眠与唤醒
我们来看看sleep和wakeup的实现，它们都在kernel/proc.c。基本思路是：让sleep把当前进程标记为SLEEPING并调用sched让出CPU；wakeup查找在等待频道上睡眠的进程并把它标记为RUNNABLE。sleep和wakeup的调用者可以使用任何方便的数字作为频道。xv6经常使用与等待相关的内核数据结构的地址。
sleep请求p->lock。现在准备睡眠的进程持有p->lock和lk。调用者持有lk是必需的(在本例中是P)：它确保没有其它进程(在本例中是运行的V)可以调用wakeup(chan)。现在sleep持有p->lock，释放lk就是安全的：其它进程可能开始调用wakeup(chan)，但wakeup将会等待获取p->lock，这样就一直等到sleep完成让进程睡眠，使得wakeup不会丢失sleep。
有一个小问题：如果lk是像p->lock一样的锁，当sleep尝试获取p->lock的时候会把自己死锁。但如果调用sleep的进程已经持有了p->lock，它并不用做其它的事来避免丢失并发的wakeup了。当wait带着p->lock调用sleep时会出现这种情况。
现在sleep仅持有p->lock，它可以通过记录睡眠频道、改变进程状态和调用sched来让进程睡眠。
稍后，某个进程将调用wakeup(chan)。wakeup在进程表里循环。它获取它检查的每个进程的p->lock，即是因为它可以管理进程的状态，也是因为p->lock不会让sleep和wakeup彼此错过。当它发现一个SLEEPING状态的进程与chan匹配的时候，它把进程状态改为RUNNABLE。下次调度器运行的时候，它会发现这个进程已经准备好运行了。
xv6代码持有”条件锁”的时候总是会调用wakeup；在信号量的例子里那个锁是s->lock。严格来说如果wakeup总是跟在acquire之后就足够了(即，应该在调用release后调用wakeup)。为什么sleep和wakeup的锁的规则要确保睡眠的进程不会丢失它需要的唤醒呢？睡眠的进程，从它检查条件之前到它标记为睡眠之后，要么持有条件锁，要么持有自己的p->lock，要么持有两者。如果一个并发的线程使得条件为真，那个线程必需持有这个条件锁，或在睡眠的线程请求条件锁之前，或在睡眠的线程在sleep里释放它之后。如果是在之前，睡眠线程必须看到新的条件值，并且不管怎样决定睡眠，所以它不担心丢失唤醒。如果是在之后，唤醒者可以请求条件锁的最早时机是在sleep请求p->lock之后，所以wakeup对p->lock的请求必须等待直到sleep让睡眠者彻底睡眠。然后wakeup将看到睡眠的进程并把它唤醒(除非有什么东西先把它唤醒)。
可能会有多个进程睡在同一个频道上的情况；例如，多个进程读取一个管道。一旦调用wakeup将会把它们全部唤醒。其中一个进程将首先执行并请求sleep被调用时所请求的锁，并读取所有等待在管道中的数据。其它进程会发现，尽管被唤醒了，但无数据可读。从它们的角度来看，这个唤醒是“假的”，它们必须再次睡眠。因此，sleep总是在检查条件的循环中被调用。
如果在两次使用“睡眠/唤醒”的时候不小心选择了同样的频道，不会造成任何伤害：它们会看到假的唤醒，但上面所述的循环可以容忍这样的问题。“睡眠/唤醒”的魅力在于它们都是轻量级的(不需要创建特殊的数据结构来充当睡眠频道)，并提供了一个间接层(调用者不需要知道它在和哪个进程交互)。
代码：管道
使用sleep和wakeup来同步生产者和消费者的一个复杂的例子，是xv6里对管道的实现。数据从管道的一端写入，复制进内核里的缓冲区，然后从管道的另一端读出。我们先来看看pipewrite和piperead的实现。
每个管道都代表了一个struct pipe，它包含了一个lock和一个data缓冲区。字段nread和nwrite记录读出或写入缓冲区的字节数。缓冲区的封装：buf[PIPESIZE-1]的下一个字节是buf[0]。计数不封装。这个约定让一个满的缓冲区(nwrite == nread + PIPESIZE)和一个空的缓冲区(nwrite == nread)区分开来，但是它也使得缓冲区的索引必须是buf[nread % PIPESIZE]而不是简单的buf[nread](对于nwrite来说也是一样)。
假定两个不同的CPU同时调用了piperead和pipewrite。pipewrite从请求管道的锁开始，这样可以保护记数、数据和相关的不变量。piperead也试着请求锁，但请求不到。它在acquire上自旋等待这个锁。当piperead等待的时候，pipewrite循环遍历要写入的字节(addr[0...n-1])，依次将每个字节添加到管道中。在循环的过程中，缓冲区可能被填满。在这种情况下，pipewrite调用wakeup来提醒睡眠的读者有数据等待在缓冲区，并睡在&pi->nwrite上来等待一些读者从缓冲区中取走一些数据。sleep释放pi->lock，这是让pipewrite的进程进入睡眠的一部分。
现在p->lock是可用的，piperead可以请求它并进到它的临界区：它发现pi->nread != pi->nwrite(pipewrite因为pi->nwrite == pi->nread+PIPESIZE而进入睡眠)，所以它进到for循环里，从管道中复制出数据，按复制出的字节数递增nread。现在有许多字节可以写入了，所以piperead在它返回前调用wakeup唤醒睡眠的写者。wakeup找到睡在&pi->nwrite上的进程，这个进程就是那个因为满了而中断的pipewrite。它把那个进程标记为RUNNABLE。
管道代码为读者和写者使用了不同的睡眠频道(pi->nread和pi->nwrite)；当有大量的读者和写者等在相同的管道上时(当然这种情况不太可能发生)，这可能会使系统更高效。在检查睡眠状态的循环里，管道代码睡眠了；如果有多个读者或写者，除了第一个进程外，所有被唤醒的进程都发现条件是假的并继续睡眠。
代码：wait, exit和kill
sleep和wakeup可以用在多种类型的等待中。一个有趣的例子是，一个子进程的exit和它的父进程的wait交互。在子进程死亡时，父进程可能已经在wait里睡眠了，或者在做其它的事；在后一种情况下，一个随后的对wait的调用必须发现子进程死亡了，可能在子进程调用exit很久之后。xv6记录子进程死亡的方式，是调用exit让子进程进入ZOMBIE状态，直到父进程的wait发现它才把状态改为UNUSED，复制子进程的退出状态，并把子进程的进程号返回给父进程。如果父进程先于子进程退出了，父进程把子进程给到init进程，init不停地调用wait；因此，每个子进程都有一个父进程来清理。代码实现的最大挑战是可能的竞争和死锁。
wait使用调用进程的p->lock作为条件锁来避免唤醒丢失，它在一开始的时候就请求了那个锁。然后它描述进程表。如果它发现了处于ZOMBIE状态的子进程，它释放那个子进程的资源和它的proc结构体，把子进程的退出状态复制到提供给wait的地址(如果它不是0的话)，并返回子进程的进程号。如果wait发现了有子进程但这些子进程都没有退出，它会调用sleep等待其中一个退出，然后重新开始描述。在这里，sleep释放的条件锁是p->lock，即上面提到的特殊情况。注意wait经常会持有两个锁，为避免死锁，它使用的锁序是先父进程后子进程。
wait使用np->parent的时候不持有np->lock，这违反了通常的规则，即共享变量必须用锁保护起来。因为np有可能是当前进程的祖先，在这种情况下请求np->lock可能会引起死锁(违背了先父进程后子进程的锁序)。在这种情况下，不使用锁检查np->parent看起来是安全的；一个进程的parent字段只能被它的父进程改变，所以如果np->parent==p为真，这个值不会改变除非当前进程改变它。
exit记录退出状态，释放一些资源，把子进程给到init进程，唤醒处于wait中的父进程，将调用者标记为僵尸进程，并永久性地让出CPU。最后的顺序有点复杂。退出的进程在把自己的状态设为ZOMBIE的时候必须持有它的父进程的锁，并且把父进程唤醒，因为父进程的锁是条件锁，这个条件锁用来防止在wait里的唤醒丢失。子进程还必须持有它自己的p->lock，否则父进程可能发现它处于ZOMBIE状态从而在它仍然运行的时候释放它。锁请求的次序对于避免死锁来说是非常重要的：因为wait先请求父进程的锁再请求子进程的锁，所以exit必须使用同样的次序。
exit调用一个特殊的唤醒程序wakeup1，它只唤醒睡在wait上的父进程。看上去子进程在把自己的状态设为ZOMBIE之前就唤醒父进程是不正确的，但实际上这很安全：虽然wakeup1可能引发父进程的运行，wait里的循环不会检测子进程直到子进程的p->lock被scheduler释放，所以wait不会看到退出的进程直到exit把它的状态设为ZOMBIE。
exit允许一个进程终止自己，kill则允许一个进程终止其它的进程。kill如果直接毁掉目标进程将会非常复杂：因为目标进程可能正在其它CPU上运行，可能正在对内核的数据结构进行一系列的敏感更新。kill只做了少量的工作就解决了这些挑战：它只是设置目标进程的p->killed，如果目标进程在睡眠就唤醒它。最终目标进程会进入或离开内核，那时如果设置了p->killed，在usertrap会调用exit。如果目标进程运行在用户空间，它也会因为系统调用或计时器中断而进入内核。
如果目标进程在sleep，kill调用wakeup会让目标进程从sleep返回。这有潜在的风险，因为正在等待的条件可能不是真的。然而xv6调用sleep问题包装在一个while循环中，这个循环会在sleep返回后重新测试条件。一些对sleep的调用也会在循环里测试p->killed，如果设置了则终止当前的活动。只有在那种终止是正确的情况下才可以这么做。例如，如果设置了killed标志管道的读写代码会返回；最终会返回到trap，然后又开始检查标志并退出。
一些xv6的sleep循环不检查p->killed，因为代码正在进行多步的系统调用，那是原子性的。virtio驱动就是一个例子：它不检查p->killed，因为为了让文件系统保持正确的状态，操作操作可能是所有必需的写操作里的其中一个。一个标记为killed的进程在等待磁盘I/O的时候不会退出，直到它完成当前的系统调用，usertrap看到killed标记。