A True O(1) Parallel Deadlock Detection Algorithm for Single-Unit Resource Systems and Its Hardware Implementation

Due to rapid technology advance, Multiprocessor System-on-Chips (MPSoCs) are likely to become commodity computing platforms for embedded applications. In the future, it is possible that an MPSoC is equipped with a large number of processing elements as well as on-chip resources. The management of these faces many challenges, among which deadlock is one of the most crucial issues. This paper presents a novel hardware-oriented deadlock detection algorithm suitable for current and future MPSoCs. Unlike previously published methods whose runtime complexities are often affected by the number of processing elements and resources in the system, the proposed algorithm leverages specialized hardware to guarantee O(1) overall runtime complexity. Such complexity is achieved by: 1) classifying resource allocation events; 2) for each type of events, using hardware to perform a set of specific detection and/or preparation operations that only takes constant runtime; and 3) updating necessary information for multiple resources in parallel in hardware. We implement the algorithm in Verilog HDL and demonstrate through simulation that each algorithm invocation takes at most four clock cycles.     

A Novel Parallel Deadlock Detection Algorithm and Hardware for Multiprocessor System-on-a-Chip

Given the projected dramatic increase in the number of processors and resources in a system-on-a-chip, a quadratic increase in the likelihood of deadlock is predicted due to complex system behavior. To deal with this issue, we here present a novel parallel hardware-oriented deadlock detection algorithm with O(l) deadlock detection and 0(min(m,n)) preparation, where m and n are the numbers of processes and resources, respectively. Our contributions are (i) the first O(l) deadlock detection hardware implementation and (ii) a new algorithmic method of achieving 0(min(m,n)) overall run-time complexity. We implement our algorithm in Verilog HDL and demonstrate that deadlock detection always takes only two clock cycles regardless of the size of a system (i.e., m and n).     

A Novel O(1) Deadlock Detection Methodology for Multiunit Resource Systems and Its Hardware Implementation for System-on-Chip

This article describes a novel parallel Multi-unit resource Deadlock Detection Algorithm (MDDA) and its hardware implementation (MDDU). The contributions are (i) the first O(1) hardware deadlock detection, (ii) reduced O(min(m, n)) preparation, where m and n are the number of processes and resources, respectively, and (iii) support for multi-unit resources. O(min(m, n)), previously O(m×n), is achieved by performing all the searches for sink nodes for each and every resource in parallel in hardware over two matrices representing resource allocations as well as other auxiliary matrices. MDDU provides a fast and deterministic deadlock detection mechanism for Multiprocessor System-on-Chips (MPSoCs), which we predict will become prevalent in the near future in system designs. Our experiments demonstrate that MDDU always takes two clock cycles to detect deadlock regardless the size of the system. Lastly, the MPSoC area overhead due to MDDU is small, approximately 0.024 percent for MDDU16x16 on our example MPSoC.     

基于SUIF2的静态死锁检测方法研究

死锁是并发程序中常见的错误之一,且由于并发程序运行的不确定性使得死锁难以检测。针对该问题,通过对C多线程程序死锁的分析,提出了一种基于SUIF2的静态死锁检测方法,设计了基于SUIF2的C多线程程序静态死锁检测的框架结构和锁集分析算法。最后通过一个实例说明了该检测方法的有效性。     

Detecting and resolving deadlocks in mobile agent systems

Mobile agents environment is a new application paradigm with unique features such as mobility and autonomy. Traditional deadlock detection algorithms in distributed computing systems do not work well in mobile agent systems due to the unique feature property of the mobile agent. Existing deadlock detection and resolution algorithms in mobile agent systems have limitations such as performance inefficiency and duplicate detection/resolution when multiple mobile agents simultaneously detect/resolve the same deadlock. To address these problems, we propose an improved deadlock detection and resolution algorithm that adopts priority-based technique and lazy reaction strategy. The priority-based technique aims to ensure that there is only one instance of deadlock detection and resolution, and it also helps reduce mobile agent movement and data traffic together with the lazy reaction strategy. The liveness and safety properties of the proposed algorithm are proved in this paper. Theoretical analysis and experimental results show that the proposed algorithm provides better performance in terms of agent movement, data traffic, and execution time.     

对角网格中的无死锁自适应路由算法

网格是多计算机中应用广泛的互连结构,提出了一种新的互连结构－对角网格。并在这种结构上提出了一类自适应无死锁的路由算法－负优先算法,证明了此算法的无死锁性。对角网格是可平面图,其结构简单,可扩充性非常好。负优先自适应路由算法的突出优点是对硬件逻辑要求简单,无须增加虚拟通道即可达 死锁和自适应。     

