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

第五章死锁与饥饿死锁的概念死锁的条件死锁的处理资源分配图死锁的预防死锁的避免死锁的发现死锁的恢复饥饿与活锁第五章死锁与饥饿死锁的概念死锁的避免1[学习目标]1.掌握死锁的定义,死锁的条件，死锁的处理以及处理死锁的算法——银行家算法。2.理解资源分配图。[学习要点]本章的重点在于掌握死锁的处理方法，会用银行家算法计算是否发生死锁。[学习目标]2第五章死锁与饥饿一个进程需要使用独占型资源必须有一定的次序：申请资源使用资源释放资源1968年Havender在评论OS/360操作系统时说：“原先多任务的概念是让多个任务不加限制的竞争资源，……但是随着系统的发展，很多任务被锁在系统中了。”1971年Lynch说：“1962年我们设计Exec2系统时并没有认识到死锁的问题，系统中也没有任何防范措施，结果现在一些程序中已被锁在系统中了。”第五章死锁与饥饿一个进程需要使用独占型资源必须有一定的次序3死锁产生的原因和必要条件死锁现象死锁产生的原因和必要条件死锁现象45.1死锁产生的原因1、进程推进顺序不当产生死锁。设系统有打印机、读卡机各一台，它们被进程P和Q共享。两个进程并发执行，它们按下列次序请求和释放资源：进程P进程Q请求读卡机请求打印机请求打印机请求读卡机释放读卡机释放读卡机释放打印机释放打印机5.1死锁产生的原因1、进程推进顺序不当产生死锁。5例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操作使用不当产生死锁例2：R1和R2为可再用资源;进程Q1和Q2共享两个资源R65.1死锁产生的原因3、同类资源分配不当引起死锁若系统中有m个资源被n个进程共享，当每个进程都要求k个资源。而m<n*k时，即资源数小于进程所需要的总数时，如果分配不得当就可能引起死锁。例3，m=5,n=5,k=2，采用的分配策略是为每个进程轮流分配。5.1死锁产生的原因3、同类资源分配不当引起死锁75.1死锁产生的原因4、进程通讯引起死锁在进程通讯时使用的信件可以看作是一种临时性资源，如果对信件的发送和接收不加限制的话，则可能引起死锁例4：进程p1等待进程p3的信件s3来到后再向进程p2发送信件s1；p2又要等待p1信件来到后再向p3发送信件s2；而p3也要等待p2的信件s2来到后才能发出信件s35.1死锁产生的原因4、进程通讯引起死锁85.2死锁定义一组进程中的每一个进程，均无限期地等待此组进程中某个其他进程占有的，因而永远无法得到的资源，这种现象称为进程死锁。几个有用的结论：参与死琐的进程至少有二个；每个参与死锁的进程均等待资源；参与死锁的进程中至少有两个进程占有资源；死锁进程是系统中当前进程集合的一个子集。5.2死锁定义一组进程中的每一个进程，均无限期地等待此组进95.3死锁的条件Coffman条件（必要条件）资源独占（mutualexclusion）又称为互斥条件，一个资源在同一时刻只能分配给一个进程。任一时刻一个资源仅为一个进程独占，若另一个进程请求一个已被占用的资源时，它被置成等待状态，直到占用者释放资源。不可剥夺（nonpreemption）任一进程不能从另一进程那里抢夺资源，即已被占用的资源，只能由占用进程自己来释放。5.3死锁的条件Coffman条件（必要条件）10保持申请（hold-while-applying）又叫占有和等待条件，一个进程请求资源得不到满足而等待时，不释放已占有的资源。循环等待（circularwait）又叫环路等待条件，存在一个循环等待链，其中，每一个进程分别等待它前一个进程所持有的资源，造成永远等待。破坏上述任意一个条件可以消除死锁。保持申请（hold-while-applying）115.4死锁的处理死锁预防（deadlockprevention）-静态通过设置某些限制条件，去破坏产生死锁的4个必要条件中的一个或几个条件，来防止死锁发生。死锁避免（deadlockavoidance）--动态不需事先采取各种限制措施去破坏产生死锁的必要条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。5.4死锁的处理死锁预防（deadlockprevent125.4死锁的处理死锁检测（deadlockdetection）这种方法预先并不采取任何限制措施，也不检查系统是否已经进入不安全区，此法允许系统在运行过程中发生死锁。但可通过系统设置的检测机构，及时地检测出死锁的发生，并精确的确定与死锁有关的进程和资源；然后采取适当的措施，从系统中将已发生的死锁清除掉。死锁恢复（deadlockrecovery）这是与检测死锁相配套的一种措施，用于将进程从死锁状态下解脱出来，常用的实施方法是撤销或挂起一些进程，以便收回一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态以继续运行。5.4死锁的处理死锁检测（deadlockdetecti135.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资源分配图定义:G=(V,E),V=PR,P145.5资源分配图申请：pi申请rj中的一个资源实例，由pi向rj画一申请边，如可满足，改为分配边。释放：去掉分配边。5.5资源分配图申请：pi申请rj中的一个资源实例，由pi15例子（无环路，无死锁）例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例子（无环路，无死锁）例1.P={p1,p2,p3},R16例子（有环路，有死锁）p1p2p3r1r3r2r4增加边（p3,r2)例子（有环路，有死锁）p1p2p3r1r3r2r4增加边（p17例子（有环路，无死锁）p1p2p3p4r1r2例子（有环路，无死锁）p1p2p3p4r1r218“死锁检测”程序如果资源分配图中无环路，则此时系统没有发生死锁如果资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程如果资源分配图中有环路，且涉及的资源类中有多个资源，则环路的存在只是产生死锁的必要条件，未必系统一定就会发生死锁。看资源分配图能否化简。“死锁检测”程序如果资源分配图中无环路，则此时系统没有发生死195.5.2资源分配图的约简可以通过对资源分配图的约简，来判断系统是否处于死锁状态．资源分配图中的约简方法如下：(1)寻找一个非孤立且没有请求边的进程结点pi,若无算法结束；(2)去除所有pi的分配边使pi成为一个孤立结点；(3)寻找所有请求边均可满足的进程pj,将pj的请求边全部改为分配边；(4)转步骤(1)．若算法结束时，所有结点均为孤点，则称资源分配图是可以完全约简的，否则称为不可完全约简的．文献已经证明，系统处于死锁状态的充分必要条件是资源分配图不可完全约简．这一结论称为死锁定理．定理：S为死锁状态的充分必要条件是S的资源分配图不可完全约简。5.5.2资源分配图的约简可以通过对资源分配图的约简，来判20判断下列资源分配图所标示的状态是否为死锁p1p2p3判断下列资源分配图所标示的状态是否为死锁p1p2p321化简下面的资源分配图，并利用死锁定理给出相应的结论p2p1化简下面的资源分配图，并利用死锁定理给出相应的结论p2p1225.6死锁预防

