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

1、操作系统第五章死锁与饥饿 第五章第五章 死锁与饥饿死锁与饥饿 死锁的概念 死锁的条件 死锁的处理 资源分配图 死锁的预防 死锁的避免 死锁的发现 死锁的恢复 饥饿与活锁 操作系统第五章死锁与饥饿 学习目标 1.掌握死锁的定义,死锁的条件，死锁的处理 以及处理死锁的算法银行家算法。 2.理解资源分配图。 学习要点 本章的重点在于掌握死锁的处理方法，会用 银行家算法计算是否发生死锁。 操作系统第五章死锁与饥饿 第五章第五章 死锁与饥饿死锁与饥饿 一个进程需要使用独占型资源必须有一定的次序： 申请资源 使用资源 释放资源 1968年Havender在评论OS/360操作系统时说：“原先多任 务的概念

2、是让多个任务不加限制的竞争资源，但是随着 系统的发展，很多任务被锁在系统中了。” 1971年Lynch说：“1962年我们设计Exec2系统时并没有认 识到死锁的问题，系统中也没有任何防范措施，结果现在一 些程序中已被锁在系统中了。” 操作系统第五章死锁与饥饿 死锁产生的原因和必要条件死锁产生的原因和必要条件 死锁现象 操作系统第五章死锁与饥饿 5.1 死锁产生的原因死锁产生的原因 1、进程推进顺序不当产生死锁。、进程推进顺序不当产生死锁。 设系统有打印机、读卡机各一台，它们被进程设系统有打印机、读卡机各一台，它们被进程P和和Q共享。两个进程并发执共享。两个进程并发执 行，它们按下列次序请求和

3、释放资源：行，它们按下列次序请求和释放资源： 进程进程P 进程进程Q 请求读卡机请求读卡机 请求打印机请求打印机 请求打印机请求打印机 请求读卡机请求读卡机 释放读卡机释放读卡机 释放读卡机释放读卡机 释放打印机释放打印机 释放打印机释放打印机 操作系统第五章死锁与饥饿 例例2： R1和和R2为可再用资源为可再用资源;进程进程Q1和和Q2共享两个资源共享两个资源R1和和R2。s1和和s2分别代分别代 表资源表资源R1和和R2能否被使用的信号量，由于能否被使用的信号量，由于R1和和R2是共享的，必须使用互斥。因是共享的，必须使用互斥。因 而而s1和和s2的初值为的初值为1。假定两个进程都要求使用

4、两个资源，它们的程序如下：。假定两个进程都要求使用两个资源，它们的程序如下： 进程进程Q1： P(s1) P(s2) 使用使用R1和和R2 V(s1) V(s2) 进程进程Q2： P(s2) P(s1) 使用使用R1和和R2 V(s2) V(s1) 5.1 5.1 死锁产生的原因死锁产生的原因 2、PV操作使用不当产生死锁操作使用不当产生死锁 操作系统第五章死锁与饥饿 5.1 死锁产生的原因死锁产生的原因 3、同类资源分配不当引起死锁 若系统中有m个资源被n个进程共享，当每个 进程都要求k个资源。而mn*k时，即资源数 小于进程所需要的总数时，如果分配不得当 就可能引起死锁。 例3，m=5,n

5、=5,k=2，采用的分配策略是为每 个进程轮流分配。 操作系统第五章死锁与饥饿 5.1 死锁产生的原因死锁产生的原因 4、进程通讯引起死锁 在进程通讯时使用的信件可以看作是一种临 时性资源，如果对信件的发送和接收不加限 制的话，则可能引起死锁 例4：进程p1等待进程p3的信件s3来到后再向 进程p2发送信件s1；p2又要等待p1信件来到 后再向p3发送信件s2；而p3也要等待p2的信 件s2来到后才能发出信件s3 操作系统第五章死锁与饥饿 5.2 死锁定义死锁定义 一组进程中的每一个进程，均无限期地等待此组进程中某个 其他进程占有的，因而永远无法得到的资源，这种现象称为 进程死锁。 几个有用的

