分布式系统中的死锁.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第六章 分布式系统中的死锁,6.1 死锁问题,死锁发生的条件,(1)互斥正如我们第五章所讨论的，互斥是一种资源分配方式，保证同一个资源在同一时刻最多只能被一个进程占用，它用于防止多个进程同时共享访问不可同时共享访问的资源2)不可剥夺的资源分配系统将一个资源的访问权分配给某一个进程后，系统不能强迫该进程放弃对该资源的控制权3)占有并等待必然有一个进程占用了至少一个资源，同时在等待获取被其他进程占用的资源4)循环等待在等待图中有一个循环路径第六章 分布式系统中的死锁,6.1 死锁问题,死锁的图论模型,可以用图模型来表示死锁，表示死锁的图模型有两种，一种是等待图，另一种是资源分配图在等待图中，节点代表进程，当且仅当进程,P,i,等待一个被进程,P,j,所占用的资源时，边(,P,i,P,j,),存在于等待图中，图中的边是有向的资源分配图中的节点有两种：一种是进程节点，另一种是资源节点每个边是一个有序对(,P,i,R,j,),或(,R,j,P,i,)，,其中,P,代表进程，,R,代表一个资源类型边(,P,i,R,j,),表示进程,P,i,请求类型为,R,j,的一个资源，并且正在等待这个资源，一个资源类型中可能有多个资源。

边(,R,j,P,i,),表示类型为,R,j,的一个资源已经分配给进程,P,i,由于等待图假定一个资源类型中只有一个资源，所以资源分配图是一个比等待图更加有力的工具第六章 分布式系统中的死锁,6.1 死锁问题,死锁的图论模型,资源分配图实例：,第六章 分布式系统中的死锁,6.1 死锁问题,死锁的图论模型,资源分配图到等待图的转化：,(1)在资源分配图中找到一个未被处理的资源R如果所有的资源都已经处理，转向步骤32)从这个资源R的每个输入进程节点到每个输出进程节点之间加一条有向边一个资源的输入进程节点是等待这个资源的进程节点，一个资源的输出进程节点是占有这个资源的进程节点转向步骤13)删除所有的资源节点以及相应的边第六章 分布式系统中的死锁,6.1 死锁问题,死锁的图论模型,资源分配图到等待图的转化实例：,第六章 分布式系统中的死锁,6.1 死锁问题,处理死锁的策略死锁,可以使用PAID来概括死锁处理的各种方法：预防(,P,revent)、避免(,A,void)、忽略(,I,gnore)和检测(,D,etect)预防死锁通过限制请求，保证四个死锁条件中至少有一个不能发生，从而预防死锁避免死锁。

如果资源分配会导致一个安全的结果状态，就将资源动态地分配给进程如果至少有一个执行序列使所有的进程都能完成运行，那么这个状态就是安全的忽略死锁忽略死锁是,UNIX,常采用的一种方法，这种方法只是简单地忽略死锁问题检测死锁和从死锁中恢复允许死锁发生，然后发现并解除死锁第六章 分布式系统中的死锁,6.1 死锁问题,死锁的,AND,条件和,OR,条件,资源死锁和通信死锁：在通信死锁中，进程等待的资源就是报文资源死锁和通信死锁的真正区别在于资源死锁通常使用,AND,条件，而通信死锁通常使用,OR,条件所谓,AND,条件就是当进程取得所有所需资源时，它才能继续执行；所谓,OR,条件就是当进程得到至少一个所需资源，它就能继续执行在使用,AND,条件的系统中，死锁条件是在等待图中存在回路但是在使用,OR,条件的系统中，等待图中的回路未必会引发死锁在使用,OR,条件的系统中，死锁条件是存在结(,knot)一个结,K,是一个节点集合，对于,K,中的任何节点,a，a,能到达,K,中的所有节点，并且只能到达,K,中的节点第六章 分布式系统中的死锁,6.1 死锁问题,死锁的,AND,条件和,OR,条件,OR条件死锁图例：,第六章 分布式系统中的死锁,6.2 死锁的预防,预防死锁的一般方法,死锁预防算法是通过限制进程的资源请求来达到预防死锁的目的，都是通过打破四个死锁条件中的一个条件来实现的。

