论文部分内容阅读
分布式数据库的死锁检测是并发控制领域的一个重要问题。在分布式系统研究领域中,死锁条件通常是根据资源请求方式来确定的。根据分布式数据库中事务发出不同的资源请求方式,现有的分布式数据库死锁检测算法通常针对某种资源请求模型而提出。分布式数据库不同于一般分布式系统,其死锁条件不仅与资源请求方式相关,而且与资源授予方式相关。同时,现有的分布式数据库死锁检测算法通常假设系统采用排它锁模式或共享/排它锁模式,而忽略了分布式数据库系统中普遍应用的多锁模式,使得算法无法有效应用于分布式数据库系统。本文将详细介绍分布式事务、并发控制和资源请求模型,总结出分布式数据库系统的通用死锁条件。分布式数据库死锁检测算法主要分为集中式、层次式和分布式。集中式和层次式算法通常正确性较高,但消息通讯量太大。与之相反,分布式算法通常消息通讯量较小,但正确性较低。由于分布式算法更为灵活、有效,论文将深入研究分布式算法,并提出一种新的分布式死锁检测算法——基于DDA和改进探针的死锁检测算法。该算法是全局状态检测方法(DDA算法)和基于探针的算法的结合;算法提出了一种新的探针传递规则,当事务结点收到第一个探针(包括启动探针)时,结点将接受并记录探针;当事务结点再次收到探针时,结点将拒绝(停止传播)该探针,并记录下探针对(被拒绝的探针,接受的探针)。算法对传统探针进行了扩展,引入了扩展探针、探针对、探针簇等概念,建立了新的死锁判断机制,如果存在一个探针路径{(Xi,Yi)}(1<=i<=n),且Yn是X1的基,那么WFG中存在环。算法通过对探针对序列的合并计算,减少DDA之间全局信息的传送。由此该算法可以有效地避免假死锁和幻象死锁,避免死锁无法被检测到的情形,降低消息量。论文对该算法进行了正确性分析、性能分析,并通过模拟实验检验了算法。