6、结论：几个有用的结论： 参与死琐的进程至少有二个；参与死琐的进程至少有二个； 每个参与死锁的进程均等待资源；每个参与死锁的进程均等待资源； 参与死锁的进程中至少有两个进程占有资源；参与死锁的进程中至少有两个进程占有资源； 死锁进程是系统中当前进程集合的一个子集。死锁进程是系统中当前进程集合的一个子集。 操作系统第五章死锁与饥饿 5.3 死锁的条件死锁的条件 Coffman条件（必要条件） 资源独占（mutual exclusion） 又称为互斥条件，一个资源在同一时刻只能分配给一 个进程。任一时刻一个资源仅为一个进程独占，若另 一个进程请求一个已被占用的资源时，它被置成等待 状态，直到占用者释

7、放资源。 不可剥夺（non preemption） 任一进程不能从另一进程那里抢夺资源，即已被占用 的资源，只能由占用进程自己来释放。 操作系统第五章死锁与饥饿 保持申请（hold-while-applying） 又叫占有和等待条件，一个进程请求资源得不到满足 而等待时，不释放已占有的资源。 循环等待（circular wait） 又叫环路等待条件，存在一个循环等待链，其中，每 一个进程分别等待它前一个进程所持有的资源，造成 永远等待。 破坏上述任意一个条件可以消除死锁。 操作系统第五章死锁与饥饿 5.4 死锁的处理死锁的处理 死锁预防（deadlock prevention）-静态 通过设置

8、某些限制条件，去破坏产生死锁的4个必 要条件中的一个或几个条件，来防止死锁发生。 死锁避免（deadlock avoidance）-动态 不需事先采取各种限制措施去破坏产生死锁的必 要条件，而是在资源的动态分配过程中，用某种 方法去防止系统进入不安全状态，从而避免发生 死锁。 操作系统第五章死锁与饥饿 5.4 死锁的处理死锁的处理 死锁检测（deadlock detection） 这种方法预先并不采取任何限制措施，也不检查系统是否已经进入不 安全区，此法允许系统在运行过程中发生死锁。但可通过系统设置的 检测机构，及时地检测出死锁的发生，并精确的确定与死锁有关的进 程和资源；然后采取适当的措施，

9、从系统中将已发生的死锁清除掉。 死锁恢复（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; 图示：进程： 资源： 申请边：由进程到资源类；

10、分配边：由资源实例到进程。 操作系统第五章死锁与饥饿 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) p1 p2 p3 r1r3 r2r4 操作系统第五章死锁与饥饿 例子（有环路，有死锁）例子（有环路，有死锁） p1 p2 p3 r1r3 r2r4 增加边

11、（p3,r2) 操作系统第五章死锁与饥饿 例子（有环路，无死锁）例子（有环路，无死锁） p1 p2 p3 p4 r1 r2 操作系统第五章死锁与饥饿 “死锁检测死锁检测”程序程序 如果资源分配图中无环路，则此时系统没有发生死锁 如果资源分配图中有环路，且每个资源类中仅有一个资源， 则系统中发生了死锁，此时，环路是系统发生死锁的充要条 件，环路中的进程便为死锁进程 如果资源分配图中有环路，且涉及的资源类中有多个资源， 则环路的存在只是产生死锁的必要条件，未必系统一定就会 发生死锁。看资源分配图能否化简。 操作系统第五章死锁与饥饿 5.5.2 资源分配图的约简资源分配图的约简 可以通过对资源分配图

12、的约简，来判断系统是否处于死锁状态资源分 配图中的约简方法如下： (1)寻找一个非孤立且没有请求边的进程结点pi,若无算法结束； (2)去除所有pi的分配边使pi成为一个孤立结点； (3)寻找所有请求边均可满足的进程pj,将pj的请求边全部改为分配边； (4)转步骤(1) 若算法结束时，所有结点均为孤点，则称资源分配图是可以完全约简的， 否则称为不可完全约简的文献已经证明，系统处于死锁状态的充分必 要条件是资源分配图不可完全约简这一结论称为死锁定理 定理：S为死锁状态的充分必要条件是S的资源分配图不可完 全约简。 操作系统第五章死锁与饥饿 判断下列资源分配图所标示的状态是否为死 锁 p1 p2

13、 p3 操作系统第五章死锁与饥饿 化简下面的资源分配图，并利用死锁定理给 出相应的结论 p2 p1 操作系统第五章死锁与饥饿 5.6 死锁预防死锁预防 对进程有关资源的活动加限制，所有进程遵 循这种限制，即可保证没有死锁发生。 优点：简单，系统不需要做什么。 缺点：对进程的约束，违反约束仍可能死锁。 预防方法： 预先分配法； 有序分配法。 操作系统第五章死锁与饥饿 5.6.1 预先分配法预先分配法 进程：运行前申请所需全部资源； 系统： 能够满足，全部分配， 否则，一个也不分配。 破坏“hold-and-wait”条件 缺点： 资源利用效率低； 一次提出申请困难。 操作系统第五章死锁与饥饿 5