进程在开始执行之前同时获得所有所需资源这种方法打破了占有并等待的条件所有的资源都要被赋予一个唯一的数字编号一个进程可以请求一个有唯一编号,i,的资源，条件是该进程没有占用编号小于或等于,i,的资源这样，就打破了循环等待的条件每个进程被赋予一个唯一的优先级标识优先级标识决定了进程,P,i,是否应该等待进程,P,j,，,从而打破了不可剥夺的条件第六章 分布式系统中的死锁,6.2 死锁的预防,基于时间戳的预防死锁方法,包括两种死锁预防方案这两种方案相互补充，这种方法常用于分布式数据库系统中等待死亡方案(,wait-die scheme)该方案是基于非剥夺方法当进程,P,i,请求的资源正被进程,P,j,占有时，只有当,P,i,的时间戳比进程,P,j,的时间戳小时，即,P,i,比,P,j,老时，,P,i,才能等待否则,P,i,被卷回(,roll-back)，,即死亡伤害等待方案(,wound-wait scheme)它是一种基于剥夺的方法当进程,P,i,请求的资源正被进程,P,j,占有时，只有当进程,P,i,的时间戳比进程,P,j,的时间戳大时，即,P,i,比,P,j,年轻时，,P,i,才能等待。

否则,P,j,被卷回(,roll-back)，,即死亡第六章 分布式系统中的死锁,6.2 死锁的预防,基于时间戳的预防死锁方法,图例说明：,第六章 分布式系统中的死锁,6.3 死锁的检测,集中式死锁检测,在集中式死锁检测方法中，利用所有的局部资源分配图(或等待图)建立一个全局资源分配图(或等待图)任何一个机器为它自己的进程和资源维持一个局部的资源分配图整个系统只有一个协调者，它维持全局的资源分配图，全局的资源分配图是由局部资源分配图组合而成的第六章 分布式系统中的死锁,6.3 死锁的检测,集中式死锁检测,全局资源分配图(或等待图)的获得方法：,当在局部图中有边被加入或删除时，向协调者发送一个报文，协调者根据报文信息对全局图进行更新定期地更新，每个机器定期地向协调者发送自上次更新以来所有添加的边和删除的边，协调者根据报文信息对全局图进行更新当协调者认为需要运行回路检测算法时，它要求所有的机器向它发送局部图的更新信息，协调者对全局图进行更新当开始死锁检测时，协调者便查找全局等待图如果发现回路，一个进程就会被卷回，从而打破循环等待缺点：容易产生假死锁的情况第六章 分布式系统中的死锁,6.3 死锁的检测,集中式死锁检测,产生假死锁的图例说明：,第六章 分布式系统中的死锁,6.3 死锁的检测,集中式死锁检测,产生假死锁的图例说明：,第六章 分布式系统中的死锁,6.3 死锁的检测,分布式死锁检测,Knapp将分布式死锁检测算法分为以下四类：,路径推动算法(,path-pushing algorithm)。

先在每个机器上建立形式简单的全局等待图每当进行死锁检测时，各个机器就将等待图的拷贝送往一定数量的邻居节点局部拷贝更新后又被传播下去这一过程重复进行直到某个节点获得了足够的信息来构造一个等待图以便做出是否存在死锁的结论边跟踪算法(,edge-chasing algorithm)分布式网络结构图中的回路可以通过沿图的边传播一种叫探测器的特殊信息来检测当一个发起者得到一个与自己发送的探测器相匹配的探测器时，它就知道它在图中的一个回路里第六章 分布式系统中的死锁,6.3 死锁的检测,分布式死锁检测,Knapp将分布式死锁检测算法分为以下四类：,扩散计算(,diffusing computation)怀疑有死锁发生时，事务管理器通过向依赖于它的进程发送查询启动一个扩散进程这里不会生成全局等待图发送查询信息时，扩散计算就增长；接收回答后，扩散计算就缩减根据所得信息，发起者会检测到死锁的发生全局状态检测(,global state detection)这个方法基于,Chandy,和,Lamport,的快照方法可以通过建立一个一致的全局状态而无需暂停当前的计算来生成一个一致的全局等待图第六章 分布式系统中的死锁,6.3 死锁的检测,层级式死锁检测,在层级式死锁检测算法中，站点被分层地放在一个树中。

