操作系统第五章死锁与饥饿.ppt

第五章 死锁与饥饿,死锁的概念死锁的条件死锁的处理资源分配图死锁的预防,死锁的避免死锁的发现死锁的恢复饥饿与活锁,学习目标1.掌握死锁的定义,死锁的条件，死锁的处理以及处理死锁的算法银行家算法。2.理解资源分配图。学习要点本章的重点在于掌握死锁的处理方法，会用银行家算法计算是否发生死锁。,第五章 死锁与饥饿,一个进程需要使用独占型资源必须有一定的次序：申请资源使用资源释放资源1968年Havender在评论OS/360操作系统时说：“原先多任务的概念是让多个任务不加限制的竞争资源，但是随着系统的发展，很多任务被锁在系统中了。”1971年Lynch说：“1962年我们设计Exec2系统时并没有认识到死锁的问题，系统中也没有任何防范措施，结果现在一些程序中已被锁在系统中了。”,死锁产生的原因和必要条件,死锁现象,5.1 死锁产生的原因,1、进程推进顺序不当产生死锁。设系统有打印机、读卡机各一台，它们被进程P和Q共享。两个进程并发执行，它们按下列次序请求和释放资源：进程P 进程Q 请求读卡机 请求打印机 请求打印机 请求读卡机 释放读卡机 释放读卡机 释放打印机 释放打印机,例2：R1和R2为可再用资源;进程Q1和Q2共享两个资源R1和R2。s1和s2分别代表资源R1和R2能否被使用的信号量，由于R1和R2是共享的，必须使用互斥。因而s1和s2的初值为1。假定两个进程都要求使用两个资源，它们的程序如下：,进程Q1：P(s1)P(s2)使用R1和R2V(s1)V(s2),进程Q2：P(s2)P(s1)使用R1和R2V(s2)V(s1),5.1 死锁产生的原因,2、PV操作使用不当产生死锁,5.1 死锁产生的原因,3、同类资源分配不当引起死锁若系统中有m个资源被n个进程共享，当每个进程都要求k个资源。而mn*k时，即资源数小于进程所需要的总数时，如果分配不得当就可能引起死锁。例3，m=5,n=5,k=2，采用的分配策略是为每个进程轮流分配。,5.1 死锁产生的原因,4、进程通讯引起死锁在进程通讯时使用的信件可以看作是一种临时性资源，如果对信件的发送和接收不加限制的话，则可能引起死锁例4：进程p1等待进程p3的信件s3来到后再向进程p2发送信件s1；p2又要等待p1信件来到后再向p3发送信件s2；而p3也要等待p2的信件s2来到后才能发出信件s3,5.2 死锁定义,一组进程中的每一个进程，均无限期地等待此组进程中某个其他进程占有的，因而永远无法得到的资源，这种现象称为进程死锁。,几个有用的结论：参与死琐的进程至少有二个；每个参与死锁的进程均等待资源；参与死锁的进程中至少有两个进程占有资源；死锁进程是系统中当前进程集合的一个子集。,5.3 死锁的条件,Coffman条件（必要条件）资源独占（mutual exclusion）又称为互斥条件，一个资源在同一时刻只能分配给一个进程。任一时刻一个资源仅为一个进程独占，若另一个进程请求一个已被占用的资源时，它被置成等待状态，直到占用者释放资源。不可剥夺（non preemption）任一进程不能从另一进程那里抢夺资源，即已被占用的资源，只能由占用进程自己来释放。,保持申请（hold-while-applying）又叫占有和等待条件，一个进程请求资源得不到满足而等待时，不释放已占有的资源。循环等待（circular wait）又叫环路等待条件，存在一个循环等待链，其中，每一个进程分别等待它前一个进程所持有的资源，造成永远等待。破坏上述任意一个条件可以消除死锁。,5.4 死锁的处理,死锁预防（deadlock prevention）-静态通过设置某些限制条件，去破坏产生死锁的4个必要条件中的一个或几个条件，来防止死锁发生。死锁避免（deadlock avoidance）-动态不需事先采取各种限制措施去破坏产生死锁的必要条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。,5.4 死锁的处理,死锁检测（deadlock detection）这种方法预先并不采取任何限制措施，也不检查系统是否已经进入不安全区，此法允许系统在运行过程中发生死锁。但可通过系统设置的检测机构，及时地检测出死锁的发生，并精确的确定与死锁有关的进程和资源；然后采取适当的措施，从系统中将已发生的死锁清除掉。死锁恢复（deadlock recovery）这是与检测死锁相配套的一种措施，用于将进程从死锁状态下解脱出来，常用的实施方法是撤销或挂起一些进程，以便收回一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态以继续运行。,5.5 资源分配图,定义:G=(V,E),V=PR,P=p1,p2,pn,R=r1,r2,rm,E=(pi,rj)(rj,pi),piP,rjR.申请边(pi,rj):pi申请rj；分配边(rj,pi):rj分配pi;图示：进程：资源：申请边：由进程到资源类；分配边：由资源实例到进程。,5.5 资源分配图,申请：pi申请rj中的一个资源实例，由pi向rj画一申请边，如可满足，改为分配边。释放：去掉分配边。,例子（无环路，无死锁）,例子（有环路，有死锁）,例子（有环路，无死锁）,p1,p2,p3,p4,r1,r2,“死锁检测”程序,如果资源分配图中无环路，则此时系统没有发生死锁如果资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程如果资源分配图中有环路，且涉及的资源类中有多个资源，则环路的存在只是产生死锁的必要条件，未必系统一定就会发生死锁。看资源分配图能否化简。,5.5.2 资源分配图的约简,可以通过对资源分配图的约简，来判断系统是否处于死锁状态资源分配图中的约简方法如下：(1)寻找一个非孤立且没有请求边的进程结点pi,若无算法结束；(2)去除所有pi的分配边使pi成为一个孤立结点；(3)寻找所有请求边均可满足的进程pj,将pj的请求边全部改为分配边；(4)转步骤(1)若算法结束时，所有结点均为孤点，则称资源分配图是可以完全约简的，否则称为不可完全约简的文献已经证明，系统处于死锁状态的充分必要条件是资源分配图不可完全约简这一结论称为死锁定理定理：S为死锁状态的充分必要条件是S的资源分配图不可完全约简。,判断下列资源分配图所标示的状态是否为死锁,p1,p2,p3,化简下面的资源分配图，并利用死锁定理给出相应的结论,p2,p1,5.6 死锁预防,对进程有关资源的活动加限制，所有进程遵循这种限制，即可保证没有死锁发生。优点：简单，系统不需要做什么。缺点：对进程的约束，违反约束仍可能死锁。预防方法：预先分配法；有序分配法。,5.6.1 预先分配法,进程：运行前申请所需全部资源；系统：能够满足，全部分配，否则，一个也不分配。破坏“hold-and-wait”条件缺点：资源利用效率低；一次提出申请困难。,5.6.2 有序分配法,在这种方法中规定，系统将所有的资源按其类型进行线性排队，并赋予不同的序号。所有进程对资源的请求必须严格按资源序号递增的次序提出，这样，在所形成的资源分配图中，不可能再出现环路，因而摒弃了“循环等待”条件。,5.6.2 有序分配法,资源集：R=r1,r2,rn 函数：F：RN 例如：R=scanner,tape,printer F(scanner)=1;F(tape)=2;F(printer)=3;,进程pi可以申请资源rj中的实例rl,pi占有rl,F(rl)F(rj),5.6.2 有序分配法,证明无死锁（deadlock free)：反证，假定死锁 时刻t1:p1无限等待rk1中的资源实例，被p2占有；t2:p2无限等待rk2中的资源实例，被p3占有；tn:pn无限等待rkn中的资源实例，被p1占有;根据有序申请假设：F(rk1)F(rk2)F(rkn)F(rk1)矛盾。,5.7 死锁避免,死锁避免定义:在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。预防死锁的几种策略，会严重地损害了系统性能。因此要施加较弱的限制，从而获得较满意的系统性能来避免死锁。由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。,安全性检查,5.7 死锁避免,定义：说系统处于安全状态,如果存在一个由系统中所有进程构成的安全进程序列；说一个进程序列 是安全的,如果对于每一个进程pi(1in),它以后尚需要的资源数量不超过系统当前剩余资源数量与所有进程pj(ji)当前占有资源数量之和.,5.7 死锁避免,例：设系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。设在T0时刻，进程P1、P2和P3分别获得5台、2台和2台，尚有3台空闲未分，如下表所示：,由安全状态向不安全状态的转换 如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。因为，此时也无法再找到一个安全序列，例如，把其余的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。,安全状态与不安全状态,不安全状态:不存在一个安全序列。不安全状态一定导致死锁？,利用银行家算法避免死锁,当一个进程提出资源请求时，银行家算法要做的工作其要点是：判断有无实施资源分配的可能。如果系统有能力，则实施预分配。预分配。判断分配后系统是否安全，若安全，则真正实施分配。,资源分配表,安全性检查表,银行家算法(Cont.),Bankers algorithm,E.W.Dijkstra.进程：事先申明所需资源最大量（并不分配）系统：对每个可满足的资源申请命令进行安全性检查。资源分配的安全性是指要保证至少有一个进程能够运行到结束，并且通过回收该进程所占用的资源再分配能依次使其他进程运行结束，然后继续回收资源、继续分配等，直到全部进程运行结束。如果计算出的资源分配是不安全的，系统将拒绝分配。,银行家算法(Cont.),数据结构：Available:array1.mof integer;/系统可用资源Availablei=k表示系统中现有Ri类资源k个。Claim:array1.n,1.mof integer;/进程最大需求Claim i,j=k表示进程Pi最多需要资源类Rj中k个资源实例。Allocation:array1.n,1.mof integer;/当前分配Allocationi,j=k表示进程Pi当前已分得k个Rj类资源。,银行家算法(Cont.),Need:array1.n,1.mof integer;/尚需资源Needi,j=k表示进程Pi还需要分得k个Rj类资源才能完成其任务 Request:array1.n,1.mof integer;/当前请求 Requesti,j=k表示进程Pi申请Rj类资源中k个资源实例。临时变量：Work:array1.mof integer;Finish:array1.nof boolean,假设某一时刻，进程Pi提出了资源请求Requestj，银行家算法的操作过程可用以下各步表示：(1)如果RequestjNeedi,j，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。(2)如果RequestjAvailablej，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。,算法5-1：银行家算法-资源分配算法,(3)系统对进程Pi实施资源的预分配 Availablej=Availablej-Requestij;Allocationi,j=Allocationi,j+Requestij;Needi,j=Needi,j-Requestij;(4)通过调用安全性算法判断此次分配是否要真正实施。调用安全性算法，根据返回值判断此次分配的真正实施是否安全。如果安全，则真正实施分配；如果不安全，则取消预分配。,算法5-1：银行家算法-资源分配算法,资源分配,Pi请求资源,RequestINeedI,请求超量，错返,RequestIAvailable,不满足，等待,Available:=Available-RequestIAllocationI:=AllocationI+RequestINeedI:=NeedI-RequestI,安全,确认，pi继续,Available:=Available+RequestIAllocationI:=AllocationI-RequestINeedI:=NeedI+RequestIpi等待,F,T,F,T,T,F,(1)设置两个向量：工作向量Work 用于记录当前可用的每类资源的数目在执行安全算法开始时，Work=Available;Finish:用于记录进程P1，P2，Pn是否可运行完成。比如，Finish i=true，表示进程Pi可运行完成；Finish i=false，表示进程Pi不能运行完成 开始时先做Finishi=false;当有足够资源分配给进程时，再令Finishi=true。,算法5-2：银行家算法安全性检查算法,算法5-2：银行家算法安全性检查算法,安全性算法按以下各步操作寻找进程的安全序列 1.Work=Available；Finish=false；2.寻找满足如下条件的i:(1)Finishi=false；(2)NeediWorki；如果不存在,则转步骤4；3.Work=Work+Allocationi；Finishi=true；转步骤24.如果对于所有i,Finishi=true,则系统处于安全状态,否则处于不安全状态.,安全性检测算法,F,银行家算法例子,R=A(10),B(5),C(7)P=p0,p1,p2,p3,p4,Max Allocation Need Available Work FinishA B C A B C A B C A B C A B C 7 5 3 0 1 0 7 4 3 3 3 23 2 2 2 0 0 1 2 29 0 2 3 0 2 6 0 02 2 2 2 1 1 0 1 14 3 3 0 0 2 4 3 1,P0:p1:p2:p3:p4:,安全进程序列：p1请求：Request1=(1,0,2),(2)P1请求资源：P1发出请求向量Request(1，0，2)，系统按银行家算法进行检查：Request(1,0,2)Need(1,2,2)Request(1,0,2)Available(3,3,2)系统先假定可为P1分配资源，并修改Available,Allocation1和Need1向量 再利用安全性算法检查此时系统是否安全。,银行家算法例子,Max Allocation Need Available Work FinishA B C A B C A B C A B C A B C 7 5 3 0 1 0 7 4 3 2 3 03 2 2 3 0 2 0 2 09 0 2 3 0 2 6 0 02 2 2 2 1 1 0 1 14 3 3 0 0 2 4 3 1,P0:p1:p2:p3:p4:,假定分配：,安全进程序列：p4请求：Request4=(3,3,0),能否满足？p0请求：Request0=(0,2,0),能否满足？,(3)p4请求资源：p4发出请求向量Request(3，3，0)，系统按银行家算法进行检查：Request(3,3,0)Need(4,3,1);Request(3,3,0)Available(2,3,0)，让p4等待。(4)p0请求资源：p0发出请求向量Requst(0，2，0)，系统按银行家算法进行检查：Request(0,2,0)Need(7,4,3);Request(0,2,0)Available(2,3,0);系统暂时先假定可为p0分配资源，并修改有关数据,银行家算法的保守性,例子：R=A,B,申请a,b;释放a,b P=p1,p2,p1:a b a b;p2:b b b a a b,Max Allocation Need Available Work Finish A B A B A B A B A B p1：1 1 0 0 1 1 1 1p2：1 1 0 0 1 1,Request1=(1,0),安全，分配。,银行家算法的保守性,Request2=(0,1),不安全，不分配，（分配不导致死锁）,Claim Allocation Need Available Work Finish A B A B A B A B A B p1：1 1 1 0 0 1 0 1p2：1 1 0 0 1 1,分配后：,练习：某系统中有10台打印机，有三个进程P1、P2、P3分别需要8台、7台和4台。若P1、P2、P3已申请到4台、2台和2台。试问：按银行家算法能安全分配吗？请说明分配过程。,例2：假定系统中有4个进程P1、P2、P3、P4和3类资源R1、R2、R3（资源数量分别为9、3、6），在t0时刻的资源分配情况如下表所示：资源情况 claim allocation need available进程 R1R2R3 R1R2R3 R1R2R3 R1R2R3 P1 3 2 2 1 0 0 2 2 2 1 1 2 P2 6 1 3 5 1 1 1 0 2 P3 3 1 4 2 1 1 1 0 3 P4 4 2 2 0 0 2 4 2 0 试问:(1)t0时刻系统是否安全？(2)P2发出请求向量request2(1,0,1),系统能否将资源分配给它？(3)在P2申请资源后，若P1发出请求向量request1(1,0,1),系统能否将资源分配给它？,5.8 死锁检测,考虑因素：死锁发生频度；死锁影响进程。1.等待时检测：发现早，恢复代价小，开销大（overhead)。2.定时检测：3.资源（eg.CPU）利用率下降时检测。,5.8.1 死锁检测算法,数据结构：Available:array1.mof integer;Allocation:array1.n,1.mof integer;Request:array1.n,1.mof integer;临时变量：Work:array1.mof integer;Finish:array1.nof boolean;,5.8.1 死锁检测算法,FinishI=truefor allocationI=0,Remarks,1.上述算法可以检测到参与死锁的全部进程，包括占有资 源和不占有资源的进程。2.如果希望只检测占有资源的进程，初始化时：Finishi=true,for AllocationI=0,死锁例子,例子：R=A(7),B(2),C(6);P=p0,p1,p2,p3,p4,Allocation Request Available Work Finish A B C A B C A B C A B C p0:0 1 0 0 0 0 0 0 0p1:2 0 0 2 0 2 p2:3 0 3 0 0 0p3:2 1 1 1 0 0p4:0 0 2 0 0 2,未死锁。此时，Request2=(0,0,1),死锁，参与死锁进程p1,p2,p3,p4,5.9 死锁的恢复,1.重新启动 简单，代价大，涉及未参与死锁的进程。2.终止进程(process termination)通过终止参与死锁的进程并收回它们所占有的资源,死锁也能得以解除.这又有两种处理策略:一次性撤销所有参与死锁的全部进程,这种处理方法简单,但代价较高;(2)逐一撤销参与死锁的进程,即按照某种算法选择一个参与死锁的进程,将其撤销并收回其占有的全部资源,然后判断是否还存在死锁,如果是选择并且淘汰下一个将被淘汰的进程,如此重复直至死锁解除.,5.9 死锁的恢复,3.剥夺资源(resource preemption)即剥夺死锁进程所占有的全部或部分资源.在实现时又可分为两种情形:(1)逐步剥夺:一次剥夺死锁进程所占有的一个或一组资源,如死锁尚未解除再继续剥夺,直至死锁解除为止.(2)一次剥夺:一次性地剥夺参与死锁进程所占有的全部资4.进程回退(rollback)所谓进程回退就是让参与死锁的进程回退到以前没有发生死锁的某个点处,并由此点开始继续,希望进程交叉执行时不再发生死锁.,5.12 饥饿与饿死,定义：当等待时间给进程推进和响应带来明显影响时，称发生了进程饥饿(starvation)，当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被饿死(starve to death).饥饿：没有时间上界的等待排队等待忙式等待饿死：等待时间超过极限(deadline)饿死 vs 死锁死锁进程处于等待状态，饿死不然死锁可以检测，饿死不然,饿死与死锁,饿死与死锁有一定联系：二者都是由于竞争资源而引起的，但又有明显差别，主要表现在如下几个方面：(1)从进程状态考虑，死锁进程都处于等待状态，忙式等待(处于运行或就绪状态)的进程并非处于等待状态，但却可能被饿死.(2)死锁进程等待永远不会被释放的资源，饿死进程等待会被释放但却不会分配给自己的资源，其等待时限没有上界(排队等待或忙式等待).(3)死锁一定发生了循环等待，而饿死则不然.这也表明通过资源分配图可以检测死锁存在与否，但却不能检测是否有进程饿死.(4)死锁一定涉及多个进程，而饥饿或被饿死的进程可能只有一个,5.13 死锁的例子,过河问题：,水流,1,2,n-1,n,West,East,W-E,E-W,Deadlock prevention:one direction at any time.,过河问题,Var west_crossing,east_crossing:integer;(0,0)west_wait,east_wait:integer;(0,0);wq,eq:semaphore;mutex:semaphore;西面过河者活动：P(mutex);If east_crossing0 Then Begin west_wait:=west_wait+1;V(mutex);P(wq)End;Else Begin west_crossing:=west_crossing+1;,V(mutex)End;过河；P(mutex);west_crossing:=west_crossing-1;If west_crossing=0 Then While east_wait 0 Do Begin east_wait:=east_wait-1;east_crossing:=east_crossing+1;V(eq);End;V(mutex);,过河问题,过河问题,东面过河者活动：P(mutex);If west_crossing0 Then Begin east_wait:=east_wait+1;V(mutex);P(eq)End Else Begin east_crossing:=east_crossing+1;V(mutex)End;,过河问题,过河；P(mutex);east_crossing:=east_crossing-1;If east_crossing=0 Then While west_wait 0 Do Begin west_wait:=west_wait-1;west_crossing:=west_crossing+1;V(wq);End;V(mutex);,思考问题,对于过河问题，考虑一个没有饿死情况的解法。,例2.过河问题(2),水流,West,East,1-2-5-6-4-3,4-3-7-8-2-1,要求:(1)无死锁;(2)无饿死;(3)并行度高。,WE:P(S);P(s1);走到1;P(s2);走到2;V(s1);P(s5);走到5；V(s2);P(s6);走到6；,EW:P(S);P(s3);走到3;P(s4);走到4;V(s3);P(s7);走到7；V(s4);P(s8);走到8；,V(s5);P(s3);P(s4);走到4;V(s6);走到3;V(s4);走到E;V(s3);V(S);,V(s7);P(s1);P(s2);走到2;V(s8);走到1;V(s2);走到W;V(s1);V(S);,Var S,s1,s2,s3,s4,s5,s6,s7,s8:semaphore;(5,1,1,1,1,1,1,1,1),死锁综合处理,各种处理死锁的方法都有局限性，无论哪种方法都无法适用于各类资源。1973年，Howard提出了死锁综合处理的建议。其思想是：把系统中的全部资源分成几大类，整体上采用资源顺序分配法，在对每类资源根据其特点选择最适合的方法。例如将系统资源分成以下4类：（1）内部资源（系统所用的资源，如PCB表、页表等）。（2）主存。（3）作业资源（如行打印机、磁带驱动器、文件等）。（4）辅存。按编号递增次序申请资源。对第（1）、（4）两类资源采用预分配法；对第（2）类采用剥夺法；对第（3）类采用死锁避免法。而对那些哪种方法也不适合的资源，可用死锁检测程序定期对系统进行检测，发现死锁后再排除死锁。,练习1：某系统有ABCD这4类资源供5个进程共享，进程对资源的需求和分配情况如下表所示。现在系统还剩资源A类1个，B类5个，C类2个和D类0个，请按银行家算法回答下面问题：,1、现在系统是否处于安全状态？2、如果现在进程P2提出需要（0，4，2，0）个资源的要求，系统能否满足它的请求？,