1、 王xx主要内容银行家算法的实现思想为什么叫银行家算法？如何利用银行家算法避免死锁？例题分析实验分析总结23银行家算法的实现思想 银行家算法是一个非常经典的银行家算法是一个非常经典的避免死锁避免死锁的算法，它的基本的算法，它的基本思想是思想是：当某个进程提出申请时，必须先判断把资源分配给当某个进程提出申请时，必须先判断把资源分配给该进程后，会不会引起死锁；如果不会，再进行分配。否则，该进程后，会不会引起死锁；如果不会，再进行分配。否则，就不分配。就不分配。这样做能保证在任何时刻，至少有一个进程可以得到所需这样做能保证在任何时刻，至少有一个进程可以得到所需要的全部资源，而执行结束。当这个进程执行
2、结束后，就会要的全部资源，而执行结束。当这个进程执行结束后，就会释放本身所占资源，放到系统新的资源中，而这些新的资源释放本身所占资源，放到系统新的资源中，而这些新的资源又可以满足另一个进程的最大需求，这样就保证了所有进程，又可以满足另一个进程的最大需求，这样就保证了所有进程，都能在有限的时间内执行完毕。都能在有限的时间内执行完毕。主要内容银行家算法的实现思想为什么叫银行家算法？如何利用银行家算法避免死锁？例题分析实验分析总结45为什么叫银行家算法？该算法就相当于银行贷款一样，银行要把一笔款贷该算法就相当于银行贷款一样，银行要把一笔款贷给你，首先要对你的资产或者你的项目进行评估，看你给你，首先要
3、对你的资产或者你的项目进行评估，看你贷款以后有没有能力偿还，如果没有能力偿还，银行肯贷款以后有没有能力偿还，如果没有能力偿还，银行肯定是不会把款贷给你的。如果能够偿还，银行就可以贷定是不会把款贷给你的。如果能够偿还，银行就可以贷款给你。款给你。主要内容银行家算法的实现思想为什么叫银行家算法？如何利用银行家算法避免死锁？例题分析实验分析总结61、银行家算法中的数据结构(1)可利用资源向量可利用资源向量Available。这是一个含有这是一个含有m个元素的数组，其个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置
4、的该类全部可用资源的数目，其数值随该类资源的分配和回收配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果而动态地改变。如果Availablej=K，则表示系统中现有，则表示系统中现有Rj类资类资源源K个。个。Needi,j=Maxi,j-Allocationi,j(2)最大需求矩阵最大需求矩阵Max。这是一个这是一个nm的矩阵，它定义了系统中的矩阵，它定义了系统中n个进程中的每一个进程对个进程中的每一个进程对m类资源的最大需求。如果类资源的最大需求。如果Maxi,j=K，则表示进程则表示进程i需要需要Rj类资源的最大数目为类资源的最大数目为K。(3)分配矩阵分配矩阵A
5、llocation。这也是一个这也是一个nm的矩阵，它定义了系统的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K，则表示进程，则表示进程i当前已分得当前已分得Rj类资源的数目为类资源的数目为K。(4)需求矩阵需求矩阵Need。这也是一个这也是一个nm的矩阵，用以表示每一个进的矩阵，用以表示每一个进程尚需的各类资源数。如果程尚需的各类资源数。如果Needi,j=K，则表示进程，则表示进程i还需要还需要Rj类资源类资源K个，方能完成其任务。个，方能完成其任务。2、银行家算法设设Requesti是进程是进程
6、Pi的请求向量，如果的请求向量，如果Requestij=K，表示进程，表示进程Pi需要需要K个个Rj类型的资源。当类型的资源。当Pi发出资源请求后，系统按下述步骤发出资源请求后，系统按下述步骤进行检查：进行检查：(1)如果如果RequestijNeedi,j，便转向步骤，便转向步骤2；否则认为出错，；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。因为它所需要的资源数已超过它所宣布的最大值。(2)如果如果RequestijAvailablej，便转向步骤，便转向步骤(3)；否则，表；否则，表示尚无足够资源，示尚无足够资源，Pi须等待。须等待。(3)系统试探着把资源分配给进程系统试探着
7、把资源分配给进程Pi，并修改下面数据结构中的数，并修改下面数据结构中的数值：值：Availablej =Availablej-Requestij;Allocationi,j =Allocationi,j+Requestij;Needi,j =Needi,j-Requestij;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；，以完成本次分配；否则，否则，将本次的试探分配作废，恢复原来的资源分配状态，让进将本次的试探分配作废，恢复原来
8、的资源分配状态，让进程程Pi等待。等待。3、安全性算法(1)设置两个向量：设置两个向量：工作向量工作向量Work:它表示系统可提供给进程继续它表示系统可提供给进程继续运行所需的各类资源数目，它含有运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，个元素，在执行安全算法开始时，Work =Available;Finish:它表示系统是否有足够的资源分配给它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做进程，使之运行完成。开始时先做Finishi =false;当有足够资当有足够资源分配给进程时，源分配给进程时，再令再令Finishi =true。(2)从进程集合中找到一
9、个能满足下述条件的进程：从进程集合中找到一个能满足下述条件的进程：Finishi=false;Needi,jWorkj；若找到，若找到，执行步骤执行步骤(3)，否则，执否则，执行步骤行步骤(4)。(3)当进程当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：的资源，故应执行：Workj =Worki+Allocationi,j;Finishi =true;go to step 2;(4)如果所有进程的如果所有进程的Finishi=true都满足，都满足，则表示系统处于安全状则表示系统处于安全状态；否则，系统处于不安全
10、状态。态；否则，系统处于不安全状态。主要内容银行家算法的实现思想为什么叫银行家算法？如何利用银行家算法避免死锁？例题分析实验分析总结10例题分析假定系统中有假定系统中有5个进程个进程P1,P2,P3,P4,P5和和3类资源类资源A,B,C，各类资，各类资源的数量分别为源的数量分别为10,5,7，在，在T0时刻的资源分配情况如表时刻的资源分配情况如表1所示。所示。试问：试问：(1)该状态是否安全？该状态是否安全？(2)若进程若进程P2提出请求提出请求Request(1,0,2)后，系统能否将资源后，系统能否将资源分配给它？分配给它？MaxAllocationNeedAvailableA B CA
11、 B CA B CA B CP1 7 5 3 0 1 0 7 4 3 3 3 2P2 3 2 2 2 0 0 1 2 2P3 9 0 2 3 0 2 6 0 0P4 2 2 2 2 1 1 0 1 1P5 4 3 3 0 0 2 4 3 1资源进程表1：T0时刻的资源分配表 例题分析解答解答:(1)T0时刻的安全性：利用安全性算法对时刻的安全性：利用安全性算法对T0时刻的资源分配情时刻的资源分配情况进行分析，可知，在况进行分析，可知，在T0时刻存在着一个安全序列时刻存在着一个安全序列P2,P4,P5,P3,P1，因此，系统是安全的。因此，系统是安全的。表2：T0时刻的安全序列WorkNeedA
12、llocationWork+AllocationFinishA B CA B CA B CA B CP2 3 3 2 1 2 2 2 0 0 5 3 2TureP4 5 3 2 0 1 1 2 1 1 7 4 3TureP5 7 4 3 4 3 1 0 0 2 7 4 5 TureP3 7 4 5 6 0 0 3 0 2 10 4 7TureP1 10 4 7 7 4 3 0 1 0 10 5 7Ture进程资源例题分析(2)P2请求资源：请求资源：P2发出请求向量发出请求向量Request2(1,0,2)，系统按照银行家算，系统按照银行家算法进行检查：法进行检查：Request2(1,0,2
13、)Need2(1,2,2)Request2(1,0,2)Available2(3,3,2)系统先假定系统先假定P2分配资源，并修改分配资源，并修改Available，Allocation2和和Need2向向量，由此形成的资源变化情况如表量，由此形成的资源变化情况如表3所示：所示：MaxAllocationNeedAvailableA B CA B CA B CA B CP1 7 5 3 0 1 0 7 4 3 2 3 0P2 3 2 2 3 0 2 0 2 0P3 9 0 2 3 0 2 6 0 0P4 2 2 2 2 1 1 0 1 1P5 4 3 3 0 0 2 4 3 1表3：T1时刻的
14、资源分配表 资源进程例题分析再利用安全性算法检查此时系统是否是安全的。如表再利用安全性算法检查此时系统是否是安全的。如表4所示。所示。表4：T1时刻的安全序列WorkNeedAllocationWork+AllocationFinishA B CA B CA B CA B CP2 3 3 2 1 2 2 2 0 0 5 3 2TureP4 5 3 2 0 1 1 2 1 1 7 4 3TureP5 7 4 3 4 3 1 0 0 2 7 4 5 TureP1 7 4 5 6 0 0 3 0 2 10 4 7TureP3 10 4 7 7 4 3 0 1 0 10 5 7Ture进程资源由所进行
15、的安全性检查得知，可以找到一个安全序列由所进行的安全性检查得知，可以找到一个安全序列P2,P4,P5,P1,P3。因此，系统是安全的，可以立即将。因此，系统是安全的，可以立即将P2所申请的资所申请的资源分配给它。源分配给它。主要内容银行家算法的实现思想为什么叫银行家算法？如何利用银行家算法避免死锁？例题分析实验分析总结15实验分析实验分析主要内容银行家算法的实现思想为什么叫银行家算法？如何利用银行家算法避免死锁？例题分析实验分析总结18总结银行家算法资源分配的原则 当一个进程对资源的最大需求量不超过系统中的资源数时可以接当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程纳该进程当进程可以分期请求资源，但请求的总数不能超过最大需求量当进程可以分期请求资源，但请求的总数不能超过最大需求量当系统现有的资源不能满足进程尚需资源数时，对进程的请求可当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间内得到资源以推迟分配，但总能使进程在有限的时间内得到资源当系统现有的资源能满足进程尚需资源数时，必须测试系统现存当系统现有的资源能满足进程尚需资源数时，必须测试系统现存的资源能否满足该进程尚需的最大资源数，若能满足则按当前的申的资源能否满足该进程尚需的最大资源数，若能满足则按当前的申请量分配资源，否则也要推迟分配请量分配资源，否则也要推迟分配
