正文
环岛道路的交通堵塞（图片来源于网络）
这种情况发生的原因是车辆的等待构成了循环，在这个循环中每辆车的状态都是等待前车，因此所有车都等不到到它所要等待的。这种车辆死锁状态会持续恶化并产生严重的后果：首先造成路口交通堵塞，而堵塞如果进一步扩大会导致大面积交通瘫痪。车辆死锁很难自愈，通过自身走出死锁状态非常困难或者需要很长时间，一般都只能通过人工（如交通警察）干预才能解决。
在多线程或者分布式系统程序中，死锁也会发生。其本质和上述的路口车辆堵塞是一样的，都是因为参与者构成了循环等待，使得所有参与者都等不到想要的结果，从而永远等在那里不能取得进展。Linux 内核当然也会发生死锁，如果核心部分（Core），如调度器和内存管理，或者子系统，如文件系统，发生死锁，都会导致整个系统不可用。
死锁是随机发生的。就像上图中环岛的情况一样，环岛就在那里而死锁并不是总在发生。但是环岛本身就是死锁隐患，尤其在交通压力比较大的路口，环岛会比较容易产生死锁。而如果这种路口设计成交通信号灯就会好很多，如果设计成立交桥则又会好很多。在程序中，我们把可能产生死锁的场景称作潜在死锁（Potential Deadlock Scenario），而把即将发生或正在发生的死锁称为死锁实例（Concrete Deadlock）。
如何对付死锁一直是学术界和应用领域积极研究和解决的问题。我们可以将对死锁的解决方案粗略地分为：死锁发现（Detection）、死锁避免（Prevention）和死锁预测（Prediction）。死锁发现是指在在程序运行中发现死锁实例；死锁避免则是在发现死锁实例即将生成时进一步防止这个实例；而死锁预测则是通过静态或者动态方法找出程序中的潜在死锁，从而从根本上预先消除死锁隐患。
在死锁中，因为用锁（Lock）不当而导致的死锁是一个重要死锁来源。锁是同步的一种主要手段，用锁是不可避免的。对于复杂的同步关系，锁的使用会比较复杂。如果使用不当很容易造成锁的死锁。从等待的角度来说，锁的死锁是由于参与线程等待锁的释放，而这种等待构成了等待循环，如 ABBA 死锁：
其中，线程中的黑色箭头代表线程当前执行语句，红色箭头表示线程语句之间的等待关系。可以看到，红色箭头构成了一个圆圈（或者循环）。再一次回顾潜在死锁和死锁实例，如果这两个线程执行的时间稍有改变，那么很有可能不会发生死锁实例，比如如果让 Thread1 执行完这一段代码 Thread2 才开始执行。但是这样的用锁行为（Locking Behavior）毫无疑问是一个潜在死锁。
进一步可以看出，如果我们能够追踪并分析程序的用锁行为就有可能预测死锁或者找出潜在死锁，而不是等死锁发生时才能检测出死锁实例。Linux 内核的 Lockdep 工具就是去刻画内核的用锁行为进而预测潜在死锁并报告出来。
Lockdep 能够刻画出一类锁（Lock Class）的行为，主要是通过记录一类锁中所有锁实例的加锁顺序（Locking Order），即如果一个线程拿着锁A，在没有释放前又去拿锁B，那么锁A和锁B就有一个 A->B 的加锁顺序，在 Lockdep 中这个加锁顺序被称为：锁依赖 （Lock Dependency）。同样的，对于 ABBA 类型的死锁，我们并不需要 Thread1 和 Thread2 恰好产生一个死锁实例，只要有线程产生了 A->B 加锁顺序行为，又有线程产生了一个 B->A 的加锁顺序行为，那么这就构成了一个潜在死锁，如下图所示：
由此推广开来，我们可以把所有的加锁顺序（即锁依赖）记录和保存下来，构成一个加锁顺序图（Graph）。其中，如果有锁依赖 A->B ，又有锁依赖 B->C ，那么由于锁依赖的关系（Relation）是传递的（Transitive），因此我们还可以得到锁依赖 A->C 。A->B 和 B->C 称为直接依赖（Direct Dependency），而 A->C 称为间接依赖（Indirect Dependency）。对于每一个新的直接锁依赖，我们去检查这个依赖是否和图中已经存在的锁依赖构成一个循环，如果是的话，那么我们就可以预测产生了一个潜在死锁。
