银行家算法习题资料

《银行家算法习题资料》由会员分享，可在线阅读，更多相关《银行家算法习题资料（10页珍藏版）》请在金锄头文库上搜索。

1、银行家算法习题 假设一家银行拥有资金 2000 万，现有 10 家公司向其贷款进行筹建，每家均 需 300 万才能建成。如果这家银行将 2000 万的资金平均贷给这 10 家公司，则每 家公司将得到 200 万的贷款，都不能筹建成功，也就不能还贷，那么这 10 家公 司都将“死锁” 。若这家银行给其中的 4 家各贷 300 万，另 4 家各贷 200 万，这 样将还有 2 家公司得不到贷款，不能开工建设，但有 4 家可筹建完成，这 4 家公 司运营所得利润可向该银行还贷， 银行可以利用还贷的资金继续向其他的公司贷 款，从而保证所有公司筹建成功投入运营。 银行家算法是为了把一定数量的资金供多个用

2、户周转，并保证资金的安全。 银行家算法可归纳为： （1）当一个用户对资金的最大需求量不超过银行家现有的资金时，就可接纳该 用户。 （2）用户可以分期贷款，但贷款总数不能超过最大需求量。 （3）当银行家现有的资金不能满足用户的尚需贷款数时，可以推迟支付，但总 能使用户在有限的时间里得到贷款。 （4）当用户得到所需的全部资金后，一定能在有限时间里归还所有的资金。 我们可以把操作系统看作银行家，把进程看作用户，把操作系统管理的资 源看作银行家管理的资金，把进程向操作系统请求资源看作用户向银行家贷款。 操作系统按照银行家规定的规则为进程分配资源。当进程首次申请资源 时， 要测试该进程对资源的最大需求量

3、。如果系统现存的资源可以满足它的最大 需求量，则按当前的申请量分配资源，否则推后分配。 当进程在执行中继续申请资源时， 先测试该进程已占有的资源数与本次申 请的资源数之和是否超过该进程对资源的最大需求量。如果超过，则拒绝分配资 源，否则再测试系统现存的资源能否满足该进程尚需的最大资源量。若能满足， 则按当前的申请量分配资源，否则也要推迟分配。 这样做， 能保证在任何时刻至少有一个进程可以得到所需要的全部资源而 执行到结束，执行结束后归还资源，并把这些资源加入到系统的剩余资源中，用 同样的方法为其他的进程分配资源。 银行家算法的数据结构包括： （1）可用资源向量 Available。 （2）最大

4、需求矩阵 Max。 （3）分配矩阵 Allocation。 （4）需求矩阵 Need。 银行家算法如下： 设 Requesti 是进程 Pi 的请求向量，Requesti (j)=k 表示进程 Pi 请求分配 Rj 类资源 k 个，当 Pi 发出资源请求后，系统按照下列步骤进行检查。 （1）若 RequestiNeed，则执行步骤（2） ；否则系统会因为它所需要的资源数 已超过它要求的最大值而认为出错。 （2）若 RequestiAvailable，则执行步骤（3） ；否则系统会因为系统中尚无足够 的资源满足 Pi 的申请而使进程 Pi 等待。 （3）系统试探地把资源分配给进程 Pi 并修改如

5、下数据结构中的值： Available=Available-Requesti Allocationi=Allocationi+Requesti Needi=Needi-Requesti （4）系统执行安全算法，检查此次资源分配后，系统是否处于安全状态。若是 则系统才真正将资源分配给进程 Pi 以完成本次分配；若不是则系统将试探分配 作废，恢复原来的资源分配状态，让进程 Pi 等待。 系统所执行的安全性算法描述如下： （1）设置两个向量：Work 和 Finish。其中 Work 表示系统可提供给进程继续运 行的各类资源数，初始时 Work=Available；Finish 表示系统是否有足够的

6、资源分 配给进程并使之运行结束，初始时 Finish(i)=false，当有足够资源分配给进程 Pi 时，令 Finish(i)=true。 （2）从进程集合中找到一个能满足下述条件的进程： Finish(i)=false NeediWork 若能找到这样的进程则执行步骤（3） ，否则跳过步骤（3）而执行步骤（4） 。 （3）当进程 Pi 获得资源后可顺利执行直到完成，然后释放分配给它的资源，并 做如下工作： Work=Work+Allocation Finish(i)=true 最后转去执行步骤（2） 。 （4）若所有进程的 Finish(i)的值都为 true，则说明系统处于安全状态；否则

7、系统 处于不安全状态。 例 1某系统有 A、B、C 类型的 3 种资源，在 T0 时刻进程 P1、P2、P3、P4 对资源的占用和需求情况见下表。此刻系统可用资源向量为（2，1，2） 。问： （1）将系统中各种资源总数和进程对资源的需求数目用向量或矩阵表示出来。 （2）判定此刻系统的安全性。如果是安全的，写出安全序列，如果是不安全的， 写出参与死锁的进程。 （3）如果此时 P1 和 P2 均再发出资源请求向量 Request（1，0，1） ，为了保持系 统安全性，应该如何分配资源给这两个进程？说明你所采用策略的原因。 （4）如果（3）中的请求都立刻满足后，系统此刻是否处于死锁状态？最终能否 进