对进程有关资源的活动加限制，所有进程遵循这种限制，即可保证没有死锁发生。优点：简单，系统不需要做什么。缺点：对进程的约束，违反约束仍可能死锁。预防方法：预先分配法；有序分配法。5.6死锁预防对进程有关资源的活动加限制，235.6.1预先分配法进程：运行前申请所需全部资源；系统：能够满足，全部分配，否则，一个也不分配。破坏“hold-and-wait”条件缺点：资源利用效率低；一次提出申请困难。5.6.1预先分配法进程：运行前申请所需全部资源；245.6.2有序分配法在这种方法中规定，系统将所有的资源按其类型进行线性排队，并赋予不同的序号。所有进程对资源的请求必须严格按资源序号递增的次序提出，这样，在所形成的资源分配图中，不可能再出现环路，因而摒弃了“循环等待”条件。5.6.2有序分配法在这种方法中规定，系统将所有的资源按其255.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......申请次序5.6.2有序分配法资源集：R={r1,r2,…,rn}进265.6.2有序分配法证明无死锁（deadlockfree)：反证，假定死锁时刻t1:p1无限等待rk1中的资源实例，被p2占有；t2:p2无限等待rk2中的资源实例，被p3占有；…tn:pn无限等待rkn中的资源实例，被p1占有;根据有序申请假设：F(rk1)<F(rk2)<…<F(rkn)<F(rk1)矛盾。5.6.2有序分配法证明无死锁（deadlockfree275.7死锁避免死锁避免定义:在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。预防死锁的几种策略，会严重地损害了系统性能。因此要施加较弱的限制，从而获得较满意的系统性能来避免死锁。由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。安全性检查5.7死锁避免死锁避免定义:在系统运行过程中，对进程发出的285.7死锁避免检测可满足请求分配不分配安全不安全定义：说系统处于安全状态,如果存在一个由系统中所有进程构成的安全进程序列<p1,p2,…,pn>；说一个进程序列<p1,p2,…,pn>是安全的,如果对于每一个进程pi(1≤i≤n),它以后尚需要的资源数量不超过系统当前剩余资源数量与所有进程pj(j<i)当前占有资源数量之和.5.7死锁避免检测可满足请求分配不分配安全不安295.7死锁避免例：设系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。设在T0时刻，进程P1、P2和P3分别获得5台、2台和2台，尚有3台空闲未分，如下表所示：进程最大需求已分配可用P1P2P3104952235.7死锁避免例：设系统中有三个进程P1、P2和P3，共有30由安全状态向不安全状态的转换如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。因为，此时也无法再找到一个安全序列，例如，把其余的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。由安全状态向不安全状态的转换31安全状态与不安全状态不安全状态:不存在一个安全序列。不安全状态一定导致死锁？安全状态与不安全状态不安全状态:不存在一个安全序列。不安32利用银行家算法避免死锁

