分布式数据库中常见死锁检测算法分析课件

主要内容死锁的形成1分布式系统中常见的死锁检测方法2死锁检测的实例3关于死锁检测和恢复的研究方向4一死锁的形成产生死锁的原因：由于系统提供的资源数比多个进程所需的资源数少，并且系统的资源分配策略和进程并发执行的速度不当。死锁问题如果处理不当，将严重影响系统的效率和可靠性。产生死锁的必要条件是：互斥使用资源，占有且等待资源，非抢夺式分配，循环等待资源。一死锁的形成在左图中，T1封锁X后T2又封锁Y，而它们又要到提交后才撤去各自的锁，调度Hl不能通过AEF所包围的封锁区，最后落入E点陷入死锁，在这种情况下，只能借助于死锁检测器中止并重发。T2使调度转变为串行的。由上可知，形成死锁至少要有两对冲突操作，死锁是冲突不能解决的结果。二分布式系统中常见的死锁检测方法死锁的检测：基于事先避免死锁的一些方法通常会增加系统开销，降低资源的利用率，因此并不太常用，特别是在分布式系统中更少用。为了降低系统开销，在分配资源时不加限制，只要有剩余资源，总是把资源分配给申请者。当然，这样可能会出现死锁。这种系统采用定时运行一个“死锁检测”程序的方法，当检测到死锁时再设法将其排除。这种方法在分布式系统中最为常用。1超时法超时法就是一个事务的等待时间如果超过了规定的时限,就认为发生了死锁。在该算法中，每个事务在发出一个新的操作请求前设置一个超时。如果在超时结束以前，没有收到请求的操作已经成功执行的确认信息，事务则认为它自己已经处于死锁同时夭折自己。

全局资源分配图(或等待图)的获得方法当协调者认为需要运行回路检测算法时，它要求所有的机器向它发送局部图的更新信息，协调者对全局图进行更新。定期地更新，每个机器定期地向协调者发送自上次更新以来所有添加的边和删除的边，协调者根据报文信息对全局图进行更新。当在局部图中有边被加入或删除时，向协调者发送一个报文，协调者根据报文信息对全局图进行更新。2集中式检测方法当开始死锁检测时，协调者便查找全局等待图。如果发现回路，一个进程就会被卷回，从而打破循环等待。2集中式检测方法12它易受运行集中检测程序的站点的故障的影响它可能需要大量的通讯费用，因为集中式检测程序可能离网络中的其他站点很远。集中式死锁检测比较简单，但它容易产生假死锁的情况。它有两个主要缺点：产生假死锁的图例说明：3分布式死锁检测方法123路径推动算法:先在每个机器上建立形式简单的全局等待图。每当进行死锁检测时，各个机器就将等待图的拷贝送往一定数量的邻居节点。局部拷贝更新后又被传播下去。这一过程重复进行直到某个节点获得了足够的信息来构造一个等待图以便做出是否存在死锁的结论。边跟踪算法:分布式网络结构图中的回路可以通过沿图的边传播一种叫探测器的特殊信息来检测。当一个发起者得到一个与自己发送的探测器相匹配的探测器时，它就知道它在图中的一个回路里。扩散计算：怀疑有死锁发生时，事务管理器通过向依赖于它的进程发送查询启动一个扩散进程。这里不会生成全局等待图。发送查询信息时，扩散计算就增长；接收回答后，扩散计算就缩减。根据所得信息，发起者会检测到死锁的发生。4全局状态检测:这个方法基于Chandy和Lamport的快照方法。可以通过建立一个一致的全局状态而无需暂停当前的计算来生成一个一致的全局等待图。Knapp将分布式死锁检测算法分为以下四类：3分布式死锁检测方法321在集中式方案中全部潜在的死锁循环都发送给某个指定的站点，而在分布式检测方案中则没有这种站点。分布式死锁检测机构中没有本地和非本地死锁检测程序的任何区别，每个站点具有同样的责任。在分布式方案中，死锁检测程序需要一种规则来决定应该把潜在的死锁循环发送给哪个站点，这种规则必须保证能最终检测到全局死锁，并且必须尽量减小传送的信息量。分布式死锁检测和集中式的主要差别是：4层级式死锁检测在层级式死锁检测算法中，站点被分层地放在一个树中。一个站点的死锁检测只涉及到它的下一级站点。例如，设A、B和C是控制器，而C是A和B的最低的公共祖先。假定节点Pi出现在控制器A和B的局部等待图中，那么节点Pi也必定出现在如下控制器的等待图中：(1)C控制器；(2)所有位于从C到A的路径上的控制器；(3)所有位于从C到B的路径上的控制器。而且，如果Pi和Pj出现在控制器D的等待图中，并且在D的一个下一级控制器(子控制器)的等待图中有一条从Pi到Pj的路径，那么边(Pi,Pj)一定存在于D的等待图中。死锁处理是分布式系统中一个需要解决的重要问题。死锁的解决方法有多种，不同的系统应根据实际情况采用不同的解决方法。在实际应用中，不仅要解决死锁问题，还要注意尽可能地提高资源利用率。死锁的检测与解除构成了数据库管理系统的主要内容。死锁检测对应于在等待图中确定一个循环。在分布式数据库中死锁检测问题比在集中式数据库的死锁检测问题更困难，这是因为确定一个死锁的循环等待状态可能要涉及到多个场地，而不仅仅是一个场地。4层级式死锁检测三死锁检测的实例OR模型下的Chandy-Misra-Hass算法：使用两类报文：(query,i,j,k)和(reply,i,j,k)，表示这些报文属于由进程Pi发起的并由Pj送往Pk的扩散计算。一个进程的依赖集合包括所有它在等待以便获得报文的进程。如果接收进程Pk是活动的，它会忽略所有的查询和回答报文。如果它被阻塞，它会向它的依赖集合中的进程发送查询。一旦收集到回答报文，接收进程将向发起者发送一个回答报文。发起者以及每个中间进程用一个计数器记录查询和回答的数目。如果这两个数字相同，即发起者的每个查询都得到了回答，就表明发起者处于死锁状态。OR模型下的Chandy-Misra-Hass算法：当接收进程Pk处于阻塞状态时，会有几种可能：

