On the Optimality of Randomized Deadlock Avoidance Policies

This paper revisits the problem of selecting an optimal deadlock resolution strategy, when the selection criterion is the maximization of the system throughput, and the system is Markovian in terms of its timing and routing characteristics. This problem was recently addressed in some of our previous work, that (i) provided an analytical formulation for it, (ii) introduced the notion of randomized deadlock avoidance as a generalization of the more traditional approaches of deadlock prevention/avoidance, and detection and recovery, and (iii) provided a methodology for selecting the optimal randomized deadlock avoidance policy for a given resource allocation system (RAS) configuration. An issue that remained open in the problem treatment of that past work, was whether the proposed policy randomization is essential, i.e., whether there exist any RAS configurations for which a randomized deadlock avoidance policy is superior to any other policy that does not employ randomization. The work presented in this paper establishes that for the basic problem formulation where the only concern is the (unconstrained) maximization of the system throughput—or the other typical performance objectives of minimizing the system work-in-process and mean sojourn time—randomization of the deadlock resolution strategy is not essential. However, it is also shown that, sometimes, it can offer an effective mechanism for accommodating additional operational constraints, like the requirement for production according to a specified product mix. Furthermore, the undertaken analysis provides an analytical characterization of the dependence of the aforementioned performance measures on the transition rates relating to the various events of the underlying state space, which can be useful for the broader problem of synthesizing efficient scheduling policies for the considered class of resource allocation systems.     

Deadlock Detection and Avoidance for Shared Logical Resources

Logical resources are defined as shared passive entities that can be concurrently accessed by multiple processes. Concurrency restrictions depend upon the mode or manner in which a process may manipulate a resource. Models incorporating these single unit resources can be used to analyze information locking for consistency and integrity purposes. Mode compatibility is defined and used to derive dead-lock detection and avoidance methods. These methods generalize well-known deadlock results for single unit resources by permitting greater concurrency while still guaranteeing data consistency. This model is applicable to the standard shared (read-only) and exclusive (read-write) access modes as well as a useful subset of those proposed in the CODASYL DBMS report.     

基于初等运动的多机器人避碰及死锁预防

该文以一实际应用为背景提出了多移动机器人避碰及死锁预防算法,该算法将机器人的运行环境形式化地描述为初等运动集、冲突图、总任务集及机器人作业集,利用集合论、图论的有关方法及技术实现了多机器人间的避碰与死锁预防。当机器人的运行环境改变时,只需要对相应的集合描述文件进行修改,而不用对程序做任何屐改动。算法的另一个特点是利用避碰算法巧妙地完成了死锁预防。仿真和实际运行证明了该算法高效可靠。     

分布式系统死锁的预防、避免和检测

分布式系统涉及到资源和数据的高度共享,从而可能引发死锁。分布式系统的死锁是由于资源和通讯产生的。从分布式系统死锁产生的条件,解决策略,以及分布式系统中死锁预防、避免和检测的各种算法进行了具体阐述。     

Generalized Algebraic Deadlock Avoidance Policies for Sequential Resource Allocation Systems

Currently, one of the most actively researched approaches regarding the design of deadlock avoidance policies for sequential resource allocation systems is based on concepts and techniques provided by the, so called, theory of regions, that addresses the broader problem of synthesizing PN models with prespecified behaviors. However, one limitation of the theory of regions and its aforementioned derivatives is that they cannot be applied when the target behavior has a nonconvex representation in the underlying state space. In this note, we show how this problem can be circumvented by appropriately generalizing the employed class of the candidate policies.     

Resource-Oriented Petri Net for Deadlock Avoidance in Flexible Assembly Systems

In many flexible assembly systems, base components are transported with pallets; parts to be mounted onto the base ones are transported by trays with no pallets. When an assembly operation is performed by using some parts in a tray but not all, the tray with the remaining parts still occupies a buffer space. In this way, an assembly/disassembly material flow is formed. In such a material flow, deadlock can occur both in the base component and part flow. Furthermore, the assembly operations can also result in a deadlock. Thus, it is a great challenge to tackle deadlocks in such processes. This paper models them using resource-oriented Petri nets. Based on the models, a deadlock control policy is proposed and proved to be computationally efficient and less conservative than the existing policies in the literature. An industrial case study is used to show the results.     

Routing Function and Deadlock Avoidance in a Star Graph Interconnection Network

In this paper the properties of paths in a star graph are investigated through the analysis of the corresponding star transposition tree. The general algebraic expression for all shortest paths between any two nodes (routing function) is found, and it is shown that every shortest path consists of a number of subpaths which can be combined in an arbitrary order or even mutually nested. Further, due to the known routing function the deadlock problem is solved using the method of virtual channels. A minimal deterministic routing algorithm is developed which recognizes the structure of the path by extracting subpaths and allows optimal adaptive management of virtual channels. Finally, based on the sufficient number of virtual channels, the minimal fully adaptive routing algorithm is suggested which offers an opportunity to reroute the message a number of times, while maintaining the shortest path between two nodes.     

An Improved Protocol for Deadlock and Livelock Avoidance Resource Co-allocation in Network Computing

