银行家算法习题

银行家算法习题假设一家银行拥有资金2000万，现有10家公司向其贷款进行筹建，每家均需300万才能建成。如果这家银行将2000万的资金平均贷给这10家公司，则每家公司将得到200万的贷款，都不能筹建成功，也就不能还贷，那么这10家公司都将“死锁”。若这家银行给其中的4家各贷300万，另4家各贷200万，这样将还有2家公司得不到贷款，不能开工建设，但有4家可筹建完成，这4家公司运营所得利润可向该银行还贷，银行可以利用还贷的资金继续向其他的公司贷款，从而保证所有公司筹建成功投入运营。银行家算法是为了把一定数量的资金供多个用户周转，并保证资金的安全。银行家算法可归纳为：（1）当一个用户对资金的最大需求量不超过银行家现有的资金时，就可接纳该用户。（2）用户可以分期贷款，但贷款总数不能超过最大需求量。（3）当银行家现有的资金不能满足用户的尚需贷款数时，可以推迟支付，但总能使用户在有限的时间里得到贷款。（4）当用户得到所需的全部资金后，一定能在有限时间里归还所有的资金。我们可以把操作系统看作银行家，把进程看作用户，把操作系统管理的资源看作银行家管理的资金，把进程向操作系统请求资源看作用户向银行家贷款。操作系统按照银行家规定的规则为进程分配资源。当进程首次申请资源时，要测试该进程对资源的最大需求量。如果系统现存的资源可以满足它的最大需求量，则按当前的申请量分配资源，否则推后分配。当进程在执行中继续申请资源时，先测试该进程已占有的资源数与本次申请的资源数之和是否超过该进程对资源的最大需求量。如果超过，则拒绝分配资源，否则再测试系统现存的资源能否满足该进程尚需的最大资源量。若能满足，则按当前的申请量分配资源，否则也要推迟分配。这样做，能保证在任何时刻至少有一个进程可以得到所需要的全部资源而执行到结束，执行结束后归还资源，并把这些资源加入到系统的剩余资源中，用同样的方法为其他的进程分配资源。银行家算法的数据结构包括：（1）可用资源向量Available。（2）最大需求矩阵Max。（3）分配矩阵Allocation。（4）需求矩阵Need。银行家算法如下：设Requesti是进程Pi的请求向量，Requesti(j)=k表示进程Pi请求分配Rj类资源k个，当Pi发出资源请求后，系统按照下列步骤进行检查。（1）若Requesti≤Need，则执行步骤（2）；否则系统会因为它所需要的资源数已超过它要求的最大值而认为出错。（2）若Requesti≤Available，则执行步骤（3）；否则系统会因为系统中尚无足够的资源满足Pi的申请而使进程Pi等待。（3）系统试探地把资源分配给进程Pi并修改如下数据结构中的值：Available=Available-RequestiAllocationi=Allocationi+RequestiNeedi=Needi-Requesti（4）系统执行安全算法，检查此次资源分配后，系统是否处于安全状态。若是则系统才真正将资源分配给进程Pi以完成本次分配；若不是则系统将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。系统所执行的安全性算法描述如下：（1）设置两个向量：Work和Finish。其中Work表示系统可提供给进程继续运行的各类资源数，初始时Work=Available；Finish表示系统是否有足够的资源分配给进程并使之运行结束，初始时Finish(i)=false，当有足够资源分配给进程Pi时，令Finish(i)=true。（2）从进程集合中找到一个能满足下述条件的进程：①Finish(i)=false②Needi≤Work若能找到这样的进程则执行步骤（3），否则跳过步骤（3）而执行步骤（4）。（3）当进程Pi获得资源后可顺利执行直到完成，然后释放分配给它的资源，并做如下工作：①Work=Work+Allocation②Finish(i)=true最后转去执行步骤（2）。（4）若所有进程的Finish(i)的值都为true，则说明系统处于安全状态；否则系统处于不安全状态。例1．某系统有A、B、C类型的3种资源，在T0时刻进程P1、P2、P3、P4对资源的占用和需求情况见下表。此刻系统可用资源向量为（2，1，2）。问：（1）将系统中各种资源总数和进程对资源的需求数目用向量或矩阵表示出来。（2）判定此刻系统的安全性。如果是安全的，写出安全序列，如果是不安全的，写出参与死锁的进程。（3）如果此时P1和P2均再发出资源请求向量Request（1，0，1），为了保持系统安全性，应该如何分配资源给这两个进程？说明你所采用策略的原因。（4）如果（3）中的请求都立刻满足后，系统此刻是否处于死锁状态？最终能否进入死锁状态？若能，说明参与死锁的进程，若不能，说明原因。解：（1）系统资源总数向量＝available+Allocation＝（2，1，2）＋（7，2，4）＝（9，3，6）进程对资源的需求矩阵100411211002322613314422P1P2P2P4ABCABC已分配资源Allocation最大需求量max资源请求进程222202103420need=max－Allocation=322613314422100411211002—=（2）采用银行家算法进行计算步骤如下：work=(2,1,2)finish=(false,false,false,false)①因为：need[2]available，故系统可以满足P2对资源的请求，将资源分配给P2后，P2可执行完成，然后释放它所占有的资源。因此，finish[2]=true;work=work+allocation[2]=(2,1,2)+(4,1,1)=(6,2,3)②此时，need[1]work，故：P1可执行完成。finish[1]=true;work=work+allocation[1]=(6,2,3)+(1,0,0)=(7,2,3)③此时，need[3]work，故：P3可执行完成。finish[3]=true;work=work+allocation[3]=(7,2,3)+(2,1,1)=(9,3,4)④此时，need[4]work，故：P4可执行完成。finish[4]=true;work=work+allocation[4]=(9,3,4)+(0,0,2)=(9,3,6)结论：系统至少可以找到一个安全的执行序，如（P2，P1，P3，P4）可使各进程正常运行终结。（3）系统不能将资源分配给进程P1，因为虽然可利用资源还可以满足进程P1现在的需求，但是一旦分配给进程P1后，就找不到一个安全执行的序列保证各进程能够正常运行终结。所以进程P1应该进入阻塞状态。（4）系统满足进程P1和P2的请求后，没有立即进入死锁状态，因为这时所有进程没有提出新的资源申请，全部进程均没有因资源没有得到满足而进入阻塞状态。只有当进程提出资源申请且全部进程都进入阻塞状态时，系统才处于死锁状态。但最终会进入死锁状态。例2：某系统有同类资源m个，n个并发进程可共享该类临界资源。求：每个进程最多可申请多少个该类临界资源，保证系统一定不会发生死锁。解：设每个进程最多申请该类资源的最大量为x。每个进程最多申请x个资源，则n个进程最多同时申请的该类临界资源数为：n*x。为保证系统不会发生死锁，应满足下列不等式：n(x-1)+1≤m（*）则系统一定不会发生死锁。这是因为进程最多申请x个资源，最坏的情况是每个进程都已得到了(x-1)个资源，现均申请要最后一个资源。只要系统至少还有一个资源就可使其中一个或几个进程得到所需的全部资源，在它们执行结束后归还的资源可供其他进程使用，因而不可以发生死锁。解不等式（*），可得：x≤1+[(m-1)/n]即：x的最大值为1+[(m-1)/n]。因而，当每个进程申请资源的最大数值为1+[(m-1)/n]时，系统肯定不会发生死锁。例3：设系统中有3中类型的资源（A,B,C）和5个进程P1、P2、P3、P4、P5，A类资源的数目为17，B类资源的数目为5，C类资源的数目为20。在T0时刻系统状态如下表所示。系统采用银行家算法实施死锁避免策略。MaxABCAllocationABCAvailableABCP1559212233P2536402P34011405P4425204P5424314（1）T0时刻是否为安全状态？若是，给出安全序列。（2）若在T0时刻进程P2请求资源（0，3，4），是否能实施资源分配？为什么？（3）在（2）的基础上，若进程P4请求资源（2，0，1），是否能实施资源分配？为什么？（1）由题目所给出的最大资源需求量和已分配的资源数量，可以计算出T0时刻各进程的资源需求量Need，Need＝Max-Allocation，利用银行家算法对T0时刻的资源分配情况进行分析，可得此时的安全性分析情况，如下表：WorkABCNeedABCAllocationABCWork+AllocationABCFinishP5233110314547trueP45472212047411trueP3741100640511416trueP21141613440215418trueP11541834721217520true从T0的安全性分析中可以看出，存在一个安全序列{P5、P4、P3、P2、P1}，故T0时刻的状态是安全的。（6分）（2）若在T0时刻进程P2请求资源（0，3，4），因请求资源数（0，3，4）大于剩余资源数（2，3，3），所以不能分配。（2分）（3）在（2）的基础上，若进程P4请求资源（2，0，1），按银行家算法进行检查：P4请求资源（2，0，1）=P4需求资源（2，2，1）P4请求资源（2，0，1）=剩余资源数（2，3，3）试分配并修改相应的数据结构，由此形成的资源分配情况如下表所示：进程资源情况资源情况进程AllocationABCNeedABCAvailableABCP1212347033P2402134P3405006P4405020P5314110此时，如题（1）利用银行家算法检查系统的安全状态，存在一个安全序列{P4、P5、P3、P2、P1}，故该状态是安全的，可以立即将P4请求的资源分配给它。例4：某系统有同类资源m个，n个并发进程可共享该类临界资源。求：每个进程最多可申请多少个该类临界资源，保证系统一定不会发生死锁。解：设每个进程最多申请该类资源的最大量为x。为保证系统不会发生死锁，应满足下列不等式：n(x-1)+1≤m（*）解不等式（*），可得：x≤1+[(m-1)/n]即：x的最大值为1+[(m-1)/n]。因而，当每个进程申请资源的最大数值为1+[(m-1)/n]时，系统肯定不会发生死锁。某系统中有5个并发进程，都需要同类资源3个，试问该系统不会发生死锁的最少资源数是（11）。某系统中有4个并发进程，都需要同类资源3个，试问该系统不会发生死锁的最少资源数是(9)。某计算机系统中有8台打印机,有K个进程竞争使用,每个进程最多需要3台打印机.该系统可能会发生死锁的K的最小值是(4)系统中有3个进程，每个进程需2台打印机，如果系统配有4台打印机，则系统______不可能________出现死锁的情况（本题要判断出现死锁的可能性：可能或不可能）。进程资源情况若系统运行中出现如下表所示的资源分配情况，该系统是否安全？若是，给出安全序列；如果进程P2此时提出资源申请（1，2，2，2），系统能否将资源分配给它？为什么？Allocation(已分配资源数)Need(还需要资源数)Available(系统可以分配资源数)P0003200121622P110001750P213542356P303320652P400140656答：（1）利用安全性算法对此刻的资源分配情况进行如下表的安全性检：WorkNeedAllocationWork+AllocationP01622001200321654P31654065203321986P419860656001419910P1199101750100029910P2299102356