任何操作系统的进程都可能比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
的不同功能分开。
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
);当有大量的读者和写者等在相同的管道上时(当然这种情况不太可能发生),这可能会使系统更高效。在检查睡眠状态的循环里,管道代码睡眠了;如果有多个读者或写者,除了第一个进程外,所有被唤醒的进程都发现条件是假的并继续睡眠。
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标记。