死锁的预防避免和检测

死锁问题,系统中有进程处于相互的无限等待状态（被阻塞）资源死锁和通信死锁等待图：将系统中进程对资源的占用与需求共享情况用有向图表示进程集合P0,P1,Pn为节点集，当且仅当进程Pi等待一个被进程Pj占用的资源时，边(Pi,Pj)存在于图中。,资源(resources)分类,根据资源性质：可剥夺资源(抢占)和不可剥夺资源可抢占资源：指资源占有进程虽然需要使用该资源，但另一个进程却强行把资源从占有者进程处抢来。不可抢占资源：指只有占用者进程不再需要使用该资源而主动释放资源外，其它进程不得在占有者进程使用资源过程中强行抢占。,可抢占资源如：CPU、主存、硬盘，该类资源可为多个进程共享（可抢占）不可抢占资源如：打印机、读卡机，磁带驱动器，该类资源可为某个进程独享（不可抢占）,资源分类,根据使用方式：共享资源和独享资源根据使用期限：永久资源和临时性资源永久资源是可顺序重复使用的资源临时性资源是由一个进程产生，被另外一个进程使用短暂时间之后便无用的资源。,产生死锁的原因,竞争资源。当系统中供多个进程所共享的资源，不足以同时满足它们的需要时，引起它们对资源的竞争而产生死锁。进程推进的顺序不当。进程在运行过程中，请求和释放资源的顺序不当，导致进程的死锁。,竞争资源,竞争非剥夺性资源竞争临时性资源,S1，S2，S3是临时资源P1:Release(S1);Request(S3)P2:Release(S2);Request(S1)P3:Release(S3);Request(S2)不可能发生死锁P1:Request(S3);Release(S1)P2:Request(S1);Release(S2)P3:Request(S2);Release(S3)可能发生死锁,死锁问题一实例：哲学家问题,哲学家,筷子,盘子,哲学家1号,哲学家5号,哲学家4号,哲学家2号,哲学家3号,1,5,3,2,4,未就餐时示意图,哲学家1号,哲学家4号,哲学家2号,哲学家3号,1,5,3,2,4,哲学家5号,先拿左,拿到后再拿右,成功后进餐.吃完后先放左再放右.虽可保证不会有相邻的同时进餐,但可能死锁,如动画所示.,此时没有一个哲学家可以完成进餐.,哲学家1号,哲学家4号,哲学家2号,哲学家3号,1,5,3,2,4,哲学家5号,此时5号哲学家被禁止拿筷子.1号哲学家拿起他右边即5号哲学家左边的筷子.,解决方法一:至多只允许四位哲学家同时去拿左边的筷子,1号哲学家开始进餐,完成后放下筷子,其它哲学家开始进餐,哲学家1号,哲学家4号,哲学家2号,哲学家3号,哲学家5号,解决方法二:仅当哲学家左右两边筷子都能用才允许拿筷子,设1号进餐,则3,4两位哲学家可以拿筷子,1号进餐完毕,放下筷子,先左后右.,1号放下左边筷子的同时,3号可拿起右边筷子,3号开始进餐,同时1号放下右边的筷子,此时4号条件不再满足,放下筷子.,此时5号条件满足,可在下一时钟周期拿左筷子,哲学家4号,哲学家1号,哲学家2号,哲学家3号,1,5,2,4,哲学家5号,解决方法三:奇数先拿左边,偶数先拿右边,这种方法将出现1,2号哲学家单键1号筷子,3,4号哲学家竞争3号筷子的情况.,而5号没有人与他竞争,得到左边的筷子,若4号在与3号的竞争中得到筷子,则与5号竞争4号筷子.,无论4号5号谁得到4号筷子,都有一个可以进餐,若4号在与3号的竞争中没有得到筷子,则5号得到4号筷子,进餐,死锁问题一条件,死锁发生的充要条件互斥：一个资源在同一时刻不能被共享；占有并等待：必然有一个进程占用了至少一个资源，同时在等待获得被其它进程占用的资源；不可剥夺：已占用的资源不能被剥夺循环等待：等待图中有一个回路死锁的形式AND条件：当进程获得所有所需的资源后才能继续执行OR条件：当进程至少获得一个所需的资源后才能继续执行P-out-of-Q：进程同时请求Q个资源但至少获得P个之后才能继续执行,处理死锁的策略死锁的避免,动态检查资源的分配情况，只有在结果状态是安全的情况下，才将资源分配给进程；在分布式系统中实现的开销较大银行家算法：至少总可以满足一个客户的要求银行共有资金800万：A的余额是600万，B的余额是400万，C的余额是500万；A要求一次提走300万，B要求一次提走200万，C要求一次提走100万，假设客户在存款后会立即重新全额存入。当以上提款要求被满足后，银行当前存款余额还剩200万。这时，A、B和C均要求提取剩余款，则服务次序BCA是安全的，其他的服务顺序或上述条件的违反都可能导致不安全的结果状态。,死锁避免的方法,死锁避免，即动态检查资源状态，以保证没有循环等待发生。在集中式系统中，银行家算法是死锁避免的一个经典算法。基于Petri网的死锁避免方法适合应用在分布式系统中。,基于Petri网的死锁避免方法步骤,1)给出描述特定系统的模型2)得到相应的Petri网的可达树3)由可达树确定死锁状态4)根据死锁状态，找到所有的临界状态和它们的抑制变迁。,Petri网描述的状态,安全状态：包括临界状态和非临界状态不安全状态：包括死锁状态和死锁边界状态临界状态：如果一个状态接近死锁状态但是仍可以到达其他不导致死锁的状态。非临界状态：如果在某个状态下总不会到达死锁状态，则称该状态为非临界状态。死锁状态：导致死锁的不安全状态称为死锁状态死锁边界状态：可能导致死锁的不安全状态称为死锁边界状态。,死锁的图论模型,可以用图模型来表示死锁，表示死锁的图模型有两种，一种是等待图，另一种是资源分配图。,在等待图中，节点代表进程，当且仅当进程Pi等待一个被进程Pj所占用的资源时，边(Pi,Pj)存在于等待图中，图中的边是有向的。资源分配图中的节点有两种：一种是进程节点，另一种是资源节点。每个边是一个有序对(Pi,Rj)或(Rj,Pi)，其中P代表进程，R代表一个资源类型。边(Pi,Rj)表示进程Pi请求类型为Rj的一个资源，并且正在等待这个资源，一个资源类型中可能有多个资源。边(Rj,Pi)表示类型为Rj的一个资源已经分配给进程Pi。由于等待图假定一个资源类型中只有一个资源，所以资源分配图是一个比等待图更加有力的工具。,死锁的图论模型,资源分配图实例：,死锁的图论模型,资源分配图到等待图的转化：(1)在资源分配图中找到一个未被处理的资源R。如果所有的资源都已经处理，转向步骤3。(2)从这个资源R的每个输入进程节点到每个输出进程节点之间加一条有向边。一个资源的输入进程节点是等待这个资源的进程节点，一个资源的输出进程节点是占有这个资源的进程节点。转向步骤1。(3)删除所有的资源节点以及相应的边。,死锁的图论模型,资源分配图到等待图的转化实例：,处理死锁的策略,可以使用PAID来概括死锁处理的各种方法：预防(Prevent)、避免(Avoid)、忽略(Ignore)和检测(Detect)。预防死锁。通过限制请求，保证四个死锁条件中至少有一个不能发生，从而预防死锁。避免死锁。如果资源分配会导致一个安全的结果状态，就将资源动态地分配给进程。如果至少有一个执行序列使所有的进程都能完成运行，那么这个状态就是安全的。忽略死锁。忽略死锁是UNIX常采用的一种方法，这种方法只是简单地忽略死锁问题。检测死锁和从死锁中恢复。允许死锁发生，然后发现并解除死锁。,分布式系统处理死锁的策略,基于死锁预防的策略基于死锁检测的策略分布式系统死锁的特点：由于信息散布在多台机器上，死锁难以检测和处理。,分布式系统预防死锁的方法,要求进程在开始执行前就已经获得了所有了所有需要的资源。所有资源都被唯一编号，进程必须按资源编号单调申请。进程具有优先级编号，优先级低的首先放弃资源。为了提高公平性，进程的优先级可以动态变化。,用预防策略解决哲学家问题,基于资源编号：所有哲学家均要先拿编号大的叉子，再拿编号小的叉子，在没有获得大编号的叉子前，即使编号小的叉子没有被占有，也不允许使用。基于进程编号：优先级高的哲学家可以等待优先级低的哲学家的叉子，反之不然。即当一个哲学家发现自己在等待另一个比自己有更高优先级的哲学家的资源时，他必须放弃已经控制的叉子。,基于时间戳的死锁预防方法,等待死亡方案(wait-diescheme)。该方案是基于非剥夺方法。当Pi要使用Pj正在使用的资源时，如果当Pi比Pj老，则Pi等待Pj的结束(舍不得)；否则Pi回卷(不要了)。例如：假定进程p1，p2和p3分别有时间戳5，10和15，若p1申请已由p2占有的资源，p1就等待；如果p3申请已由p2占有的资源，p3就被撤离。2）伤害等待方案(wound-waitscheme)。它是一种基于剥夺的方法。当Pi要使用Pj正在使用的资源时，如果当Pi比Pj新，则Pi等待Pj的结束；否则Pj回卷(尊老)。例如：假定进程p1，p2和p3分别有时间戳5，10和15，如果p1申请已由p2占有的资源，那么该资源从p2手中抢占，而且p2被撤离；如果p3申请已由p2占有的资源，则p2就等待。,等待-死亡预防方案图示,等待-死亡方案例题,例题：根据表1描述的5个进程的优先级及请求时间等信息，用等待-死亡方案画出时间轴上5个进程执行的时间和先后顺序。并说明进程之间的等待关系。,伤害-等待预防方案图示,基于时间戳的预防死锁方法,图例说明：假设P1的时间戳小于P2的时间戳,基于时间戳的死锁预防方法,两种方案的区别：在“等待-死亡”方案中，年长的进程必须等待年轻的进程释放它的资源，因此进程越“年长”，它就越容易引起等待。与此相反，在“因伤等待”方案中，年长的进程决不会等待年轻的进程。在“等待-死亡”方案中，进程pi可能被撤离若干次。在“伤害-等待”方案中，进程pi撤离的次数较少。,集中式死锁检测,使用一个协调者来集中检测系统状态，并消除出现的死锁利用各节点的局部等待图在协调者建立全局等待图当在局部等待图中有新的边被加入或删除时修改全局等待图协调者定期检查局部等待图的变化协调者认为有必要时运行回路检查算法时缺点：如果不能保证状态的一致性，则可能会得出错误结论（假死锁）,集中式死锁检测,产生假死锁的图例说明：,集中式死锁检测,产生假死锁的图例说明：,分布式死锁检测,每个节点独立进行死锁检测每个节点维持一个全局等待图的拷贝全局等待图分解到若干个节点上进行维护，需要时通过消息交换组合起来。路径推动算法在每个节点建立部分的全局等待图，当需要进行死锁检测时，节点将自己的全局等待图向邻接点进行扩散；接到消息的节点用自己的等待图信息完善全局等待图并进行邻接点扩散操作，直到在某节点形成最终的全局等待图并将检测结论通知各个节点。状态比较难一致，可能依据部分等待图来判断,分布式死锁检测,边跟踪算法：各节点将自己的资源需求作为探测器沿依赖关系发送出去，如果某节点收到自己发出的探测器，则表明存在资源依赖回路。扩散计算算法：当需要检测时，进程向它所依赖的进程发起询问，并将因此而引发的各个询问关联成等待图，或者通过接收应答将图消解，或者从中发现死锁。全局状态检测：通过建立一致的全局状态图来检测是否有死锁发生。,等级式死锁检测,死锁检测和恢复的研究方向,算法正确性。通常由于报文的传输延迟是不可预料的，严格证明死锁检测算法的正确性有难度。算法性能。需要在信息流量(监测和恢复算法的复杂性)和死锁持续时间(监测和恢复的速度)之间达成妥协。死锁解决。一个好而快的死锁检测算法可能并不能提供足够的信息用于解决死锁。假死锁。一个检测程序不仅要满足前进要求，即必须在有限的时间内发现死锁，还要满足安全要求。如果一个死锁被发现，那么这个死锁应该是确实存在的。死锁概率。检测和恢复算法的设计依赖于给定系统中死锁发生的概率。,死锁检测算法,AND模型下的Chandy-Misra-Hass算法,基本思想：在等待图中，将探测报文(probemessage)从一个进程发送到另一个进程。如果报文回到发起者，那么就有死锁存在。探测报文包含一个三元组(i,j,k)，表示该报文是一个由进程Pi发起的死锁检测报文，现在由进程Pj所在的站点发往进程Pk所在的站点。当一个进程接收到一个探测报文时，如果该进程正在等待某个(或某些)进程，它将向某个(或某些)等待的进程转发探测报文。,死锁检测的实例,AND模型下的Chandy-Misra-Hass算法图例说明：,死锁检测的实例,AND模型下的Chandy-Misra-Hass算法中打破死锁方法：,如果检测到死锁，则由探测报文的发起者杀死自己。存在问题：当有多个进程同时检测到同一个死锁时，与同一个死锁有关的多个进程会被杀死。解决方法：每个收到探测报文的进程将自己的标识符附加到探测报文的后面，当探测报文回到发起者进程时，发起者进程选取一个具有最大标识符号码