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