8、入死锁状态？若能，说明参与死锁的进程，若不能，说明原因。 解： （1）系统资源总数向量available+Allocation （2，1，2）（7，2，4）（9，3，6） 进程对资源的需求矩阵 100 411 211 002 322 613 314 422 P1 P2 P2 P4 ABCABC 已分配资源Allocation最大需求量 max资源 请求进程 222 202 103 420 need=maxAllocation= 3 22 613 314 422 100 411 211 002 = （2）采用银行家算法进行计算步骤如下： work=(2,1,2) finish=(false,fa

9、lse,false,false) 因为：need2available，故 系统可以满足 P2 对资源的请求，将资源分配给 P2 后，P2 可执行完成，然后释 放它所占有的资源。因此， finish2=true; work = work +allocation2 =(2,1,2)+(4,1,1)=(6,2,3) 此时，need1 work ，故： P1 可执行完成。finish1=true; work=work+allocation1=( 6,2,3)+(1,0,0)=(7,2,3) 此时，need3 work ，故： P3 可执行完成。finish3=true; work= work+allo

10、cation3=( 7,2,3)+(2,1,1)=(9,3,4) 此时，need4 work ，故： P4 可执行完成。finish4=true; work= work+allocation4 =( 9,3,4)+(0,0,2)=(9,3,6) 结论： 系统至少可以找到一个安全的执行序，如（P2，P1，P3，P4）可使各进 程正常运行终结。 （3）系统不能将资源分配给进程 P1，因为虽然可利用资源还可以满足进程 P1 现在的需求，但是一旦分配给进程 P1 后，就找不到一个安全执行的序列保证各 进程能够正常运行终结。所以进程 P1 应该进入阻塞状态。 （4）系统满足进程 P1 和 P2 的请求后

11、，没有立即进入死锁状态，因为这时所有 进程没有提出新的资源申请， 全部进程均没有因资源没有得到满足而进入阻塞状 态。 只有当进程提出资源申请且全部进程都进入阻塞状态时，系统才处于死锁状 态。但最终会进入死锁状态。 例例 2 ： 某系统有同类资源某系统有同类资源 m 个个， n 个并发进程可共享该类临界资源个并发进程可共享该类临界资源。 求求： 每个进程最多可申请多少个该类临界资源，保证系统一定不会发生死锁。每个进程最多可申请多少个该类临界资源，保证系统一定不会发生死锁。 解：设每个进程最多申请该类资源的最大量为x。 每个进程最多申请x个资源，则n个进程最多同时申请的该类临界资源数 为：n*x。

12、 为保证系统不会发生死锁，应满足下列不等式： n(x-1)+1m（*） 则系统一定不会发生死锁。这是因为进程最多申请x个资源，最坏的情 况是每个进程都已得到了(x-1)个资源，现均申请要最后一个资源。只要系统至少 还有一个资源就可使其中一个或几个进程得到所需的全部资源， 在它们执行结束 后归还的资源可供其他进程使用，因而不可以发生死锁。 解不等式（*） ，可得： x1+(m-1)/n 即：x的最大值为1+(m-1)/n。因而，当每个进程申请资源的最大数值为 1+(m-1)/n时，系统肯定不会发生死锁。 例 3：设系统中有 3 中类型的资源（A,B,C）和 5 个进程 P1、P2、P3、P4、

13、P5，A 类资源的数目为 17，B 类资源的数目为 5，C 类资源的数目为 20。在 T0 时刻系统状态如下表所示。系统采用银行家算法实施死锁避免策略。 Max ABC Allocation ABC Available ABC P1559212233 P2536402 P34011405 P4425204 P5424314 （1）T0时刻是否为安全状态？若是，给出安全序列。 （2）若在 T0时刻进程 P2 请求资源（0，3，4） ，是否能实施资源分配？为什么？ （3）在（2）的基础上，若进程 P4 请求资源（2，0，1） ，是否能实施资源分配？ 为什么？ （1）由题目所给出的最大资源需求量和已

14、分配的资源数量，可以计算出 T0时刻 各进程的资源需求量 Need，NeedMax-Allocation，利用银行家算法对 T0时刻 的资源分配情况进行分析，可得此时的安全性分析情况，如下表： Work ABC Need ABC Allocation ABC Work+Allocation ABC Finish P5233110314547true P45472212047411true P3741100640511416true P21141613440215418true P11541834721217520true 从 T0的安全性分析中可以看出，存在一个安全序列 P5、P4、P3、P2

15、、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） 试分配并修改相应的数据结构，由此形成的资源分配情况如下表所示： 进程 资源情况 资源情况 进程 Allocation ABC Need ABC Available ABC P121234703

16、3 P2402134 P3405006 P4405020 P5314110 此时，如题（1）利用银行家算法检查系统的安全状态，存在一个安全序列 P4、P5、P3、P2、P1，故该状态是安全的，可以立即将 P4 请求的资源分配给 它。 例 4 ：某系统有同类资源 m 个，n 个并发进程可共享该类临界资源。求： 每个进程最多可申请多少个该类临界资源，保证系统一定不会发生死锁。 解：设每个进程最多申请该类资源的最大量为 x。 为保证系统不会发生死锁，应满足下列不等式： n(x-1)+1m（*） 解不等式（*） ，可得： x1+(m-1)/n 即：x 的最大值为 1+(m-1)/n。因而，当每个进程申请资源的最大数值为 1+(m-1)/n时，系统肯定不会发生死锁。 某系统中有 5 个并发进程，都需要同类资源 3 个，试问该系统不会发生死锁 的最少资源数是（ 11） 。 某系统中有 4 个并发进程，都需要同类资源 3 个，试问该系统不会发生死锁 的最少资源数