如何求解银行家算法

死锁、银行家算法死锁、银行家算法 11.死锁概念指指多多个个进进程程因因竞竞争争共共享享资资源源而而造造成成的的一一种种僵僵局局，若若无无外外力力作作用用，这这些些进进程程都将永远不能再向前推进。都将永远不能再向前推进。即即：一一组组进进程程中中，每每个个进进程程都都无无限限等等待待被被该该组组进进程程中中另另一一进进程程所所占占有有的的资资源源，因因而而永永远远无无法法得得到到的的资资源源，这这种种现现象象称称为为进进程程死死锁锁，这这一一组组进进程程就就称称为死锁进程。为死锁进程。2思考：如果系统中有n个进程，则在等待队列中进程的个数最多为（）个有n个进程的系统出现死锁时，死锁进程的个数k应满足的条件是（）3 产生死锁的原因1.1.竞争资源（资源不足）竞争资源（资源不足）2.2.进程的推进顺序不当进程的推进顺序不当 41.1.竞争系统资源 若若系系统统中中只只有有一一台台打打印印机机R1R1和和一一台台读读卡卡机机R2R2，可可供供进进程程P1P1和和P2P2共共享享。若若形形成成环环路路，这样会产生死锁这样会产生死锁。5由于进程的调度是独立的，请求和释放操作可按如下序列进行：Ar1,Ar2,Ar3,Ar4,Br1,Br2,Br3,Br4Br1,Br2,Br3,Br4,Ar1,Ar2,Ar3,Ar4Ar1,Ar2.Br1,Ar3,Ar4,Br2,Br3,Br4Ar1,Br1,Ar2,Br2,Ar3,Ar4,Br3,Br4对序列三个进程都能顺利进行，则会产生死锁。进程A、B对资源的请求和释放 2.2.进程推进顺序不当引起死锁进程推进顺序不当引起死锁6思考：某系统中有3个并发进程都需要4个同类资源，该系统不会发生死锁的最少资源是（）个P341 例872.死锁避免死死锁锁避避免免定定义义:在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。8由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。93.安全状态与不安全状态 安安全全状状态态指指系系统统能能按按某某种种进进程程顺顺序序PP1 1，P Pn n 来来为为每每个个进进程程P Pi i(1(1i in n）分分配配其其所所需需资资源源，直直至至最最大大需需求求，使使每每个个进进程程都都可可顺顺序序完完成成。若若系系统统不不存存在在这这样样一一个个序序列列，则则称称系系统统处处于于不不安安全全状状态态。如如果果存存在在，则则称称序序列列P 为为安安全全序列。序列。10说 明并非所有的不安全状态都必然会转为并非所有的不安全状态都必然会转为死锁状态，但当系统进入不安全状态死锁状态，但当系统进入不安全状态后，便有可能进入死锁。后，便有可能进入死锁。安全状态一定是没有死锁发生的。安全状态一定是没有死锁发生的。避免死锁的实质：系统进行资源分配避免死锁的实质：系统进行资源分配时，如何使系统不进入不安全状态。时，如何使系统不进入不安全状态。11 2)安全状态之例安全状态之例 假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：进 程 最 大 需 求 已 分 配 可 用 P1P2P310495223问：T0时刻是否安全？12 3)由安全状态向不安全状态的转换由安全状态向不安全状态的转换 如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。因为，此时也无法再找到一个安全序列，例如，把其余的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。P3的请求应拒绝。13安全状态与不安全状态 不安全状态:不存在一个安全序列，不安全状态不一定导致死锁144.利用银行家算法避免死锁 1)银行家算法中的数据结构银行家算法中的数据结构 (1)可可利利用用资资源源向向量量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Availablej=K，则表示系统中现有Rj类资源K个。15 (2)最最大大需需求求矩矩阵阵Max。这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi,j=K，则表示进程i需要Rj类资源的最大数目为K。(3)分分配配矩矩阵阵Allocation。这也是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K，则表示进程i当前已分得Rj类资源的数目为K。16(4)需求矩阵Need。这也是一个nm的矩阵，用以表 示 每 一 个 进 程 尚 需 的 各 类 资 源 数。如 果Needi,j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。Needi,j=Maxi,j-Allocationi,j17 2)银行家算法银行家算法 设 Requesti是 进 程 Pi的 请 求 向 量，如 果 Requestij=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：(1)如果RequestijNeedi,j，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。(2)如果RequestijAvailablej，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。18 (3)系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Availablej=Availablej-Requestij;Allocationi,j=Allocationi,j+Requestij;Needi,j=Needi,j-Requestij;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。193)安全性算法安全性算法(1)设置两个向量：工作向量Work:它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available;Finish:它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=false;当有足够资源分配给进程时，再令Finishi=true。20 (2)从进程集合中找到一个能满足下述条件的进程：Finishi=false;Needi,jWorkj；若找到，执行步骤(3)，否则，执行步骤(4)。(3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Workj=Worki+Allocationi,j;Finishi=true;go to step 2;(4)如果所有进程的Finishi=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。214)银行家算法之例银行家算法之例 假定系统中有五个进程P0,P1,P2,P3,P4和三类资源A,B,C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图 3-16 所示。图 3-16 T0时刻的资源分配表 22(1)T0时刻的安全性检查 图 3-17 T0时刻的安全序列 23 (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向量，由此形成的资源变化情况如图 3-16 中的圆括号所示。再利用安全性算法检查此时系统是否安全。如图 3-18 24图 3-18 P1申请资源时的安全性检查 25 (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-19 所示。26图 3-19为P0分配资源后的有关资源数据 27（5）安全性检查：Available(2,1,0)不能满足任何进程的需求，系统进入不安全状态，不能分配资源。思考：P0 请求改为 Request0(0，1，0)，系统是否能分配资源？28