14、.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) r1r2rkrm . 申请次序 操作系统

15、第五章死锁与饥饿 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 死锁避免死锁避免 死锁避免定义:在系统运行过程中，对进程发出的每一个系统 能够满足的资源申请进行动态检查，并根据检查结果决定是 否分配资源，若分配后系统可能发生死锁，则不予分配，否 则予以分配。 预防死锁的几种

16、策略，会严重地损害了系统性能。因此要施 加较弱的限制，从而获得较满意的系统性能来避免死锁。 由于在避免死锁的策略中，允许进程动态地申请资源。因而， 系统在进行资源分配之前预先计算资源分配的安全性。若此 次分配不会导致系统进入不安全状态，则将资源分配给进程； 否则，进程等待。其中最具有代表性的避免死锁算法是银行 家算法。 安全性检查 操作系统第五章死锁与饥饿 5.7 死锁避免死锁避免 检测 可满足请求 分配 不分配 安全 不安全 定义：说系统处于安全状态, 如果存在一个由系统中所有进程构成的安全 进程序列；说一个进程序列 是安全的, 如果对 于每一个进程pi(1in), 它以后尚需要的资源数量不

17、超过系统当前剩余资 源数量与所有进程pj(ji)当前占有资源数量之和. 操作系统第五章死锁与饥饿 5.7 死锁避免死锁避免 例：设系统中有三个进程P1、P2和P3，共有12台磁带机。 进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。 设在T0时刻，进程P1、P2和P3分别获得5台、2台和2台，尚 有3台空闲未分，如下表所示： 进进 程程 最最 大大 需需 求求 已已 分分 配配 可可 用用 P1 P2 P3 10 4 9 5 2 2 3 操作系统第五章死锁与饥饿 由安全状态向不安全状态的转换由安全状态向不安全状态的转换 如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状

18、态。 例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分 配给P3，则系统便进入不安全状态。 因为，此时也无法再找到一个安全序列， 例如，把其余的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足 P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成， 彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。 操作系统第五章死锁与饥饿 安全状态与不安全状态安全状态与不安全状态 不安全状态:不存在一个安全序列。不安全状 态一定导致死锁？ 操作系统第五章死锁与饥饿 利用银行家算法避免死锁利用银行家算法避免死锁 当一个进程提出资源请求时，银行家算法

19、要 做的工作其要点是： 判断有无实施资源分配的可能。如果系统有 能力，则实施预分配。 预分配。 判断分配后系统是否安全，若安全，则真正 实施分配。 资源分配表 安全性检查表 操作系统第五章死锁与饥饿 银行家算法银行家算法(Cont.) Bankers algorithm, E.W. Dijkstra. 进程：事先申明所需资源最大量（并不分配） 系统：对每个可满足的资源申请命令进行安全性检查。 资源分配的安全性是指要保证至少有一个进程能够运行到结束，并且通过回 收该进程所占用的资源再分配能依次使其他进程运行结束，然后继续回收资 源、继续分配等，直到全部进程运行结束。如果计算出的资源分配是不安全

20、的，系统将拒绝分配。 操作系统第五章死锁与饥饿 银行家算法银行家算法(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.) Ne

21、ed: 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 ，银行家算法的操作，银行家算法的操作 过程可用以下各步表示：过程可用以下各步表示： (

22、1) 如果如果RequestjNeedi,j，便转向步骤，便转向步骤2；否则认为出错，因为它；否则认为出错，因为它 所需要的资源数已超过它所宣布的最大值。所需要的资源数已超过它所宣布的最大值。 (2) 如果如果RequestjAvailablej，便转向步骤，便转向步骤(3)；否则，；否则， 表示尚无表示尚无 足够资源，足够资源，Pi须等待。须等待。 算法算法5-15-1：银行家算法：银行家算法-资源分配算法资源分配算法 操作系统第五章死锁与饥饿 (3)系统对进程系统对进程Pi实施资源的实施资源的预分配预分配 Availablej=Availablej-Requestij; Allocatio