A Two-Level Distributed Detection Algorithm of AND/OR Deadlocks

Numerous algorithms on distributed deadlock detection in distributed systems have been proposed for various deadlock models such as the AND model, OR model, and AND/OR model. This paper describes a new distributed algorithm for the AND/OR model by two levels of deadlock detection procedures. In every deadlock model, the existence of a cycle in a wait-for graph is a necessary condition. At the first level of our algorithm, a wait-for cycle is detected with a very simple operation. If no cycle is found, a deadlock does not exist. In this level, deadlocks consisting of AND-requested nodes are detected, and for the cycle of AND- and OR-requested nodes, an initiator is elected and the second-level algorithm is initiated by the initiator. The second-level algorithm uses the deadlock detection method of Herman and Chandy, but the communication cost is reduced even in the worst case because the second-level operation can be initiated by only qualified initiators.     

容错的分布式系统通用死锁模型检测解除算法

分布式系统技术为采用低成本购建高性能系统提供了有效的途径,但是由于资源的分配与需求可能产生冲突,造成系统中发生死锁,导致系统运行陷入停滞.在不可靠的分布式系统中,故障会干扰正常的死锁检测,但现有的死锁检测算法不具有容错功能.对失效形式进行了归类,提出一个容错的死锁检测解除算法.算法建立在通用的AND-OR模型基础上,采用扩散计算和集中规约方式,不仅能够检测到死锁,而且能给出死锁环的全部成员.若死锁拓扑处于静态且为环状,算法的消息复杂度的上限为e n-1,时间复杂度为d,其中e为死锁等待图中边的个数,n和d为构成死锁环的节点的个数,分析表明算法性能等于或优于同类算法.     

一种基于移动Agent技术的分布式死锁检测算法

死锁的处理长期以来一直是分布式系统的研究重点,已有许多成熟算法.随着网络技术的发展,越来越多的客户和资源可在网络中自由移动,这种可移动性使得传统算法面临了新的挑战.在这种新的应用背景下,本文结合移动Agent技术,提出了一种分布式系统死锁检测和解除算法：Agent Guard.该算法使用一个移动Agent,使其遵循一定的路线算法在各个站点间移动来收集资源请求和分配信息并进行分析,从而发现并解除死锁.模拟实验证明,A-gent Guard算法能取得较短的死锁持续时间,较小的伪死锁率,且网络的通信复杂度也有降低.     

Performance analysis of distributed deadlock detection algorithms

The paper presents a probabilistic performance analysis of a deadlock detection algorithm in distributed systems. Although there has been extensive study on deadlock detection algorithms in distributed systems, little attention has been paid to the study of the performance of these algorithms. Most work on performance study has been achieved through simulation but not through an analytic model. Min (1990), to the best of our knowledge, made the sole attempt to evaluate the performance of distributed deadlock detection algorithms analytically. Being different from Min's, our analytic approach takes the time-dependent behavior of each process into consideration rather than simply taking the mean-value estimation. Furthermore, the relation among the times when deadlocked processes become blocked is studied, which enhances the accuracy of the analysis. We measure performance metrics such as duration of deadlock, the number of algorithm invocations, and the mean waiting time of a blocked process. It is shown that the analytic estimates are nearly consistent with simulation results     

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.     

Deadlock Models and a General Algorithm for Distributed Deadlock Detection

This paper deals with the problem of deadlock detection in asynchronous message passing systems in a system model that covers unspecified receptions and non-FIFO channels. It presents a hierarchy of deadlock models and deadlock detection problems. It abstracts deadlocks by a general deadlock model that has the same modeling power as the OR-AND model; however, it has much concise expressive power. An abstract general definition of deadlocks in distributed systems is presented that defines deadlocks independently of the underlying deadlock model. This formulation can be used to design a single distributed deadlock detection algorithm which uniformly addresses all deadlocks in the context of various request models such as AND, OR, AND-OR, and k-out-of-n requests. A simple generalized deadlock detection algorithm that uses a circulating token is presented to illustrate the concept. The algorithm is formally described and proven correct. Moreover, possible refinements of the basic solution concerning improvements of token routing and parallel implementation are outlined and evaluated. Extensions to individual and global termination issues are also addressed. Since the proposed deadlock detection algorithm is designed around the abstract definition of deadlocks, it has some very favorable features.     

