3.6死锁的检测与解除
当系统为进程分配资源时,若未采取任何限制性措施,则系统必须提供检测和解除死锁的手段,为此系统必须:
- 保存有关资源的请求和分配信息;
- 提供一种算法,以利用这些信息来检测系统是否已进入死锁状态。
资源分配图
系统死锁可利用资源分配图来描述。
圆圈表示进程
方框表示一类资源,其中的一个点代表一个该类资源
请求边由进程指向方框中的资源
分配边则由方框中的一个点即资源。
一、死锁的检测
1.检测时机:
- 当进程等待时检测死锁
- 定时检测
- 系统资源利用率下降时检测死锁
2.死锁定理
利用资源分配图简化法来检测死锁。
简化方法如下:
(1)在资源分配图中找出一个既不阻塞又非独立的进程结点Pi,在顺利的情况下运行完毕,释放其占有的全部资源。
(2)由于释放了资源,这样能使其它被阻塞的进程获得资源继续运行。消去了Pi的边。
(3)经过一系列简化后,若能消去图中所有边,使结点都孤立,称该图是可完全简化的。
S状态为死锁状态的充分条件是当且仅当S状态的资源分配图是不可完全简化的。<死锁定理>
死锁检测算法:
- 每个进程和资源指定唯一编号
- 设置一张资源分配表
记录各进程与其占用资源之间的关系 - 设置一张进程等待表
记录各进程与要申请资源之间的关系
反复检测这两张表,列出所有等待与分配的关系,若出现循环等待,则出现了死锁!
二、死锁的解除
当发现进程死锁时,便应立即把它们从死锁状态中解脱出来。常采用的方法是:
- 剥夺资源。从其他进程剥夺足够数量的资源给死锁进程以解除死锁状态。
- 撤销进程。最简单的是让全部进程都死掉;温和一点的是按照某种顺序逐个撤销进程,直至有足够的资源可用,使死锁状态消除为止。