(query,4,4,2)
P4
(reply,4,5,4)
P2 (query,4,2,3)
(reply,4,2,4) (query,4,4,5) (reply,4,3,2)
P5 (reply,4,2,5)
(query,4,5,2) P2
P3 (query,4,3,4)
(reply,4,4,3) P4
(c) 图(a)的死锁检测过程
(d) 图 (b)的死锁检测过程
7/7/2013
四 关于死锁检测和恢复的研究方向
算法正确性。严格证明死锁检测算法的正确性是困难的， 由于报文的传输延迟是不可预料的，所以得到一致的全局 状态是很困难的。 算法性能。需要在信息流量(监测和恢复算法的复杂性)和 死锁持续时间(监测和恢复的速度)之间达成妥协。 死锁解决。一个好而快的死锁检测算法可能并不能提供足 够的信息用于解决死锁。 假死锁。一个检测程序不仅要满足前进要求，即必须在有 限的时间内发现死锁，还要满足安全要求。如果一个死锁 被发现，那么这个死锁应该是确实存在的。 死锁概率。检测和恢复算法的设计依赖于给定系统中死锁 发生的概率。
7/7/2013
3
分布式死锁检测方法
分布式死锁检测和集中式的主要差别是：
1
在集中式方案中全 部潜在的死锁循环 都发送给某个指定 的站点，而在分布 式检测方案中则没 有这种站点。
2
分布式死锁检测机构 中没有本地和非本地 死锁检测程序的任何 区别，每个站点具有 同样的责任。
3
在分布式方案中，死锁 检测程序需要一种规则 来决定应该把潜在的死 锁循环发送给哪个站点， 这种规则必须保证能最 终检测到全局死锁，并 且必须尽量减小传送的 信息量。
7/7/2013
参考文献
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-17 7. KshemkalyaniAD, SinghalM. Invariant-based verification of a distributed deadlock detection algorithm. IEEE Trans Software Eng ,1991, 17(8): 789-799 8. 田润芙，杨旭.分布式数据库死锁检测算法评价.网络财富.2009（4）. 9. 张翠玲.一种新的分布式死锁检测算法.现代图书情报技术.2006(5). 10. 王伟东，楼荣生.分布式死锁检测方法研究.第十一届全国数据库学 术会议论文集.1993.
2
3
扩散计算：怀疑有死锁发生时，事务管理器通过向依赖于它的进程发送查询启动一 个扩散进程。这里不会生成全局等待图。发送查询信息时，扩散计算就增长；接收 回答后，扩散计算就缩减。根据所得信息，发起者会检测到死锁的发生。
4
全局状态检测:这个方法基于Chandy和Lamport 的快照方法。可以通过建立一个一 致的全局状态而无需暂停当前的计算来生成一个一致的全局等待图。
7/7/2013
一 死锁的形成
在左图中，T1封锁X后T2又封锁Y， 而它们又要到提交后才撤去各自的 锁，调度Hl不能通过AEF所包围的封 锁区，最后落入E点陷入死锁，在这 种情况下，只能借助于死锁检测器 中止并重发。T2使调度转变为串行 的。
由上可知，形成死锁至少要有两对冲突操作，死锁是冲突不能解决的结果。
7/7/2013
OR模型下的Chandy-Misra-Hass算法：
当接收进程Pk处于阻塞状态时，会有几种可能：
如果这是Pi发起的第一个来自Pj的报文(这个报文的发送 者Pj叫做Pk关于Pi的结合者)，它将向它的依赖集合中的 所有进程发送这个查询，并且将查询数目存储在一个局部 变量num(i)中。令局部变量wait(i)表示这一进程从它接 收到它的第一个由Pi发起的查询起一直被阻塞这一事实。 如果这个查询是Pi发起的但不是第一个来自Pj的报文，即 当wait(i)仍然成立时，Pk将马上回答。 如果从wait(i)变为假的那一时刻Pk运行过，那么这个查 询就被丢弃。
7/7/2013
4 层级式死锁检测
死锁处理是分布式系统中一个需要解决的重要问题。死锁 的解决方法有多种，不同的系统应根据实际情况采用不同 的解决方法。在实际应用中，不仅要解决死锁问题，还要 注意尽可能地提高资源利用率。
死锁的检测与解除构成了数据库管理系统的主要内容。死 锁检测对应于在等待图中确定一个循环。在分布式数据库 中死锁检测问题比在集中式数据库的死锁检测问题更困难， 这是因为确定一个死锁的循环等待状态可能要涉及到多个 场地，而不仅仅是一个场地。
7/7/2013
三 死锁检测的实例
OR模型下的Chandy-Misra-Hass算法：
使用两类报文：(query,i,j,k)和(reply,i,j,k)，表示这 些报文属于由进程Pi发起的并由Pj送往Pk的扩散计算。 一个进程的依赖集合包括所有它在等待以便获得报文的，它会向它的依赖集合中的进程发 送查询。 一旦收集到回答报文，接收进程将向发起者发送一个回答 报文。发起者以及每个中间进程用一个计数器记录查询和 回答的数目。如果这两个数字相同，即发起者的每个查询 都得到了回答，就表明发起者处于死锁状态。
全局资源分配图(或 等待图)的获得方法
当开始死锁检测时，协调者便查找全局等待图。如果发现回路，一个进 程就会被卷回，从而打破循环等待。
7/7/2013
2 集中式检测方法
集中式死锁检测比较简单，但它容易产生假死锁的情况。
它有两个主要缺点：
1
它易受运行集中检测程序的站点的故障的影响
2
它可能需要大量的通讯费用，因为集中式检测程序可 能离网络中的其他站点很远。
7/7/2013
产生假死锁的图例说明：
A S S C A S C A S
R
T
R
T
R
B (a)机器 0 (b)机器 1
B (c)协调者
B (d)机器 0
T
S
C
A
S
C
A
S
C
T
R
T
R
T
B
7/7/2013
B (f)协调者
B (g)协调者：假死锁
(e)机器 1
3
1
分布式死锁检测方法
Knapp将分布式死锁检测算法分为以下四类：
优点
该算法简单，实现方 便，而且不会由于死锁 检测而引起任何网络传 输问题。 由于该算法判断死锁 的标准与资源请求模型 无关，因此它可以适用 于任何类型的资源请求 模型中。
缺点
1.该方法的主要缺点是夭折了过 多的事务。夭折的事务可能并没 有死锁，造成了不必要的事务夭 折与重启。2.另一个缺点是超时 间隔难以把握。如果时间间隔太 短，则会使更多的事务发生不必 要的夭折，如果太长，则会延长 死锁在系统中的持续时间，进而 降低系统性能。由于系统中的各 种应用存在相当大的差异，所以 通常超时间隔不得不设置为比一 个事务的平均执行时间更长。
7/7/2013
二 分布式系统中常见的死锁检测方法
死锁的检测： 基于事先避免死锁的一些方法通常会增加系统开销， 降低资源的利用率，因此并不太常用，特别是在分布式系 统中更少用。为了降低系统开销，在分配资源时不加限制， 只要有剩余资源，总是把资源分配给申请者。当然，这样 可能会出现死锁。这种系统采用定时运行一个“死锁检测” 程序的方法，当检测到死锁时再设法将其排除。这种方法 在分布式系统中最为常用。
7/7/2013
2 集中式检测方法
当在局部图中有边被加入或删除时， 向协调者发送一个报文，协调者根据 报文信息对全局图进行更新。 定期地更新，每个机器定期地向协调者 发送自上次更新以来所有添加的边和删 除的边，协调者根据报文信息对全局图 进行更新。 当协调者认为需要运行回路检测算法时， 它要求所有的机器向它发送局部图的更 新信息，协调者对全局图进行更新。
7/7/2013
参考文献
1. 邵佩英著.分布式数据库系统及其应用.北京:科学出版社, 2000
2. 刘键，《分布式计算机系统》，人民邮电出版社，1990年.
3. Knapp E . Deadlock detection in distributed databases.ACM ComputSurv, 1987, 19(4): 303-328 4. GligorVD, Shattuck SH . On deadlock detection in distributed systems. IEEE Trans Software Eng, 1980, 6(5): 435–440 5.RoeslerM, BurkhardWA, CooperKB. Efficient deadlock resolutionfor lock-based concurrency control schemes. In: Proceedings of the 8th International onference on Distributed Computing Systems, San Jose, California, June 13–17, 1988. IEEE-CS Press, 1988, 224-233
7/7/2013
1 超时法
超时法就是一个事务的等待时间如果超过了规定的时限, 就认为发生了死锁。
在该算法中，每个事务在发出一个新的操作请求前设置一 个超时。如果在超时结束以前，没有收到请求的操作已经 成功执行的确认信息，事务则认为它自己已经处于死锁同 时夭折自己。