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

1、分布式数据库中常见死锁检测算法分析主要内容死锁的形成死锁的形成 1分布式系统中常见的死锁检测方法分布式系统中常见的死锁检测方法2死锁检测的实例死锁检测的实例3关于死锁检测和恢复的研究方向关于死锁检测和恢复的研究方向4一 死锁的形成n 产生死锁的原因： 由于系统提供的资源数比多个进程所需的资源数少，并且系统的资源分配策略和进程并发执行的速度不当。 死锁问题如果处理不当，将严重影响系统的效率和可靠性。n 产生死锁的必要条件是： 互斥使用资源，占有且等待资源，非抢夺式分配，循环等待资源。一 死锁的形成在左图中，T1封锁X后T2又封锁Y，而它们又要到提交后才撤去各自的锁，调度Hl不能通过AEF所包围的

2、封锁区，最后落入E点陷入死锁，在这种情况下，只能借助于死锁检测器中止并重发。T2使调度转变为串行的。由上可知，形成死锁至少要有两对冲突操作，死锁是冲突不能解决的结果。二 分布式系统中常见的死锁检测方法n 死锁的检测： 基于事先避免死锁的一些方法通常会增加系统开销，降低资源的利用率，因此并不太常用，特别是在分布式系统中更少用。为了降低系统开销，在分配资源时不加限制，只要有剩余资源，总是把资源分配给申请者。当然，这样可能会出现死锁。这种系统采用定时运行一个“死锁检测”程序的方法，当检测到死锁时再设法将其排除。这种方法在分布式系统中最为常用。1 超时法n 超时法就是一个事务的等待时间如果超过了规定的

3、时限,就认为发生了死锁。n 在该算法中，每个事务在发出一个新的操作请求前设置一个超时。如果在超时结束以前，没有收到请求的操作已经成功执行的确认信息，事务则认为它自己已经处于死锁同时夭折自己。1 超时法优点缺点n该算法简单，实现方便，而且不会由于死锁检测而引起任何网络传输问题。n由于该算法判断死锁的标准与资源请求模型无关，因此它可以适用于任何类型的资源请求模型中。1.该方法的主要缺点是夭折了过多的事务。夭折的事务可能并没有死锁，造成了不必要的事务夭折与重启。2.另一个缺点是超时间隔难以把握。如果时间间隔太短，则会使更多的事务发生不必要的夭折，如果太长，则会延长死锁在系统中的持续时间，进而降低系统

4、性能。由于系统中的各种应用存在相当大的差异，所以通常超时间隔不得不设置为比一个事务的平均执行时间更长。2 集中式检测方法n 在分布式系统中，每个站点都有一个本地死锁检测程序，其任务是判断在其站点所有潜在的全局死锁；其方法是：在站点的输入端口开始，沿本地等待图反向搜索，如果最终会搜索到输出端口，就说明具有潜在的全局死锁。n 在集中式死锁检测方法中，利用所有的局部资源分配图(或等待图)建立一个全局资源分配图(或等待图)。任何一个机器为它自己的进程和资源维持一个局部的资源分配图。整个系统只有一个协调者，它维持全局的资源分配图，全局的资源分配图是由局部资源分配图组合而成的。 全局资源分配图(或等待图)

5、的获得方法当协调者认为需要运行回路检测算法时，它要求所有的机器向它发送局部图的更新信息，协调者对全局图进行更新。定期地更新，每个机器定期地向协调者发送自上次更新以来所有添加的边和删除的边，协调者根据报文信息对全局图进行更新。当在局部图中有边被加入或删除时，向协调者发送一个报文，协调者根据报文信息对全局图进行更新。2 集中式检测方法当开始死锁检测时，协调者便查找全局等待图。如果发现回路，一个进程就会被卷回，从而打破循环等待。2 集中式检测方法12它易受运行集中检测程序的站点的故障的影响它可能需要大量的通讯费用，因为集中式检测程序可能离网络中的其他站点很远。集中式死锁检测比较简单，但它容易产生假死

