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