您好,欢迎访问三七文档
死锁、银行家算法1.死锁概念•指多个进程因竞争共享资源而造成的一种僵局,若无外力作用,这些进程都将永远不能再向前推进。•即:一组进程中,每个进程都无限等待被该组进程中另一进程所占有的资源,因而永远无法得到的资源,这种现象称为进程死锁,这一组进程就称为死锁进程。思考:•如果系统中有n个进程,则在等待队列中进程的个数最多为()个•有n个进程的系统出现死锁时,死锁进程的个数k应满足的条件是()产生死锁的原因1.竞争资源(资源不足)2.进程的推进顺序不当1.竞争系统资源若系统中只有一台打印机R1和一台读卡机R2,可供进程P1和P2共享。若形成环路,这样会产生死锁。由于进程的调度是独立的,请求和释放操作可按如下序列进行:①Ar1,Ar2,Ar3,Ar4,Br1,Br2,Br3,Br4②Br1,Br2,Br3,Br4,Ar1,Ar2,Ar3,Ar4③Ar1,Ar2.Br1,Ar3,Ar4,Br2,Br3,Br4④Ar1,Br1,Ar2,Br2,Ar3,Ar4,Br3,Br4对序列①②③三个进程都能顺利进行,④则会产生死锁。进程A、B对资源的请求和释放2.进程推进顺序不当引起死锁思考:•某系统中有3个并发进程都需要4个同类资源,该系统不会发生死锁的最少资源是()个•P341例82.死锁避免•死锁避免定义:在系统运行过程中,对进程发出的每一个系统能够满足的资源申请进行动态检查,并根据检查结果决定是否分配资源,若分配后系统可能发生死锁,则不予分配,否则予以分配。•由于在避免死锁的策略中,允许进程动态地申请资源。因而,系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态,则将资源分配给进程;否则,进程等待。其中最具有代表性的避免死锁算法是银行家算法。3.安全状态与不安全状态安全状态指系统能按某种进程顺序{P1,…,Pn}来为每个进程Pi(1≤i≤n)分配其所需资源,直至最大需求,使每个进程都可顺序完成。若系统不存在这样一个序列,则称系统处于不安全状态。如果存在,则称序列P1,…,Pn为安全序列。说明•并非所有的不安全状态都必然会转为死锁状态,但当系统进入不安全状态后,便有可能进入死锁。•安全状态一定是没有死锁发生的。•避免死锁的实质:系统进行资源分配时,如何使系统不进入不安全状态。2)安全状态之例假定系统中有三个进程P1、P2和P3,共有12台磁带机。进程P1总共要求10台磁带机,P2和P3分别要求4台和9台。假设在T0时刻,进程P1、P2和P3已分别获得5台、2台和2台磁带机,尚有3台空闲未分配,如下表所示:进程最大需求已分配可用P1P2P310495223问:T0时刻是否安全?3)由安全状态向不安全状态的转换如果不按照安全序列分配资源,则系统可能会由安全状态进入不安全状态。例如,在T0时刻以后,P3又请求1台磁带机,若此时系统把剩余3台中的1台分配给P3,则系统便进入不安全状态。因为,此时也无法再找到一个安全序列,例如,把其余的2台分配给P2,这样,在P2完成后只能释放出4台,既不能满足P1尚需5台的要求,也不能满足P3尚需6台的要求,致使它们都无法推进到完成,彼此都在等待对方释放资源,即陷入僵局,结果导致死锁。P3的请求应拒绝。安全状态与不安全状态不安全状态:不存在一个安全序列,不安全状态不一定导致死锁4.利用银行家算法避免死锁1)银行家算法中的数据结构(1)可利用资源向量Available。这是一个含有m个元素的数组,其中的每一个元素代表一类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源的数目,其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K,则表示系统中现有Rj类资源K个。(2)最大需求矩阵Max。这是一个n×m的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。(3)分配矩阵Allocation。这也是一个n×m的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K,则表示进程i当前已分得Rj类资源的数目为K。(4)需求矩阵Need。这也是一个n×m的矩阵,用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K,则表示进程i还需要Rj类资源K个,方能完成其任务。Need[i,j]=Max[i,j]-Allocation[i,j]2)银行家算法设Requesti是进程Pi的请求向量,如果Requesti[j]=K,表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后,(1)如果Requesti[j]≤Need[i,j],便转向步骤2;否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。(2)如果Requesti[j]≤Available[j],便转向步骤(3);否则,表示尚无足够资源,Pi须等待。(3)系统试探着把资源分配给进程Pi,并修改下面数据Available[j]∶=Available[j]-Requesti[j];Allocation[i,j]∶=Allocation[i,j]+Requesti[j];Need[i,j]∶=Need[i,j]-Requesti[j];(4)系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则,将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待。3)安全性算法(1)设置两个向量:①工作向量Work:它表示系统可提供给进程继续运行所需的各类资源数目,它含有m个元素,在执行安全算法开始时,Work∶=Available;②Finish:它表示系统是否有足够的资源分配给进程,使之运行完成。开始时先做Finish[i]∶=false;当有足够资源分配给进程时,再令Finish[i]∶=true。(2)从进程集合中找到一个能满足下述条件的进程:①Finish[i]=false;②Need[i,j]≤Work[j];若找到,执行步骤(3),否则,执行步骤(4)。(3)当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,Work[j]∶=Work[i]+Allocation[i,j];Finish[i]∶=true;gotostep2;(4)如果所有进程的Finish[i]=true都满足,则表示系统处于安全状态;否则,系统处于不安全状态。4)银行家算法之例假定系统中有五个进程{P0,P1,P2,P3,P4}和三类资源{A,B,C},各种资源的数量分别为10、5、7,在T0时刻的资源分配情况如图3-16所示。图3-16T0时刻的资源分配表(1)T0时刻的安全性检查图3-17T0时刻的安全序列(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图3-18P1申请资源时的安全性检查(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所示。图3-19为P0分配资源后的有关资源数据•(5)安全性检查:Available(2,1,0)不能满足任何进程的需求,系统进入不安全状态,不能分配资源。•思考:P0请求改为Request0(0,1,0),系统是否能分配资源?
本文标题:如何求解银行家算法
链接地址:https://www.777doc.com/doc-239885 .html