文档介绍：分布式数据库死锁检测算法研究
重庆大学
硕士学位论文
分布式数据库死锁检测算法研究
姓名:陈鹏
申请学位级别:硕士
专业:计算机系统结构
指导教师:李相枢
20040512中文摘要
摘要
分布式数据库的死锁检铡是并发控制领域的一个重要问题。
在分布式系统研究领域中,死锁条件通常是根据资源请求方式来确定的。根
据分布式数据库中事务发出不同的资源请求方式,现有的分布式数据库死锁检测
算法通常针对某种资源请求模型而提出。分布式数据库不同于一般分布式系统,
其死锁条件不仅与资源请求方式相关,而且与资源授予方式相关。同时,现有的
分布式数据库死锁检测算法通常假设系统采用排它锁模式或共享/排它锁模式,而
忽略了分布式数据库系统中普遍应用的多锁模式,使得算法无法有效应用于分布
式数据库系统。本文将详细介绍分布式事务、并发控制和资源请求模型,总结出
分布式数据库系统的通用死锁条件。
分布式数据库死锁检测算法主要分为集中式、层次式和分布式。集中式和层
次式算法通常正确性较高,但消息通讯量太大。与之相反,分布式算法通常消息
通讯量较小,但正确性较低。由于分布式算法更为灵活、有效,论文将深入研究
分布式算法,并提出~种新的分布式死锁检测算法~基于和改进探针的死
锁检测算法。该算法是全局状态检测方法算法和基于探针的算法的结合;
算法提出了一种新的探针传递规则,当事务结点收到第一个探针包括启动探针
时,结点将接受继续传播并记录探针:当事务结点在接受某个探针后再收到
其它探针时,结点将拒绝停止传播该探针,并记录下探针对被拒绝的探针,
接受的探针。算法对传统探针进行了扩展,引入了扩展探针、探针对、探针簇等
概念,建立了新的死锁判断机制,如果存在一个探针路径,??,且
是的基,那么中存在环。算法通过对探针对序列的合并计算,减少
之间全局信息的传送。由此该算法可以有效地避免假死锁和幻象死锁,避免
死锁无法被检测到的情形,降低消息量。
论文对该算法进行了正确性分析、性能分析,并通过模拟实验检验了算法。
关键词:分布式数据库,死锁检测,等待图,扩展探针,探针对,探针簇,死锁
检测代理,多锁模式英文摘要蛐
.
,., .
,
,’
. . ,
.. .
,.
.
,
,
,.
,
每 .
.,
,,
? , .
, .?,? 百
,
?,??, 豇?.
,锄 .
.,
重庆大学硕士学位论文
.
:
, ,?
,,
,
,
绪论
绪论
.研究意义与目的
伴随着网络技术的不断成熟,商业应用系统逐步发展为分布式体系结构,这种体系结构的底层数据库最初采用的仍然是集中式数据库系统。为了提高数
据本
地访问能力,降低网络通讯量,人们发现必须对应用的共享数据资源进行分
布式
管理,由此诞生了分布式数据库系统。分布式数据库系统是数据库技术和网
络技
术相结合的产物,而不仅仅是两者简单的组合。
由于分布式数据库系统强大的事务处理能力和数据管理能力,越来越多的企业采用分布式数据库系统实现企业管理数据化。随着企业的不断发展,分布
式数
据库系统变得相当庞大,需要支持大量的并发事务处理。目前各种大型分布式数
据库系统在并发控制策略上普遍采用了封锁技术。由于大量用户频繁地并行地访
问数据,对同一资源的冲突操作必然存在,这就可能导致分布式死锁的产生。
如果系统中存在死锁而不能被及时检测到并加以解决,那么处于死锁的那些
事务将永远处于阻塞状态,应用将无法正常结束,甚至,随着死锁存在时问的延
长,将导致更多事务的阻塞,最终使系统陷于瘫痪。因此及时检测出死锁是分布
式数据库系统必须加以解决的重要现实问题。同时,我们知道,死锁问题并不是
数据库系统所特有的,任何资源共享系统都可能存在死锁问题。分布式数据库系
统作为一种典型的资源共享系统,对其死锁检钡的研究,可以为其它系统的死锬
检测研究提供一定的参考价值。
由于分布式死锁检测方法比集中式和层次式检测方法具有更高的灵活性和有
毅性。我们期望在前人研究的基础上,继续深入对分布式死锁检测方法的研究。
目前,分布式死锁检损研究中的主要问题有:
根据应用的不同需求,应用所发出的资源请求方式不尽相同。现有的资源请
求模型包括了:单一资源模型、模型、模型、.模型及..
模型。针对不同的资源请求模型,相应的死锁条件各有区别。尽管很多算法的作
者指出研究的算法是应用于分布式数据库系统的,但实际上是