当一个进程提出资源请求时，银行家算法要做的工作其要点是：①判断有无实施资源分配的可能。如果系统有能力，则实施预分配。②预分配。③判断分配后系统是否安全，若安全，则真正实施分配。资源分配表安全性检查表利用银行家算法避免死锁

当一个进程提出资源请求时，银行家算法33银行家算法(Cont.)Banker’salgorithm,E.W.Dijkstra.进程：事先申明所需资源最大量（并不分配）系统：对每个可满足的资源申请命令进行安全性检查。资源分配的安全性是指要保证至少有一个进程能够运行到结束，并且通过回收该进程所占用的资源再分配能依次使其他进程运行结束，然后继续回收资源、继续分配等，直到全部进程运行结束。如果计算出的资源分配是不安全的，系统将拒绝分配。银行家算法(Cont.)Banker’salgorithm34银行家算法(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.)数据结构：35银行家算法(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]ofinteger;Finish:array[1..n]ofboolean银行家算法(Cont.)Need:array[1..n,136

假设某一时刻，进程Pi提出了资源请求Request[j]，银行家算法的操作过程可用以下各步表示：

(1)如果Request［j］≤Need［i,j］，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。(2)如果Request［j］≤Available［j］，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。算法5-1：银行家算法---资源分配算法假设某一时刻，进程Pi提出了资源请求Reque37

(3)系统对进程Pi实施资源的预分配

Available［j］=Available［j］-Requesti［j］;

Allocation［i,j］=Allocation［i,j］+Requesti［j］;

Need［i,j］=Need［i,j］-Requesti［j］;(4)通过调用安全性算法判断此次分配是否要真正实施。调用安全性算法，根据返回值判断此次分配的真正实施是否安全。如果安全，则真正实施分配；如果不安全，则取消预分配。算法5-1：银行家算法---资源分配算法(3)系统对进程Pi实施资源的预分配算法5-1：银行家38资源分配Pi请求资源Request[I]Need[I]请求超量，错返Request[I]Available不满足，等待Available:=Available-Request[I]Allocation[I]:=Allocation[I]+Request[I]Need[I]:=Need[I]-Request[I]安全确认，pi继续Available:=Available+Request[I]Allocation[I]:=Allocation[I]-Request[I]Need[I]:=Need[I]+Request[I]pi等待FTFTTF资源分配Pi请求资源Request[I]Need[I]请求39

(1)设置两个向量：①工作向量Work用于记录当前可用的每类资源的数目在执行安全算法开始时，Work∶=Available;②Finish:用于记录进程P1，P2，……，Pn是否可运行完成。比如，Finish[i]=true，表示进程Pi可运行完成；Finish[i]=false，表示进程Pi不能运行完成开始时先做Finish［i］=false;当有足够资源分配给进程时，再令Finish［i］=true。算法5-2：银行家算法安全性检查算法(1)设置两个向量：算法5-2：银行家算法安全性检查算40算法5-2：银行家算法安全性检查算法安全性算法按以下各步操作寻找进程的安全序列1.Work=Available；Finish=false；2.寻找满足如下条件的i:(1)Finish[i]==false；(2)Need[i]≤Work[i]；如果不存在,则转步骤4；3.Work=Work+Allocation[i]；Finish[i]=true；转步骤24.如果对于所有i,Finish[i]=true,则系统处于安全状态,否则处于不安全状态.算法5-2：银行家算法安全性检查算法安全性算法按以下各步操41安全性检测算法FWork:=Available;Finish:=false;有满足条件的j:Finish[j]=falseNeed[j]WorkFinish[j]=true;Work:=Work+Allocation[j]Tj,finish[j]=trueTF安全不安全安全性检测算法FWork:=Available;有满足条件的42银行家算法例子R={A(10),B(5),C(7)}P={p0,p1,p2,p3,p4}Max

Allocation

Need

Available

Work

FinishABCABCABCABCABC753010743332322200122902302600222211011433002431P0:p1:p2:p3:p4:安全进程序列：<p1,p3,p4,p2,p0>p1请求：Request[1]=(1,0,2)银行家算法例子R={A(10),B(5),C(7)}Ma43

(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向量④再利用安全性算法检查此时系统是否安全。(2)P1请求资源：P1发出请求向量Requ44银行家算法例子Max

Allocation

Need

Available

Work

FinishABCABCABCABCABC753010743230322302020902302600222211011433002431P0:p1:p2:p3:p4:假定分配：安全进程序列：<p1,p3,p4,p0,p2>p4请求：Request[4]=(3,3,0),能否满足？p0请求：Request[0]=(0,2,0),能否满足？银行家算法例子MaxAllocation45(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分配资源，并修改有关数据(3)p4请求资源：p4发出请求向量Request(3，46银行家算法的保守性例子：R={A,B},申请a,b;释放a,bP={p1,p2},p1:abab;p2:bbbaab

Max

Allocation

Need

Available

Work

FinishABABABABABp1：11001111p2：110011Request[1]=(1,0),安全，分配。银行家算法的保守性例子：R={A,B},申请a,b;释47银行家算法的保守性Request[2]=(0,1),不安全，不分配，（分配不导致死锁）

Claim

Allocation

Need

Available

Work

FinishABABABABABp1：11100101p2：110011分配后：银行家算法的保守性Request[2]=(0,1),不安全48练习：某系统中有10台打印机，有三个进程P1、P2、P3分别需要8台、7台和4台。若P1、P2、P3已申请到4台、2台和2台。试问：按银行家算法能安全分配吗？请说明分配过程。练习：49例2：假定系统中有4个进程P1、P2、P3、P4和3类资源R1、R2、R3（资源数量分别为9、3、6），在t0时刻的资源分配情况如下表所示：资源情况claimallocationneedavailable进程R1R2R3R1R2R3R1R2R3R1R2R3P1322100222112P2613511102P3314211103P4422002420试问:(1)t0时刻系统是否安全？(2)P2发出请求向量request2(1,0,1),系统能否将资源分配给它？(3)在P2申请资源后，若P1发出请求向量request1(1,0,1),系统能否将资源分配给它？例2：假定系统中有4个进程P1、P2、P3、P4和3类资源R505.8死锁检测考虑因素：死锁发生频度；死锁影响进程。1.等待时检测：发现早，恢复代价小，开销大（overhead)。2.定时检测：3.资源（eg.CPU）利用率下降时检测。5.8死锁检测考虑因素：515.8.1死锁检测算法数据结构：Available:array[1..m]ofinteger;Allocation:array[1..n,1..m]ofinteger;Request:array[1..n,1..m]ofinteger;临时变量：Work:array[1..m]ofinteger;Finish:array[1..n]ofboolean;5.8.1死锁检测算法数据结构：525.8.1死锁检测算法Work:=Available;Finish:=false;有满足条件的i:Finish[i]=falseRequest[i]WorkFinish[i]=true;Work:=Work+Allocation[i]Ti,finish[i]=trueTFF无死锁死锁Finish[I]=trueforallocation[I]=05.8.1死锁检测算法Work:=Available;有满53Remarks1.上述算法可以检测到参与死锁的全部进程，包括占有资源和不占有资源的进程。2.如果希望只检测占有资源的进程，初始化时：Finish[i]=true,forAllocation[I]=0Remarks1.上述算法可以检测到参与死锁的全部进程，54死锁例子例子：R={A(7),B(2),C(6)};P={p0,p1,p2,p3,p4}

Allocation

Request

Available

Work

FinishABCABCABCABCp0:010000000p1:200202p2:303000p3:211100p4:002002未死锁。此时，Request[2]=(0,0,1),死锁，参与死锁进程{p1,p2,p3,p4}死锁例子例子：R={A(7),B(2),C(6)};P=555.9死锁的恢复1.重新启动

简单，代价大，涉及未参与死锁的进程。2.终止进程(processtermination)

通过终止参与死锁的进程并收回它们所占有的资源,死锁也能得以解除.这又有两种处理策略:一次性撤销所有参与死锁的全部进程,这种处理方法简单,但代价较高;(2)逐一撤销参与死锁的进程,即按照某种算法选择一个参与死锁的进程,将其撤销并收回其占有的全部资源,然后判断是否还存在死锁,如果是选择并且淘汰下一个将被淘汰的进程,如此重复直至死锁解除.5.9死锁的恢复1.重新启动565.9死锁的恢复3.剥夺资源(resourcepreemption)即剥夺死锁进程所占有的全部或部分资源.在实现时又可分为两种情形:(1)逐步剥夺:一次剥夺死锁进程所占有的一个或一组资源,如死锁尚未解除再继续剥夺,直至死锁解除为止.(2)一次剥夺:一次性地剥夺参与死锁进程所占有的全部资4.进程回退(rollback)所谓进程回退就是让参与死锁的进程回退到以前没有发生死锁的某个点处,并由此点开始继续,希望进程交叉执行时不再发生死锁.5.9死锁的恢复3.剥夺资源(resourcepre575.12饥饿与饿死定义：当等待时间给进程推进和响应带来明显影响时，称发生了进程饥饿(starvation)，当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被饿死(starvetodeath).饥饿：没有时间上界的等待排队等待忙式等待饿死：等待时间超过极限(deadline)饿死vs死锁死锁进程处于等待状态，饿死不然死锁可以检测，饿死不然5.12饥饿与饿死定义：当等待时间给进程推进和响应带来明显58饿死与死锁饿死与死锁有一定联系：二者都是由于竞争资源而引起的，但又有明显差别，主要表现在如下几个方面：(1)从进程状态考虑，死锁进程都处于等待状态，忙式等待(处于运行或就绪状态)的进程并非处于等待状态，但却可能被饿死.(2)死锁进程等待永远不会被释放的资源，饿死进程等待会被释放但却不会分配给自己的资源，其等待时限没有上界(排队等待或忙式等待).(3)死锁一定发生了循环等待，而饿死则不然.这也表明通过资源分配图可以检测死锁存在与否，但却不能检测是否有进程饿死.(4)死锁一定涉及多个进程，而饥饿或被饿死的进程可能只有一个．饿死与死锁饿死与死锁有一定联系：二者都是由于竞争资源而引起的595.13死锁的例子过河问题：水流12n-1n…WestEastW-EE-WDeadlockprevention:onedirectionatanytime.5.13死锁的例子过河问题：水12n-1n…WestEa60过河问题Varwest_crossing,east_crossing:integer;(0,0)west_wait,east_wait:integer;(0,0);wq,eq:semaphore;mutex:semaphore;西面过河者活动：P(mutex);Ifeast_crossing>0ThenBeginwest_wait:=west_wait+1;V(mutex);P(wq)End;ElseBeginwest_crossing:=west_crossing+1;过河问题Varwest_crossing,east_cro61V(mutex)End;过河；P(mutex);west_crossing:=west_crossing-1;Ifwest_crossing=0ThenWhileeast_wait>0DoBegineast_wait:=east_wait-1;east_crossing:=east_crossing+1;V(eq);End;V(mutex);过河问题V(mutex)过62过河问题东面过河者活动：P(mutex);Ifwest_crossing>0ThenBegineast_wait:=east_wait+1;V(mutex);P(eq)EndElseBegineast_crossing:=east_crossing+1;V(mutex)End;过河问题东面过河者活动：63过河问题过河；P(mutex);east_crossing:=east_crossing-1;Ifeast_crossing=0ThenWhilewest_wait>0DoBeginwest_wait:=west_wait-1;west_crossing:=west_crossing+1;V(wq);End;V(mutex);过河问题过河；64思考问题对于过河问题，考虑一个没有饿死情况的解法。思考问题对于过河问题，考虑一个没有饿死情况的解法。65例2.过河问题(2)水流WestEast124387561-2-5-6-4-34-3-7-8-2-1要求:(1)无死锁;(2)无饿死;(3)并行度高。例2.过河问题(2)水WestEast12438756166WE: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);VarS,s1,s2,s3,s4,s5,s6,s7,s8:semaphore;(5,1,1,1,1,1,1,1,1)WE:EW:V(s5);V(s7);VarS,s1,67死锁综合处理

各种处理死锁的方法都有局限性，无论哪种方法都无法适用于各类资源。1973年，Howard提出了死锁综合处理的建议。其思想是：把系统中的全部资源分成几大类，整体上采用资源顺序分配法，在对每类资源根据其特点选择最适合的方法。例如将系统资源分成以下4类：（1）内部资源（系统所用的资源，如PCB表、页表等）。（2）主存。（3）作业资源（如行打印机、磁带驱动器、文件等）。（4）辅存。按编号递增次序申请资源。对第（1）、（4）两类资源采用预分配法；对第（2）类采用剥夺法；对第（3）类采用死锁避免法。而对那些哪种方法也不适合的资源，可用死锁检测程序定期对系统进行检测，发现死锁后再排除死锁。死锁综合处理各种处理死锁的方法都有局限性，无论哪种方68练习1：某系统有ABCD这4类资源供5个进程共享，进程对资源的需求和分配情况如下表所示。现在系统还剩资源A类1个，B类5个，C类2个和D类0个，请按银行家算法回答下面问题：进程已占资源数最大需求数ABCDABCDP100120012P210001750P313542356P406320652P5001406561、现在系统是否处于安全状态？2、如果现在进程P2提出需要（0，4，2，0）个资源的要求，系统能否满足它的请求？练习1：某系统有ABCD这4类资源供5个进程共享，进程对资源69第五章死锁与饥饿死锁的概念死锁的条件死锁的处理资源分配图死锁的预防死锁的避免死锁的发现死锁的恢复饥饿与活锁第五章死锁与饥饿死锁的概念死锁的避免70[学习目标]1.掌握死锁的定义,死锁的条件，死锁的处理以及处理死锁的算法——银行家算法。2.理解资源分配图。[学习要点]本章的重点在于掌握死锁的处理方法，会用银行家算法计算是否发生死锁。[学习目标]71第五章死锁与饥饿一个进程需要使用独占型资源必须有一定的次序：申请资源使用资源释放资源1968年Havender在评论OS/360操作系统时说：“原先多任务的概念是让多个任务不加限制的竞争资源，……但是随着系统的发展，很多任务被锁在系统中了。”1971年Lynch说：“1962年我们设计Exec2系统时并没有认识到死锁的问题，系统中也没有任何防范措施，结果现在一些程序中已被锁在系统中了。”第五章死锁与饥饿一个进程需要使用独占型资源必须有一定的次序72死锁产生的原因和必要条件死锁现象死锁产生的原因和必要条件死锁现象735.1死锁产生的原因1、进程推进顺序不当产生死锁。设系统有打印机、读卡机各一台，它们被进程P和Q共享。两个进程并发执行，它们按下列次序请求和释放资源：进程P进程Q请求读卡机请求打印机请求打印机请求读卡机释放读卡机释放读卡机释放打印机释放打印机5.1死锁产生的原因1、进程推进顺序不当产生死锁。74例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操作使用不当产生死锁例2：R1和R2为可再用资源;进程Q1和Q2共享两个资源R755.1死锁产生的原因3、同类资源分配不当引起死锁若系统中有m个资源被n个进程共享，当每个进程都要求k个资源。而m<n*k时，即资源数小于进程所需要的总数时，如果分配不得当就可能引起死锁。例3，m=5,n=5,k=2，采用的分配策略是为每个进程轮流分配。5.1死锁产生的原因3、同类资源分配不当引起死锁765.1死锁产生的原因4、进程通讯引起死锁在进程通讯时使用的信件可以看作是一种临时性资源，如果对信件的发送和接收不加限制的话，则可能引起死锁例4：进程p1等待进程p3的信件s3来到后再向进程p2发送信件s1；p2又要等待p1信件来到后再向p3发送信件s2；而p3也要等待p2的信件s2来到后才能发出信件s35.1死锁产生的原因4、进程通讯引起死锁775.2死锁定义一组进程中的每一个进程，均无限期地等待此组进程中某个其他进程占有的，因而永远无法得到的资源，这种现象称为进程死锁。几个有用的结论：参与死琐的进程至少有二个；每个参与死锁的进程均等待资源；参与死锁的进程中至少有两个进程占有资源；死锁进程是系统中当前进程集合的一个子集。5.2死锁定义一组进程中的每一个进程，均无限期地等待此组进785.3死锁的条件Coffman条件（必要条件）资源独占（mutualexclusion）又称为互斥条件，一个资源在同一时刻只能分配给一个进程。任一时刻一个资源仅为一个进程独占，若另一个进程请求一个已被占用的资源时，它被置成等待状态，直到占用者释放资源。不可剥夺（nonpreemption）任一进程不能从另一进程那里抢夺资源，即已被占用的资源，只能由占用进程自己来释放。5.3死锁的条件Coffman条件（必要条件）79保持申请（hold-while-applying）又叫占有和等待条件，一个进程请求资源得不到满足而等待时，不释放已占有的资源。循环等待（circularwait）又叫环路等待条件，存在一个循环等待链，其中，每一个进程分别等待它前一个进程所持有的资源，造成永远等待。破坏上述任意一个条件可以消除死锁。保持申请（hold-while-applying）805.4死锁的处理死锁预防（deadlockprevention）-静态通过设置某些限制条件，去破坏产生死锁的4个必要条件中的一个或几个条件，来防止死锁发生。死锁避免（deadlockavoidance）--动态不需事先采取各种限制措施去破坏产生死锁的必要条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。5.4死锁的处理死锁预防（deadlockprevent815.4死锁的处理死锁检测（deadlockdetection）这种方法预先并不采取任何限制措施，也不检查系统是否已经进入不安全区，此法允许系统在运行过程中发生死锁。但可通过系统设置的检测机构，及时地检测出死锁的发生，并精确的确定与死锁有关的进程和资源；然后采取适当的措施，从系统中将已发生的死锁清除掉。死锁恢复（deadlockrecovery）这是与检测死锁相配套的一种措施，用于将进程从死锁状态下解脱出来，常用的实施方法是撤销或挂起一些进程，以便收回一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态以继续运行。5.4死锁的处理死锁检测（deadlockdetecti825.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资源分配图定义:G=(V,E),V=PR,P835.5资源分配图申请：pi申请rj中的一个资源实例，由pi向rj画一申请边，如可满足，改为分配边。释放：去掉分配边。5.5资源分配图申请：pi申请rj中的一个资源实例，由pi84例子（无环路，无死锁）例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例子（无环路，无死锁）例1.P={p1,p2,p3},R85例子（有环路，有死锁）p1p2p3r1r3r2r4增加边（p3,r2)例子（有环路，有死锁）p1p2p3r1r3r2r4增加边（p86例子（有环路，无死锁）p1p2p3p4r1r2例子（有环路，无死锁）p1p2p3p4r1r287“死锁检测”程序如果资源分配图中无环路，则此时系统没有发生死锁如果资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程如果资源分配图中有环路，且涉及的资源类中有多个资源，则环路的存在只是产生死锁的必要条件，未必系统一定就会发生死锁。看资源分配图能否化简。“死锁检测”程序如果资源分配图中无环路，则此时系统没有发生死885.5.2资源分配图的约简可以通过对资源分配图的约简，来判断系统是否处于死锁状态．资源分配图中的约简方法如下：(1)寻找一个非孤立且没有请求边的进程结点pi,若无算法结束；(2)去除所有pi的分配边使pi成为一个孤立结点；(3)寻找所有请求边均可满足的进程pj,将pj的请求边全部改为分配边；(4)转步骤(1)．若算法结束时，所有结点均为孤点，则称资源分配图是可以完全约简的，否则称为不可完全约简的．文献已经证明，系统处于死锁状态的充分必要条件是资源分配图不可完全约简．这一结论称为死锁定理．定理：S为死锁状态的充分必要条件是S的资源分配图不可完全约简。5.5.2资源分配图的约简可以通过对资源分配图的约简，来判89判断下列资源分配图所标示的状态是否为死锁p1p2p3判断下列资源分配图所标示的状态是否为死锁p1p2p390化简下面的资源分配图，并利用死锁定理给出相应的结论p2p1化简下面的资源分配图，并利用死锁定理给出相应的结论p2p1915.6死锁预防

对进程有关资源的活动加限制，所有进程遵循这种限制，即可保证没有死锁发生。优点：简单，系统不需要做什么。缺点：对进程的约束，违反约束仍可能死锁。预防方法：预先分配法；有序分配法。5.6死锁预防对进程有关资源的活动加限制，925.6.1预先分配法进程：运行前申请所需全部资源；系统：能够满足，全部分配，否则，一个也不分配。破坏“hold-and-wait”条件缺点：资源利用效率低；一次提出申请困难。5.6.1预先分配法进程：运行前申请所需全部资源；935.6.2有序分配法在这种方法中规定，系统将所有的资源按其类型进行线性排队，并赋予不同的序号。所有进程对资源的请求必须严格按资源序号递增的次序提出，这样，在所形成的资源分配图中，不可能再出现环路，因而摒弃了“循环等待”条件。5.6.2有序分配法在这种方法中规定，系统将所有的资源按其945.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......申请次序5.6.2有序分配法资源集：R={r1,r2,…,rn}进955.6.2有序分配法证明无死锁（deadlockfree)：反证，假定死锁时刻t1:p1无限等待rk1中的资源实例，被p2占有；t2:p2无限等待rk2中的资源实例，被p3占有；…tn:pn无限等待rkn中的资源实例，被p1占有;根据有序申请假设：F(rk1)<F(rk2)<…<F(rkn)<F(rk1)矛盾。5.6.2有序分配法证明无死锁（deadlockfree965.7死锁避免死锁避免定义:在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。预防死锁的几种策略，会严重地损害了系统性能。因此要施加较弱的限制，从而获得较满意的系统性能来避免死锁。由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。安全性检查5.7死锁避免死锁避免定义:在系统运行过程中，对进程发出的975.7死锁避免检测可满足请求分配不分配安全不安全定义：说系统处于安全状态,如果存在一个由系统中所有进程构成的安全进程序列<p1,p2,…,pn>；说一个进程序列<p1,p2,…,pn>是安全的,如果对于每一个进程pi(1≤i≤n),它以后尚需要的资源数量不超过系统当前剩余资源数量与所有进程pj(j<i)当前占有资源数量之和.5.7死锁避免检测可满足请求分配不分配安全不安985.7死锁避免例：设系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。设在T0时刻，进程P1、P2和P3分别获得5台、2台和2台，尚有3台空闲未分，如下表所示：进程最大需求已分配可用P1P2P3104952235.7死锁避免例：设系统中有三个进程P1、P2和P3，共有99由安全状态向不安全状态的转换如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。因为，此时也无法再找到一个安全序列，例如，把其余的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。由安全状态向不安全状态的转换100安全状态与不安全状态不安全状态:不存在一个安全序列。不安全状态一定导致死锁？安全状态与不安全状态不安全状态:不存在一个安全序列。不安101利用银行家算法避免死锁

当一个进程提出资源请求时，银行家算法要做的工作其要点是：①判断有无实施资源分配的可能。如果系统有能力，则实施预分配。②预分配。③判断分配后系统是否安全，若安全，则真正实施分配。资源分配表安全性检查表利用银行家算法避免死锁

当一个进程提出资源请求时，银行家算法102银行家算法(Cont.)Banker’salgorithm,E.W.Dijkstra.进程：事先申明所需资源最大量（并不分配）系统：对每个可满足的资源申请命令进行安全性检查。资源分配的安全性是指要保证至少有一个进程能够运行到结束，并且通过回收该进程所占用的资源再分配能依次使其他进程运行结束，然后继续回收资源、继续分配等，直到全部进程运行结束。如果计算出的资源分配是不安全的，系统将拒绝分配。银行家算法(Cont.)Banker’salgorithm103银行家算法(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.)数据结构：104银行家算法(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]ofinteger;Finish:array[1..n]ofboolean银行家算法(Cont.)Need:array[1..n,1105

假设某一时刻，进程Pi提出了资源请求Request[j]，银行家算法的操作过程可用以下各步表示：

(1)如果Request［j］≤Need［i,j］，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。(2)如果Request［j］≤Available［j］，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。算法5-1：银行家算法---资源分配算法假设某一时刻，进程Pi提出了资源请求Reque106

(3)系统对进程Pi实施资源的预分配

Available［j］=Available［j］-Requesti［j］;

Allocation［i,j］=Allocation［i,j］+Requesti［j］;

Need［i,j］=Need［i,j］-Requesti［j］;(4)通过调用安全性算法判断此次分配是否要真正实施。调用安全性算法，根据返回值判断此次分配的真正实施是否安全。如果安全，则真正实施分配；如果不安全，则取消预分配。算法5-1：银行家算法---资源分配算法(3)系统对进程Pi实施资源的预分配算法5-1：银行家107资源分配Pi请求资源Request[I]Need[I]请求超量，错返Request[I]Available不满足，等待Available:=Available-Request[I]Allocation[I]:=Allocation[I]+Request[I]Need[I]:=Need[I]-Request[I]安全确认，pi继续Available:=Available+Request[I]Allocation[I]:=Allocation[I]-Request[I]Need[I]:=Need[I]+Request[I]pi等待FTFTTF资源分配Pi请求资源Request[I]Need[I]请求108

(1)设置两个向量：①工作向量Work用于记录当前可用的每类资源的数目在执行安全算法开始时，Work∶=Available;②Finish:用于记录进程P1，P2，……，Pn是否可运行完成。比如，Finish[i]=true，表示进程Pi可运行完成；Finish[i]=false，表示进程Pi不能运行完成开始时先做Finish［i］=false;当有足够资源分配给进程时，再令Finish［i］=true。算法5-2：银行家算法安全性检查算法(1)设置两个向量：算法5-2：银行家算法安全性检查算109算法5-2：银行家算法安全性检查算法安全性算法按以下各步操作寻找进程的安全序列1.Work=Available；Finish=false；2.寻找满足如下条件的i:(1)Finish[i]==false；(2)Need[i]≤Work[i]；如果不存在,则转步骤4；3.Work=Work+Allocation[i]；Finish[i]=true；转步骤24.如果对于所有i,Finish[i]=true,则系统处于安全状态,否则处于不安全状态.算法5-2：银行家算法安全性检查算法安全性算法按以下各步操110安全性检测算法FWork:=Available;Finish:=false;有满足条件的j:Finish[j]=falseNeed[j]WorkFinish[j]=true;Work:=Work+Allocation[j]Tj,finish[j]=trueTF安全不安全安全性检测算法FWork:=Available;有满足条件的111银行家算法例子R={A(10),B(5),C(7)}P={p0,p1,p2,p3,p4}Max

Allocation

Need

Available

Work

FinishABCABCABCABCABC753010743332322200122902302600222211011433002431P0:p1:p2:p3:p4:安全进程序列：<p1,p3,p4,p2,p0>p1请求：Request[1]=(1,0,2)银行家算法例子R={A(10),B(5),C(7)}Ma112

(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向量④再利用安全性算法检查此时系统是否安全。(2)P1请求资源：P1发出请求向量Requ113银行家算法例子Max

Allocation

Need

Available

Work

FinishABCABCABCABCABC753010743230322302020902302600222211011433002431P0:p1:p2:p3:p4:假定分配：安全进程序列：<p1,p3,p4,p0,p2>p4请求：Request[4]=(3,3,0),能否满足？p0请求：Request[0]=(0,2,0),能否满足？银行家算法例子MaxAllocation114(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