8.4 死锁的检测与恢复
一般来说,由于操作系统有并发,共享以及随机性等特点,通过预防和避免的手段达到排除死锁的目的是很困难的。这需要较大的系统开销,而且不能充分利用资源。为此,一种简便的方法是系统为进程分配资源时,不采取任何限制性措施,但是提供了检测和解脱死锁的手段:能发现死锁并从死锁状态中恢复出来。因此,在实际的操作系统中往往采用死锁的检测与恢复方法来排除死锁。
死锁检测与恢复是指系统设有专门的机构,当死锁发生时,该机构能够检测到死锁发生的位置和原因,并能通过外力破坏死锁发生的必要条件,从而使得并发进程从死锁状态中恢复出来。
1.放大观看>>)
图中所示为一个小的死锁的例子。这时进程P1占有资源R1而申请资源R2,进程P2占有资源R2而申请资源R1,按循环等待条件,进程和资源形成了环路,所以系统是死锁状态。进程P1,P2是参与死锁的进程。
下面我们再来看一看死锁检测算法。算法使用的数据结构是如下这些:
占有矩阵A:n*m阶,其中n表示并发进程的个数,m表示系统的各类资源的个数,这个矩阵记录了每一个进程当前占有各个资源类中资源的个数。
申请矩阵R:n*m阶,其中n表示并发进程的个数,m表示系统的各类资源的个数,这个矩阵记录了每一个进程当前要完成工作需要申请的各个资源类中资源的个数。
空闲向量T:记录当前m个资源类中空闲资源的个数。
完成向量F:布尔型向量值为真(true)或假(false),记录当前n个并发进程能否进行完。为真即能进行完,为假则不能进行完。
临时向量W:开始时W:=T。
算法步骤:
(1)W:=T,
对于所有的i=1,2,...,n,
如果A[i]=0,则F[i]:=true;否则,F[i]:=false
(2)找满足下面条件的下标i:
F[i]:=false并且R[i]〈=W
如果不存在满足上面的条件i,则转到步骤(4)。
(3)W:=W+A[i]
F[i]:=true
转到步骤(2)
(4)如果存在i,F[i]:=false,则系统处于死锁状态,且Pi进程参与了死锁。什麽时候进行死锁的检测取决于死锁发生的频率。如果死锁发生的频率高,那麽死锁检测的频率也要相应提高,这样一方面可以提高系统资源的利用率,一方面可以避免更多的进程卷入死锁。如果进程申请资源不能满足就立刻进行检测,那麽每当死锁形成时即能被发现,这和死锁避免的算法相近,只是系统的开销较大。为了减小死锁检测带来的系统开销,一般采取每隔一段时间进行一次死锁检测,或者在CPU的利用率降低到某一数值时,进行死锁的检测。
2.死锁的恢复
一旦在死锁检测时发现了死锁,就要消除死锁,使系统从死锁状态中恢复过来。
(1)最简单,最常用的方法就是进行系统的重新启动,不过这种方法代价很大,它意味着在这之前所有的进程已经完成的计算工作都将付之东流,包括参与死锁的那些进程,以及未参与死锁的进程。
(2)撤消进程,剥夺资源。终止参与死锁的进程,收回它们占有的资源,从而解除死锁。这时又分两种情况:一次性撤消参与死锁的全部进程,剥夺全部资源;或者逐步撤消参与死锁的进程,逐步收回死锁进程占有的资源。一般来说,选择逐步撤消的进程时要按照一定的原则进行,目的是撤消那些代价最小的进程,比如按进程的优先级确定进程的代价;考虑进程运行时的代价和与此进程相关的外部作业的代价等因素。
此外,还有进程回退策略,即让参与死锁的进程回退到没有发生死锁前某一点处,并由此点处继续执行,以求再次执行时不再发生死锁。虽然这是个较理想的办法,但是操作起来系统开销极大,要有堆栈这样的机构记录进程的每一步变化,以便今后的回退,有时这是无法做到的。
来源: http://www.bubuko.com/infodetail-2267898.html