On Deadlock Detection in Distributed Systems

A hierarchically organized and a distributed protocol for deadlock detection in distributed databases are presented in [1]. In this paper we show that the distributed protocol is incorrect, and present possible remedies. However, the distributed protocol remains impractical because "condensations" of "transaction-wait-for" graphs make graph updates difficult to perform. Delayed graph updates cause the occurrence of false deadlocks in this as well as in some other deadlock detection protocols for distributed systems. The performance degradation that results from false deadlocks depends on the characteristics of each protocol.     

FC3D: flow control-based distributed deadlock detection mechanism for true fully adaptive routing in wormhole networks

Two general approaches have been proposed for deadlock handling in wormhole networks. Traditionally, deadlock-avoidance strategies have been used. In this case, either routing is restricted so that there are no cyclic dependencies between channels or cyclic dependencies between channels are allowed provided that there are some escape paths to avoid deadlock. More recently, deadlock recovery strategies have begun to gain acceptance. These strategies allow the use of unrestricted fully adaptive routing, usually outperforming deadlock avoidance techniques. However, they require a deadlock detection mechanism and a deadlock recovery mechanism that is able to recover from deadlocks faster than they occur. In particular, progressive deadlock recovery techniques are very attractive because they allocate a few dedicated resources to quickly deliver deadlocked messages, instead of killing them. Unfortunately, distributed deadlock detection is usually based on crude time-outs, which detect many false deadlocks. As a consequence, messages detected as deadlocked may saturate the bandwidth offered by recovery resources, thus degrading performance. Additionally, the threshold required by the detection mechanism (the time-out) strongly depends on network load, which is not known in advance at the design stage. This limits the applicability of deadlock recovery on actual networks. We propose a novel distributed deadlock detection mechanism that uses only local information, detects all the deadlocks, considerably reduces the probability of false deadlock detection over previously proposed techniques, and is not significantly affected by variations in message length and/or message destination distribution.     

A distributed deadlock resolution algorithm for the AND model

Previous proposals for Distributed Deadlock Detection/Resolution algorithms for the AND model have the main disadvantage of resolving false deadlocks, that is, nonexisting or currently being resolved deadlocks. This paper provides an algorithm free of false deadlock resolutions, A simple specification for a safe deadlock resolution algorithm is introduced, and the new distributed solution is developed in a hierarchical fashion from its abstract specification. The algorithm is probe-based, uses node priorities, and coordinates the actions of resolvers so that false deadlocks are not resolved. The solution is formally proven correct by using the input-output Automata Model. Finally, a study about the liveness of the algorithm is provided     

A cost-effective approach to deadlock handling in wormhole networks

Wormhole networks have traditionally used deadlock avoidance strategies. More recently, deadlock recovery strategies have begun to gain acceptance. In particular, progressive deadlock recovery techniques allocate a few dedicated resources to quickly deliver deadlocked packets. Deadlock recovery is based on the assumption that deadlocks are rare; otherwise, recovery techniques are not efficient. Measurements of deadlock occurrence frequency show that deadlocks are highly unlikely when enough routing freedom is provided. However, networks are more prone to deadlocks when the network is close to or beyond saturation, causing some network performance degradation. Similar performance degradation behavior at saturation was also observed in networks using deadlock avoidance strategies. In this paper, we take a different approach to handling deadlocks and performance degradation. We propose the use of an injection limitation mechanism that prevents performance degradation near the saturation point and, at the same time, reduces the probability of deadlock to negligible values. We also propose an improved deadlock detection mechanism that uses only local information, detects all deadlocks, and considerably reduces the probability of false deadlock detection over previous proposals. In the rare case when impending deadlock is detected, our proposal consists of using a simple recovery technique that absorbs the deadlocked message at the current node and later reinjects it for continued routing toward its destination. Performance evaluation results show that our new approach to handling deadlock is more efficient than previously proposed techniques     

A safe algorithm for resolving OR deadlocks