一个站点的死锁检测只涉及到它的下一级站点例如，设A、B和C是控制器，而C是A和B的最低的公共祖先假定节点P,i,出现在控制器A和B的局部等待图中，那么节点P,i,也必定出现在如下控制器的等待图中：,(1)C控制器；,(2)所有位于从C到A的路径上的控制器；,(3)所有位于从C到B的路径上的控制器而且，如果P,i,和P,j,出现在控制器D的等待图中，并且在D的一个下一级控制器(子控制器)的等待图中有一条从P,i,到P,j,的路径，那么边(P,i,P,j,)一定存在于D的等待图中第六章 分布式系统中的死锁,6.3 死锁的检测,关于死锁检测和恢复的研究方向：,算法正确性严格证明死锁检测算法的正确性是困难的，由于报文的传输延迟是不可预料的，所以得到一致的全局状态是很困难的算法性能需要在信息流量(监测和恢复算法的复杂性)和死锁持续时间(监测和恢复的速度)之间达成妥协死锁解决一个好而快的死锁检测算法可能并不能提供足够的信息用于解决死锁一个检测程序不仅要满足前进要求，即必须在有限的时间内发现死锁，还要满足安全要求如果一个死锁被发现，那么这个死锁应该是确实存在的死锁概率检测和恢复算法的设计依赖于给定系统中死锁发生的概率。

第六章 分布式系统中的死锁,6.3 死锁的检测,死锁检测的实例,AND,模型下的,Chandy,-,Misra,-Hass,算法,在Chandy-Misra-Hass算法中，分布式死锁检测算法使用一个特殊的报文，在等待图中该报文从一个进程传递到另一个进程，该报文称为探测报文(probe message)如果报文回到发起者，那么就有死锁存在探测报文包含一个三元组(i,j,k)，表示该报文是一个由进程P,i,发起的死锁检测报文，现在由进程P,j,所在的站点发往进程P,k,所在的站点当一个进程接收到一个探测报文时，它首先检查自己是否等待某个(或某些)进程，如果它正在等待某个(或某些)进程，它将向所有它等待的进程转发这个探测报文第六章 分布式系统中的死锁,6.3 死锁的检测,死锁检测的实例,AND,模型下的,Chandy,-,Misra,-Hass,算法图例说明：,第六章 分布式系统中的死锁,6.3 死锁的检测,死锁检测的实例,AND,模型下的,Chandy,-,Misra,-Hass,算法中打破死锁方法,：,一种方法是由探测报文的发起者杀死自己，但是，当有多个进程同时检测到同一个死锁时，与同一个死锁有关的多个进程会被杀死，这样做的效率会很低。

另一种方法是每个收到探测报文的进程将自己的标识符附加到探测报文的后面，当探测报文回到发起者进程时，发起者进程选取一个具有最大标识符号码的进程杀死，即使有多个进程同时检测到同一个死锁，它们也会选择杀死同一个进程第六章 分布式系统中的死锁,6.3 死锁的检测,死锁检测的实例,AND,模型下的,Mitchell-Merritt,算法,Mitchell-Merritt,算法与,Chandy,-,Misra,-Hass,算法的区别：,其限制是每个进程每次只能请求一个资源探测报文在等待图中，沿等待方向的相反方向传送，这样的图叫反向等待图(,reversed wait-for graph)每当进程收到探测报文时，它将自己的标识符和探测报文发起者的标识符相比较，如果自己的标识符大于探测报文发起者的标识符，它就用自己的标识符取代探测报文发起者的标识符，自己变成探测报文的发起者当几个进程同时发起死锁检测时，只有一个进程能够成为唯一的探测者第六章 分布式系统中的死锁,6.3 死锁的检测,。