面向环和结的分布式死锁检测算法研究

论文摘要

在分布式系统中,如果资源的分配与需求产生冲突,系统中可能发生死锁,这是一种无限阻塞状态:发生死锁的进程集合中的已经持有部分资源的进程在发出新的资源申请时,发现被申请的资源正在被这个集合中的其它进程所占据,这个集合中的进程都将无限期地相互等待资源被释放,从而导致系统运行陷入停滞。死锁可以在分布式系统设计之初就采取措施加以避免,但这样一来或者需要系统拥有足够多的资源,或者需要对进程的资源请求做出严格的限制,以运行时间的延长来换取不被锁住。所以避免方法要预知系统可能出现的各种运行状态,适用于进程的并发时间和规模相对固定的分布式系统,如机场的实时控制系统。而大多数分布式系统中的进程对资源的需求时间和规模是不确定的,避免算法无法应对所有的可能情况,此时可行的死锁处理方法是死锁的检测和解决。对分布式死锁检测算法的研究由来已久,根据进程对资源的需求条件不同,分布式计算可以被分为单资源模型、AND模型、OR模型以及AND-OR模型,这些模型的通用性逐渐增强,它们在系统等待图中所产生的死锁拓扑结构相应地表示单环、多环和结（后两种模型都为结）,学者们对各种算法的研究过程也是按着这个拓扑结构的顺序展开的。对每一种模型下发生的死锁,在算法研究中都出现了一些经典的死锁检测方法,如Mitchell和Merritt提出的单环检测算法,Chandy和Misra提出的环检测算法,Lee提出的结检测算法和Manivannan提出的通用检测算法等等。在我们看来,在已提出的算法中,为单环和多环检测所设计的算法可被归纳为资源管理节点相关（RD）和资源管理节点无关（RI）两类,而为结检测设计的算法可被归纳为起始点归约（IR）和中间结点归约（NR）两类。在对这些算法的分析中我们发现资源管理节点相关和资源管理节点无关类算法存在着检测效率不高,不能克服交叠环等缺陷,而起始点归约和中间节点归约类算法存在着算法过于复杂,不能适用于动态环境等缺陷。此外,已有算法的共性问题还包括不能容错,不能并发执行等缺陷,而这些缺陷或者在非形式化证明中被忽略,或者在性能模拟中被掩盖。本文所作的工作就是在分析已有算法不足的基础上,对现有的分布式死锁检测算法进行改进和创新。这些工作分为四个部分:1)在原有的资源管理节点相关和资源管理节点无关类算法的基础上,将单环死锁检测算法改进为仅与资源管理节点相关（RDO）的检测方法,将原来的算法的执行载体由进程管理节点或/和资源管理节点改为全部为资源管理节点,这样就大大化简了检测的执行步

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题背景
• 1.2 分布式算法的概念
• 1.2.1 分布式算法的定义
• 1.2.2 分布式算法需完善的问题
• 1.3 死锁的概念与处理
• 1.3.1 死锁的定义
• 1.3.2 死锁的表示方法
• 1.3.3 分布式系统死锁处理方法分析
• 1.4 分布式死锁检测算法研究现状
• 1.4.1 基本的分布式死锁检测方法
• 1.4.2 环检测算法
• 1.4.3 结检测算法
• 1.4.4 分布式死锁检测算法的研究方向
• 1.5 本文主要研究内容与结构
• 第2章 仅与资源管理节点相关的单环检测算法
• 2.1 分布式系统的基本框架
• 2.2 单资源模型的实现
• 2.3 经典的资源管理节点无关和资源管理节点相关算法描述
• 2.3.1 资源管理节点无关类算法--MM 算法
• 2.3.2 资源管理节点相关类算法--CH 算法
• 2.3.3 资源管理节点无关与资源管理节点相关方法在单环检测时的不足..
• 2.4 仅与资源管理节点相关算法
• 2.4.1 仅与资源管理节点相关算法的死锁检测
• 2.4.2 仅与资源管理节点相关算法例子
• 2.5 资源管理节点无关、资源管理节点相关与仅与资源管理节点相关算法的性能比较
• 2.5.1 仅与资源管理节点相关算法的理论性能分析
• 2.5.2 仿真平台简介
• 2.5.3 仿真结果比较
• 2.6 小结
• 第3章 双边发送的环检测算法
• 3.1 资源管理节点无关与资源管理节点相关方法在环检测时的不足
• 3.2 双边发送算法
• 3.2.1 资源管理节点的执行
• 3.2.2 进程管理节点的执行
• 3.2.2 一个双边发送算法检测实例
• 3.3 双边发送算法的正确性证明
• 3.3.1 活性证明
• 3.3.2 安全性证明
• 3.4 资源管理节点无关、资源管理节点相关与双边发送算法性能比较
• 3.4.1 双边发送算法的理论性能分析
• 3.4.2 AND 模型仿真平台
• 3.4.3 仿真结果比较
• 3.5 小结
• 第4章 快速结检测算法
• 4.1 结检测算法的相关工作
• 4.2 经典的起始点归约和中间节点归约算法
• 4.2.1 中间节点归约类算法--Kshemkalyani 算法
• 4.2.2 起始点归约类算法--Lee 算法
• 4.2.3 中间节点归约和起始点归约检测算法的不足
• 4.3 快速结检测算法
• 4.3.1 基本数据结构
• 4.3.2 基本执行
• 4.3.3 死锁检测
• 4.3.4 一个检测实例
• 4.4 算法正确性证明
• 4.5 性能分析与比较
• 4.6 小结
• 第5章 容错的死锁检测算法
• 5.1 不可靠的分布式系统--移动计算系统
• 5.2 现有算法在处理失效时的不足
• 5.3 基于动态等待图的通用死锁检测算法
• 5.3.1 不可靠的分布式系统的故障分类
• 5.3.2 不可靠的分布式系统模型
• 5.3.3 容错死锁检测算法
• 5.3.4 死锁解决
• 5.3.5 容错死锁检测算法的例子
• 5.4 算法正确性证明
• 5.4.1 静态等待图的活性条件和安全性条件
• 5.4.2 动态等待图的活性条件
• 5.5 新算法的性能评价
• 5.6 小结
• 结论
• 参考文献
• 攻读博士学位期间发表的学术论文
• 哈尔滨工业大学博士学位论文原创性声明
• 哈尔滨工业大学博士学位论文使用授权书
• 哈尔滨工业大学博士学位涉密论文管理
• 致谢
• 个人简历