操作系统教程（第6版）课件6.16 死锁的避免.pptx

理解死锁的避免

掌握银行家算法

理解银行家算法(例)计算机操作系统6并发程序设计–6.6死锁6.6.3死锁的避免

死锁的避免当不能防止死锁的产生时，如果能掌握并发进程中与每个进程有关的资源申请情况，仍然可以避免死锁的发生只需在为申请者分配资源前先测试系统状态，若把资源分配给申请者会产生死锁的话，则拒绝分配，否则接收申请，为它分配资源

银行家算法银行家算法：借钱给有偿还能力的客户系统首先检查申请者对资源的最大需求量，如果现存的资源可以满足它的最大需求量时，就满足当前的申请换言之，仅仅在申请者可能无条件地归还它所申请的全部资源时，才分配资源给它

银行家算法(例)为了进一步说明这种算法，考虑下面的例子。假设系统有三个进程P,Q,R，系统只有一类资源共10个，目前分配情况如下：进程已占资源还需要申请数P44Q22R27

银行家算法(例)P或者R再申请资源时，不能分配，因为现在只剩下2个资源，不能满足它们的最大需求进程已占资源还需要申请数P44Q22R36进程已占资源还需要申请数P53Q22R27对P执行分配剩余资源1对R执行分配剩余资源1

掌握死锁检测

掌握死锁检测的方法

掌握死锁检测后的解决方法

计算机操作系统6并发程序设计–6.6死锁6.6.4死锁的检测

死锁的检测解决死锁问题的另一条途径是死锁检测方法这种方法对资源的分配不加限制，但系统定时运行一个“死锁检测”程序，判断系统内是否已出现死锁，若检测到死锁则设法加以解除

死锁的检测检测的一种方法：可设置两张表格来记录进程使用资源的情况等待资源表记录每个被阻塞进程等待的资源占用资源表记录每个进程占有的资源进程申请资源时，先查该资源是否为其它进程所占用；若资源空闲，则把该资源分配给申请者且登入占用资源表；否则，则登入进程等待资源表

死锁的检测资源占用进程r1P1r2P2r3P3r4P4r5P5……进程等待资源P1r1P2r2P3r3……

死锁的检测死锁检测程序定时检测这两张表，若有进程Pi等待资源rk，且rk被进程Pj占用，则说Pi和Pj具有“等待占用关系”，记为W(Pi,Pj)死锁检测程序反复检测这两张表，可以列出所有的“等待占用关系”如果出现W(Pi,Pj),W(Pj,Pk),……,W(Pm,Pn),W(Pn,Pi)时，显然，系统中存在一组循环等待资源的进程：Pi,Pj,Pk,……,Pm,Pn，也就是说出现了死锁

死锁检测的数据结构把两张表格中记录的进程使用和等待资源的情况用一个矩阵A来表示P1P2......PnP1b11b12......bn2P2b21b22......bn2..................Pnbn1bn2......bn2进程进程A[bij]其中bij=1当Pi等待被Pj占用的资源时0当Pi与Pj不存在等待占用关系时

死锁检测的算法死锁检测程序可用Warshall的传递闭包算法检测是否有死锁发生，即对矩阵A构造传递闭包A*[bij]A*[bij]中的每个bij是对A[bij]执行如下算法： fork:=1tondo fori:=1tondo forj:=1todo bij:=bij?(bik?bkj)

死锁检测后的解决办法可以采用重新启动进程执行的办法，恢复工作应包含重启动一个或全部进程，以及从哪一点开始重启动全部卷入死锁从头开始启动，但这样的代价是相当大的在进程执行过程中定时设置校验点，从校验点开始重执行中止一个卷入死锁的进程，以后重执行