A deadlock recovery strategy for unified automated material handling systems in 300 mm wafer fabrications

A key issue emerging from the unified automated material handling systems (UAMHSs) in 300 mm wafer fabrications is the system deadlock. This paper addresses the deadlock recovery strategy of unified automated material handling systems (UAMHSs) with limited buffers. A formal model for UAMHSs deadlock detection is proposed. Sufficient conditions for system deadlocks based on actual UAMHS characteristics are defined along with a novel deadlock recovery strategy. Moreover, an effective heuristic algorithm is proposed for parallel resolving UAMHS deadlocks. The performances are evaluated in simulation by monitoring indexes reflecting efficiency of the material handling system. Results of the simulation experiments show that the novel deadlock recovery strategy is superior to the benchmark strategy in reducing deadlock time and improving tools’ utilization. Furthermore, the proposed algorithm features real-time operation and large scale cases, and is suitable for practical applications.     

基于资源等待图的死锁检测算法

死锁是操作系统、数据库系统以及通信网络中经常出现的现象.分析了使用资源分配图和进程等待图完成死锁检测的不足,提出了资源等待图的概念,并给出了基于资源等待图进行死锁检测的方法,该算法能够完成当资源类含有多个实例时的死锁检测.     

Deadlock detection in distributed database systems: a new algorithm and a comparative performance analysis

This paper attempts a comprehensive study of deadlock detection in distributed database systems. First, the two predominant deadlock models in these systems and the four different distributed deadlock detection approaches are discussed. Afterwards, a new deadlock detection algorithm is presented. The algorithm is based on dynamically creating deadlock detection agents (DDAs), each being responsible for detecting deadlocks in one connected component of the global wait-for-graph (WFG). The DDA scheme is a “self-tuning” system: after an initial warm-up phase, dedicated DDAs will be formed for “centers of locality”, i.e., parts of the system where many conflicts occur. A dynamic shift in locality of the distributed system will be responded to by automatically creating new DDAs while the obsolete ones terminate. In this paper, we also compare the most competitive representative of each class of algorithms suitable for distributed database systems based on a simulation model, and point out their relative strengths and weaknesses. The extensive experiments we carried out indicate that our newly proposed deadlock detection algorithm outperforms the other algorithms in the vast majority of configurations and workloads and, in contrast to all other algorithms, is very robust with respect to differing load and access profiles. Received December 4, 1997 / Accepted February 2, 1999     

一种基于依赖分析的并发程序潜在死锁检测算法

死锁是并发程序特有的一种运行时错误,由于并发程序在执行时的不确定性,死锁的检测和定位是非常困难的.本文提出了一种基于依赖分析的并发程序潜在死锁检测算法,该算法是一种静态分析算法,能检测并发程序中是否存在潜在死锁,并能定位死锁发生时各线程可能被挂起的语句节点.本文给出了算法的形式化定义和时间复杂度分析,实验测试结果表明算法是正确且有效的.     

A deadlock detection interface to a commercial simulation language

In this research, issues related to deadlock detection in discrete event simulation models and the feasibility of interfacing a deadlock detection algorithm to a commercial simulation language have been explored. For the purpose of this research, a deadlock detection algorithm has been designed, developed and interfaced to the SIMAN commercial simulation language. Both the algorithm and the interface have been validated using a set of sample scenarios. The details of the deadlock detection algorithm, the interface to the chosen commercial simulation language and the validation scenarios are discussed in this paper, along with the lessons learned and recommendations for future enhancements.     

Fast, centralized detection and resolution of distributed deadlocks in the generalized model

In the literature, only a few studies have been performed on the distributed deadlock detection and resolution problem in the generalized request model. Most of the studies are based on the diffusing computation technique where propagation of probes and backward propagation of replies are required to detect deadlock. The replies carry the dependency information between processes for the initiator of the algorithm to determine deadlock. Since fast detection of deadlock is critical, we take a centralized approach that removes the need of backward propagation of replies, but sends the dependency information directly to the initiator of the algorithm. This enables reduction of time cost for deadlock detection to half of that of the existing distributed algorithms. The algorithm is extended to handle concurrent executions in order to further improve deadlock detection time, whereas the current algorithms focus only on a single execution. Simulation experiments are performed to see the effectiveness of this centralized approach as compared to previous distributed algorithms. It is found that our algorithm shows better results in several performance metrics especially in deadlock latency and algorithm execution time.     

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.