李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com 第 10讲 处理机调度与死锁（4） 李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com 1/

教学目标与内容 教学目标 教学内容 掌握银行家算法 理解死锁的检测与解除的方法 银行家算法 死锁的检测与解除 计算机科学与技术系 2/ 信息与教育技术中心 2/

复习 死锁的定义 死锁的原因 死锁的必要条件 处理死锁的基本方法 预防死锁有哪些方法？ 什么是安全状态？什么是不安全状态？ 3/

利用银行家算法避免死锁 银行家算法中的数据结构 可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available［j］=K，则表示系统中现有Rj类资源K个。 4/

利用银行家算法避免死锁 最大需求矩阵Max。这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max［i,j］=K，则表示进程i需要Rj类资源的最大数目为K。 分配矩阵Allocation。这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation［i,j］=K，则表示进程i当前已分得Rj类资源的数目为K。 5/

利用银行家算法避免死锁 需求矩阵Need。这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need［i,j］=K，则表示进程i还需要Rj类资源K个，方能完成其任务。 Need［i,j］=Max［i,j］-Allocation［i,j］ 6/

利用银行家算法避免死锁 银行家算法 设Requesti是进程Pi的请求向量，如果Requesti[j］=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： (1)如果Requesti［j］≤Need［i,j］，便转向步骤（2）；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 (2)如果Requesti［j］≤Available［j］，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。 7/

利用银行家算法避免死锁 (3)系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Available［j]∶=Available［j]-Requesti［j]; Allocation［i,j]∶=Allocation［i,j]+Requesti［j]; Need［i,j]∶=Need［i,j]-Requesti［j]; 8/

利用银行家算法避免死锁 系统执行安全性算法，检查此次资源分配后，系 统是否处于安全状态。若安全，才正式将资源 分配给进程Pi，以完成本次分配；否则， 将本次 的试探分配作废，恢复原来的资源分配状态，让 进程Pi等待。 9/

利用银行家算法避免死锁 安全性算法 (1)设置两个向量 (2) 从进程集合中找到一个能满足下述条件的进程： a.工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work∶=Available; b.Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]:=false; 当有足够资源分配给进程时， 再令Finish[i]:=true。 (2) 从进程集合中找到一个能满足下述条件的进程： Finish［i］=false; Need［i,j］≤Work［j］； 若找到， 执行步 骤(3)， 否则，执行步骤(4)。 10/

利用银行家算法避免死锁 (3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出 分配给它的资源，故应执行： Work[j]:=Work[j］+Allocation[i,j］; Finish[i] :=true; go to step 2; (4)如果所有进程的Finish[i]=true都满足， 则表示系统处于安 全状态；否则，系统处于不安全状态。 11/

利用银行家算法避免死锁 银行家算法举例 假定系统中有五个进程｛P0, P1, P2, P3, P4｝和三类资源｛A, B, C｝，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图 3-16 所示。 12/

利用银行家算法避免死锁 图 3-16 T0时刻的资源分配表 13/

利用银行家算法避免死锁 T0时刻的安全性： 图 3-17 T0时刻的安全序列 14/

利用银行家算法避免死锁 Request1(1, 0, 2)≤Need1(1, 2, 2) P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查： Request1(1, 0, 2)≤Need1(1, 2, 2) Request1(1, 0, 2)≤Available (3, 3, 2) 系统先假定可为P1分配资源，并修改Available, Allocation1和Need1向量，由此形成的资源变化情况如图 3-18所示。 再利用安全性算法检查此时系统是否安全。 15/

利用银行家算法避免死锁 Request1(1，0，2) 图 3-18 资源变化情况 16/

利用银行家算法避免死锁 图 3-19 申请分配后 17/

利用银行家算法避免死锁 图 3-20 P1申请资源时的安全性检查 18/

利用银行家算法避免死锁 P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查： Request4(3, 3, 0)≤Need4(4, 3, 1); Request4(3, 3, 0) ≤ Available (2, 3, 0)，让P4等待。 P0请求资源：P0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查： Request0(0, 2, 0)≤Need0(7, 4, 3); Request0(0, 2, 0)≤Available(2, 3, 0); 系统暂时先假定可为P0分配资源，并修改有关数据，如图 3-21 所示。 19/

利用银行家算法避免死锁 图 3-21为P0分配资源后的有关资源数据 20/

利用银行家算法避免死锁 P0请求：Reqest(0,1,0) Allocation A B C Need Available P0 0 1 0 7 4 3 2 3 0 P1 3 0 2 0 2 0 P2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 21/

利用银行家算法避免死锁 试探分配后 2 2 0 P1 5 2 2 P3 7 3 3 P4 7 3 5 P0 7 5 5 P2 10 5 7 2 2 0 P1 5 2 2 P3 7 3 3 P4 7 3 5 P0 7 5 5 P2 10 5 7 Allocation Need Available P0 0 2 0 7 3 3 2 2 0 P1 3 0 2 P2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 22/

预防死锁的方法 Work Allocation Need W+A Finish P1 2 2 0 3 0 2 0 2 0 5 2 2 T 2 2 0 3 0 2 0 2 0 5 2 2 T P3 2 1 1 0 1 1 7 3 3 P4 0 0 2 4 3 1 7 3 5 P0 7 5 5 P2 6 0 0 10 5 7 安全系列 23/

死锁的检测与解除 死锁的检测 当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段。 保存有关资源的请求和分配信息； 提供一种算法，以利用这些信息来检测系统是否已经进入死锁状态。 24/

死锁的检测与解除 资源分配图(Resource Allocation Graph) 图 3-120 每类资源有多个时的情况 25/

死锁的检测与解除 凡属于E中的一个边e∈E，都连接着P中的一个结点和R中的一个结点，e={pi, rj}是资源请求边，由进程pi指向资源rj， 它表示进程pi请求一个单位的rj资源。e={rj, pi}是资源分配边，由资源rj指向进程pi, 它表示把一个单位的资源rj分配给进程pi。 26/

死锁的检测与解除 死锁定理 S为死锁状态的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。 图 3-21 资源分配图的简化 27/

死锁的检测与解除 死锁检测中的数据结构 可利用资源向量Available，它表示了m类资源中每一类资源的可用数目。 把不占用资源的进程(向量Allocation∶=0)记入L表中， 即Li∪L。 从进程集合中找到一个Requesti≤Work的进程，做如下处理： 将其资源分配图简化，释放出资源，增加工作向量Work∶=Work+Allocationi。 将它记入L表中。 28/

死锁的检测与解除 若不能把所有进程都记入L表中， 便表明系统状态S的资源分配图是不可完全简化的。 因此，该系统状态将发生死锁。 Work ∶=Available; L∶={Li|Allocationi=0∩Requesti=0} for all Li L do begin for all Requesti≤Work do Work∶=Work+Allocationi; Li∪L; end deadlock∶ = (L={p1, p2, …, pn}); 若不能把所有进程都记入L表中， 便表明系统状态S的资源分配图是不可完全简化的。 因此，该系统状态将发生死锁。 29/

死锁的检测与解除 死锁的解除 剥夺资源 撤消进程 30/

小结 银行家算法 死锁的检测与解除 31/

作业 P119 21 ,22,30,31 32/