如何求解银行家算法ppt课件

1、死锁、银行家算法 .1.死锁概念指多个进程因竞争共享资源而呵斥的一种僵局，假设无外力作用，这些进程都将永远不能再向前推进。即：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因此永远无法得到的资源，这种景象称为进程死锁，这一组进程就称为死锁进程。.思索：假设系统中有n个进程，那么在等待队列中进程的个数最多为 个有n个进程的系统出现死锁时，死锁进程的个数k应满足的条件是. 产生死锁的缘由1.竞争资源资源缺乏2.进程的推进顺序不当 .1. 竞争系统资源 假设系统中只需一台打印机R1和一台读卡机R2，可供进程P1和P2共享。假设构成环路，这样会产生死锁。.由于进程的调度是独立的，恳求

2、和释放操作可按如下序列进展：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.进程推进顺序不当引起死锁.思索：某系统中有3个并发进程都需求4个同类资源，该系统不会发生死锁的最少资源是 个P341 例8.2. 死锁防止死锁防止定义:在系统运转过程中，对进程发出的每一

3、个系统可以满足的资源恳求进展动态检查，并根据检查结果断定能否分配资源，假设分配后系统能够发生死锁，那么不予分配，否那么予以分配。.由于在防止死锁的战略中，允许进程动态地恳求资源。因此，系统在进展资源分配之前预先计算资源分配的平安性。假设此次分配不会导致系统进入不平安形状，那么将资源分配给进程；否那么，进程等待。其中最具有代表性的防止死锁算法是银行家算法。.3. 平安形状与不平安形状 平安形状指系统能按某种进程顺序P1，Pn来为每个进程Pi(1in分配其所需资源，直至最大需求，使每个进程都可顺序完成。假设系统不存在这样一个序列，那么称系统处于不平安形状。假设存在，那么称序列为平安序列。 .说 明

4、并非一切的不平安形状都必然会转为死锁形状，但当系统进入不平安形状后，便有能够进入死锁。 平安形状一定是没有死锁发生的。防止死锁的本质：系统进展资源分配时，如何使系统不进入不平安形状。. 2) 平安形状之例 假定系统中有三个进程P1、 P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时辰，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示： 进 程 最 大 需 求 已 分 配 可 用 P1P2P310495223问：T0时辰能否平安？. 3) 由平安形状向不平安形状的转换 假设不按照平安序列分配资源，那么系统能

5、够会由平安形状进入不平安形状。 例如，在T0时辰以后，P3又恳求1台磁带机，假设此时系统把剩余3台中的1台分配给P3，那么系统便进入不平安形状。 由于，此时也无法再找到一个平安序列， 例如，把其他的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即堕入僵局，结果导致死锁。 P3的恳求应回绝。.平安形状与不平安形状 不平安形状:不存在一个平安序列，不平安形状不一定导致死锁.4.利用银行家算法防止死锁 1)银行家算法中的数据构造 (1) 可利用资源向量Available。这是一个含有m

6、个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改动。假设Availablej=K，那么表示系统中现有Rj类资源K个。 . (2) 最大需求矩阵Max。这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。假设Maxi,j=K，那么表示进程i需求Rj类资源的最大数目为K。 (3) 分配矩阵Allocation。这也是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。假设Allocationi,j=K，那么表示进程i当前已分得Rj类资源的数目为K。 .(4) 需

7、求矩阵Need。这也是一个nm的矩阵，用以表示每一个进程尚需的各类资源数。假设Needi,j=K，那么表示进程i还需求Rj类资源K个，方能完成其义务。 Needi,j=Maxi,j-Allocationi,j. 2)银行家算法 设Requesti是进程Pi的恳求向量，假设Requestij=K，表示进程Pi需求K个Rj类型的资源。当Pi发出资源恳求后，系统按下述步骤进展检查： (1) 假设RequestijNeedi,j，便转向步骤2；否那么以为出错，由于它所需求的资源数已超越它所宣布的最大值。 (2) 假设RequestijAvailablej，便转向步骤(3)；否那么， 表示尚无足够资源，

8、Pi须等待。 . (3) 系统试探着把资源分配给进程Pi，并修正下面数据构造中的数值： Availablej=Availablej-Requestij; Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij; (4) 系统执行平安性算法，检查此次资源分配后，系统能否处于平安形状。假设平安，才正式将资源分配给进程Pi，以完本钱次分配；否那么， 将本次的试探分配作废，恢复原来的资源分配形状，让进程Pi等待。 .3)平安性算法 (1) 设置两个向量： 任务向量Work: 它表示系统可提供应进程继续运转所需的各类资源数目，它含

9、有m个元素，在执行平安算法开场时，Work=Available; Finish: 它表示系统能否有足够的资源分配给进程，使之运转完成。开场时先做Finishi=false; 当有足够资源分配给进程时， 再令Finishi=true。 . (2) 从进程集合中找到一个能满足下述条件的进程： Finishi=false; Needi,jWorkj； 假设找到， 执行步骤(3)， 否那么，执行步骤(4)。 (3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Workj=Worki+Allocationi,j; Finishi=true; go to step 2;

10、 (4) 假设一切进程的Finishi=true都满足， 那么表示系统处于平安形状；否那么，系统处于不平安形状。 .4) 银行家算法之例 假定系统中有五个进程P0, P1, P2, P3, P4和三类资源A, B, C，各种资源的数量分别为10、5、7，在T0时辰的资源分配情况如图 3-16 所示。 图 3-16 T0时辰的资源分配表 .(1) T0时辰的平安性检查 图 3-17 T0时辰的平安序列 . (2) P1恳求资源：P1发出恳求向量Request1(1，0，2)，系统按银行家算法进展检查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0,

11、2)Available1(3, 3, 2) 系统先假定可为P1分配资源，并修正Available, Allocation1和Need1向量，由此构成的资源变化情况如图 3-16 中的圆括号所示。 再利用平安性算法检查此时系统能否平安。如图 3-18 .图 3-18 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,