Deadlocks in the OR model are usually resolved by aborting a deadlocked process. Prior algorithms for the same model sometimes abort nodes needlessly wasting computing resources. This paper presents a new deadlock resolution algorithm for the OR model that satisfies the following correctness criteria: (Safety) the algorithm does not resolve false deadlocks; (Liveness) the algorithm resolves all deadlocks in finite time. The communication cost of the algorithm is similar to that of previous nonsafe proposals. The theoretical cost has been validated by simulation. In addition, different algorithm initiation alternatives have been analyzed in order to reduce the latency of deadlocks.     

OpenMP Fortran程序中死锁的静态检测

与BARRIER相关的死锁是导致OpenMP程序失效的重要隐患之一.对该类隐患的静态检测有助于在OpenMP程序运行之前提高其正确性.为了便于检测,将这种死锁分为两类.借助搜索与数据流分析分别按照存在性规则和非一致性规则检测第1类和第2类死锁.扩展了传统的控制流图以表示OpenMP程序.对于每个检测到的死锁,通过回溯记录控制流图中相关的路径,并利用静态分支预测量化其严重程度.基于上述思想,实现了一个OpenMP Fortran程序中死锁的静态检测工具C-Checker.实验表明,该工具能有效地检测OpenMP程序中与BARRIER相关的死锁.     

PDR: A protocol for dynamic network reconfiguration based on deadlock recovery scheme

Dynamic network reconfiguration is described as the process of replacing one routing function with another while the network keeps running. The main challenge is avoiding deadlock anomalies while keeping limitations on packet injection and forwarding minimal. Current approaches which have a high complexity and as a result have a limited practical applicability either require the existence of extra network resources, or they will affect the network performance during the reconfiguration process. In this paper we present a simple, fast and efficient mechanism for dynamic network reconfiguration which is based on regressive deadlock recovery instead of avoiding deadlock. The mechanism which is referred to as PDR guarantees a deadlock-free reconfiguration based on wormhole switching. In PDR, a particular approach is taken to handle both deadlocks and performance degradation. We propose the use of a packet injection restriction mechanism that prevents performance degradation near the saturation by controlling the network traffic. Further, in this approach, to accurately detect deadlocks, the deadlock detection mechanism is implemented and also improved by using only the local information, thereby considerably reducing false deadlock detections. In the rare cases when deadlocks are suspected, we propose a new technique that absorbs the deadlocked packet at the current node instead of dropping deadlocked packets and re-injects it later into the network. The main advantage of this method is its simplicity and also it does not require any additional buffers in intermediate nodes to handle deadlocks. It requires only some buffer space in the local node to temporarily hold the deadlocked packets removed from the network. Evaluating results reveal that the mechanism shows substantial performance improvements over the other methods and it works efficiently in different topologies with various routing algorithms.     

死锁检测工具的能力分析与综合应用

并发软件运行的不确定性使得死锁检测十分困难。现有的工作集中在使用分析、验证或测试的单一途径来检测死锁。通过分析现有工具的死锁检测能力,提出了综合使用工具的死锁检测方法。同时根据分析、验证和测试途径的不同特点,给出了评估工具检测结果的度量方法。实验结果显示了该方法的有效性。     

A one-phase algorithm to detect distributed deadlocks in replicateddatabases

Replicated databases that use quorum-consensus algorithms to perform majority voting are prone to deadlocks. Due to the P-out-of-Q nature of quorum requests, deadlocks that arise are generalized deadlocks and are hard to detect. We present an efficient distributed algorithm to detect generalized deadlocks in replicated databases. The algorithm performs reduction of a distributed wait-for-graph (WFG) to determine the existence of a deadlock. If sufficient information to decide the reducibility of a node is not available at that node, the algorithm attempts reduction later in a lazy manner. We prove the correctness of the algorithm. The algorithm has a message complexity of 2e messages and a worst-case time complexity of 2d+2 hops, where e is the number of edges and d is the diameter of the WFG. The algorithm is shown to perform significantly better in both time and message complexity than the best known existing algorithms. We conjecture that this is an optimal algorithm, in time and message complexity, to detect generalized deadlocks if no transaction has complete knowledge of the topology of the WFG or the system and the deadlock detection is to be carried out in a distributed manner     

