死锁和锁顺序

如果内核中的一个代码路径必须同时持有多个锁，那么所有代码路径以相同的顺序获取这些锁是很重要的。如果它们不这样做，就有死锁的风险。假设 xv6 中的两个代码路径需要锁 A 和 B，但代码路径 1 按 A 然后 B 的顺序获取锁，而另一个路径按 B 然后 A 的顺序获取它们。假设线程 T1 执行代码路径 1 并获取锁 A，线程 T2 执行代码路径 2 并获取锁 B。接下来 T1 将尝试获取锁 B，而 T2 将尝试获取锁 A。两个获取都将无限期地阻塞，因为在这两种情况下，另一个线程都持有需要的锁，并且在它的获取返回之前不会释放它。为了避免这种死锁，所有代码路径都必须以相同的顺序获取锁。需要一个全局锁获取顺序意味着锁实际上是每个函数规范的一部分：调用者必须以导致锁按约定顺序获取的方式调用函数。

由于 sleep 的工作方式（参见第 7 章），Xv6 有许多涉及每个进程锁（每个 struct proc 中的锁）的长度为 2 的锁顺序链。例如，consoleintr 是处理键入字符的中断例程。当一个新行到达时，任何等待控制台输入的进程都应该被唤醒。为此，consoleintr 在调用 wakeup 时持有 cons.lock，wakeup 会获取等待进程的锁以唤醒它。因此，全局死锁避免锁顺序包括 cons.lock 必须在任何进程锁之前获取的规则。文件系统代码包含 xv6 最长的锁链。例如，创建一个文件需要同时持有一个目录的锁、一个新文件 inode 的锁、一个磁盘块缓冲区的锁、磁盘驱动程序的 vdisk_lock 以及调用进程的 p->lock。为了避免死锁，文件系统代码总是按前面句子中提到的顺序获取锁。

遵守全局死锁避免顺序可能出人意料地困难。有时锁顺序与逻辑程序结构冲突，例如，也许代码模块 M1 调用模块 M2，但锁顺序要求在 M1 中的锁之前获取 M2 中的锁。有时锁的身份事先不知道，也许是因为必须持有一个锁才能发现下一个要获取的锁的身份。这种情况在文件系统中查找路径名的连续组件时出现，在 wait 和 exit 的代码中搜索进程表以查找子进程时也出现。最后，死锁的危险通常是对锁方案可以做得多细粒度的一个约束，因为更多的锁通常意味着更多的死锁机会。避免死锁的需要通常是内核实现中的一个主要因素。