如果代码在内核中需要同时持有多个锁,那么有一点很重要,就是获取锁的顺序要相同。如果顺序不同,那么就会有死锁的风险。假设XV6中两个代码路径要获取锁A和B,但是路径1先获取A再获取B,而另一条路径先获取B再获取A。假设线程T1执行代码路径1并获取了锁A,而线程T2执行路径2并获取了锁B。那么接下来T1会尝试获取获取锁B而T2会尝试获取锁A。两个获取就肯定都会被阻塞,因为另一个线程持有需要的锁,并且不会释放直到它的acquire返回。为了避免这种死锁,所有代码路径必须以同样的顺序获取锁。对全局锁获取顺序的需要意味着锁实际上是每个函数规范的一部分:调用者必须以某种方式调用函数,使锁按约定的顺序被获取。
XV6有很多长度为2的涉及每个进程的锁的锁顺序链,因为在路径上sleep函数会工作。例如consoleintr是处理输入字符的中断程序。当一个新行到达,任何等待控制台输入的进程就会被唤醒。当调用wakeup时consoleintr持有cons.lock,而wakeup又会获取等待进程的锁来唤醒它。因此,避免全局死锁的锁顺序包含cons.lock锁必须在每个进程锁之前被获取的规则。文件系统代码包含XV6的最长的锁链。例如创建文件需要同时获取目录上的锁,新文件的inode的锁,磁盘块缓冲区的锁,磁盘驱动的vdisk_lock以及调用进程的锁。为了避免死锁,文件系统代码通常要求以一定顺序来获取锁。
遵守避免全局死锁的顺序可能会十分困难。有时候锁顺序会与程序结构的逻辑冲突,如模块M1调用模块M2,但是锁顺序要求M2的锁在M1之前获取。有时候也无法预知需要的锁,可能获取一个锁之后才能直到下一个锁是什么。这种情况出现于在文件系统中根据路径名连续查找模块以及wait和exit函数在进程表中查找子进程中。最后,死锁的危险通常会限制锁策略能够使用多细粒度的锁,越多的锁就意味着越多死锁的可能性。在内核实现中,避免死锁通常是很重要的一部分。
锁和中断处理程序XV6中有一些自旋锁保护了会同时被线程和中断处理程序使用的数据。例如clockintr定时器中断处理程序可能会增加ticks当一个内核线程同时在sys_sleep函数中读取ticks。tickslock锁会将两个访问串行化。
自旋锁和中断的交互会带来潜在的风险。假设sys_sleep持有锁,并且CPU产生了一个定时器中断。clockintr将会尝试申请锁,发现锁被持有,于是等待其被释放。在这种情况下,锁将永远不会被释放:只有sys_sleep会释放锁,但是sys_sleep不会释放锁直到clockintr返回。因此CPU会进入死锁状态,并且其他需要该锁的代码都会被冻结。
为了避免这种情况,如果一个自旋锁在中断处理程序中被使用,CPU必须在中断允许时不会持有该锁。XV6更加保守:当CPU申请任何锁时,XV6总是会在该CPU上关闭中断。中断可能仍在其他CPU上发生,因此中断的acquire可以等待一个线程释放自旋锁,只要不在同一个CPU上。
XV6会重新允许中断当一个CPU不再持有自旋锁,必须通过一些小的记录来处理嵌套临界区。acquire调用push_off而release调用pop_off来追踪当前CPU的嵌套的层次。当计数器为0时,pop_off恢复最外层临界区开始前的中断允许状态。intr_off和intr_on函数分别执行RISC-V的关和开中断指令。
在acquire设置lk->locked之前调用push_off是非常重要的。如果两者顺序交换,就会有一个小窗口,此时锁被获取而中断是允许的,如果不幸此时发生了中断,就可能会使系统死锁。相同的,release释放锁之后再调用pop_off也是很重要的。
指令和内存顺序自然地会认为程序以源代码语句出现的顺序来执行程序。但在很多编译器和CPU中,代码是乱序执行的从而来获得更高的性能。如果一条指令需要很多个周期来完成,CPU可能会更早地发射指令,使其与其他指令重叠,从而避免CPU停顿。例如CPU可能注意到一串指令序列A和B不依赖彼此,CPU就可能会先执行指令B,因为其输入比A的输入更早就绪或者为了将A和B的执行重叠起来。编译器也可能会进行类似的重排,通过先于源代码中之前的语句的指令发射一条语句的指令。
编译器和CPU允许通过不会改变一串代码执行结果的规则来重排语句。然而,这些允许重排的规则会改变并发代码的结果,并且很容易在多处理器上导致错误的行为。CPU的排序规则被成为内存模型。
例如push的代码,如果CPU将第4行对应的store指令移动到release之后就会引起灾难:
l = malloc(sizeof *l); l->data = data; acquire(&listlock); l->next = list; list = l; release(&listlock);如果这种重排发生了,这里就会有一个窗口使得其他CPU可以获取锁并且更新list,但是看见的并不是初始的list->next。