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

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

简介 编辑

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

起因 编辑

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

死锁的四个条件是:

  • 禁止抢占(no preemption):系统资源不能被强制从一个进程中退出。
  • 持有和等待(hold and wait):一个进程可以在等待时持有系统资源。
  • 互斥(mutual exclusion):资源只能同时分配给一个行程,无法多个行程共享。
  • 循环等待(circular waiting):一系列进程互相持有其他进程所需要的资源。

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

预防 编辑

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

消除 编辑

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

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

活锁 编辑

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

示例 编辑

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

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

参见 编辑

参考文献 编辑

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