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.     

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

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

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

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

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.     

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.     

A Polynomial Deadlock Avoidance Method for a Class of Nonsequential Resource Allocation Systems

This correspondence introduces a deadlock-avoidance algorithm for a class of manufacturing systems with the following characteristics: 1) Production orders are allowed to have assembly operations (which give the nonsequential nature to the resource allocation system model) but not disassembly operations, 2) the use of system resources must be conservative (resources are neither created nor destroyed), and 3) actions related to the granting of resources are controllable. The proposed solution represents a sufficient condition for a given system state to be safe and is based on an adaptation of the well-known Banker's approach for deadlock avoidance. The time complexity of the proposed solution is proved to be polynomial with the size of the Place/Transition net model     

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 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.     

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

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

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.     

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

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

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.     

Oracle数据库死锁问题研究

数据库是网络环境下多用户使用的共享资源,数据库在处理多线程大量数据存取过程中很可能出现死锁现象。文中介绍了Oracle数据库锁机制和死锁发生的原因,Oracle数据库检测死锁采用的相关视图。详细叙述了SQL语句检测死锁、死锁的定位方法和解决数据库死锁的方法。编写了在Linux环境中死锁检测脚本,模拟Oracle数据库死锁测试了脚本的正确性。实际应用表明该方法可以有效监测程序中的主要模块是否发生死锁,而且简单有效。     

基于常微分方程的死锁检测实验分析

用静态分析方法对并发程序进行死锁检测通常比较困难,其原因是会遇到状态空间爆炸问题.文中针对作者曾提出的一种可有效避免状态爆炸问题的死锁检测方法,进行进一步实验验证.该方法的基本框架是首先将表示并发系统的离散Petri网模型连续化,得到一种新的连续Petri网模型;在此基础上,建立系统的常微分方程模型;通过分析常微分方程组的解来检测系统中是否存在死锁.与传统方法不同点在于:该方法不需要遍历状态空问,而是分析一组常微分方程组的解.为了减少在求解常微分方程模型过程中的计算机系统的开销,作者还采取了一系列优化策略.哲学家进餐问题被用来说明死锁检测的方法.大量的实验结果说明作者所提出的方法有着较强的静态分析能力.作为副产品,这种分析方法还可以用来判定系统的有界性.     

Subsystems, time scales and multimodeling

Through a couple of naive examples the control theorists are invited to re-examine the role of modeling in the study of large scale dynamic systems. Instead of assuming the existence of ‘N diagonally dominant blocks’, it is possible to justify one strongly coupled slow core and N weakly coupled fast subsystems. This structure is exhibited with a physically meaningful choice of state variables. The controls are introduced following the recent concept of multimodeling.     

The Deadlock Problem: An Overview

Deadlock is a constant threat in terminal-oriented systems. This comprehensive study of deadlock-handling techniques introduces a method for on-line detection in distributed data bases.