XV6学习(10)锁 (3)

如果代码在内核中需要同时持有多个锁,那么有一点很重要,就是获取锁的顺序要相同。如果顺序不同,那么就会有死锁的风险。假设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。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpyzgp.html