在两种情况下,xv6会将CPU从一个进程切换至另一个进程并以此实现复用。第一种情况是当一个进程等待设备或管道I/O完成,或等待子进程退出,或在 sleep
系统调用中等待时将CPU切换至另一个进程。第二种是xv6周期性地强制将进程切换以应对进行了长期运算却不执行 sleep
的进程。这种复用创造了一种每个进程都拥有自己的CPU的假象,就像xv6通过内存分配器和页表创造了一种每个进程都拥有自己的内存的假象。
实现复现向我们提出了一些挑战。首先,我们应如何从一个进程切换至另一个进程?尽管上下文切换的实现思路很简单,它的实现却是xv6中最晦涩的代码之一。其次,如何以一种对用户进程透明的方式来实现强制切换?对此xv6采用了通过记时器中断来触发上下文切换的传统做法。再者,所有CPU在一个共享的进程池中进行切换,这就要求通过锁来避免竞争。此外,一个进程的内存和其他资源在进程退出时必须被释放,然而进程本身并不能自行完成所有工作(例如进程的内核堆栈的释放)。再然后,多核机器中的每一个核都需要记录其正在运行的进程以保证系统调用可以更改正确的进程的内核状态。最后,sleep
和 wakeup
允许一个进程将CPU让出直到被另一个进程或者中断唤醒。因此需要避免进程唤醒通知的丢失。Xv6尽可能地以简单的方式解决这些问题,尽管如此,这些代码仍然十分棘手。
Figure 7.1: Switching from one user process to another. In this example, xv6 runs with one CPU(and thus one scheduler thread).
图 7.1 概述了从一个用户进程切换至另一个用户进程的步骤:一个通过(系统调用或中断)从用户到旧进程的内核线程的切换,一个到当前CPU的调度器线程的上下文切换,一个到新进程的内核线程的上下文切换,最后是到用户级进程的陷阱返回。Xv6的调度器在每个核都拥有独有的线程(以及保存的寄存器和堆栈),因为在待切换进程的内核堆栈上运行是不安全的:其他核心可能会将进程唤醒并执行这个进程,而在两个不同的核心上使用相同的堆栈的后果是灾难性的。在本节中,我们将研究在内核线程和调度器线程之间切换的机制。
线程间的切换涉及到将旧线程的CPU寄存器保存并将之前保存的新线程的寄存器复原;堆栈指针和指令计数器会被保存和恢复的事实意味着CPU会更换堆栈和将要执行的代码。
swtch
函数在内核线程切换时负责保存和恢复工作,函数并不直接涉及线程的内容,而是只将 32 个RISC-V寄存器的内容保存和恢复,并调用 contexts
。当一个进程让出CPU时,该进程的内核线程调用 swtch
将其上下文保存起来并返回至调度器线程。所有上下文都被保存至 struct context(kernel/proc.h:2)
中,而它本身也被包含于一个进程的 struct proc
中或是一个CPU的 struct cpu
中。
我们现在跟随进程由 swtch
进入调度器,我们在第四章可以看到中断的一个结束的可能性是 usertrap
调用 yield
。 yield
随后调用 sched
, sched
紧跟着调用 swtch
将 p->context
中的当前上下文保存下来,然后切换至之前存储在 cpu->context
中的调度器上下文。
swtch(kernel/swtch.S:3)
只保存被调用者所保存的寄存器;而C语言编译器负责在调用者中生成用以保存调用者所保存的寄存器到堆栈上的代码。 swtch
了解每个寄存器位于 struct context
中的偏移。它不保存程序计数器 pc
,反之, stwch
保存的是 ra
寄存器。该寄存器所包含的地址指向调用 swtch
函数的指令处。而后, swtch
将新的上下文中的寄存器恢复,该上下文保存的是之前调用 swtch
所保存的寄存器中的值。当 swtch
返回时,它返回至其恢复的 ra
寄存器中指向的位置上的指令,也就是这个新进程之前调用 swtch
的那个指令。此外,函数还返回至新线程的堆栈,因为那就是函数所恢复的 sp
所指向的地方。
在我们的例子中, sched
通过调用 swtch
来切换至 cpu->scheduler
以及每个CPU独占的调度器线程。该上下文是在之前 scheduler
调用 swtch(kernel/proc.c:456)
以切换至当前这个正在让出CPU的进程时被保存的。当我们一直在跟踪的 swtch
返回时,它返回的不是 sched
,而是 scheduler
,堆栈指针指向当前CPU但调度器的堆栈。
我们在上一节了解了 swtch
的底层细节;现在让我们将 swtch
看作一个给定的函数并研究一下从一个进程的内核线程通过调度器到另一个进程的切换过程。调度器以每个CPU都有的特殊线程的形式存在,每个调度器都运行着 scheduler
函数。这个函数负责决定哪个进程作为下一个运行的进程。一个想要让出CPU的进程必须先获取自己的进程锁 p->lock
,释放其他任何它持有的锁,更新它自身的状态 p->state
,而后调用 sched
。你可以在 yield (kernel/proc.c:496)
, sleep
和 exit
中看到这个序列。 sched
二次检查上面提到的部分要求是否满足(kernel/proc.c:480-485),而后检查一个隐含的条件:既然一个锁被获取,那么此时中断应已被禁用。最后, sched
调用 swtch
以将当前上下文保存至 p->context
并转换至 cpu->scheduler
中的调度器上下文。 swtch
返回至调度器的堆栈,仿佛 scheduler
的 swtch
已经返回一般。之后,调度器继续它的 for
循环,查找一个可以运行的进程,切换至该进程并重复这个过程。
我们可以看到xv6在调用 swtch
前和途中都持有着 p->lock
: swtch
的调用者必须在调用时已持有该锁,而后将锁的控制权移交。这种做法是不寻常的,通常来说获取一个锁的线程同时还负责将锁释放,这有利于确保正确性。但对于上下文切换而言,打破该惯例是有必要的,因为 p->lock
保护了执行 swtch
过程中时失效的进程 state
和 context
字段的不变性。一个可能会产生的问题的例子时,如果在 swtch
执行过程中 p->lock
不被持有,那么可能在 yield
将进程的状态设置为 RUNNABLE
后,但 swtch
还未使该进程停止使用其内核堆栈时,另外一个CPU决定运行这个进程,从而导致两个CPU在同一个堆栈上运行。这会导致混乱的产生。
内核线程让出其CPU的唯一地点位于 sched
,且永远切换至 scheduler
中的同一位置,同时也几乎永远都切换至其他之前调用了 sched
的内核线程。因此,如果一个人在xv6切换线程时输出当前执行的代码的位置,他将看到下面的简单模式:(kernel/proc.c:456), (kernel/proc.c:490), (kernel/proc.c:456), (kernel/proc.c:490)……
通过线程切换有意地将控制转交给彼此的程序有时被称作协程;在这个例子中, sched
和 scheduler
是彼此的协程。
在一种情况下调度器对 swtch
的调用不会在 sched
中结束。 allocproc
将新进程的上下文的 ra
寄存器设置为 forkret(kernel/proc.c:508)
,这样它的第一次 swtch
“返回”至 forkret
的起始位置。 forkret
的存在是为了释放 p->lock
,否则由于新进程需要像从 fork
返回一样返回至用户空间,它有可能反而从 usertrapret
处开始执行。
scheduler(kernel/proc.c:438)
运行了一个循环:寻找一个进程以运行,执行这个进程直到它 yield
,重复这个循环。调度器将进程表循环遍历以寻找一个可运行的进程(即 p->state == RUNNABLE
)。一旦调度器找到一个进程,调度器将每个CPU均有的用以指示当前正在执行的进程的变量 c->proc
设置为该进程,将进程标记为 RUNNING
,并调用 swtch
以开始运行该进程(kernel/proc.c:451:456)。
调度代码的结构的一个值得思考的角度是它对每个进程都强制维护了一组不变量,同时在这些不变量失效时持有 p->lock
。其中一个不变量时如果一个进程处于 RUNNING
状态,计时器中断所调用的 yield
必须可以安全地从进程中转移出去;这意味着CPU寄存器必须仍持有进程的寄存器的值(例如 swtch
还没将它们转移到一个 context
中),且 c->proc
必须指向这个进程。另一个不变量是 p->context
必须持有进程的寄存器 (例如他们没有实际上在真正的寄存器中),以及没有CPU正在该进程的内核堆栈上运行,以及没有CPU的 c->proc
指向至该进程。在 p->lock
被持有时常常能观测到这些属性不为真。