《银行家算法(精品).ppt》由会员分享，可在线阅读，更多相关《银行家算法(精品).ppt（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、银行家算法银行家算法 基本思想：当系统现有的资源可保证申请进程完基本思想：当系统现有的资源可保证申请进程完成时，才进行分配。否则，申请进程等待。成时，才进行分配。否则，申请进程等待。系统现有的资源系统现有的资源进程占有的资源进程占有的资源进程还需要的资源进程还需要的资源 进程占有的资源进程占有的资源进程还需要的资源进程还需要的资源系统现有的资源系统现有的资源不不 进进 行行 分分 配配 进进 行行 分分 配配PiPi：PjPj：例例:某系统有三个进程共享10个同类的资源。进程已占资源数还需资源数进程已占资源数还需资源数P 0 8Q 0 4R 0 9系统资源数：系统资源数：10P 4 4系统资源
2、数：系统资源数：8R 2 7Q 2 2系统资源数：系统资源数：4系统资源数：系统资源数：2提问：提问：这种方法是如何避免死锁的？这种方法是如何避免死锁的？允许环存在，允许环存在，但任何时候都有一个进程是可完成的。但任何时候都有一个进程是可完成的。该进程完成后，释放资源，则又有一个进程可完成的。该进程完成后，释放资源，则又有一个进程可完成的。如此重复，直到所有的进程完成。如此重复，直到所有的进程完成。如上例中：如上例中：进程申请序列：进程申请序列：.RPQ；进程完成序列：进程完成序列：QPR Q 4 0Q 系统资源数：系统资源数：0系统资源数：系统资源数：4P 8 0P 系统资源数：系统资源数：
3、0系统资源数：系统资源数：8 缺点：缺点：(1)(1)不够大胆，有些还需的资源，以后也可能不会再申不够大胆，有些还需的资源，以后也可能不会再申请。请。(2)(2)对多类资源，算法复杂，系统开销大。对多类资源，算法复杂，系统开销大。算法思想为：算法思想为：(a)(a)若每类资源的还需数都若每类资源的还需数都 系统拥有数：则分配。系统拥有数：则分配。(b)(b)若每类资源的还需数都若每类资源的还需数都 系统拥有数：不分配。系统拥有数：不分配。(c)(c)若仅部分资源类的还需数若仅部分资源类的还需数 系统拥有数：系统拥有数：先进行假分配，再判别系统的状态是否安全先进行假分配，再判别系统的状态是否安全
4、 。若安全：不会死锁，则分配。若安全：不会死锁，则分配。若不安全：可能会死锁，则不分配。若不安全：可能会死锁，则不分配。安全状态与不安全状态安全状态与不安全状态 安安全全状状态态指指系系统统能能按按某某种种进进程程顺顺序序来来为为每每个个进进程程分分配配其其所所需需资资源源，直直至至最最大大需需求求，使使每每个个进进程程都都可可顺顺序序完完成成。若若系系统统不不存存在在这这样样一一个个序列，则称系统处于不安全状态。序列，则称系统处于不安全状态。1)安全序列 一个进程序列一个进程序列PP1 1，P Pn n 是安全的，如是安全的，如果对于每一个进程果对于每一个进程P Pi i(1(1i in n
5、），），它以后尚需它以后尚需要的资源量不超过系统当前剩余资源量与所有要的资源量不超过系统当前剩余资源量与所有进程进程P Pj j(j i)(j i)当前占有资源量之和，系统处当前占有资源量之和，系统处于安全状态。于安全状态。(安全状态一定是没有死锁发生的安全状态一定是没有死锁发生的)2)2)安全状态之例安全状态之例 我我们们通通过过一一个个例例子子来来说说明明安安全全性性。假假定定系系统统中中有有三三个个进进程程P P1 1、P P2 2和和P P3 3，共共有有1212台台磁磁带带机机。进进程程P P1 1总总共共要要求求1010台台磁磁带带机机，P P2 2和和P P3 3分分别别要要求求
6、4 4台台和和9 9台台。假假设设在在T T0 0时时刻刻，进进程程P P1 1、P P2 2和和P P3 3已已分分别别获获得得5 5台台、2 2台台和和2 2台台磁磁带带机机，尚有尚有3 3台空闲未分配，如下表所示：台空闲未分配，如下表所示：进进 程程 最最 大大 需需 求求 已已 分分 配配 可可 用用 P1P2P310495223 3)3)由安全状态向不安全状态的转换由安全状态向不安全状态的转换 如如果果不不按按照照安安全全序序列列分分配配资资源源，则则系系统统可可能能会会由由安安全全状状态态进进入入不不安安全全状状态态。例例如如，在在T T0 0时时刻刻以以后后，P P3 3又又请请
7、求求1 1台台磁磁带带机机，若若此此时时系系统统把把剩剩余余3 3台台中中的的1 1台台分分配配给给P P3 3，则则系系统统便便进进入入不不安安全全状状态态。因因为为，此此时时也也无无法法再再找找到到一一个个安安全全序序列列，例例如如，把把其其余余的的2 2台台分分配配给给P P2 2，这这样样，在在P P2 2完完成成后后只只能能释释放放出出4 4台台，既既不不能能满满足足P P1 1尚尚需需5 5台台的的要要求求，也也不不能能满满足足P P3 3尚尚需需6 6台台的的要要求求，致致使使它它们们都都无无法法推推进进到到完完成成，彼彼此此都都在在等等待待对对方方释释放放资源，即陷入僵局，结果
8、导致死锁。资源，即陷入僵局，结果导致死锁。安全状态与不安全状态 不安全状态不安全状态:不存在一个安全序列，不安不存在一个安全序列，不安全状态一定导致死锁全状态一定导致死锁利用银行家算法避免死锁利用银行家算法避免死锁 1)1)银行家算法中的数据结构银行家算法中的数据结构 (1)(1)可可利利用用资资源源向向量量AvailableAvailable。这这是是一一个个含含有有m m个个元元素素的的数数组组，其其中中的的每每一一个个元元素素代代表表一一类类可可利利用用的的资资源源数数目目，其其初初始始值值是是系系统统中中所所配配置置的的该该类类全全部部可可用用资资源源的的数数目目，其其数数值值随随该该
9、类类资资源源 的的 分分 配配 和和 回回 收收 而而 动动 态态 地地 改改 变变。如如 果果AvailableAvailablej j=K=K，则则表表示示系系统统中中现现有有R Rj j类类资资源源K K个。个。(2)(2)最最大大需需求求矩矩阵阵MaxMax。这这是是一一个个n nm m的的矩矩阵阵，它它定定义义了了系系统统中中n n个个进进程程中中的的每每一一个个进进程程对对m m类类资资源源的的最最大大需需求求。如如果果MaxMaxi,ji,j=K=K，则表示进程则表示进程i i需要需要R Rj j类资源的最大数目为类资源的最大数目为K K。(3)(3)分分配配矩矩阵阵Alloca
10、tionAllocation。这这也也是是一一个个n nm m的的矩矩阵阵，它它定定义义了了系系统统中中每每一一类类资资源源当当前前已已 分分 配配 给给 每每 一一 进进 程程 的的 资资 源源 数数。如如 果果AllocationAllocationi,ji,j=K=K，则则表表示示进进程程i i当当前前已已分分得得R Rj j类资源的数目为类资源的数目为K K。(4)(4)需需求求矩矩阵阵NeedNeed。这这也也是是一一个个n nm m的的矩矩阵阵，用用以以表表示示每每一一个个进进程程尚尚需需的的各各类类资资源源数数。如如果果NeedNeedi,ji,j=K K，则则表表示示进进程程i
11、 i还还需需要要R Rj j类类资资源源K K个，方能完成其任务个，方能完成其任务。NeedNeedi,ji,j=Max=Maxi,ji,j-Allocation-Allocationi,ji,j 2)2)银行家算法银行家算法 设设 RequestRequesti i是是 进进 程程 P Pi i的的 请请 求求 向向 量量，如如 果果RequestRequesti ij j=K K，表表示示进进程程P Pi i需需要要K K个个R Rj j类类型型的的资资源源。当当P Pi i发发出出资资源源请请求求后后，系系统统按按下下述述步步骤骤进行检查：进行检查：(1)(1)如如果果RequestRe
12、questi ij jNeedNeedi,ji,j，便便转转向向步步骤骤2 2；否否则则认认为为出出错错，因因为为它它所所需需要要的的资资源数已超过它所宣布的最大值。源数已超过它所宣布的最大值。(2)(2)如如果果RequestRequesti ij jAvailableAvailablej j，便便转转向向步步骤骤(3)(3)；否否则则，表表示示尚尚无无足足够够资资源源，P Pi i须等待。须等待。(3)(3)系统试探着把资源分配给进程系统试探着把资源分配给进程PiPi，并修，并修改下面数据结构中的数值：改下面数据结构中的数值：AvailableAvailablej j=Available=
13、Availablej j-RequestiRequestij j;AllocationAllocationi,ji,j=Allocation=Allocationi,ji,j+RequestiRequestij j;Need Needi,ji,j=Need=Needi,ji,j-RequestiRequestij j;(4)(4)系系统统执执行行安安全全性性算算法法，检检查查此此次次资资源源分分配配后后，系系统统是是否否处处于于安安全全状状态态。若若安安全全，才才正正式式将将资资源源分分配配给给进进程程P Pi i，以以完完成成本本次次分分配配；否否则则，将将本本次次的的试试探探分分配配作作废
14、废，恢恢复复原原来来的的资资源源分配状态，让进程分配状态，让进程P Pi i等待。等待。3)3)安全性算法安全性算法 (1)(1)设设置置两两个个向向量量：工工作作向向量量Work:Work:它它表表示示系系统统可可提提供供给给进进程程继继续续运运行行所所需需的的各各类类资资源源数数目目，它它含含有有m m个个元元素素，在在执执行行安安全全算算法法开开始始时时，Work=Available;Work=Available;Finish:Finish:它它表表示示系系统统是是否否有有足足够够的的资资源源分分配配给给进进程程，使使之之运运行行完完成成。开开始始时时先先做做FinishFinishi
15、i=false;=false;当当有有足足够够资资源源分配给进程时，分配给进程时，再令再令FinishFinishi i=true=true。(2)(2)从进程集合中找到一个能满足下述条件从进程集合中找到一个能满足下述条件的进程：的进程：FinishFinishi i=false;=false;Need Needi,ji,jWorkWorkj j；若找到，若找到，执行步骤执行步骤(3)(3)，否则，执行步骤否则，执行步骤(4)(4)。(3)(3)当进程当进程P Pi i获得资源后，可顺利执行，直获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：至完成，并释放出分配给它的资源，
16、故应执行：WorkWorkj j=Work=Worki i+Allocation+Allocationi,ji,j;FinishFinishi i=true;=true;go to step 2;go to step 2;(4)(4)如果所有进程的如果所有进程的FinishFinishi i=true=true都满都满足，则表示系统处于安全状态；否则，系统处足，则表示系统处于安全状态；否则，系统处于不安全状态。于不安全状态。4)4)银行家算法之例银行家算法之例 假假定定系系统统中中有有五五个个进进程程P P0 0,P P1 1,P P2 2,P P3 3,P P4 4和和三三类类资资源源A,A
17、,B,B,C C，各各种种资资源源的的数数量量分分别别为为1010、5 5、7 7，在，在T T0 0时刻的资源分配情况如时刻的资源分配情况如图图 3-15 3-15 所示。所示。图为图为 T T0 0时刻的资源分配表时刻的资源分配表 (1)T0时刻的安全性：时刻的安全性：图图 为为 T0时刻的安全序列时刻的安全序列 (2)(2)P P1 1请请求求资资源源：P P1 1发发出出请请求求向向量量RequestRequest1 1(1(1，0 0，2)2)，系统按银行家算法进行检查：系统按银行家算法进行检查：RequestRequest1 1(1,0,2)Need(1,0,2)Need1 1(1
18、,2,2)(1,2,2)Request Request1 1(1,0,2)Available(1,0,2)Available1 1(3,3,2)(3,3,2)系系 统统 先先 假假 定定 可可 为为 P P1 1分分 配配 资资 源源，并并 修修 改改Available,Available,AllocationAllocation1 1和和NeedNeed1 1向向量量，由由此此形形成的资源变化情况如上图中的圆括号所示。成的资源变化情况如上图中的圆括号所示。再利用安全性算法检查此时系统是否安全。再利用安全性算法检查此时系统是否安全。4)4)银行家算法之例银行家算法之例 假假定定系系统统中中有有
19、五五个个进进程程P P0 0,P P1 1,P P2 2,P P3 3,P P4 4和和三三类类资资源源A,A,B,B,C C，各各种种资资源源的的数数量量分分别别为为1010、5 5、7 7，在在T T0 0时刻的资源分配情况如时刻的资源分配情况如图图 3-15 3-15 所示。所示。图为图为 T T0 0时刻的资源分配表时刻的资源分配表 图为 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,0)Available(2,3,0);系统暂时先假定可为系统暂时先假定可为P0分配资源，并修改有关分配资源，并修改有关数据，如图数据，如图 3-18 所示。所示。图为图为P P0 0分配资源后的有关资源数据分配资源后的有关资源数据