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

分布式数据库中常见死锁检测算法分析主要内容死锁的形成1分布式系统中常见的死锁检测方法2死锁检测的实例3关于死锁检测和恢复的研究方向4一死锁的形成产生死锁的原因：由于系统提供的资源数比多个进程所需的资源数少，并且系统的资源分配策略和进程并发执行的速度不当。死锁问题如果处理不当，将严重影响系统的效率和可靠性。产生死锁的必要条件是：互斥使用资源，占有且等待资源，非抢夺式分配，循环等待资源。一死锁的形成在左图中，T1封锁X后T2又封锁Y，而它们又要到提交后才撤去各自的锁，调度Hl不能通过AEF所包围的封锁区，最后落入E点陷入死锁，在这种情况下，只能借助于死锁检测器中止并重发。T2使调度转变为串行的。由上可知，形成死锁至少要有两对冲突操作，死锁是冲突不能解决的结果。二分布式系统中常见的死锁检测方法死锁的检测：基于事先避免死锁的一些方法通常会增加系统开销，降低资源的利用率，因此并不太常用，特别是在分布式系统中更少用。为了降低系统开销，在分配资源时不加限制，只要有剩余资源，总是把资源分配给申请者。当然，这样可能会出现死锁。这种系统采用定时运行一个“死锁检测”程序的方法，当检测到死锁时再设法将其排除。这种方法在分布式系统中最为常用。1超时法超时法就是一个事务的等待时间如果超过了规定的时限,就认为发生了死锁。在该算法中，每个事务在发出一个新的操作请求前设置一个超时。如果在超时结束以前，没有收到请求的操作已经成功执行的确认信息，事务则认为它自己已经处于死锁同时夭折自己。1超时法优点缺点该算法简单，实现方便，而且不会由于死锁检测而引起任何网络传输问题。由于该算法判断死锁的标准与资源请求模型无关，因此它可以适用于任何类型的资源请求模型中。1.该方法的主要缺点是夭折了过多的事务。夭折的事务可能并没有死锁，造成了不必要的事务夭折与重启。2.另一个缺点是超时间隔难以把握。如果时间间隔太短，则会使更多的事务发生不必要的夭折，如果太长，则会延长死锁在系统中的持续时间，进而降低系统性能。由于系统中的各种应用存在相当大的差异，所以通常超时间隔不得不设置为比一个事务的平均执行时间更长。2集中式检测方法在分布式系统中，每个站点都有一个本地死锁检测程序，其任务是判断在其站点所有潜在的全局死锁；其方法是：在站点的输入端口开始，沿本地等待图反向搜索，如果最终会搜索到输出端口，就说明具有潜在的全局死锁。在集中式死锁检测方法中，利用所有的局部资源分配图(或等待图)建立一个全局资源分配图(或等待图)。任何一个机器为它自己的进程和资源维持一个局部的资源分配图。整个系统只有一个协调者，它维持全局的资源分配图，全局的资源分配图是由局部资源分配图组合而成的。

全局资源分配图(或等待图)的获得方法当协调者认为需要运行回路检测算法时，它要求所有的机器向它发送局部图的更新信息，协调者对全局图进行更新。定期地更新，每个机器定期地向协调者发送自上次更新以来所有添加的边和删除的边，协调者根据报文信息对全局图进行更新。当在局部图中有边被加入或删除时，向协调者发送一个报文，协调者根据报文信息对全局图进行更新。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的等待图中。死锁处理是分布式系统中一个需要解决的重要问题。死锁的解决方法有多种，不同的系统应根据实际情况采用不同的解决方法。在实际应用中，不仅要解决死锁问题，还要注意尽可能