6、锁的情况。它有两个主要缺点：产生假死锁的图例说明： A S R B (a)机器 0 C S T (b)机器 1 C S A R B T (c)协调者 A S R B (d)机器 0 T C S T (e)机器 1 C S A R B T (g)协调者：假死锁 B A S C T R B (f)协调者 3 3 分布式死锁检测方法分布式死锁检测方法123路径推动算法:先在每个机器上建立形式简单的全局等待图。每当进行死锁检测时，各个机器就将等待图的拷贝送往一定数量的邻居节点。局部拷贝更新后又被传播下去。这一过程重复进行直到某个节点获得了足够的信息来构造一个等待图以便做出是否存在死锁的结论。边跟踪算法

7、:分布式网络结构图中的回路可以通过沿图的边传播一种叫探测器的特殊信息来检测。当一个发起者得到一个与自己发送的探测器相匹配的探测器时，它就知道它在图中的一个回路里。扩散计算：怀疑有死锁发生时，事务管理器通过向依赖于它的进程发送查询启动一个扩散进程。这里不会生成全局等待图。发送查询信息时，扩散计算就增长；接收回答后，扩散计算就缩减。根据所得信息，发起者会检测到死锁的发生。4全局状态检测:这个方法基于Chandy和Lamport 的快照方法。可以通过建立一个一致的全局状态而无需暂停当前的计算来生成一个一致的全局等待图。Knapp将分布式死锁检测算法分为以下四类：3 3 分布式死锁检测方法分布式死锁检

8、测方法321在集中式方案中全部潜在的死锁循环都发送给某个指定的站点，而在分布式检测方案中则没有这种站点。分布式死锁检测机构中没有本地和非本地死锁检测程序的任何区别，每个站点具有同样的责任。在分布式方案中，死锁检测程序需要一种规则来决定应该把潜在的死锁循环发送给哪个站点，这种规则必须保证能最终检测到全局死锁，并且必须尽量减小传送的信息量。分布式死锁检测和集中式的主要差别是：4 层级式死锁检测层级式死锁检测n 在层级式死锁检测算法中，站点被分层地放在一个树中。一个站点的死锁检测只涉及到它的下一级站点。例如，设A、B和C是控制器，而C是A和B的最低的公共祖先。假定节点Pi出现在控制器A和B的局部等待

9、图中，那么节点Pi也必定出现在如下控制器的等待图中： n (1) C控制器；n (2) 所有位于从C到A的路径上的控制器；n (3) 所有位于从C到B的路径上的控制器。 n 而且，如果Pi和Pj出现在控制器D的等待图中，并且在D的一个下一级控制器(子控制器)的等待图中有一条从Pi到Pj的路径，那么边(Pi,Pj)一定存在于D的等待图中。n 死锁处理是分布式系统中一个需要解决的重要问题。死锁的解决方法有多种，不同的系统应根据实际情况采用不同的解决方法。在实际应用中，不仅要解决死锁问题，还要注意尽可能地提高资源利用率。n 死锁的检测与解除构成了数据库管理系统的主要内容。死锁检测对应于在等待图中确定

10、一个循环。在分布式数据库中死锁检测问题比在集中式数据库的死锁检测问题更困难，这是因为确定一个死锁的循环等待状态可能要涉及到多个场地，而不仅仅是一个场地。4 层级式死锁检测层级式死锁检测三 死锁检测的实例OR模型下的模型下的Chandy-Misra-Hass算法：算法：n 使用两类报文：(query,i,j,k)和(reply,i,j,k)，表示这些报文属于由进程Pi发起的并由Pj送往Pk的扩散计算。 n 一个进程的依赖集合包括所有它在等待以便获得报文的进程。如果接收进程Pk是活动的，它会忽略所有的查询和回答报文。如果它被阻塞，它会向它的依赖集合中的进程发送查询。 n 一旦收集到回答报文，接收进

