死锁

(重定向自死結

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

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),与死锁相似,死锁是行程都在等待对方先释放资源;活锁则是行程彼此释放资源又同时占用对方释放的资源。当此情况持续发生时,尽管资源的状态不断改变,但每个行程都无法获取所需资源,使得事情没有任何进展。

示例

编辑

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

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

参见

编辑

参考文献

编辑
  1. ^ Coulouris, George. Distributed Systems Concepts and Design. Pearson. 2012: 716. ISBN 978-0-273-76059-7.