A multitude of applications require simultaneous access to multiple kinds of resources scatted in distributed sites. This problem is known as resource co-allocation which has evolved as a hot topic in network computing. How to design a kind of high-performance protocol for deadlock and livelock avoidance resource co-allocation becomes a challenging problem. In this paper, we propose a new protocol OODP³ (Optimal ODP³) which is based on the currently popular protocol ODP³ (Order-based Deadlock Prevention Protocol with Parallel requests).OODP³ not only inherits the advantage of ODP³ but also guarantees the fulfillment of resource co-allocation within polynomial time. Theoretical proof is conducted to verify the correctness of OODP³. Experimental results also show that OODP³ achieves the better performance improvements than the existing deadlock and livelock avoidance protocol.     

Collision Avoidance by Using Space-Time Representations of Motion Processes

This paper handles the problem of collision avoidance in a multi-robot environment. To solve this problem, the motion processes of the mobile robots are modelled in space-time. Since the robots are autonomous and communication is non-deterministic, there is temporal uncertainty in addition to spatial uncertainty. The paper presents a method to model both uncertainty components in a homogeneous way. It is shown, that it is not sufficient to guarantee a spatial security distance between the robots. Distances in space-time and space-time vectors must be considered. The main result of this paper is a straightforward and efficient solution to the problem of collision avoidance between up to three mobile robots by applying a space-time displacement vector. The solution is based on space-time, which is a helpful view onto our world in relativity theory and quantum physics. Space-time methods are also very valuable in Robotics, especially for problems in dynamic environments and for motion coordination of mobile robots. Practical experiments with up to two robots, and simulations of up to three robots have been performed and are reported.     

分布式死锁检测算法中伪死锁率的研究和改进

死锁处理是分布式系统中的关键问题,其中处理死锁最主要的手段为死锁检测。在评价死锁检测算法性能时伪死锁率被视为一项重要指标,故降低伪死锁率对提高算法性能有着促进作用,而目前大多数算法改进对伪死锁率关注较少。本文阐述了伪死锁研究的意义,并对若干种死锁检测算法的伪死锁率进行研究和模拟实验,认为现有的死锁算法可分为两类:环内检测和环无关检测。并分别通过减少冗余消息和本地死锁解决两种改进方法来降低目前算法的伪死锁率,最终实验表明算法性能获得较大提高。     

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.     

Deadlock avoidance in flexible flow shops with loops

This paper presents a deadlock-avoidance scheme that was developed during the MASCADA Project—Esprit LTR Project 22728. The deadlock problem occurs in a car body painting shop. From this application, an abstract problem was derived for which a deadlock-avoidance method was developed. The paper presents the deadlock-avoidance scheme and its correctness proof. In addition, implementation issues are introduced and solutions are discussed.     

Memory Subsystems in High-End Routers

As Internet routers scale to support next-generation networks, their memory subsystems must also scale. Several solutions combine static RAM and dynamic RAM buffering but still have major scaling limitations. Using a parallel architecture and distributed memory-management algorithms with hybrid SRAM/DRAM improves buffering performance. The parallel hybrid SRAM/DRAM memory system is also work conserving, which is particularly important under light traffic conditions.     

选举策略在分布式系统死锁避免中的应用

将单机系统或集中式系统中的死锁避免策略移植到分布式需要面临并发性和冲突问题的解决。本文通过分析二阶段锁的机制,引入了一种应用选举策略来幽雅地解决分布式系统中死锁避免所碰到问题的算法。     

具有异维数子系统的切换系统稳定性分析

研究一类线性切换系统的稳定性问题.该类切换系统包含2个不同维数的线性子系统.首先根据原系统的结构,构造出它的比较切换系统;然后设计出比较系统的切换率,在保证每个线性子系统的被激活时间均大于某一数值τ(＞0)的情况下,构造出2个子系统的Lyapunov函数;随后利用线性矩阵不等式(LMI)的方法给出每个子系统渐近稳定的条件.进一步利用Lyapunov稳定性理论的方法,保证整个比较系统的渐进稳定性,进而给出了原切换系统达到渐近稳定的一个充分条件.最后,一个数值例子说明文中方法的有效性.     

Deadlock detection without wait-for graphs

Deadlock detection is an important service that the run-time system of a parallel environment should provide. In parallel programs deadlock can occur when the different processes are waiting for various events, as opposed to concurrent systems, where deadlock occurs when processes wait for resources held by other processes. Therefore classical deadlock detection techniques such as checking for cycles in the wait-for graph are unapplicable. An alternative algorithm that checks whether all the processes are blocked is presented. This algorithm deals with situations in which the state transition from blocked to unblocked is indirect, as may happen when busy-waiting is used.     

Deadlock detection in MPI programs

The Message‐Passing Interface (MPI) is commonly used to write parallel programs for distributed memory parallel computers. MPI‐CHECK is a tool developed to aid in the debugging of MPI programs that are written in free or fixed format Fortran 90 and Fortran 77. This paper presents the methods used in MPI‐CHECK 2.0 to detect many situations where actual and potential deadlocks occur when using blocking and non‐blocking point‐to‐point routines as well as when using collective routines. Copyright © 2002 John Wiley & Sons, Ltd.     

基于CEGAR偏序化简的并行程序死锁检测

针对并发程序的模型检测存在大量的冗余交互和严重的状态空间爆炸问题,提出以迁移标记系统为建模语言计算Persistent Set并完成偏序化简的算法。将算法和CEGAR算法结合起来,实现对并发C程序的并行死锁检测。结果证明该算法在减缓状态空间爆炸和模型验证的效率方面较以往的算法有所提高。