Asynchronous operations in distributed concurrency control

Distributed locking is commonly adopted for performing concurrency control in distributed systems. It incorporates additional steps for handling deadlocks. This activity is carried out by methods based on wait-for-graphs or probes. The present study examines detection of conflicts based on enhanced local processing for distributed concurrency control. In the proposed "edge detection" approach, a graph-based resolution of access conflicts has been adopted. The technique generates a uniform wait-for precedence order at distributed sites for transactions to execute. The earlier methods based on serialization graph testing are difficult to implement in a distributed environment. The edge detection approach is a fully distributed approach. It presents a unified technique for locking and deadlock detection exercises. The technique eliminates many deadlocks without incurring message overheads.     

Invariant-based verification of a distributed deadlock detectionalgorithm

It is argued that most previous proposals for distributed deadlock detection are incorrect because they have used informal/intuitive arguments to prove the correctness of their algorithms. Informal and intuitive arguments are prone to errors because of the highly complex nature of distributed deadlock detection/resolution algorithms. The priority-based probe algorithm for distributed deadlock detection and resolution of A.L. Choudhary et al. (1989) is corrected, and it is formally proven that the modified algorithm is correct (i.e., that it does detect all deadlocks and does not report phantom deadlocks). The proof technique is novel in that the authors first abstract the properties of the deadlock detection and resolution algorithm by invariants, and then show that the invariants imply the desired correctness of the algorithm     

基于锁增广分段图的多线程程序死锁检测

死锁是并行程序常见的缺陷之一,动态死锁分析方法根据程序运行轨迹构建锁图、分段图等模型来检测死锁.然而,锁图及其现有的各种变型无法区分同一循环中锁授权语句的多次执行,扩展锁图中记录的锁集无法捕捉线程曾经持有而又随后释放的锁信息,分段图无法刻画锁的获取和释放操作与线程启动操作耦合而导致的段间依赖关系,上述问题导致了多种死锁的误报.为解决上述问题,本文对已有的锁图和分段图模型进行改进,在锁图基础上扩充语句的执行时序信息,在分段图的基础上扩充锁的获取和释放信息,对段进行更细粒度地划分以建模锁对象导致的段间依赖关系;最终,在上述锁增广分段图与时序增广锁图的基础上,提出一种新的死锁检测方法.所提方法能有效消除前述各种误报,从而提高死锁检测的准确率.文中开发相应的原型系统,并结合多个程序实例对所提方法的有效性进行评估验证.     

A modified priority based probe algorithm for distributed deadlockdetection and resolution

A modified, priority-based probe algorithm for deadlock detection and resolution in distributed database system is presented. Various examples are used to show that the original priority-based algorithm, presented by M.K. Sinha and N. Natarajan (1985), either fails to detect deadlocks or reports deadlocks that do not exist in many situations. A modified algorithm that eliminates these problems is proposed. The algorithm has been tested through simulation and appears to be errorfree. The performance of the modified algorithm is briefly discussed     

Efficient detection and resolution of OR deadlocks in distributed systems

This paper proposes a distributed algorithm for resolving deadlocks under the OR request model. The algorithm builds a distributed spanning tree by propagating probes. An encoding scheme is devised to deduce the ancestor–descendant relationship between tree nodes, so that the initiator of the algorithm collects only non-tree edge information to detect deadlock, whereas the current algorithms require all the edge information for deadlock detection. The proposed algorithm resolves all deadlocks reachable from the initiator. Its performance in terms of number of messages and execution time is better than or comparable to that of the existing algorithms. We further showed through analytic evaluation that the suggested algorithm substantially shortens deadlock detection time.     

MPI同步通信顺序模型死锁静态检测算法