23、ni,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij; (4)通过调用通过调用安全性算法安全性算法判断此次分配是否要真正实施。调判断此次分配是否要真正实施。调 用安全性算法，根据返回值判断此次分配的真正实施是否用安全性算法，根据返回值判断此次分配的真正实施是否 安全。如果安全，则真正实施分配；如果不安全，则取消安全。如果安全，则真正实施分配；如果不安全，则取消 预分配。预分配。 算法算法5-15-1：银行家算法：银行家算法-资源分配算法资源分配算法 操作系统第五章死锁与饥饿 资源分配资源分配 Pi请求资源 RequestINeedI 请

24、求超量，错返 RequestIAvailable 不满足，等待 Available:=Available-RequestI AllocationI:=AllocationI+RequestI NeedI:=NeedI-RequestI 安全 确认，pi继续 Available:=Available+RequestI AllocationI:=AllocationI-RequestI NeedI:=NeedI+RequestI pi等待 F T F T T F 操作系统第五章死锁与饥饿 (1) 设置两个向量：设置两个向量： 工作向量工作向量Work 用 于 记 录 当 前 可 用 的 每 类 资

25、 源 的 数 目 在 执 行 安 全 算 法 开 始 时 ，用 于 记 录 当 前 可 用 的 每 类 资 源 的 数 目 在 执 行 安 全 算 法 开 始 时 ， Work =Available; Finish: 用于记录进程用于记录进程P1，P2，Pn是否可运行完成。比如，是否可运行完成。比如，Finish i=true， 表示进程表示进程Pi可运行完成；可运行完成；Finish i=false，表示进程，表示进程Pi不能运行完成不能运行完成 开始时先做开始时先做Finishi=false; 当有足够资源分配给进程时，当有足够资源分配给进程时， 再令再令Finish i=true。 算法

26、算法5-25-2：银行家算法：银行家算法安全性检查算法安全性检查算法 操作系统第五章死锁与饥饿 算法算法5-2：银行家算法：银行家算法安全性检查算法安全性检查算法 安全性算法按以下各步操作寻找进程的安全序列 1. Work = Available；Finish = false； 2. 寻找满足如下条件的i: (1) Finishi=false；(2) NeediWorki； 如果不存在, 则转步骤4； 3. Work = Work + Allocationi；Finishi = true； 转步骤2 4. 如果对于所有i, Finishi = true, 则系统处于安全状态, 否则处 于不安全

27、状态. 操作系统第五章死锁与饥饿 安全性检测算法安全性检测算法 F Work:=Available; Finish:=false; 有满足条件的j: Finishj=false NeedjWork Finishj=true; Work:=Work+Allocationj T j ,finishj=true TF 安全 不安全 操作系统第五章死锁与饥饿 银行家算法例子银行家算法例子 R=A(10),B(5),C(7) P=p0,p1,p2,p3,p4 Max Allocation Need Available Work Finish A B C A B C A B C A B C A B C 7

28、 5 3 0 1 0 7 4 3 3 3 2 3 2 2 2 0 0 1 2 2 9 0 2 3 0 2 6 0 0 2 2 2 2 1 1 0 1 1 4 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) Request(1, 0, 2)Available(3, 3, 2) 系统先假定可为P1分配资源，并修改Available, Allocation

29、1和Need1向 量 再利用安全性算法检查此时系统是否安全。 操作系统第五章死锁与饥饿 银行家算法例子银行家算法例子 Max Allocation Need Available Work Finish A 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 0 3 2 2 3 0 2 0 2 0 9 0 2 3 0 2 6 0 0 2 2 2 2 1 1 0 1 1 4 3 3 0 0 2 4 3 1 P0: p1: p2: p3: p4: 假定分配： 安全进程序列： p4请求：Request4=(3,3,0), 能否满足？ p0请求：Reque

30、st0=(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分配资源，并修改有关数据 操作系统第五章死锁与饥饿 银行家算法的保

31、守性银行家算法的保守性 例子：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 1 p2：1 1 0 0 1 1 Request1=(1,0), 安全，分配。 操作系统第五章死锁与饥饿 银行家算法的保守性银行家算法的保守性 Request2=(0,1), 不安全，不分配，（分配不导致死锁） Claim Allocation Need Available Work Fini

32、sh A B A B A B A B A B p1：1 1 1 0 0 1 0 1 p2：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 R1

33、R2R3 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)。

