《产生死锁的原因和必要条件.ppt》由会员分享,可在线阅读,更多相关《产生死锁的原因和必要条件.ppt(64页珍藏版)》请在三一文库上搜索。
1、1,3.5产生死锁的原因 和必要条件,2,3.8 死锁问题,在多道程序系统中,多个进程并发运行,共享资源,从而提高了资源的利用率。但是若对资源的管理和使用不当,在一定条件下会导致系统发生一种随机性故障死锁。在一些系统中,比如实时控制系统,系统一旦发生死锁将导致灾难性的后果。,3,3.8.1 死锁的基本概念,资源 死锁的定义 产生死锁的原因 产生死锁的必要条件 处理死锁的基本方法,4,资源的概念,OS是计算机系统中资源的管理者,而进程是竞争资源的基本单位,故对系统中所有进程的资源分配工作,都由OS完成。 研究资源分配时,我们必须搞清该资源是可以被几个进程同时使用,还是只能为一个进程使用,资源的不
2、同使用性质正是引起系统死锁的原因。,5,根据资源性质:可剥夺(抢占)和不可剥夺(抢占)资源。 可抢占资源指资源占有进程虽然需要使用该资源,但另一个进程却强行把资源从占有者进程处抢来。 不可抢占资源指只有占用者进程不再需要使用该资源而主动释放资源外,其它进程不得在占有者进程使用资源过程中强行抢占。,资源的分类,6,根据使用方式:共享资源和独享资源。 根据使用期限;永久资源和临时性资源。,可顺序重复使用的资源,由一个进程产生,被另外一个进程使用短暂时间 之后便无用的资源,7,死锁的定义,死锁Deadlock:是计算机系统中多道程序并发执行时,两个或两个以上的进程由于竞争资源而造成的一种互相等待的现
3、象(僵局),如无外力作用,这些进程将永远不能再向前推进。 陷入死锁状态的进程称为死锁进程,所占用的资源或者需要它们进行某种合作的其它进程就会相继陷入死锁,最终可能导致整个系统处于瘫痪状态。,8,产生死锁的原因,1 竞争资源。当系统中供多个进程所共享的资源,不足以同时满足它们的需要时,引起它们对资源的竞争而产生死锁; 2 进程推进的顺序不当 。进程在运行过程中,请求和释放资源的顺序不当,导致进程的死锁。,9,竞争资源,1 竞争非剥夺性资源: 2 竞争临时性资源,打印机R1,磁带机R2,P1,P2,10,P1:Release(S1);Request(S3) P2:Release(S2);Reque
4、st(S1) P3:Release(S3);Request(S2) 不可能发生死锁,P1:Request(S3);Release(S1) P2:Request(S1);Release(S2) P3:Request(S2);Release(S3) 可能发生死锁,S1、S2、S3是临时资源,11,若干死锁的例子(1),例进程推进顺序不当产生死锁 设系统有打印机、读卡机各一台,被进程和共享。两个进程并发执行,按下列次序请求和释放资源: 进程 进程 请求读卡机 请求打印机 请求打印机 请求读卡机 释放读卡机 释放读卡机 释放打印机 释放打印机,12,P2Rel(R1),P2Rel(R2),P2Req(
5、R1),P2Req(R2),P1Req(R1),P1Req(R2),P1Rel(R1),P1Rel(R2),进程P1、P2并发执行。 资源R1、R2,曲线4将进入不安全区域(进程推进顺序非法),13,R2已经分配给P1、R1已经分配给P2,14,产生死锁的四个必要条件,互斥条件:进程访问的是临界资源,那个资源一次只能被一个进程所使用。 不剥夺条件:一个资源仅能被占有它的进程所释放,而不能被其他进程剥夺。 部分分配:(请求和保持条件)一个进程在请求新的资源的同时,保持对某些资源的占有。 环路等待条件:存在一个进程的环路链,链中每一个进程占用有着某个或某些资源,又在等待链中的另一个进程占有的资源。
6、,15,若干死锁的例子(2) 例 PV操作使用不当产生死锁,进程Q1 进程Q2 P(S1); P(s2); P(s2); P(s1); 使用r1和r2; 使用r1和r2 V(S1); V(s2); V(S2); V(S1);,16,若干死锁的例子(3) 例 资源分配不当引起死锁,若系统中有m个资源被n个进程共享,每个进程都要求个资源,而m nK时,即资源数小于进程所要求的总数时,如果分配不得当就可能引起死锁。,17,若干死锁的例子(4) 例对临时性资源使用不加限制引起死锁,进程通信使用的信件是一种临时性资源,如果对信件的发送和接收不加限制,可能引起死锁。 进程P1等待进程P3的信件S3来到后再
7、向进程P2发送信件S1;P2又要等待P1的信件S1来到后再向P3发送信件S2;而P3也要等待P2的信件S2来到后才能发出信件S3。这种情况下形成了循环等待,产生死锁。,18,3.6预防死锁的方法,破坏第一个条件 使资源可同时访问而不是互斥使用,是个简单的办法,磁盘可用这种办法管理,但有许多资源往往是不能同时访问,所以这种做法许多场合行不通。,19,死锁防止,破坏第二个条件或第四个条件 种种死锁防止办法施加于资源的限制条件太严格,会造成资源利用率和吞吐率低。两种比较实用的死锁防止方法,它们能破坏第二个条件或第四个条件。,20,死锁防止 1.摒弃”请求和保持” 静态分配策略(破坏条件2),静态分配
8、是指一个进程必须在执行前就申请它所要的全部资源,并且直到它所要的资源都得到满足后才开始执行。,21,死锁防止,2.摒弃”不剥夺”条件破坏第三个条件 采用剥夺式调度方法可破坏第三个条件,但只适用于对主存资源和处理器资源的分配, 当进程在申请资源未获准许的情况下,如主动释放资源(一种剥夺式),然后才去等待,以后再一起向系统提出申请,也能防止死锁。,22,死锁的防止 3.摒弃”环路等待”条件层次分配策略(破坏条件2和4),资源被分成多个层次 当进程得到某一层的一个资源后,它只能再申请较高层次的资源 当进程要释放某层的一个资源时,必须先释放占有的较高层次的资源 当进程得到某一层的一个资源后,它想申请该
9、层的另一个资源时,必须先释放该层中的已占资源,23,死锁防止 层次策略的变种按序分配策略,把系统的所有资源排一个顺序,例如,系统若共有n个进程,共有m个资源,用ri表示第i个资源,于是这m个资源是: r1,r2,rm 规定如果进程不得在占用资源ri(1im)后再申请rj(ji)。不难证明,按这种策略分配资源时系统不会发生死锁。,24,2 预防死锁,根据生产死锁的四个必要条件,只要使用其中之一不能成立,死锁就不会出现。但必要条件是由设备的固有特性所决定的,不仅不能改变,相反还应加以保证,因此实际上只有三种方法。 预防死锁是一种较易实现的方法,已被广泛使用,但由于所施加的限制条件往往太严格,可能导
10、致系统资源利用率和系统吞吐量降低。,1 互斥条件 2 请求和保持条件 3 不剥夺条件 4 环路等待条件,25,1:防止部分分配(摒弃请求和保持条件),系统要求任一进程必须预先申请它所需的全部资源,而且仅当该进程的全部资源要求能得到满足时,系统才能给予一次性分配,然后启动该进程运行,但是在分配时只要由一种资源不满足,系统就不会给进程分配资源。进程运行期间,不会再请求新的资源,所以,再分配就不会发生(摒弃了部分分配)。 特点:资源严重浪费 进程延迟进行,26,3 防止“不剥夺”条件的出现 采用的策略:一个已经保持了某些资源的进程,当它再提出新的资源要求而不能立即得到满足时,必须释放它已经保持的所有
11、资源,待以后需要时再重新申请。 实现比较复杂,且要付出很大代价;此外,还因为反复地申请和释放资源,而使进程的执行无限地推迟,延长了周转时间,增加了系统的开销,降低了系统吞吐量。(例如打印机打印的结果不连续),27,2.防止“环路等待”条件的出现。,采用资源顺序使用法,基本思想是:把系统中所有资源类型线性排队,并按递增规则赋予每类资源以唯一的编号。例如输入机1,打印机2,磁带机3,磁盘4等等。进程申请资源时,必须严格按资源编号的递增顺序进行,否则系统不予分配。 优点:资源利用率和系统吞吐量与另两种方法相比有较明显的改善。 缺点: 1 为系统中各种类型的资源所分配的序号必须相对稳定,这就限制了新设
12、备类型的增加 2 作业实际使用资源的顺序与系统规定的顺序不同而造成资源的浪费;,28,3 死锁避免,避免死锁与预防死锁的区别在于,预防死锁是设法至少破坏产生死锁的必要条件之一,严格地防止死锁的出现。 避免死锁,它是在进程请求分配资源时,采用银行家算法等防止系统进入不安全状态。,29,在资源的动态分配的过程中,使用某种方法去防止系统进入不安全状态,从而避免死锁的发生。 系统状态: 安全状态:指系统能按照某种顺序如(称为序列为安全序列),为每个进程分配所需的资源,直至最大需求,使得每个进程都能顺利完成。 非安全状态:即在某个时刻系统中不存在一个安全序列,则称系统处于不安全状态或非安全状态。,30,
13、虽然并非所有不安全状态都是死锁状态,但当系统进入不安全状态后,便有可能进入死锁状态;反之只要系统处于安全状态,系统便可避免进入死锁状态。因此,避免死锁的实质是如何使系统不进入不安全状态。,31,安全状态的例子,例:假定系统有三个进程P1、P2、P3,共有12台磁带机。进程P1总共要求10台磁带机,P2和P3分别要求4台和九台。设在T0时刻,进程P1、P2和P3已经获得5台、2台和2台,还有3台空闲没有分配。,进程,最大需求,已分配,可用,P1,10,5,3,P2,P3,4,2,2,9,T0时刻系统时安全的。这时存在一个安全序列,32,安全状态的例子,例:假定系统有三个进程P1、P2、P3,共有
14、12台磁带机。进程P1总共要求10台磁带机,P2和P3分别要求4台和九台。设在T0时刻,进程P1、P2和P3已经获得5台、2台和2台,还有3台空闲没有分配。,进程,最大需求,已分配,可用,P1,10,5,3,P2,P3,4,2,2,9,T0时刻系统时安全的。这时存在一个安全序列,33,虽然并非所有不安全状态都是死锁状态,但当系统进入不安全状态后,便有可能进入死锁状态;反之只要系统处于安全状态,系统便可避免进入死锁状态。因此,避免死锁的实质是如何使系统不进入不安全状态。 系统的状态可能通过下述来描述: 进程剩余申请数最大申请数占有数。 可分配资源数总数占有数之和。,34,3.6.3利用银行家算法
15、避免死锁,银行家算法 银行家拥有一笔周转资金 客户要求分期贷款,如果客户能够得到各期贷款,就一定能够归还贷款,否则就一定不能归还贷款 银行家应谨慎的贷款,防止出现坏帐 用银行家算法避免死锁 操作系统(银行家) 操作系统管理的资源(周转资金) 进程(要求贷款的客户),35,银行家算法,银行家算法是最有代表性的避免死锁算法,是Dijkstra提出的银行家算法。这是由于该算法能用于银行系统现金贷款的发放而得名。为实现银行家算法,系统中必须设置若干数据结构。,36,一、银行家算法中的数据结构 1 可利用资源向量Available 是一个含有m个元素,其中的每一个元素代表一类可利用的资源数目,其初值是系
16、统中所配置的该类全部可用资源数目。如果Availablej=k, 表示系统中现有Rj类资源k个。 2 最大需求矩阵Max 是一个含有nm的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max(i,j)=k, 表示进程i需要Rj类资源的最大数目为k。,Available= 3 5 4 2 8 3 8 6 1,37,3 分配矩阵Allocation 是一个含有nm的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation(i,j)=k, 表示进程i当前已分得Rj类资源k个。 4 需求矩阵Need 是一个含有nm的矩阵,用以表示每一个进程尚需的各类资
17、源数。如果Need(i,j)=k, 表示进程i还需要Rj类资源k个,方能完成其任务。 Need(i,j)= Max(i,j)-Allocation(i,j),38,二、银行家算法 设Requesti是进程Pi的请求向量,如果进程Pi需要K个Rj类资源,当Pi发出资源请求后,系统按下述步骤进行检查: 1 如果RequestiNeedi,则转向步骤2;否则认为出错。(因为它所需要的资源数已超过它所宣布的最大值。 2如果RequestiAvailable,则转向步骤3;否则,表示系统中尚无足够的资源,Pi必须等待 3 系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值: Availabl
18、e:=Available-Requesti; Allocation:=Allocation+Requesti; Needi:= Needi- Requesti; 4 系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,正式将资源分配给进程Pi,以完成本次分配;否则,将试探分配作废,恢复原来的资源分配状态,让进程Pi等待。,39,三、安全性算法 系统所执行的安全性算法可描述如下: 1 设置两个向量 工作向量Work.它表示系统可提供给进程继续运行所需要的各类资源的数目,它含有m个元素,执行安全算法开始时,Work:=Available。 Finish.它表示系统是否有足够的资源
19、分配给进程,使之运行完成。开始时先做Finishi:=false;当有足够的资源分配给进程时,令Finishi:=true. 2 从进程集合中找到一个能满足下述条件的进程:Finishi=false; NeediWork. 如找到,执行步骤3;否则执行步骤4。 3 当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故执行: Work:=Work+Allocation; Finishi:=true; Goto step2; 4 如果所有进程的Finishi=true,则表示系统处于安全状态;否则,系统处于不安全状态。,40,要记住的一些变量的名称,1 Available(可利用
20、资源向量) 某类可利用的资源数目,其初值是系统中所配置的该类全部可用资源数目。 2 Max最大需求矩阵 某个进程对某类资源的最大需求数 3 Allocation分配矩阵 某类资源当前非配给某进程的资源数。 4 Need需求矩阵 某个进程还需要的各类资源数。 Need= Max-Allocation 系统把进程请求的资源分配给它以后要修改的变量 Available:=Available-Request; Allocation:=Allocation+Request; Need:= Need- Request;,41,银行家算法之例,假定系统中有五个进程P0、P1、P2、P3、P4和三种类型的资源
21、A,B,C,每一种资源的数量分别为10、5、7,在T0时刻的资源分配情况如图,资源情况,进程,Allocation A B C,Max A B C,Need A B C,Available A B C,P0 P1 P2 P3 P4,0 1 0,3 2 2,9 0 2,2 2 2,4 3 3,2 0 0,( 3 0 2 ),3 0 2,2 1 1,0 0 2,7 4 3,1 2 2,( 0 2 0 ),0 0,0 1 1,4 3 1,3 3 2,( 2 3 0 ),42,3 3 2,1 2 2,2 0 0,5 3 2,true,true,true,true,true,0 1 1,2 1 1,5
22、3 2,7 4 3,7 4 3,4 3 1,0 0 2,7 4 5,7 4 5,6 0 0,3 0 2,10 4 7,10 4 7,7 4 3,0 1 0,10 5 7,最大值,已分配,还需要,可用,若P1发出请求向量 Request(1,0,2),工作向量Work.它表示系统可提供给进程继续运行所需要的各类资源的数目,10,5 7,43,思考和练习 假定系统中有五个进程P0、P1、P2、P3、P4和 三种类型的资源A,B,C,每一种资源的数量 分别为10、5、7,在T0时刻的资源分配情况如图 请找出该表中T0时刻以后存在的安全序列(至少2种),资源情况,进程,Allocation A B C
23、,Max A B C,Need A B C,Available A B C,P0 P1 P2 P3 P4,0 1 0,3 2 2,9 0 2,2 2 2,4 3 3,2 0 0,3 0 2,2 1 1,0 0 2,7 4 3,1 2 2,6 0 0,0 1 1,4 3 1,3 3 2,7 5 3,44,3 死锁的检测和恢复 死锁的检测和恢复技术是指定期启动一个软件检测系统的状态,若发现有死锁存在,则采取措施恢复之。 (1)死锁的检测 检查死锁的办法就是由软件检查系统中由进程和资源构成的有向图是否构成一个或多个环路,若是,则存在死锁,否则不存在。,45,死锁的检测:实质是确定是否存在环路等待现象
24、,一旦发现这种环路便认定死锁存在,并识别出该环路所涉及的有关进程,以供系统采取适当的措施来解除死锁。最常用的是一种基于资源分配图RAG和死锁定理的检测死锁算法。,46,资源分配图(RAG) 系统死锁可用资源分配图来描述,该图是由一组结点N和一组边E所组成的一对偶G=(N,E)。(用圆圈代表一个进程,用方框代表一类资源,由于一种类型的资源可能有多个,可用方框中的一个点代表一类资源中的一个资源) 几个概念:请求边,分配边,P1,P2,r1,r2,请求r2,资源分配图,47,封锁进程:是指某个进程由于请求了超过了系统中现有的未分配资源数目的资源,而被系统封锁的进程。 非封锁进程:即没有被系统封锁的进
25、程资源分配图的化简方法:假设某个RAG中存在一个进程Pi,此刻Pi是非封锁进程,那么可以进行如下化简:当Pi有请求边时,首先将其请求边变成分配边(即满足Pi的资源请求),而一旦Pi的所有资源请求都得到满足,Pi就能在有限的时间内运行结束,并释放其所占用的全部资源,此时Pi只有分配边,删去这些分配边(实际上相当于消去了Pi的所有请求边和分配边),使Pi成为孤立结点。(反复进行) 。,48,死锁定理: 系统中某个时刻S为死锁状态的充要条件是S时刻系统的资源分配图是不可完全简化的。 在经过一系列的简化后,若能消去图中的所有边,使所有的进程都成为孤立结点,则称该图是可完全简化的;反之的是不可完全简化的
26、。,P1,P2,r1,r2,P1,P2,r1,r2,49,死锁的恢复。是与检测死锁相配套的一种措施,用于将进程从死锁状态下解脱出来。常用的方法有: 1撤消进程;最简单撤消进程的方法是使全部死锁的进程夭折掉;另一方法是按照某种顺序逐个地撤消进程,直至有足够的资源可用,死锁状态消除为止,2挂起进程(剥夺资源)。使用挂起/激活机构挂起一些进程,剥夺它们的资源以解除死锁,待条件满足时,再激活进程。目前挂起法比较受到重视。,50,1(北大95)一个OS有20个进程,竞争使用65个同类资源,申请方式是逐个进行的,一旦某个进程获得它所需要的全部资源,则立即归还所有资源。每个进程最多使用三个资源。若仅考虑这类
27、资源,该系统有无可能产生死锁,为什么? 2死锁和饥饿的主要差别是什么?,例题,51,1 答:不可能。因为死锁产生的原因有两点:系统资源不足或推进顺序不当,在本题中,进程所需的最大资源数为60,而系统共有该类资源65个,其资源数已足够系统内各进程使用。 2 答:简言之,死锁是某进程等待一个不会发生的事件的一种现象;而饥饿现象是某进程正等待这样一个事件,它发生了但总是受到其它进程的影响,以至轮不到(或很难轮到)该进程。,52,银行家算法的基本思想(1),系统中的所有进程进入进程集合, 在安全状态下系统收到进程的资源请求后,先把资源试探性分配给它。 系统用剩下的可用资源和进程集合中其他进程还要的资源
28、数作比较,在进程集合中找到剩余资源能满足最大需求量的进程,从而,保证这个进程运行完毕并归还全部资源。,53,银行家算法的基本思想(2),把这个进程从集合中去掉, 系统的剩余资源更多了,反复执行上述步骤。 最后,检查进程集合,若为空表明本次申请可行,系统处于安全状态,可实施本次分配;否则,有进程执行不完,系统处于不安全状态,本次资源分配暂不实施,让申请进程等待。,54,3.7 死锁的检测与解除,1 资源分配图和死锁定理 2 借助于死锁的安全性测试算法的死锁检测 3 warshall传递闭包算法的死锁检测,55,简化进程-资源分配图检测系统是否处于死锁状态(1),(1)如果进程-资源分配图中无环路
29、,则此时系统没有发生死锁。 (2)如果进程-资源分配图中有环路,且每个资源类中仅有一个资源,则系统中发生了死锁,此时,环路是系统发生死锁的充要条件,环路中的进程便为死锁进程。,56,简化进程-资源分配图检测系统是否处于死锁状态(2),(3)如果进程-资源分配图中有环路,且涉及的资源类中有多个资源,则环路的存在只是产生死锁的必要条件而不是充分条件。,57,简化进程-资源分配图检测系统是否处于死锁状态(3),如果能在进程-资源分配图中消去此进程的所有请求边和分配边,成为孤立结点。经一系列简化,使所有进程成为孤立结点,则该图是可完全简化的;否则则称该图是不可完全简化的。,58,简化进程-资源分配图检
30、测系统是否处于死锁状态(4),系统为死锁状态的充分条件是:当且仅当该状态的进程-资源分配图是不可完全简化的。该充分条件称为死锁定理。,59,死锁的具体检测和解除方法(1),借助于死锁的安全性测试算法来实现。今定义布尔型向量possiblek,k=1,n。检测死锁算法如下: (1)currentavail:=available; (2)在rest中查每一个进程Pk,如果claimk,*-allock,*=0,则possiblek:=true;否则possiblek:=false;这里k=1,n。,60,死锁的具体检测和解除方法(2),(3)在rest中找一个进程Pk,需满足条件: possibl
31、ek=false&(request*currentavail) 找到这样的Pk便转(4);否则转(5); (4)currentavail:=currentavail+allocation;possiblek:=true;然后转(3); (5) 如果对k=1,n若possiblek=true不成立,那么,系统出现了死锁,并且possiblek=false的Pk为死锁进程。,61,死锁的具体检测和解除方法(3),死锁检测算法与死锁避免算法是类似的,不同在于前者考虑了检查每个进程还需要的所有资源能否满足要求;而后者则仅要根据进程的当前申请资源量来判断系统是否进入了不安全状态。,62,3.7.2死锁的解除(1),立即结束所有进程的执行,并重新启动操作系统。方法简单,但以前工作全部作废,损失可能很大。 撤销陷于死锁的所有进程,解除死锁继续运行。,63,死锁的解除(2),逐个撤销陷于死锁的进程,回收其资源,直至死锁解除。 剥夺陷于死锁的进程占用的资源,但并不撤销它, 直至死锁解除。,64,死锁的解除(3), 根据系统保存的checkpoint,让所有进程回退,直到解除死锁。 当检测到死锁时,如果存在某些未卷入死锁的进程,而这些进程随着建立一些新的抑制进程能执行到结束,则它们可能释放足够的资源来解除死锁。,
链接地址:https://www.31doc.com/p-3108859.html