死锁
死锁(英语:deadlock),又译为死结,计算机科学名词。当两个以上的运算单元,双方都在等待对方停止执行,以获取系统资源,但是没有一方提前退出时,就称为死锁[1]。在多工操作系统中,操作系统为了协调不同线程,能否获取系统资源时,为了让系统正常运作,必须要解决这个问题。另一种相似的情况称为“活锁”。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/28/Process_deadlock.svg/220px-Process_deadlock.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/23/Deadlock_at_a_four-way-stop.gif/220px-Deadlock_at_a_four-way-stop.gif)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/df/Two_processes%2C_two_resources.gif/220px-Two_processes%2C_two_resources.gif)
- 经过一个行程。
- 后面的行程需要等待。
- 当第一个行程锁定第一个资源而第二个行程锁定第二个资源时,就会发生死锁。
- 可以透过取消并重启第一个行程来解决死锁
简介
编辑例如,一个进程p1占用了显示器,同时又必须使用打印机,而打印机被进程p2占用,p2又必须使用显示器,这样就形成了死锁。 因为p1必须等待p2发布打印机才能够完成工作并发布屏幕,同时p2也必须等待p1发布显示器才能完成工作并发布打印机,形成循环等待的死锁。
起因
编辑如果系统中只有一个进程,当然不会产生死锁。如果每个进程仅需求一种系统资源,也不会产生死锁。不过这只是理想状态,在现实中是可遇不可求的。
死锁的四个条件是:
- 禁止抢占(no preemption):系统资源不能被强制从一个进程中退出。
- 持有和等待(hold and wait):一个进程可以在等待时持有系统资源。
- 互斥(mutual exclusion):资源只能同时分配给一个行程,无法多个行程共享。
- 循环等待(circular waiting):一系列进程互相持有其他进程所需要的资源。
死锁只有在四个条件同时满足时发生,预防死锁必须至少破坏其中一项。
预防
编辑系统也可以尝试回避死锁。因为在理论上,死锁总是可能产生的,所以操作系统尝试监视所有进程,使其没有死锁。
消除
编辑最简单的消除死锁的办法是重启系统。更好的办法是终止一个进程的运行。
同样也可以把一个或多个进程回滚到先前的某个状态。如果一个进程被多次回滚,迟迟不能占用必需的系统资源,可能会导致资源匮乏。
活锁
编辑活锁(livelock),与死锁相似,死锁是行程都在等待对方先释放资源;活锁则是行程彼此释放资源又同时占用对方释放的资源。当此情况持续发生时,尽管资源的状态不断改变,但每个行程都无法获取所需资源,使得事情没有任何进展。
示例
编辑假设两人正好面对面碰上对方:
- 死锁:两人互不相让,都在等对方先让开。
- 活锁:两人互相礼让,却恰巧站到同一侧,再次让开,又站到同一侧,同样的情况不断重复下去导致双方都无法通过。
参见
编辑参考文献
编辑- ^ Coulouris, George. Distributed Systems Concepts and Design. Pearson. 2012: 716. ISBN 978-0-273-76059-7.