死锁

关于尚未发行的电子游戏，请见“死锁 (游戏)”。

“死结”重定向至此。关于有关绳结上的死结，请见“单结”。

死锁（英语：deadlock），又译为死结，计算机科学名词。当两个以上的运算单元，双方都在等待对方停止执行，以获取系统资源，但是没有一方提前退出时，就称为死锁。在多工操作系统中，操作系统为了协调不同线程，能否获取系统资源时，为了让系统正常运作，必须要解决这个问题。另一种相似的情况称为“活锁”。

P1、P2两个process都需要资源才能继续执行。P1拥有资源R2、还需要额外资源R1才能执行；P2拥有资源R1、还需要额外资源R2才能执行，两边都在互相等待而没有任何一个可执行。

四个行程（蓝线）竞争一种资源（灰色圆圈），遵循先右后左的策略。当所有行程同时锁定资源（黑线）时，就会发生死锁。可以透过打破对称性来解决死锁。

两个行程以相反的顺序竞争两个资源。

1. 经过一个行程。
2. 后面的行程需要等待。
3. 当第一个行程锁定第一个资源而第二个行程锁定第二个资源时，就会发生死锁。
4. 可以透过取消并重启第一个行程来解决死锁

简介

例如，一个进程p1占用了显示器，同时又必须使用打印机，而打印机被进程p2占用，p2又必须使用显示器，这样就形成了死锁。 因为p1必须等待p2发布打印机才能够完成工作并发布屏幕，同时p2也必须等待p1发布显示器才能完成工作并发布打印机，形成循环等待的死锁。

起因

如果系统中只有一个进程，当然不会产生死锁。如果每个进程仅需求一种系统资源，也不会产生死锁。不过这只是理想状态，在现实中是可遇不可求的。

死锁的四个条件是：

• 禁止抢占（no preemption）：系统资源不能被强制从一个进程中退出。

• 持有和等待（hold and wait）：一个进程可以在等待时持有系统资源。

• 互斥（mutual exclusion）：资源只能同时分配给一个行程，无法多个行程共享。

• 循环等待（circular waiting）：一系列进程互相持有其他进程所需要的资源。

死锁只有在四个条件同时满足时发生，预防死锁必须至少破坏其中一项。

预防

(A) 两个行程竞争一种资源，遵循先到先得的策略。 (B) 当两个行程同时锁定资源时，就会发生死锁。 (C) 可以透过破坏锁的对称性来解决死锁。 (D) 可以透过改变锁的机构对称性来防止死锁。

系统也可以尝试回避死锁。因为在理论上，死锁总是可能产生的，所以操作系统尝试监视所有进程，使其没有死锁。

消除

最简单的消除死锁的办法是重启系统。更好的办法是终止一个进程的运行。

同样也可以把一个或多个进程回滚到先前的某个状态。如果一个进程被多次回滚，迟迟不能占用必需的系统资源，可能会导致资源匮乏。

活锁

活锁（livelock），与死锁相似，死锁是行程都在等待对方先释放资源；活锁则是行程彼此释放资源又同时占用对方释放的资源。当此情况持续发生时，尽管资源的状态不断改变，但每个行程都无法获取所需资源，使得事情没有任何进展。

示例

假设两人正好面对面碰上对方：

• 死锁：两人互不相让，都在等对方先让开。
• 活锁：两人互相礼让，却恰巧站到同一侧，再次让开，又站到同一侧，同样的情况不断重复下去导致双方都无法通过。

参见

• 竞争危害