跳转到内容

死锁

本页使用了标题或全文手工转换
维基百科,自由的百科全书
P1、P2两个process都需要资源才能继续执行。P1拥有资源R2、还需要额外资源R1才能执行;P2拥有资源R1、还需要额外资源R2才能执行,两边都在互相等待而没有任何一个可执行。
四个行程(蓝线)竞争一种资源(灰色圆圈),遵循先右后左的策略。当所有行程同时锁定资源(黑线)时,就会发生死锁。可以透过打破对称性来解决死锁。

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

两个行程以相反的顺序竞争两个资源。
  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.