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

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

青少年机器人足球比赛死锁解除的模糊数学法

青少年机器人足球比赛中,常常会出现死锁。目前,一般采用手工方法解除死锁,这影响了比赛的智能性与观赏性。论文对模糊系统做了概述,分析了足球机器人运动死锁的特征,定义了模糊系统的输入输出变量,以及变量在论域上的模糊集合;建立了双层模糊系统,获取了足球机器人比赛中运动死锁发生时的数据,并将模糊系统对这些数据的处理结果与机器人足球专家对相应死锁的处理结果进行了比较和分析。     

二维协同工作空间的并发操作加锁协议

提出一种用于在二维工作空间中协同作业的并发操作加锁协议和相应的锁调度算法,协议采用悲观锁,以抽象的二维空间为并发操作的对象,支持任意锁粒度,具有无死锁性质．加锁协议和算法存一个实时分布式协同绘图系统中实现．协议的实现采用多Agent系统模型。将面向Agent的程序设计中Agent的情绪值的概念用于控制锁的释放和调度,支持并发操作者之间的主动协同和细粒度感知．     

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.     

Initial configuration dependence in a self-organizing robot

In this paper, we describe the dependence of an initial state in a self-organizing robot on an optimal structure configuration, where a “fractum” is used as a basic unit. Each robot operates on a genetic algorithm (GA) by itself, and all of them will produce a desired configuration. However, problems such as a deadlock state can happen depending on the initial configuration. A deadlock state means a state in which no robots can move because each robot moves autonomously. It is proved from simulations that a difference in the initial configuration can affect both the deadlock rate and the number of movements of fracta needed to obtain an optimal structure configuration. This work was presented, in part, at the Third International Symposium on Artificial Life and Robotics, Oita, Japan, January 19–21, 1998     

高层体系结构中时间管理算法研究及改进

不恰当的最大安全推进时间(GALT)计算方法会影响系统整体运行,严重情况下可能导致系统死锁,使整个系统仿真无法向前推进。为此,分析经典时间推进Frederick算法中可能出现死锁的情况,给出死锁出现的原因,并对死锁产生的原因进行论证,在此基础上,设计一种基于该算法的改进无死锁时间管理GALT计算算法。分析结果表明,改进算法可以有效解决GALT计算产生的死锁问题。     

Deadlock prevention in concurrent real-time systems

To meet consistency requirements found in concurrent applications, a process must be guaranteed that it will be able to use all resources in a set ofpassive resources (such as shared data structures). To provide predictable execution time required in real-time systems, a process also needs guaranteed access to at least one of a set ofactive resources (such as processors) associated with each passive resource. As such, a concurrent real-time-process has AND-OR resource requirements. If locking is used to provide exclusive access to resources, deadlock is possible since processes can request additional resources while holding other resources. Deadlock detection and recovery techniques and deadlock avoidance techniques typically involve preempting resources or terminating processes, and are therefore inappropriate for real-time systems that require the execution time of processes to be predictable. This paper describes a general resource request condition that we proveprevents deadlock in AND-OR systems. It also describes how we use this AND-OR deadlock prevention technique in a concurrent real-time system.This work is supported in part by the following grants: ONR N000014-89-J-1131 and ARO DAAG-29-84-k-0061.     

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

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

On-line collision avoidance system for two PTP command-based manipulators with distributed controller

This research aims to solve online collision avoidance problem of two manipulators with independent controller. Since industrial robot controller is a closed commercial system, trajectory generation part of robot controlling is always proprietary or unknown. Thus, this paper proposes a collision avoidance system of two manipulators which are controlled by point-to-point (PTP) commands, in condition that the internal of robot controller is unknown and unchangeable. Based on this condition, collision avoidance is supposed to be realized by online scheduling of these PTP controlling commands. This paper proposes the collision avoidance method that assumes the three-dimensional common workspace between two manipulators can be partitioned into many subregion elements. And with managing these subregion elements, which are occupied by robot motion, PTP commands are scheduled to adjust execution timing for collision avoidance. A deadlock problem caused by the partition of the workspace is also taken into consideration in the method. And the effectiveness and efficiency of the method have been verified by simulations and experiments.     

A comparative performance analysis of deadlock avoidance control algorithms for FMS

A deadlock condition for flexible manufacturing systems is characterized by a set of parts, which have been processed but cannot be discharged by a set of machines or buffers. To avoid such problems, it is necessary to adopt suitable control policies which limit the resource allocation in the system, thus affecting the overall system performance. In the present work, we address the problem of evaluating and comparing the performance of deadlock avoidance control policies applied to FMS. The problem is discussed for both untimed and timed models, and for models both with and without deadlock avoidance control policies. Different control algorithms, among the most common in the literature, have been considered. Imperfect deadlock avoidance control policies are also considered. In addition, some indices are proposed to assess the structural properties of FMS with respect to deadlock occurrence and their performance. Two different application examples are analyzed, with the help of a commercial simulation package. Finally, an adaptive algorithm which can learn from system evolution to avoid deadlocks is illustrated.     