如果这是Pi发起的第一个来自Pj的报文(这个报文的发送者Pj叫做Pk关于Pi的结合者)，它将向它的依赖集合中的所有进程发送这个查询，并且将查询数目存储在一个局部变量num(i)中。令局部变量wait(i)表示这一进程从它接收到它的第一个由Pi发起的查询起一直被阻塞这一事实。如果这个查询是Pi发起的但不是第一个来自Pj的报文，即当wait(i)仍然成立时，Pk将马上回答。如果从wait(i)变为假的那一时刻Pk运行过，那么这个查询就被丢弃。OR模型下的Chandy-Misra-Hass算法图例说明：OR模型下的Chandy-Misra-Hass算法图例说明：四关于死锁检测和恢复的研究方向算法正确性。严格证明死锁检测算法的正确性是困难的，由于报文的传输延迟是不可预料的，所以得到一致的全局状态是很困难的。算法性能。需要在信息流量(监测和恢复算法的复杂性)和死锁持续时间(监测和恢复的速度)之间达成妥协。死锁解决。一个好而快的死锁检测算法可能并不能提供足够的信息用于解决死锁。假死锁。一个检测程序不仅要满足前进要求，即必须在有限的时间内发现死锁，还要满足安全要求。如果一个死锁被发现，那么这个死锁应该是确实存在的。死锁概率。检测和恢复算法的设计依赖于给定系统中死锁发生的概率。参考文献1.邵佩英著.分布式数据库系统及其应用.北京:科学出版社,20002.刘键，《分布式计算机系统》，人民邮电出版社，1990年.3.KnappE.Deadlockdetectionindistributeddatabases.ACMComputSurv,1987,19(4):303-3284.GligorVD,ShattuckSH.Ondeadlockdetectionindistributedsystems.IEEETransSoftwareEng,1980,6(5):435–4405.RoeslerM,BurkhardWA,CooperKB.Efficientdeadlockresolutionforlock-basedconcurrencycontrolschemes.In:Proceedingsofthe8thInternationalonferenceonDistributedComputingSystems,SanJose,California,June13–17,1988.IEEE-CSPress,1988,224-233

参考文献6.ChoudharyAN,KohlerWH,StankovicJA,TowsleyD.Amodifiedpriority-basedprobealgorithmfordistributeddeadlockdetectionandresolution.IEEETransSoftwareEng,1989,15(1):10-177.KshemkalyaniAD,SinghalM.Invariant-basedverificationofadistributeddeadlockd