【作者】 程欣；

【导师】 杨孝宗；

【作者基本信息】 哈尔滨工业大学 ， 计算机系统结构， 2006， 博士

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

【Abstract】 During the running of distributed computing, deadlock would happen if the re-source allocation and requirement confliction occur. It is an infinite waiting state: a part of a process set which have held some resources send new resource requests to other resources, at the same time they find the requested resources have been held by another part of the same set of processes, all the processes are waiting each other for the holding resources releasing, then the system running stop.Deadlock can be overcome by avoiding method, while this method either re-quires the system possesses enough resources or assigns strict rules for the resource requirement of processes before in order to prolong the running time to get unblock-ing. So the avoid method need to know the total running states of the system, it is appropriate for the systems which have fixed concurrent running scale and time, such as the real-time control system of airport. While for most of the network-based dis-tributed systems, resource requirement scale and time of the processes are uncer-tainty, the avoid method can not forecast all the possible states, therefore another deadlock resolve method, the deadlock detection method may be the better choice for distributed systems.Research about the deadlock detection method experienced a long time. Ac-cording to the resource requirement types of the processes, the distributed computa-tion models can be divided into single resource model, AND model, OR model and AND-OR model. Generalization of these models is stronger gradually and the dead-lock topologies of these models are single cycle, cycle and knot respectively. Dead-lock detection algorithm is developed gradually in the same order of the resource re-quire models. Some classical algorithms were proposed in last decades, such as the single cycle detection algorithm proposed by Mitchell and Merritt, the cycle detec-tion algorithm proposed by Chandy and Misra, the knot detection algorithm proposed by Lee and the generalized algorithm proposed by Manivannan. In our opinion, the algorithms proposed for the single resource model and AND model can be reduced to the Resource node Dependent (RD) and the Resource node Independent (RI) meth-ods, and the algorithms proposed for the OR model and the AND model can be re-duced to the Initial node Reduction (IR) and the Neutral node Reduction (NR) methods. Study on these methods show that the RD and RI methods have the defi-ciencies such as low detection efficiency and incorrect resolution for the overlapped cycles, and the IR and NR methods have the deficiencies such as complication and useless in dynamic environment. Furthermore, there are still common problems exist更多还原