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

第五章死锁与饥饿死锁(deadlock)是程序并发带来的另一重要问题，也是操作系统及并发程序设计中最难处理的问题。5.1死锁的概念例设r1和r2为可再用资源;P1:…申请r1;…申请r2;…释放r2;…释放r1;P2:…申请r2;…申请r1;…释放r1;…释放r2;12这种由于进程竞争资源而引起的僵持称为死锁。死锁：一组进程中的每个进程均等待此组进程中某一其它进程占有的、因而永远无法得到的资源,这种现象称进程死锁。死锁发生后,参与死锁的进程将一直等待下去,除非有外来干预。关于死锁的几个有用结论：(1)参与死锁的进程数至少为二；(2)参与死锁的所有进程均等待资源；(3)参与死锁的进程至少有两个占有资源；(4)参与死锁的进程是系统中当前正在运行进程集合的一个子集。5.2死锁类型1.资源竞争引起的死锁由于进程争夺系统中有限资源引起的死锁称为资源竞争引起的死锁。以后如未特别指明，均假定死锁是由于进程竞争资源引起的。2.进程通讯引起的死锁P1:receive(P2,M1);P2:receive(P3,M2);P3:receive(P1,M3);3.其它原因引起的死锁例假设有一扇一次只能通过一个人的小门,有两位先生M1和M2都要通过此门。此时,门相当于一个独占型资源。若他们都在门口处对对方说“您先过”,则二者均无法通过,造成僵持。上例也称“AfterYou/AfterYou”问题5.3死锁的条件死锁发生的必要条件(Coffman条件)：(1)资源独占(mutualexclusion)，即一个资源在同一时刻只能分配给一个进程。如果进程申请某一资源,而该资源正被另一进程占用,则申请者需等待,直到占有者释放该资源。(2)不可剥夺(non-preemption)，即资源申请者不能从资源占有者手中抢夺资源。(3)保持申请(hold-while-applying)，即进程占有部分资源后还可申请新的资源,且申请新资源时并不释放已占有资源。(4)循环等待(circularwait)，即存在一个进程等待序列{p1,p2,…,pn},其中p1等待p2占用的某一资源,p2等待p3占用的某一资源,…,pn等待p1占用的某一资源。仅当四个条件同时满足死锁才会发生。注意：1.只要破坏一个条件,死锁就不会发生.2.每类资源只有一个时,为充要条件.5.4死锁的处理处理死锁的策略可分为两大类:一类不让死锁发生；另一类允许死锁发生,但当死锁发生时能将死锁检测出来并加以消除。不让死锁发生的策略又分为:死锁预防(prevention)：静态死锁避免(avoidance)：动态所谓静态是指对进程有关资源的活动按某种协议加以限制,若所有进程都遵守此协议,则可保证死锁不发生。所谓动态是指对进程有关资源的申请命令加以实时检测,拒绝不安全的资源申请命令，以保证死锁不发生。死锁所要研究的问题：静态死锁预防策略(deadlockprevention)动态死锁避免策略(deadlockavoidance)动态死锁检测策略(deadlockdetection)动态死锁恢复策略(deadlockrecovery)5.5资源分配图5.5.1资源分配图的定义：资源分配图是一个二元组G=(V,E),其中,V是结点集,V=P∪R,P={p1,p2,…,pn}为系统中所有进程的集合,R={r1,r2,…,rm}为系统中所有资源类的集合。E是边集，E={(pi,rj)}∪{(rj,pi)},piP,rjR。(pi,rj)表示pi申请rj中的一个资源,(rj,pi)表示rj中的一个资源被pi占用。(pi,rj)称为申请边，(rj,pi)称为分配边。资源分配图中进程:圆圈资源类:方框资源类中的子资源:圆点pi申请rj中的一个资源时,由pi向rj画一申请边，若可满足，则改为分配边。进程释放一个资源时,去掉相应的分配边。例1.设进程集P,资源类集R及边集E如下:P={p1,p2,p3}R={r1(1),r2(2),r3(1),r4(3)}E={(r1,p2),(r2,p2),(r2,p1),(r3,p3),(p1,r1),(p2,r3),(p2,r4),(r4,p3)}资源分配图如下：p1p2p3r1r3r2r4p1占有r2中的一个实例，申请r1中的一个实例；p2占有r1和r2中各一个实例，申请r3中的一个实例；p3占有r3和r4中各一个实例。资源分配图中无环路，故不存在死锁。例2.假设例1中p3申请r2中的一个实例。由于无空闲资源,故增加一申请边(p3,r2).此时出现了两个环路:p1r1p2r3p3r2p1p2r3p3r2p2p1p2p3r1r3r2r4有环路,有死锁,且p1,p2,p3都参与了死锁。例3.图中有一个环路，但无死锁。p1p2p3p4r1r2图中p2可能会释放r1中的一个资源,该资源可分配给p3,环路断开。结论：(1)若资源分配图中不存在环路,则系统中不存在死锁;(2)若资源分配图中存在环路,则系统中可能存在死锁,也可能不存在死锁。(3)若每个资源类均只有一个资源，则环路的存在意味着死锁的存在；若每个资源类含多个资源，则环路的存在不一定意味着死锁的存在。5.5.2资源分配图的约简可通过对资源分配图的约简来判断系统是否处于死锁状态.资源分配图中的约简方法：(1)寻找一个非孤立且没有请求边的进程结点pi,若无，则算法结束；(2)去除pi的所有分配边使pi成为一个孤立结点；(3)寻找所有请求边均可满足的进程pj,将pj的请求边全部改为分配边；(4)转步骤(1)。若算法结束时所有结点均为孤点，则称资源分配图是可完全约简的，否则称是不可完全约简的。已证明，系统处于死锁状态的充分必要条件是资源分配图不可完全约简。死锁定理：S为死锁状态的充分必要条件是S的资源分配图不可完全约简。5.6死锁预防死锁预防的基本思想：对于进程有关资源的申请命令规定某种协议,如果所有进程都遵守这一协议,则系统不会进入死锁状态。优点：简单，系统不需要做什么。缺点：违反对进程的约束仍可能死锁。常见的死锁预防策略有两种:预先分配策略有序分配策略5.6.1预先分配法进程：运行前申请所需全部资源；系统：若能满足，则全部分配，否则，一个也不分配。破坏“保持申请”条件缺点：(1)资源利用率低。(2)进程在运行前可能并不知道它所需的全部资源。5.6.2有序分配法资源类集合：R={r1,r2,…,rm}函数f:RN事先将所有资源类全排序,即赋予每一个资源类一个唯一的整数。例资源集R={driver,scanner,printer}函数f:f(driver)=1f(scanner)=5f(printer)=12有序分配法规定进程必须按照资源编号由小到大的次序申请资源。即进程不占用资源时可申请ri的多个资源，此后它申请rj中资源的充要条件是：f(ri)f(rj)；若进程需同一资源类中的若干资源,它必须一次申请。换言之,进程可申请某一资源类ri中资源的充要条件是它已释放了资源类rj中的所有资源,这里f(ri)f(rj)。结论：若所有进程申请资源时都遵守上述规定，则系统不会发生死锁。证明：(反证法)假定存在死锁(p1p2…pnp1)t1时刻:p1无限等待rk1中的资源,被p2占有；t2:p2无限等待rk2中的资源,被p3占有；…tn:pn无限等待rkn中的资源,被p1占有;根据有序申请规定,可推知：f(rk1)f(rk2)…f(rkn)f(rk1)矛盾DBACW:直行E:左转S:左转有序分配法举例：资源编号：F(D)=1;F(B)=2;F(A)=3;F(C)=4;死锁的可能性：情形1，情形2ProcedureSP(S1);驶入D；P(S2);驶入B;V(S1);P(S3);驶入A；V(S2);驶出A;V(S3)ProcedureEP(S2);驶入B；P(S3);驶入A;V(S2);P(S4);驶入C；V(S3);驶出C;V(S4);ProcedureWP(S1);P(S4);驶入C;驶入D；V(S4);驶出D；V(S1);VarS1,S2,S3,S4:semaphore;(1,1,1,1)COBEGINS1:S;…;Sm:S;E1:E;…;En:E;W1:W;...;Wp:WCOEND;5.7死锁避免检测可满足请求分配不分配安全不安全系统处于安全状态：存在安全进程序列p1,p2,…,pn进程序列p1,p2,…,pn安全，p1,p2,…,pn可依次进行完。安全不安全死锁银行家算法Banker’salgorithm,E.W.Dijkstra.进程：事先申明所需资源最大量（并不分配）系统：对每个可满足的资源申请命令进行安全性检查。P={p1,p2,…,pn};R={r1,r2,…,rm};数据结构：Available:array[1..m]ofinteger;//系统可用资源Claim:array[1..n,1..m]ofinteger;//进程最大需求Allocation:array[1..n,1..m]ofinteger;//当前分配Need:array[1..n,1..m]ofinteger;//尚需资源Request:array[1..n,1..m]ofinteger;//当前请求临时变量：Work:array[1..m]ofinteger;Finish:array[1..n]ofboolean;设X,Y为下标1..l的一维数组：XYj(1jl),X[j]Y[j]X:=Yj(1jl),X[j]:=Y[j]X:=cj(1jl),X[j]:=cX±Yj(1jl),X[j]±Y[j]资源分配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安全性检测算法FWork:=Available;Finish:=false;有满足条件的j:Finish[j]=falseNeed[j]WorkFinish[j]=true;Work:=Work+Allocation[j]Tj,finish[j]=trueTF安全不安全银行家算法例子R={A(10),B(5),C(7)}P={p0,p1,p2,p3,p4}ClaimAllocationNeedAvailableWorkFinishABCABCABCABCABC753010743332322200122902302600222211011433002431P0:p1:p2:p3:p4:安全进程序列：p1,p3,p4,p2,p0p1请求：Request[1]=(1,0,2)ClaimAllocationNeedAvailableWorkFinishABCABCABCABCABC753010743230322302020902302600222211011433002431P0:p1:p2:p3:p4:假定分配：安全进程序列：p1,p3,p4,p2,p0p4请求：Request[4]=(3,3,0),不能满足，等待；p0请求：Request[0]=(0,2,0),不安全，等待。银行家算法的保守性例子：R={A,B},申请a,b;释放a,bP={p1,p2},p1:abab;p2:bbbaabClaimAllocationNeedAvailableWorkFinishABABABABABp1：11001111p2：110011Request[1]=(1,0),安全，分配。Request[2]=(0,1),不安全，不分配，（分配不导致死锁）C