34、 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 死锁检测算法死锁检测算法 Work:=Available; Finish:=false; 有满足条

35、件的i: Finishi=false RequestiWork Finishi=true; Work:=Work+Allocationi T i ,finishi=true TF F 无死锁 死锁 FinishI=true for allocationI=0 操作系统第五章死锁与饥饿 Remarks 1. 上述算法可以检测到参与死锁的全部进程，包括占有资 源和不占有资源的进程。 2. 如果希望只检测占有资源的进程，初始化时： Finishi=true, for AllocationI=0 操作系统第五章死锁与饥饿 死锁例子死锁例子 例子：R=A(7),B(2),C(6); P=p0,p1,p2

36、,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 0 p1: 2 0 0 2 0 2 p2: 3 0 3 0 0 0 p3: 2 1 1 1 0 0 p4: 0 0 2 0 0 2 未死锁。 此时，Request2=(0,0,1), 死锁，参与死锁进程p1,p2,p3,p4 操作系统第五章死锁与饥饿 5.9 死锁的恢复死锁的恢复 1. 重新启动重新启动 简单，代价大，涉及未参与死锁的进程。简单，代价大，涉及未参与死锁的进程。 2. 终止进程终止进程(proces

37、s termination) 通过终止参与死锁的进程并收回它们所占有的资源通过终止参与死锁的进程并收回它们所占有的资源, 死锁也能得死锁也能得 以解除以解除. 这又有两种处理策略这又有两种处理策略: 一次性撤销所有参与死锁的全部进程一次性撤销所有参与死锁的全部进程, 这种处理方法这种处理方法 简单简单, 但代价较高但代价较高; (2) 逐一撤销参与死锁的进程逐一撤销参与死锁的进程, 即按照某种算法选择一个即按照某种算法选择一个 参与死锁的进程参与死锁的进程, 将其撤销并收回其占有的全部资源将其撤销并收回其占有的全部资源, 然然 后判断是否还存在死锁后判断是否还存在死锁, 如果是选择并且淘汰下一

38、个将如果是选择并且淘汰下一个将 被淘汰的进程被淘汰的进程, 如此重复直至死锁解除如此重复直至死锁解除. 操作系统第五章死锁与饥饿 5.9 死锁的恢复死锁的恢复 3. 剥夺资源(resource preemption) 即剥夺死锁进程所占有的全部或部分资源. 在实现时又可分为两种情形: (1) 逐步剥夺: 一次剥夺死锁进程所占有的一个或一组资源, 如死锁尚未解除再继 续剥夺, 直至死锁解除为止. (2) 一次剥夺: 一次性地剥夺参与死锁进程所占有的全部资 4. 进程回退(rollback) 所谓进程回退就是让参与死锁的进程回退到以前没有发生死锁的某个 点处, 并由此点开始继续, 希望进程交叉执行

39、时不再发生死锁. 操作系统第五章死锁与饥饿 5.12 饥饿与饿死饥饿与饿死 定义：当等待时间给进程推进和响应带来明显影响时，称发 生了进程饥饿(starvation)，当饥饿到一定程度的进程所赋予 的任务即使完成也不再具有实际意义时称该进程被饿死 (starve to death). 饥饿：没有时间上界的等待 排队等待 忙式等待 饿死：等待时间超过极限(deadline) 饿死 vs 死锁 死锁进程处于等待状态，饿死不然 死锁可以检测，饿死不然 操作系统第五章死锁与饥饿 饿死与死锁饿死与死锁 饿死与死锁有一定联系：二者都是由于竞争资源而引起的，但又有明显 差别，主要表现在如下几个方面： (1)

40、 从进程状态考虑，死锁进程都处于等待状态，忙式等待(处于运行或就绪 状态)的进程并非处于等待状态，但却可能被饿死. (2) 死锁进程等待永远不会被释放的资源，饿死进程等待会被释放但却不会 分配给自己的资源，其等待时限没有上界(排队等待或忙式等待). (3) 死锁一定发生了循环等待，而饿死则不然. 这也表明通过资源分配图可以 检测死锁存在与否，但却不能检测是否有进程饿死. (4) 死锁一定涉及多个进程，而饥饿或被饿死的进程可能只有一个 操作系统第五章死锁与饥饿 5.13 死锁的例子死锁的例子 过河问题： 12 n-1n West East W-EE-W Deadlock prevention:

41、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(mu