2019年操作系统第五章死锁与饥饿.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来到后才能发出信件s35.2死锁定义一组进程中的每一个进程，均无限期地等待此组进程中某个其他进程占有的，因而永远无法得到的资源，这种现象称为进程死锁。几个有用的结论：–参与死琐的进程至少有二个；–每个参与死锁的进程均等待资源；–参与死锁的进程中至少有两个进程占有资源；–死锁进程是系统中当前进程集合的一个子集。5.3死锁的条件Coffman条件（必要条件）–资源独占（mutualexclusion）又称为互斥条件，一个资源在同一时刻只能分配给一个进程。任一时刻一个资源仅为一个进程独占，若另一个进程请求一个已被占用的资源时，它被置成等待状态，直到占用者释放资源。–不可剥夺（nonpreemption）任一进程不能从另一进程那里抢夺资源，即已被占用的资源，只能由占用进程自己来释放。–保持申请（hold-while-applying）又叫占有和等待条件，一个进程请求资源得不到满足而等待时，不释放已占有的资源。–循环等待（circularwait）又叫环路等待条件，存在一个循环等待链，其中，每一个进程分别等待它前一个进程所持有的资源，造成永远等待。破坏上述任意一个条件可以消除死锁。5.4死锁的处理死锁预防（deadlockprevention）-静态–通过设置某些限制条件，去破坏产生死锁的4个必要条件中的一个或几个条件，来防止死锁发生。死锁避免（deadlockavoidance）--动态–不需事先采取各种限制措施去破坏产生死锁的必要条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。5.4死锁的处理死锁检测（deadlockdetection）–这种方法预先并不采取任何限制措施，也不检查系统是否已经进入不安全区，此法允许系统在运行过程中发生死锁。但可通过系统设置的检测机构，及时地检测出死锁的发生，并精确的确定与死锁有关的进程和资源；然后采取适当的措施，从系统中将已发生的死锁清除掉。死锁恢复（deadlockrecovery）–这是与检测死锁相配套的一种措施，用于将进程从死锁状态下解脱出来，常用的实施方法是撤销或挂起一些进程，以便收回一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态以继续运行。5.5资源分配图定义:G=(V,E),V=PR,P={p1,p2,…,pn},R={r1,r2,…,rm},E={(pi,rj)}{(rj,pi)},piP,rjR.申请边(pi,rj):pi申请rj；分配边(rj,pi):rj分配pi;图示：进程：资源：申请边：由进程到资源类；分配边：由资源实例到进程。5.5资源分配图申请：pi申请rj中的一个资源实例，由pi向rj画一申请边，如可满足，改为分配边。释放：去掉分配边。例子（无环路，无死锁）例1.P={p1,p2,p3},R={r1(1),r2(2),r3(1),r4(3)}E={(p1,r1),(p2,r3),(r1,p2),(r2,p1),(r2,p2),(r3,p3)}p1p2p3r1r3r2r4例子（有环路，有死锁）p1p2p3r1r3r2r4增加边（p3,r2)例子（有环路，无死锁）p1p2p3p4r1r2“死锁检测”程序如果资源分配图中无环路，则此时系统没有发生死锁如果资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程如果资源分配图中有环路，且涉及的资源类中有多个资源，则环路的存在只是产生死锁的必要条件，未必系统一定就会发生死锁。看资源分配图能否化简。5.5.2资源分配图的约简可以通过对资源分配图的约简，来判断系统是否处于死锁状态．资源分配图中的约简方法如下：–(1)寻找一个非孤立且没有请求边的进程结点pi,若无算法结束；–(2)去除所有pi的分配边使pi成为一个孤立结点；–(3)寻找所有请求边均可满足的进程pj,将pj的请求边全部改为分配边；–(4)转步骤(1)．若算法结束时，所有结点均为孤点，则称资源分配图是可以完全约简的，否则称为不可完全约简的．文献已经证明，系统处于死锁状态的充分必要条件是资源分配图不可完全约简．这一结论称为死锁定理．定理：S为死锁状态的充分必要条件是S的资源分配图不可完全约简。判断下列资源分配图所标示的状态是否为死锁p1p2p3化简下面的资源分配图，并利用死锁定理给出相应的结论p2p15.6死锁预防对进程有关资源的活动加限制，所有进程遵循这种限制，即可保证没有死锁发生。–优点：简单，系统不需要做什么。–缺点：对进程的约束，违反约束仍可能死锁。预防方法：–预先分配法；–有序分配法。5.6.1预先分配法进程：运行前申请所需全部资源；系统：–能够满足，全部分配，–否则，一个也不分配。破坏“hold-and-wait”条件缺点：–资源利用效率低；–一次提出申请困难。5.6.2有序分配法在这种方法中规定，系统将所有的资源按其类型进行线性排队，并赋予不同的序号。所有进程对资源的请求必须严格按资源序号递增的次序提出，这样，在所形成的资源分配图中，不可能再出现环路，因而摒弃了“循环等待”条件。5.6.2有序分配法资源集：R={r1,r2,…,rn}函数：F：RN例如：R={scanner,tape,printer}F(scanner)=1;F(tape)=2;F(printer)=3;进程pi可以申请资源rj中的实例rl,pi占有rl,F(rl)F(rj)r1r2rkrm......申请次序5.6.2有序分配法证明无死锁（deadlockfree)：反证，假定死锁时刻t1:p1无限等待rk1中的资源实例，被p2占有；t2:p2无限等待rk2中的资源实例，被p3占有；…tn:pn无限等待rkn中的资源实例，被p1占有;根据有序申请假设：F(rk1)F(rk2)…F(rkn)F(rk1)矛盾。5.7死锁避免死锁避免定义:在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。预防死锁的几种策略，会严重地损害了系统性能。因此要施加较弱的限制，从而获得较满意的系统性能来避免死锁。由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。安全性检查5.7死锁避免检测可满足请求分配不分配安全不安全定义：说系统处于安全状态,如果存在一个由系统中所有进程构成的安全进程序列p1,p2,…,pn；说一个进程序列p1,p2,…,pn是安全的,如果对于每一个进程pi(1≤i≤n),它以后尚需要的资源数量不超过系统当前剩余资源数量与所有进程pj(ji)当前占有资源数量之和.5.7死锁避免例：设系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。设在T0时刻，进程P1、P2和P3分别获得5台、2台和2台，尚有3台空闲未分，如下表所示：进程最大需求已分配可用P1P2P310495223由安全状态向不安全状态的转换如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。因为，此时也无法再找到一个安全序列，例如，把其余的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。安全状态与不安全状态不安全状态:不存在一个安全序列。不安全状态一定导致死锁？利用银行家算法避免死锁当一个进程提出资源请求时，银行家算法要做的工作其要点是：①判断有无实施资源分配的可能。如果系统有能力，则实施预分配。②预分配。③判断分配后系统是否安全，若安全，则真正实施分配。资源分配表安全性检查表银行家算法(Cont.)Banker’salgorithm,E.W.Dijkstra.进程：事先申明所需资源最大量（并不分配）系统：对每个可满足的资源申请命令进行安全性检查。资源分配的安全性是指要保证至少有一个进程能够运行到结束，并且通过回收该进程所占用的资源再分配能依次使其他进程运行结束，然后继续回收资源、继续分配等，直到全部进程运行结束。如果计算出的资源分配是不安全的，系统将拒绝分配。银行家算法(Cont.)数据结构：①Available:array[1..m]ofinteger;//系统可用资源Available[i]=k表示系统中现有Ri类资源k个。②Claim:array[1..n,1..m]ofinteger;//进程最大需求Claim[i,j]=k表示进程Pi最多需要资源类Rj中k个资源实例。③Allocation:array[1..n,1..m]ofinteger;//当前分配Allocation[i,j]=k表示进程Pi当前已分得k个Rj类资源。银行家算法(Cont.)④Need:array[1..n,1..m]ofinteger;//尚需资源Need[i,j]=k表示进程Pi还需要分得k个Rj类资源才能完成其任务⑤Request:array[1..n,1..m]ofinteger;//当前请求Request[i,j]=k表示进程Pi申请Rj类资源中k个资源实例。临时变量：⑥Work:array[1..m]ofinteg