03_处理机调度与死锁讲.pptVIP

P1 P2 r1 r2 不可简化 死锁检测算法（类似银行家算法） 基本思想 获得某时刻t系统中各类可利用资源的数目向量w(t),对于系统中的一组进程{P1,P2, …,Pn}，找出那些对各类资源请求数目均小于系统现有的各类可利用资源数目的进程。这样的进程可以获得它们所需要的全部资源并运行结束，当它们运行结束后释放所占有的全部资源，从而可用资源数目增加，将这样的进程加入到可运行结束的进程序列L中，然后对剩下的进程再作上述考查。如果一组进程{ P1,P2, …,Pn}中有几个进程不属于序列L中，那么它们会发生死锁。 死锁检测算法 死锁检测中的数据结构 可利用资源Available，它表示m类资源中每类资源可用数目 请求矩阵Request ，一个m×n矩阵，用以表示进程当前对各类资源的请求数目 分配矩阵Allocation，一个m×n矩阵，用以表示某一时刻的资源的分配情况 工作向量Work，表示系统可提供的各类资源的数目 进程向量L，记录当前已不占用资源的各进程 死锁检测算法步骤 把某时刻t的可用资源向量Available赋予Work 把不占用资源的进程(向量Allocation:=0)记入L表中， 即Li∪L 从进程集合中找到一个Requesti≤Work的进程，做如下处理： ① 将其资源分配图简化，释放出资源，增加工作向量 Work∶=Work+Allocationi ② 将它记入L表中 若不能把所有进程都记入L表中，说明系统状态S的资源分配图是不可完全简化的。因此，该系统状态将发生死锁 死锁检测的算法 Work:=Available; L:={Li|Allocationi=0∩Requesti=0} For all Li∈L do begin for all Requesti≤Work do begin Work:=Work+Allocationi; Li∪L; end end deadlock:= (L={p1,p2,…,Pn}); 应用死锁检测算法 应该何时调用检测算法？取决于两个因素 死锁可能发生的频率是多少？ 当死锁发生时，有多少进程会受影响？ 检测时机 当进程等待时检测死锁 其缺点是系统的开销大 定时检测 系统资源利用率下降时检测死锁 死锁的检测与解除 死锁的检测 死锁的解除 死锁的解除 当发现有进程死锁后，便应立即把它从死锁状态中解脱出来，重要的是以最小的代价恢复系统的运行。常用方法如下： 剥夺资源 从其他进程剥夺足够的资源给死锁进程，直到死锁环被打破，以解除死锁状态 撤消进程 撤消所有死锁进程 按照某种顺序逐个地撤消进程，直至有足够的资源可用，使死锁状态消除； 代价大，被终止进程的 前期工作必须放弃 系统开销大，每次终止进程时都要调 用死锁检测算法确定进程是否仍处于 死锁 死锁的解除 为解除死锁状态所需撤销的进程数目最小；或者，撤销进程所付出的代价最小； 可采用以下策略： （1）假定在死锁状态时，有死锁进程P1,P2,…,Pk。首先，撤销进程P1，使系统状态由S→U1，付出的代价为Cu1,然后，仍然从S状态中撤销进程P2，使状态由S→U2，其代价为Cu2，…,如此下去可得到状态U1,U2,…,Uk。 （2）若此时系统仍处于死锁状态，需再进一步撤销进程，如此下去，直至解除死锁状态为止。这种方法为解除死锁状态可能付出的代价将是(k(k-1)(k-2)…/2)C。花费代价较高，很不实际的方法。 死锁的解除 一个比较有效方法是对死锁状态做如下处理：从死锁状态S中先撤销一个死锁进程P1，使系统状态由S→U1，将P1记入被撤销进程的集合d(T)中，并把付出的代价C1加入到rc(T)中；对死锁进程P2，P3重复以上过程，得到状态U1,U2，Uk，然后按照撤销进程时所花费代价的大小，把它插入到由S状态所演变的新状态队列L中。显然，队列L中的第一个状态U1是由S状态花最小代价撤销一个进程所演变成的状态。在撤销一个进程后，若系统仍处于死锁状态，则再从U1状态按照上述处理方式在依次地撤销一个进程，得到U1‘， U2‘，… Uk‘状态，再从U‘状态中选取一个代价最小的Ui‘，如此下去，直到死锁状态解除为止。 S Uk Vk1 Vk2 Vkk U2 V21 V22 V2k U1 V12 V13 V1k W132 W13k P1(CU1) … … … P1(CU2) Pk(CUk) … P2 P3 Pk … W134 P2 W231 W23k … W234 P1 P4 Pk P4 Pk Wk21 Wk2k … Wk22 P1 P4 Pk 为把系统从死锁状