死锁的PETRI NETS模型

本文给出了操作系统(OS)的一种基于Petri网的形式化模型,由此把死锁问题转化为线性代数问题。我们得到了OS中死锁存在的充要条件,以及一种消除系统中所有的死锁、保证系统正常工作的最优化方法。特别是对于分布式OS,我们大大改进了以往的一些处理死锁的方法,最后还通过举例进行了说明。     

数据库并发操作的可串行化调度与死锁检测算法

封锁与可串行化调度是数据库并发操作采取的两种主要措施。判断一个调度是否可串行化调度的最有效方法是两段锁协议。但是,一方面,事务遵守两段锁协议只是可串行化调度的充分条件而不是必要条件;另一方面,遵守两段锁协议的事务仍可能发生死锁。文中给出了一种算法,利用该算法,不仅可判断出一个调度是否为可串行化调度,而且可判断出该调度是否会发生死锁。     

Proof Pearl: A Formal Proof of Dally and Seitz’ Necessary and Sufficient Condition for Deadlock-Free Routing in Interconnection Networks

Avoiding deadlock is crucial to interconnection networks. In ’87, Dally and Seitz proposed a necessary and sufficient condition for deadlock-free routing. This condition states that a routing function is deadlock-free if and only if its channel dependency graph is acyclic. We formally define and prove a slightly different condition from which the original condition of Dally and Seitz can be derived. Dally and Seitz prove that a deadlock situation induces cyclic dependencies by reductio ad absurdum. In contrast we introduce the notion of a waiting graph from which we explicitly construct a cyclic dependency from a deadlock situation. Moreover, our proof is structured in such a way that it only depends on a small set of proof obligations associated to arbitrary routing functions and switching policies. Discharging these proof obligations is sufficient to instantiate our condition for deadlock-free routing on particular networks. Our condition and its proof have been formalized using the ACL2 theorem proving system.     

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

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

Deadlock-freedom in resource contentions

Summary The paper establishes two necessary and sufficient conditions for the absence of deadlock in resource contentions under the expedient allocation policy. Their equivalence is proved. One of these was discovered independently by Ibaraki and Kameda. The conditions are essentially the condition of the König-Hall Theorem for the existence of a system of distinct representatives. If there are no multiple resources the conditions simplify to the condition for acyclicity of hypergraphs.This work was sponsored by the Defense Advanced Research Projects Agency ARPA Order 3771 and monitored by the Office of Naval Research under Contract N00014-79-C-0597. It was carried out at the California Institute of Technology     

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.     

A generalized deadlock predicate

Satisfiability of the deadlock predicate constructed by the semaphore invariant method is a necessary condition for total deadlock in PV programs. Clarke (1980) has developed a technique, based on a view of resource invariants as fixed points of a functional, for constructing a deadlock predicate such that satisfiability is a necessary and sufficient condition for total deadlock. We describe a technique for synthesizing a generalized deadlock predicate such that satisfiability is a necessary and sufficient condition for both total and partial deadlock. Our method constructs a strongest resource invariant using Clarke's fixed point functional. We then use this strongest resource invariant and a predicate transformer to construct a generalized deadlock predicate.     

多计算机互连网通信中关于死锁问题的一种理论

如何获得死锁而且通信性能良好的选路算法始终是人们十分关心的问题。本文提出了纯分流点的概念并证明了选路算法无死锁的充要条件，从理论上解决了死锁关系问题，为死锁的判定，消除和设计无死锁的算法提供了有力的依据。     

Sufficient condition for a communication deadlock and distributeddeadlock detection

The necessary and sufficient condition for deadlock in a distributed system and an algorithm for detection of a distributed deadlock based on the sufficient condition are formulated. The protocol formulated, checks all wait-for contiguous requests in one iteration. A cycle is detected when a query message reaches the initiator. A wait-for cycle is only the necessary condition for the distributed deadlock. A no-deadlock message is expected by the query initiator to infer a deadlock-free situation if at least one wait-for cycle is present. A no-deadlock message is issued by a dependent (query intercessor) that is not waiting-for. No no-deadlock message implies a deadlock, and processes listed in the received query messages are the processes involved in a distributed deadlock. Properties of the protocol are discussed. The authors show that a replication of a requested higher-priority (or older) process can prevent a distributed deadlock (in a continuous deadlock treatment). A replication is shown to recover (in a periodical deadlock handling) a sequence of processes from an indefinite wait-die scheme     

一类FMS的最佳活Petri网模型的综合

利用Petri网为一类柔性制造系统建模,并讨论避免系统死锁问题.通过Petri网模 型的结构分析,证明了系统产生死锁的一个充分必要条件.给出了避免死锁的最佳控制器,它 可以通过给系统的Petri网模型增加一些新的位置与相应的弧来实现.从而导出了这类制造 系统的最佳活Petri网模型.