11、程将向发起者发送一个回答报文。发起者以及每个中间进程用一个计数器记录查询和回答的数目。如果这两个数字相同，即发起者的每个查询都得到了回答，就表明发起者处于死锁状态。OROR模型下的模型下的Chandy-Misra-HassChandy-Misra-Hass算法：算法：当接收进程Pk处于阻塞状态时，会有几种可能： n 如果这是Pi发起的第一个来自Pj的报文(这个报文的发送者Pj叫做Pk关于Pi的结合者)，它将向它的依赖集合中的所有进程发送这个查询，并且将查询数目存储在一个局部变量num(i)中。令局部变量wait(i)表示这一进程从它接收到它的第一个由Pi发起的查询起一直被阻塞这一事实。 n 如

12、果这个查询是Pi发起的但不是第一个来自Pj的报文，即当wait(i)仍然成立时，Pk将马上回答。 n 如果从wait(i)变为假的那一时刻Pk运行过，那么这个查询就被丢弃。 OROR模型下的模型下的Chandy-Misra-HassChandy-Misra-Hass算法图例说明：算法图例说明： P1 P2 P3 P4 P5 (a) 无死锁 P1 P2 P3 P4 P5 (b) 有死锁 OROR模型下的模型下的Chandy-Misra-HassChandy-Misra-Hass算法图例说明：算法图例说明：P4P2P3P4P5(c) 图(a)的死锁检测过程P4P2P3P4P5(d) 图(b)的死锁

13、检测过程(query,4,4,2)(query,4,2,3)(query,4,3,4)(reply,4,4,3)(reply,4,3,2)(reply,4,2,4)(query,4,4,5)(query,4,4,2)(query,4,2,3)(query,4,3,4)(reply,4,4,3)(reply,4,3,2)(reply,4,2,4)(query,4,4,5)P2(query,4,5,2)(reply,4,2,5)(reply,4,5,4)P4P2P3P4P5(c) 图(a)的死锁检测过程P4P2P3P4P5(d) 图(b)的死锁检测过程(query,4,4,2)(query,4,2

14、,3)(query,4,3,4)(reply,4,4,3)(reply,4,3,2)(reply,4,2,4)(query,4,4,5)(query,4,4,2)(query,4,2,3)(query,4,3,4)(reply,4,4,3)(reply,4,3,2)(reply,4,2,4)(query,4,4,5)P2(query,4,5,2)(reply,4,2,5)(reply,4,5,4)四 关于死锁检测和恢复的研究方向n 算法正确性。严格证明死锁检测算法的正确性是困难的，由于报文的传输延迟是不可预料的，所以得到一致的全局状态是很困难的。 n 算法性能。需要在信息流量(监测和恢复算法的

15、复杂性)和死锁持续时间(监测和恢复的速度)之间达成妥协。 n 死锁解决。一个好而快的死锁检测算法可能并不能提供足够的信息用于解决死锁。 n 假死锁。一个检测程序不仅要满足前进要求，即必须在有限的时间内发现死锁，还要满足安全要求。如果一个死锁被发现，那么这个死锁应该是确实存在的。 n 死锁概率。检测和恢复算法的设计依赖于给定系统中死锁发生的概率。参考文献n 1. 邵佩英著.分布式数据库系统及其应用.北京:科学出版社, 2000n 2. 刘键，分布式计算机系统，人民邮电出版社，1990年.n 3. Knapp E . Deadlock detection in distributed databa

16、ses.ACM ComputSurv, 1987, 19(4): 303-328n 4. GligorVD, Shattuck SH . On deadlock detection in distributed systems. IEEE Trans Software Eng, 1980, 6(5): 435440n 5.RoeslerM, BurkhardWA, CooperKB. Efficient deadlock resolutionfor lock-based concurrency control schemes. In: Proceedings of the 8th Intern

17、ational onference on Distributed Computing Systems, San Jose, California, June 1317, 1988. IEEE-CS Press, 1988, 224-233 参考文献n 6. ChoudharyAN, KohlerWH, Stankovic JA, Towsley D . A modified priority-based probe algorithm for distributed deadlock detection and resolution. IEEE Trans Software Eng, 1989, 15(1): 10-17n 7. Kshemkal