3第三章处理机的调度与死锁第四版课案.ppt

　2．银行家算法 　　设Request i是进程Pi的请求向量，如果Request i[j]=K，表示进程P i需要K个R j类型的资源。当P i发出资源请求后，系统按下述步骤进行检查： 　　(1) 如果Request i[j]≤Need[i,j]，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 　　(2) 如果Requesti[j]≤Available[j]，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。 　　(3) 系统试探着把资源分配给进程P i，并修改下面数据结构中的数值： Available[j]:= Available[j]-Request i[j]； Allocation[i,j]:= Allocation[i,j]+Request i[j]； Need[i,j]:= Need[i,j]-Request i[j]； 　　(4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 　　3．安全性算法 　　系统所执行的安全性算法可描述如下： 　　(1) 设置两个向量： 　　① 工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work:=Available。 　　② Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]:=false；当有足够资源分配给进程时，再令Finish[i]:=true。 　　(2) 从进程集合中找到一个能满足下述条件的进程： 　　① Finish[i]=false； 　　② Need[i,j]≤Work[j]；若找到，执行步骤(3)，否则，执行步骤(4)。 　　(3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Work[j]:= Work[j]+Allocation[i,j]； Finish[i]:=true； go to step 2； (4) 如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。 　4．银行家算法之例 　　假定系统中有五个进程{P0，P1，P2，P3，P4}和三类资源{A，B，C}，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图所示。 T0时刻的资源分配表 　　(1) T0时刻的安全性：利用安全性算法对T0时刻的资源分配情况进行分析(见图所示)可知，在T0时刻存在着一个安全序列{P1，P3，P4，P2，P0}，故系统是安全的。 　T0时刻的安全序列 　　(2) ?P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查： 　　① Request1(1，0，2)≤Need1(1，2，2) 　　② Request1(1，0，2)≤Available1(3，3，2) 　　③ 系统先假定可为P1分配资源，并修改Available，Allocation1和Need1向量，由此形成的资源变化情况如图中的圆括号所示。 ④ 再利用安全性算法检查此时系统是否安全。如图所示。 　P1申请资源时的安全性检查 　　(3) ?P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查： 　　① Request4(3，3，0)≤Need4(4，3，1)； 　　② Request4(3，3，0)≤Available(2，3，0)，让P4等待。 　　(4) ?P0请求资源：P0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查： 　　① Request0(0，2，0)≤Need0(7，4，3)； 　　② Request0(0，2，0)≤Available(2，3，0)； 　　③ 系统暂时先假定可为P0分配资源，并修改有关数据，如图3-18所示。 　为P0分配资源后的有关资源数据 　(5) 进行安全性检查：可用资源Available(2，1，0)已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。 　　如果在银行家算法中，把P0发出的请求向量改为Request0(0，1，0)，系统是否能将资源分配给它，请读者考虑。 作业：pp119 第30和31题 3.8　死锁的检测与解除 3.8.1　死锁的检测 　　当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段，为此，系统必须做到： 　　(1) 保存有关资源的请求和分配信息； 　　(2) 提供一种算法，以利用这些信息来检测系统是否已进