静态检测MPI程序同步通信死锁比较困难,通常需要建立程序模型。顺序模型是其他所有复杂模型的基础。通过一种映射方法将顺序模型转化为字符串集合,将死锁检测问题转化为等价的多队列字符串匹配问题,从而设计并实现了一种MPI同步通信顺序模型的静态死锁检测算法。该算法的性能优于通常的环检测方法,并能适应动态消息流。     

一种Java并发程序死锁动态检测的新方法

死锁是并发程序中最为常见的一类错误,直到现在并没有得到很好地解决.本文以Java并发程序为例,重点研究针对资源死锁较为有效的动态检测算法:根据并发程序的动态执行追踪信息,分析出加锁控制依赖关系,再根据死锁所应满足的条件在该依赖关系集上作适量演算便得到潜在死锁关系对.进一步地,结合线程间控制流图所反映的部分静态依赖关系,剔除假性死锁关系对,提高了计算结果的精度.该算法显著的特点是简单易于实现,且无需构造锁树或锁图等图形表示.     

On Concurrency Control in Multidatabase Systems with an Extended Transaction Model

A major concurrency control problem that we have to cope in multidatabase systems is the global deadlock detection and resolution problem. This detection must take into account the autonomy of local systems, which make impossible the visibility of the state of local transactions. A well-known approach to detect such deadlocks, called potential global deadlocks, is one based on the potential conflict graph (PCG) appropriate for the multidatabase transaction model with a global commit protocol. This classical transaction model is very constraining for applications manipulating great volumes of information, and where subtransaction terminations (commit or abort) of global transactions are not totally dependant. In this paper we present an effective potential global deadlock characterization, and an efficient potential global deadlock detection algorithm, in multidatabase systems with an extended transaction model more suited for such applications.     

Locking and Deadlock Detection in Distributed Data Bases

This paper descrbes two protocols for the detection of deadlocks in distributed data bases–a hierarchically organized one and a distributed one. A graph model which depicts the state of execution of all transactions in the system is used by both protocols. A cycle in this graph is a necessary and sufficient condition for a deadlock to exist. Nevertheless, neither protocol requires that the global graph be built and maintained in order for deadlocks to be detected. In the case of the hierarchical protocol, the communications cost can be optimized if the topology of the hierarachy is appropriately chosen.     

NECESSARY AND SUFFICIENT CONDITIONS FOR DEADLOCKS IN FLEXIBLE MANUFACTURING SYSTEMS BASED ON A DIGRAPH MODEL

As typical discrete event systems, flexible manufacturing systems have been extensively studied in such aspects as modeling, control and performance analysis. One important topic in the study of such systems is the deadlock detection, prevention and avoidance. In the past decade, two major modeling formalisms, i.e., Petri nets and digraphs, have been adopted for developing deadlock control policies for flexible manufacturing systems. In this paper, the concepts of slack, knot, order and effective free space of circuits in the digraph are established and used to concisely and precisely quantify the sufficient conditions for a system state to be live. Necessary conditions for this liveness is quantified for a special class of system states ‐ called evaluation states. The significance of the result is that the conditions are true for avoiding both primary deadlocks and impending deadlocks that are arbitrary steps away from a primary one, whereas only second level deadlocks have been studied in the literature. Examples are provided to illustrate the method.     

A partially distributed deadlock detection algorithm

In this paper, a partially distributed deadlock detection algorithm [PDDDA] with multiple outstanding requests is presented for use in distributed database systems. This algorithm allows a process to request many resources simultaneously and uses a central controller for detecting multisite deadlocks. The detection of local deadlocks and the maintenance of local deadlock information are performed at each of the local sites. This partially distributed algorithm alleviates the problem of congestion at the central controller in a centralized algorithm and needs fewer messages and smaller storage space than a fully decentralized algorithm. A set of criteria for comparing deadlock detection algorithms are also given and then used to compare PDDDA with a fully decentralized algorithm proposed by Isloor and Marsland.Research reported herein was supported by US Army CECOM, Ft. Monmouth, New Jersey, under Contract No. DAAB07-83-K-K542. The views, opinions, and/or findings contained in this paper are those of the authors and should not be construed as an official Deportment of the Army position, policy or decision.