《操作系统死锁.ppt》由会员分享，可在线阅读，更多相关《操作系统死锁.ppt（62页珍藏版）》请在课桌文档上搜索。
1、1,提 纲,死锁的检测和解除,四,死琐的概念和资源分配图,一,产生死琐的原因和必要条件,二,死锁的预防和避免,三,2,死锁的概念和资源分配图,3,死锁现象(以过桥为例),1.死锁现象与例子,4,申请不同类型资源设系统有一台打印机(R1)一台扫描仪(R2)，两进程共享这两台设备。,P1：申请打印机申请扫描仪使用释放打印机释放扫描仪,P2：申请扫描仪申请打印机使用释放打印机释放扫描仪,申请相同类型资源，如内存,1.死锁现象与例子,5,一个结点集合N和边集合E结点N被分为两个互斥子集进程结点子集P=P1,P2,Pn资源结点子集R=R1,R2,RmN=P R=P1,P2,Pn R1,R2,Rm圆圈表一
2、进程，方框表一类资源，其数目由方框中的小圆圈数表示边E 请求边：直接Pi Rj,即e=(Pi,Rj)分配边：Pi Rj 即e=(Rj,Pi),进程,有三个资源,Pi 请求一个Rj,Pi 持有一个Rj,2.资源分配图（Resource Allocation Graph）,6,死锁：指多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。,3.死锁的定义与结论,7,注意：参与死锁的进程数至少为2参与死锁的所有进程均等待资源参与死锁的进程是系统中当前正在运行进程的一部分。,3.死锁的定义与结论,8,相同点：二者都是由于竞争资源而引起的。差别：(1)从进程状态考虑，死锁
3、进程都处于等待状态，忙式等待(处于运行或就绪状态)的进程并非处于等待状态，但却可能被饿死；(2)死锁进程等待永远不会被释放的资源，饿死进程等待会被释放但却不会分配给自己的资源，表现为等待时限没有上界(排队等待或忙式等待)；(3)死锁一定发生了循环等待，而饿死则不然。这也表明通过资源分配图可以检测死锁存在与否，但却不能检测是否有进程饿死；(4)死锁一定涉及多个进程，而饥饿或被饿死的进程可能只有一个。(5)在饥饿的情形下，系统中有至少一个进程能正常运行，只是饥饿进程得不到执行机会。而死锁则可能会最终使整个系统陷入死锁并崩溃。,饥饿是指在预计时间内，某个或某些进程永远得不到完成工作的机会，因为他们所
4、需的资源总是被别的进程占有或抢占。这种状况称作“饥饿”或者“饿死”（Starvation）。,4.死锁竞争饥饿,9,竞争是指两个以上进程以显式或隐式方式共享资源的状态。死锁与竞争是多道程序一对必然状态竞争是资源共享的正常现象，系统有能力协调，有利于提高资源的利用率。死锁是资源共享的异常现象，会浪费大量系统资源，甚至系统崩溃，它是竞争处理不妥造成的。,4.死锁竞争饥饿,10,死锁产生的原因和必要条件,11,根据资源本身的性质可剥夺资源：如主存、CPU不可剥夺资源：如驱动器、打印机等 根据资源使用期限永久性资源：可再次使用，如所有硬件。临时性资源：消耗性的资源，如消息、信号和数据,1.资源分类,1
5、2,竞争资源 当系统中供多个进程所共享的资源不足以同时满足它们的需要时，引起它们对资源的竞争而产生死锁；进程推进顺序非法 进程在运行过程中，请求和释放资源的顺序不当，导致进程的死锁。,2.产生死锁的原因,13,1)竞争非剥夺性资源：,R1代表系统中仅有的一台打印机R2代表系统中仅有的一台磁带机P1、P2代表可共享资源的进程,（1）竞争资源,2.产生死锁的原因,14,2)竞争临时性资源,P1：Release(S3);Request(S1)P2：Release(S1);Request(S2)P3：Release(S2);Request(S3),P1：Request(S1);Release(S3)P
6、2：Request(S2);Release(S1)P3：Request(S3);Release(S2),S1、S2、S3是临时资源,不可能发生死锁,可能发生死锁,（1）竞争资源,2.产生死锁的原因,15,2）进程推进顺序不当（进程并发的异步性）无法控制进程之间的推进顺序（固有的），因此死锁是基本特征的“副作用”；进程可能按下述两种顺序向前推进 进程推进顺序合法 推进顺序非法,2.产生死锁的原因,16,D,进程推进顺序对死锁的影响,P2Rel(R1),P2Rel(R2),P2Req(R1),P2Req(R2),P1Req(R1),P1Req(R2),P1Rel(R1),P1Rel(R2),进程P
7、1、P2并发执行。共享资源R1、R2,曲线4将进入不安全区域（进程推进顺序非法）,17,互斥条件(Mutual Exclusion)即资源独占，某资源要求进程互斥地访问。请求和保持(Hold and wait)进程已占用至少一个资源，且又提出资源请求，当不能满足而阻塞时，保持原资源不释放。不剥夺条件(No preemption)资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放。环路等待条件(Circular wait)必有一进程-资源的环形链。环路中的进程形成等待链。,3.产生死锁的必要条件,18,死锁预防与避免,19,不让死锁发生：死锁预防(prevention)：是一
8、种静态的策略;死锁避免(Avoidance)：是一种动态的策略.允许死锁发生：检测和解除死锁忽略这个问题（鸵鸟算法）,1.处理死锁的基本方法,20,(1)预防死锁 在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一。优点：实现简单；缺点：条件严格，降低系统资源利用率和吞吐量。(2)避免死锁 在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配优点：条件较弱，较高资源利用率和吞吐量。缺点：实现困难.,1.处理死锁的基本方法,21,(3)死锁检测与解除：允许死
9、锁发生，操作系统不断监视系统进展情况，判断死锁是否发生;一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行.,1.处理死锁的基本方法,22,(4)鸵鸟算法（置之不理）是解决死锁的最简单方法。即像鸵鸟一样，当遇到危险时，将头埋进沙子里，假装毫无问题。即不保证死锁从不发生，也不提供死锁检测和恢复的机制。当死锁出现最终导致系统停止工作时，手工重新启动。当死锁在计算机中很少出现时，比如说每五年或更长时间才出现一次时，人们就不必花费更多的精力去解决它，而是采用类似鸵鸟一样的办法忽略它。UNIX系统即采用这样的做法。,1.处理死锁的基本方法,23,因为“互斥条件”是设备的固有属性决定的，
10、不仅不能改变，还应加以保证。,根据生产死锁的四个必要条件，只要使其中之一不能成立，死锁就不会出现。,互斥条件请求和保持条件不剥夺条件环路等待条件,所以只能设法破坏另三个必要条件。,2.死锁的预防,24,(1)摒弃“请求和保持”条件（资源一次性分配）要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。缺点：1）对于“紧俏”资源，进程在整个生命周期一直占用，浪费严重；2）进程延迟运行(starvation possible)。,2.死锁的预防,25,(2)摒弃“不剥夺”条件：资源可剥夺采取的策略：某进程在申请新资源不能满足时，释放已占用的所有资源，
11、以后需要时再重新申请。意味着：进程已经占有的资源，在运行过程中可能会暂时的释放，也可认为是被剥夺了。缺点：实现比较复杂反复地申请和释放资源使进程的执行无限地推迟，延长了周转时间，增加了系统的开销，降低了系统吞吐量。（例如打印机打印的结果不连续）,2.死锁的预防,26,(3)摒弃“环路等待”条件资源有序分配法思想：所有资源按类型进行线性排队，并赋予不同的序号。进程对资源的请求必须按资源序号递增的次序提出。如：输入机1,打印机2,磁带机3,磁盘4缺点：系统中各种类型的资源序号须相对稳定，这就限制了新设备类型的增加 作业实际使用资源的顺序与系统规定的顺序不同而造成资源的浪费；,2.死锁的预防,27,
12、2.死锁的预防,28,3.死锁的避免,29,避免死锁与预防死锁的区别:预防死锁是对于进程的资源申请命令施加限制。避免死锁是在进程请求分配资源时进行动态检查，并根据检查结果决定是否实施资源分配。避免死锁中，可把系统状态分为安全状态和不安全状态。,3.1避免死锁与预防死锁的区别,30,（1）安全状态定义系统能按某种顺序（如）来为每个进程分配其所需的资源，使每个进程都可顺利完成，则称此时系统处于安全状态。若对于每个Pi,Pi申请的资源小于当前可用资源加上所有进程Pj(j称为安全序列。若不存在安全序列，则称系统处于不安全状态。,3.2系统的安全状态,31,（2）安全状态实例 设系统中共有12台磁带机，
13、假设在T0时刻，各进程的需求、占用磁带机的情况如下表所示：,若按P2、P1、P3的顺序执行，则三进程都可顺利完成，因此，此时系统处于安全状态。,进程,最大需求,已分配,剩余,1,2,3,10,4,9,2,3,1,2,4,5,0,5,10,10,P2,P1,P3,存在一个正确的顺序推进进程,3.2系统的安全状态,32,（3）由安全状态向不安全状态的转换,若P3再申请1个磁带机，需求是否可以分配？,进程,最大需求,已分配,剩余,1,2,3,10,4,9,3,2,5,2,2,3,此时，找不到一个序列可使三进程都顺利的运行结束。即系统进入不安全状态，将导致死锁。因此，在进程提出申请时，即使系统中的资源
14、可以满足，也不一定就可以分配，要考虑分配后是否会进入不安全状态。,3.2系统的安全状态,33,（4）安全状态与不安全状态,Basic facts：如果一个系统在安全状态，就没有死锁.如果一个系统处于不安全状态，就有可能死锁.避免死锁的实质：确保系统不进入不安全状态.,安全状态,不安全状态,死锁状态,3.2系统的安全状态,34,思考：以下几种状态安全吗？,35,(1)利用银行家算法避免死锁前提条件1965年由Dijkstra给出，模型基于小城镇银行家，为一群客户提供小额度贷款。银行家拥有资金，被N个客户共享。对客户提出下述约束条件：每个客户必须预先说明自己所要求的最大资金量；每个客户每次提出部分
15、资金量申请和获得分配；如果银行家满足了客户对资金的最大需求量，则客户在资金运作后，能在有限时间内全部归还。,3.3死锁的避免实现-银行家算法,36,(2)设置数据结构 假定系统中有n个进程（P1，P2，Pn），m类资源（R1，R2，Rm），银行家算法中使用的数据结构如下：1）可用资源向量Available：是含有m个元素的数组，每一元素代表一类可用资源的数目。初值为系统中该类资源的全部数目。如：Availablej=k，即系统中现有Rj类资源k个 2）最大需求矩阵Max：是nm矩阵，定义了系统中每一进程对每类资源的最大需求。如Max(i,j)=k，即进程i需要Rj类资源的最大数目为k,3.3死
16、锁的避免实现-银行家算法,37,(2)设置数据结构(续)3）分配矩阵Allocation：是nm矩阵，定义了每一类资源已分配给每一进程的资源数 如：Allocation(i,j)=k，即进程i已分得Rj类资源k个4）需求矩阵Need：是nm矩阵，表示每一进程还需要的各类资源数。如：Need(i,j)=k，表示进程i还需要Rj类资源k个,Need（i，j）=Max（i，j）Allocation（i，j）,3.3死锁的避免实现-银行家算法,38,（3）银行家算法(Bankers Algorithm)描述 资源分配算法 设Requesti是进程Pi的请求向量。如：Requesti(j)=k，表示进程
17、Pi申请Rj类资源k个。当进程发出申请后：1)if requesti=needi then 转2)else 出错中断,因为进程申请资源量超过它申明的最大量。2)if requesti=Available then 转3)else 表明资源不够,需等待。,3.3死锁的避免实现-银行家算法,39,(3)、银行家算法(Bankers Algorithm)描述资源分配算法（续）3)试分配，修改各数据结构中的值：Availablej=Availablej-Requestij Allocationi,j=Allocationi,j+Requestij Needi,j=Needi,j-Requestij4)
18、执行安全性算法，检测试分配后系统是否处于安全状态。若安全，则正式分配，否则恢复原状态让进程Pi等待。,3.3死锁的避免实现-银行家算法,40,(4)银行家算法(Bankers Algorithm)描-安全检查性算法设置两个向量：工作向量Work，是含有m个元素的数组。表示系统中当前可提供的各类资源数目。初值Work=Avaliable；Finishn：布尔型数组，表示系统是否有足够的资源分配给进程。初值Finishi=false，若有足够资源则可设Finishi=true。,3.3死锁的避免实现-银行家算法,41,1)初始化：Work:=Available Finish i=false2)寻找
19、满足如下条件的进程Pi Finishi=false Needi,j Work,如果找到，转3)，否则转4)3)当进程Pi获得资源后，可顺利执行完，并释放分配给它的资源，故执行：Work:=Work+Allocation Finishi:=true 转2).4)若所有进程的Finishi=true，则表示系统处于安全状态，否则处于不安全状态。,3.3死锁的避免实现-银行家算法,(4)银行家算法(Bankers Algorithm)描-安全检查性算法（续）,42,假定系统中有五个进程P0,P1,P2,P3,P4和三类资源A,B,C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图 所
20、示。,图 15 T0时刻的资源分配表,3.4银行家算法实例,43,(1)T0时刻的安全性：,Work=Available=(3,3,2)Finishi=false（i=0,1,4）,3 3 2,5 3 2,Finish,F,F,F,F,F,P0 P1 P2 P3 P4,T,7 4 3,T,7 4 5,T,T,T,10 4 7,10 5 7,3.4银行家算法实例,44,存在一个安全序列P1,P3,P4,P2,P0，系统是安全的。,3.4银行家算法实例,45,(2)P1请求资源：P1发出请求向量Request1(1,0,2)，系统按银行家算法进行检查：,Request1(1,0,2)Need1(1
21、,2,2)Request1(1,0,2)Available(3,3,2)系统先假定可为P1分配资源，并修改Available、Allocation1和Need1向量，由此形成的资源变化情况如图所示。我们再利用安全性算法检查此时系统是否安全。,3.4银行家算法实例,46,2 3 0,0 2 0,3 0 2,资源情况,进程,NeedA B C,workA B C,WorkAllocationA B C,AllocationA B C,P1,finish,5 3 2,true,true,true,true,true,0 1 1,2 1 1,5 3 2,7 4 3,7 4 3,4 3 1,0 0 2,
22、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,2 3 0,3 0 2,0 2 0,由安全性检查分析得知：可以找到一个安全序列P1,P3,P4,P2,P0，系统是安全的，可立即将P1所申请的资源分配给它。,P3,P4,P2,P0,2 3 0,0 2 0,3 0 2,47,(3)P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查：Request4(3,3,0)Need4(4,3,1);Request4(3,3,0)Available(2,3,0)不成立，让P4等待。,3.4银行家算法实例,48,
23、Requst0(0，2，0),(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.4银行家算法实例,49,P0请求资源Requst0(0，2，0)时的资源分配表,2 1 0,0 3 0,7 2 3,P0 请求Requst0(0，1，0)?,因Avaliable(2,1,0)已不能满足任何进程需要,故系统进入不安全状态,此时系统不分配资源。,3.4银行家算法实例,50,银行家算法不足：对资源分配过
24、于保守，计算太多，且缺乏实用价值！为什么？,进程数动态变化，另外事先也不知道需多少资源,思考：1、不安全状态一定引起死锁吗？2、一台计算机有8台磁带机，它们由N个进程竞争使用，每个进程可能需要3台磁带机，请问N为多少时，系统没有死锁的危险？,否,4,3.4银行家算法实例,51,死锁的检测与解除,52,如果在一个系统中，即未采用死锁预防方法，也未采用死锁避免方法，而是直接为进程分配资源，则系统中便有可能发生死锁。一旦死锁发生，系统应能将其找到并加以消除，为此需提供死锁检测和解除的手段。,保存有关资源的请求和分配信息。提供一种算法，以利用这些信息来检测系统是否已进入死锁状态。,1.死锁检测和解除概
25、述,53,有环路且有死锁的资源分配图,有环但没有死锁的资源分配图,重要结论：如果资源分配图中不存在环路，则系统中不存在死锁；如果资源分配图中存在环路，则系统中可能存在死锁，也可能不存在死锁。,1.死锁检测和解除概述,54,1）简化资源分配图：在资源分配图中找到一个既不阻塞也不独立的进程结点（即它的请求边可以得到满足）认为此进程可顺利完成，即它的资源可释放，所以可以去掉它的资源请求边和分配边。重复查找这种结点，去边。若能消去图中所有的边，所有进程结点都成为独立结点，则称该图是可完全简化的。否则，称为不可完全简化。所有的简化顺序，可得到相同的不可简化图。,2.死锁定理,55,P1,P2,(a),P
26、1,P2,(b),P1,P2,(c),2.死锁定理,56,死锁定理：S为死锁状态的充分条件是，当且仅当S状态的资源分配图是不可完全简化的。,如右图：该图是不可完全简化的,2.死锁定理,57,1）可利用资源向量Avaliable2）表L，记录独立的结点（不占用资源的进程向量）过程：从进程集合中找到一个Request=Work的进程(Work初值为Avaliable)去掉此进程的边，且Work=Work+Allocation 将此进程结点从进程集合中去掉，记入L中。循环执行、直到找不到满足条件结点。若此时，结点集合中的所有结点都在L中，则此时的资源分配图是可完全简化的。否则为不可完全简化，系统将发
27、生死锁。,（1）死锁检测算法描述,3.死锁检测,58,3.死锁检测,（2）基本思想 获得某时刻t系统中各类可利用资源的数目向量w(t),对于系统中的一组进程 p1,p2,pn，找出那些对各类资源请求数目均小于系统现有的各类可利用资源数目的进程。这样的进程可以获得它们所需要的全部资源并运行结束，当它们运行结束后释放所占有的全部资源，从而可用资源数目增加，将这样的进程加入到可运行结束的进程序列L中，然后对剩下的进程再作上述考查。如果一组进程 p1,p2,pn中有几个进程不属于序列L中，那么它们会发生死锁。,59,（3）死锁检测中的数据结构,类似于银行家算法中的数据结构：可利用资源向量:availa
28、blej=k,资源Rj有k个可用最大需求矩阵:Maxi,j=k,进程Pi最大请求k个Rj资源分配矩阵：Allocationi,j=k,进程Pj分配到k个Rj资源需求矩阵：Needi,j=k,进程Pj还需要k个Rj资源三个矩阵的关系：Need i,j=Maxi,j Allocation i,j.,3.死锁检测,60,（4）检测算法采用银行家算法中的安全检查方法。,1.初始化：(a)Work:=Available(b)For i=1,2,n,if Allocationi 0,then Finishi:=false;otherwise,Finishi:=true.2.找到下标 i(a)Finishi
29、=false(b)Requesti Work如果没有这样的i存在，转43.Work:=Work+Allocationi Finishi:=true go to step 2.4.If Finishi=false,for some i,1 i n,then the system is in deadlock state.Moreover,if Finishi=false,then Pi is deadlocked.,3.死锁检测,61,4、死锁的解除,一旦检测出系统中出现了死锁，就应将陷入死锁的进程从死锁状态中解脱出来。常用的解除死锁方法有两种:资源剥夺法:当发现死锁后,从其进程剥夺足够数量的资源给死锁进程,以解除死锁状态.撤消进程法:采用强制手段从系统中撤消一个/一部分死锁进程,并剥夺这些进程的资源供其它死锁进程使用.,62,练 习,已知：某系统有三类非剥夺性资源，其中r1类有2个、r2类有2个、r3类有4个；当前有三个进程P1、P2、P3，对资源的占用和请求如表：1）画出当前资源分配图；2）通过化简资源分配图判断是否发生死锁。,
