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

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

分布式系统死锁的Petri网分析

阐述了分布式系统中的死锁问题,采用Petri网对分布式系统中的死锁进行分析,给出了几种解决死锁的模型,并分析了这些模型的优缺点,指出了分析和解决死锁的一般方法.     

一个两段加锁不死锁的充分条件

两段加锁是分布式系统中最广泛使用的并发控制算法。该算法除实现较为复杂外，其致命弱点是容易产生死锁。本文在分析两段加锁产生死锁原因的基础上，给出了一个不会产生死锁的两段加锁方法的充分条件和构造性定理以及实现的方法。     

分布式系统死锁的Petri网分析

阐述了分布式系统中的死锁问题，采用Petri网对分布式系统中的死锁进行分析，给出了几种解决死锁的模型，并分析了这些模型的优缺点，指出了分析和解决死锁的一般方法。     

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

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

N个有限状态机的死锁和死环回避算法

死锁和死环是分布式系统或计算机网络中进程间通信时经常发生的逻辑错误，它们往往造成分布式系统中的部分主机或整个系统瘫痪，本文提出两个回避死锁和死环的算法，这些算法可被用来设计分布式系统的通信协议，从而提高分布式系统的可靠性和减少协议开发成本。     

并发操作系统中基于有色Petri网的死锁检测与避免

1.引言系统的并发性与资源的共享性是并发操作系统的主要特征,其目的是最大限度地提高计算机资源的利用率。死锁是并发操作系统必须解决的一个重要问题。人们试图用不同的方法来解决死锁问题。如Dijkstra提出的有名的死锁避免的“银行家算法”,Coffman等人给出的死锁检测算法。 Petri网模型作为模拟与分析并发、异步、分布式系统的一种有效工具,已被用于解决操作系统中的许多问题。如进程通讯中的生产者/消费者问题、哲学家用餐问题,资源竞     

分布式锁的Petri网建模及死锁检测

分布式锁管理DLM细化了锁模式的粒度,使得分布式系统具有更高的并发性,但死锁检测等锁的管理过程却更加复杂了,Petri网的应用能很好地解决该问题。为分布式锁建立Petri网模型,通过化简和合成建立系统的Petri网模型,借助Petri网的可达标识图实时检测出分布式系统的死锁状态,并查找死锁进程。     

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

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

基于Petri网的分布式系统并发进程的死锁检测

分布式系统中的并发进程具有明显的并发、异步及分布性,而Petri网是模拟与分析并发、异步、分布式系统的有效工具.为此通过引入Petri网,给出了分布式系统局部并发进程等待的Petri网模型及死锁检测方法,提出了全链路合成的概念,利用全链路合成技术组装了全局并发进程等待的Petri网模型,给出了判断整个系统是否出现死锁的充分必要条件.     

On Characterization and Correctness of Distributed Deadlock Detection

Distributed deadlock detection requires identifying the presence of certain properties in the global state of distributed systems. Distributed deadlock detection is complicated due to the lack of both global memory and a common physical clock, and due to unpredictable message delays. We characterize the formation and detection of distributed deadlocks in terms of the contents of local memory of distributed nodes/sites. We describe how the interaction between deadlock detection and deadlock resolution can lead to the detection of false deadlocks that are impossible to avoid due to inherent system limitations. We define shadow, phantom, and pseudo deadlocks in the proposed framework. We give examples of existing incorrect deadlock detection algorithms to illustrate how they violate the developed requirements for distributed deadlock detection. The characterization provides an insight into the properties of distributed deadlocks, expresses inherent limitations of distributed deadlock detection, and yields new correctness criteria for distributed deadlock detection algorithms.     

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

Deadlock avoidance schemes in a distributed robotic system: Petri net modeling and analysis

This article presents a Petri net-based approach to modeling and evaluating four different deadlock avoidance schemes for a distributed robotic system, i.e., a five-robot-five-assembly-line system. Among these four schemes are the conventional, full synchronization, global semaphore, and partial synchronization schemes. To explore such issues as the system performance and control structure complexity, this article conducts detailed Petri net modeling for this system and evaluates performance of the deadlock avoidance schemes using stochastic Petri nets. The interesting results presented include that: (1) any possible system deadlock can seriously degrade the system performance even if effective deadlock resolution techniques are available; (2) conservative use of resources is likely to be the best policy; and (3) higher resource utilization may not necessarily imply higher system production rate in a resource-sharing environment. The related results need to be further explored for the larger resource-sharing discrete event systems. © 1995 John Wiley & Sons, Inc.     

分布式移动代理系统的异步死锁检测

移动代理技术在为分布式应用提供全新的网络计算方式的同时也产生了传统分布式计算领域所没有的新的交互模式和执行模式。传统分布式计算的处理方法如并发控制和死锁检测方法不再适用于客户和服务提供者都可在网络中随处移动的移动代理系统。通过移动代理来建模长寿事务,并根据移动代理的特点提出了一种异步分布式死锁检测和解除算法。它将事务代理的执行与死锁检测机制分离,用专门的代理负责死锁检测的初始化、检测和消除等工作。死锁的检测通过创建若干检测代理,使其在各个站点间移动来收集资源请求和分配信息,并据此构造全局等待图;通过分析和探测全局等待图中是否存在圈来完成。算法具有独立于网络的拓扑结构,死锁的检测和事务代理的执行异步操作,不对代理的移动性施加任何限制等特点。     

部分可控Petri网分布式死锁监控器设计

研究了部分可控Petri网柔性制造系统中的死锁避免的问题。为了保证死锁避免和资源最大允许利用,提出了基于分支定界法的Petri网死锁监控器的优化设计方法,采用多个子控制节点对全局状态建立分布式监控器,通过行为可行和分布可行对分布式监控器下合法状态空间进行检测,对最大行为可行子集建立线性规划模型求解最大分布可行合法状态集,得到分布式监控器下的最大合法状态子空间。最后,建立了柔性制造系统的部分可控Petri网模型,针对系统的死锁避免等多个行为特性要求,分别设计了集中式监控器和分布式监控器,分布式监控器能有效地避免死锁。     

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

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

基于动态探针的分布式死锁预防策略

数据库系统中事务死锁的检测和预防,对提高系统并发性和整体性能具有重要意义。在研究了现有的分布式数据库系统死锁预防策略的基础上,利用创建动态探针(DP)技术,提出了一种改进的死锁预防策略。该DP方法在创建探针后将其发往可能产生死锁的节点,接收到探针后,根据节点信息与探针所包含信息的比较结果,可以判断是否有死锁发生,从而达到预防死锁的目的。分析表明,该方法提高了死锁预防的有效性和系统资源的利用率。