6.4: Deadlock and lock ordering

注释：该内容基于原版课程的textbook和源代码，在大模型辅助翻译的基础上进行的整理。

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

在 xv6 中，由于 sleep 的工作方式（详见第 7 章），涉及每个进程锁（每个 struct proc 中的锁）的两级锁顺序链非常常见。
例如，consoleintr（kernel/console.c:136）是处理输入字符的中断例程。当有换行符到达时，应该唤醒任何等待控制台输入的进程。
为此，consoleintr 在调用 wakeup 时持有 cons.lock，而 wakeup 为唤醒进程会获取等待进程的锁。因此，全局的避免死锁锁顺序规则包括 cons.lock 必须在任何进程锁之前获取。
文件系统代码包含 xv6 中最长的锁链。例如，创建文件需要同时持有目录的锁、新文件的 inode 锁、磁盘块缓冲区的锁、磁盘驱动程序的 vdisk_lock 以及调用进程的 p->lock。
为避免死锁，文件系统代码总是按照前述顺序获取锁。

遵守全局避免死锁的顺序可能是非常困难的。有时锁顺序与逻辑程序结构冲突，例如，代码模块 M1 调用模块 M2，但锁顺序要求在获取 M1 的锁之前先获取 M2 的锁。
有时锁的身份事先不清楚，例如需要先持有一个锁才能确定下一个要获取的锁的身份。这种情况在文件系统中查找路径名的连续组件以及 wait 和 exit 的代码中寻找子进程时都会发生。
最后，死锁的风险通常对锁定方案的粒度提出限制，因为更多的锁意味着更多的死锁机会。避免死锁的需求通常是内核实现中的一个重要因素。