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

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

Invariant-based verification of a distributed deadlock detectionalgorithm

It is argued that most previous proposals for distributed deadlock detection are incorrect because they have used informal/intuitive arguments to prove the correctness of their algorithms. Informal and intuitive arguments are prone to errors because of the highly complex nature of distributed deadlock detection/resolution algorithms. The priority-based probe algorithm for distributed deadlock detection and resolution of A.L. Choudhary et al. (1989) is corrected, and it is formally proven that the modified algorithm is correct (i.e., that it does detect all deadlocks and does not report phantom deadlocks). The proof technique is novel in that the authors first abstract the properties of the deadlock detection and resolution algorithm by invariants, and then show that the invariants imply the desired correctness of the algorithm     

Mobile agent-enabled framework for structuring and building distributed systems on the internet

Mobile agent has shown its promise as a powerful means to complement and enhance existing technology in various application areas. In particular, existing work has demonstrated that MA can simplify the development and improve the performance of certain classes of distributed applications, especially for those running on a wide-area, heterogeneous, and dynamic networking environment like the Internet. In our previous work, we extended the application of MA to the design of distributed control functions, which require the maintenance of logical relationship among and/or coordination of proc- essing entities in a distributed system. A novel framework is presented for structuring and building distributed systems, which use cooperating mobile agents as an aid to carry out coordination and cooperation tasks in distributed systems. The framework has been used for designing various distributed control functions such as load balancing and mutual ex- clusion in our previous work. In this paper, we use the framework to propose a novel ap- proach to detecting deadlocks in distributed system by using mobile agents, which dem- onstrates the advantage of being adaptive and flexible of mobile agents. We first describe the MAEDD (Mobile Agent Enabled Deadlock Detection) scheme, in which mobile agents are dispatched to collect and analyze deadlock information distributed across the network sites and, based on the analysis, to detect and resolve deadlocks. Then the design of an adaptive hybrid algorithm derived from the framework is presented. The algorithm can dynamically adapt itself to the changes in system state by using different deadlock detec- tion strategies. The performance of the proposed algorithm has been evaluated using simulations. The results show that the algorithm can outperform existing algorithms that use a fixed deadlock detection strategy.     

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

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

移动Agent系统的一种分布式死锁检测方案

传统的分布式死锁解决方案不适合于实体在网络中自由移动的MAS系统.本文描述了一种移动Agent系统的分布式死锁算法,使用专职Agent从事死锁检测和解决.该方案的特点是地点参考、拓扑独立、容错、异步操作.文中建立了StochasticPetri Net模型,并使用仿真试验给出它和Diffusion Computation算法的性能比较.     

A modified priority based probe algorithm for distributed deadlockdetection and resolution

A modified, priority-based probe algorithm for deadlock detection and resolution in distributed database system is presented. Various examples are used to show that the original priority-based algorithm, presented by M.K. Sinha and N. Natarajan (1985), either fails to detect deadlocks or reports deadlocks that do not exist in many situations. A modified algorithm that eliminates these problems is proposed. The algorithm has been tested through simulation and appears to be errorfree. The performance of the modified algorithm is briefly discussed     

基于行为优先与模糊控制的移动机器人导航

由于动态未知环境下自主移动机器人的导航具有较大困难,为实现自主机器人在动态未知环境下的无碰撞运行,文中将行为优先级控制与模糊逻辑控制相结合,提出4种基本行为控制策略:目标寻找、避障、跟踪和解锁.针对'U'型和'V'型障碍物运行解锁问题,提出了行走路径记忆方法,并通过构建虚拟墙来避免机器人再次走入此类区域.仿真实验表明,所提出的控制策略可有效地运用于复杂和未知环境下自主移动机器人的导航,且具有较好的鲁棒性和适应性.     

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.     

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

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

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     

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

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

The Performance of Alternative Strategies for Dealing with Deadlocks in Database Management Systems

There is growing evidence that, for a fairly wide variety of database workloads and system configurations, locking is the concurrency control strategy of choice. With locking, of course, comes the possibility of deadlocks. Although the database literature is full of algorithms for dealing with deadlocks, very little in the way of practical performance information is available to a database system designer faced with the decision of choosing a good deadlock resolution strategy. This paper is an attempt to bridge this gap in our understanding of the behavior and performance of alternative deadlock resolution strategies. We employ a simulation model of a database environment to study the relative performance of several strategies based on deadlock detection, several strategies based on deadlock prevention, and a strategy based on timeouts. We show that the choice of the best deadlock resolution strategy depends upon the level of data contention, the resource utilization levels, and the types of transactions. We provide guidelines for selecting a deadlock resolution strategy for different operating regions.     

A Direct Execution Approach to Simulating Mobile Agent Algorithms

Mobile agent technology has been applied to develop the solutions for various kinds of parallel and distributed computing problems. However, performance evaluation of mobile agent algorithms remains a difficult task, mainly due to the characteristics of mobile agents such as distributed and asynchronous execution, autonomy and mobility. This paper proposes a general approach based on direct execution simulation for evaluating the performance of mobile agent algorithms by collecting and analyzing the information about the agents during their execution. We describe the proposed generic simulation model, named MADES, the architecture of a software environment based on MADES, and a prototype implementation. A mobile agent-based distributed load balancing algorithm has been used for experiments with the prototype.     

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.     

ORA——一种负载平衡的虚通道分配算法

MPP互联网中通常使用虚通病来防止死锁和提高网络吞吐率。但通常的虚通道分配算法会导致通道的负载不平衡,从而降低网络的性能。针对采用虫孔路由技术和维序路由算法下的Torus互联网,提出了ORA虚通道负载平衡分配算法。与Naive分配算法和Scott分配算法的比较表明,ORA能够较好地实现负载平衡,能够较好地提高网络的性能。     

Deadlock detection in distributed systems

The author describes a series of deadlock detection techniques based on centralized, hierarchical, and distributed control organizations. The point of view is that of practical implications. An up-to-date and comprehensive survey of deadlock detection algorithms is presented, their merits and drawbacks are discussed, and their performances (delays as well as message complexity) are compared. Related issues such as correctness of the algorithms, performance of the algorithms, and deadlock resolution, which require further research are examined     

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.     

Particle swarm optimization based clustering algorithm with mobile sink for WSNs

Wireless sensor networks with fixed sink node often suffer from hot spots problem since sensor nodes close to the sink usually have more traffic burden to forward during transmission process. Utilizing mobile sink has been shown as an effective technique to enhance the network performance such as energy efficiency, network lifetime, and latency, etc. In this paper, we propose a particle swarm optimization based clustering algorithm with mobile sink for wireless sensor network. In this algorithm, the virtual clustering technique is performed during routing process which makes use of the particle swarm optimization algorithm. The residual energy and position of the nodes are the primary parameters to select cluster head. The control strategy for mobile sink to collect data from cluster head is well designed. Extensive simulation results show that the energy consumption is much reduced, the network lifetime is prolonged, and the transmission delay is reduced in our proposed routing algorithm than some other popular routing algorithms.     

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