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

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

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.     

False Deadlock Detection in Distributed Systems

Detecting a nonexistent deadlock in distributed systems has been referred to as false deadlock detection. This correspondence shows that false deadlock wi1l never occur in a system of two-phase locking transactions. We also describe an algorithm to avoid false deadlock detection when transactions are not two-phase locking.     

On Deadlock Detection in Distributed Systems

A hierarchically organized and a distributed protocol for deadlock detection in distributed databases are presented in [1]. In this paper we show that the distributed protocol is incorrect, and present possible remedies. However, the distributed protocol remains impractical because "condensations" of "transaction-wait-for" graphs make graph updates difficult to perform. Delayed graph updates cause the occurrence of false deadlocks in this as well as in some other deadlock detection protocols for distributed systems. The performance degradation that results from false deadlocks depends on the characteristics of each protocol.     

一种基于改进非局部雾线先验的新型图像能见度检测算法

为了提高图像能见度检测的准确率,本文提出一种利用单幅日光条件图片检测能见度的方法,该方法基于非局部雾线先验和大气成像理论,首先通过改进非局部雾线先验选择图片中用于能见度估计的目标域 ;然后计算雾图像的透射率和恢复为清晰图像后的透射率,并计算二者的比值;最后,将清晰大气的消光系数与该比值相乘,得到被观测雾场景的大气消光系数,最终得到场景能见度。该方法一方面解决传统方法需要摄像机参数标定或者大数据量训练的问题,另一方面相比采用暗通道先验的能见度估计方法,该方法在估计能见度时保留场景的全局性,并一定程度上避免了暗通道先验对光照的敏感,可以较好地在日光户外场景下使用。算法平均准确率在89%以上,相较基于暗通道先验的比值法,平均准确率提升1%。     

Local Distributed Deadlock Detection by Cycle Detection and Clusterng

A distributed algorithm for the detection of deadlocks in store-and-forward communication networks is presented. At first, we focus on a static environment and develop an efficient knot detection algorithm for general graphs. The knot detection algorithm uses at most O(n²+ m) messages and O(log (n)) bits of memory to detect all deadlocked nodes in the static network. Using the knot detection algorithm as a building block, a deadlock detection algorithm in a dynamic environment is developed. This algorithm has the following properties: It detects all the nodes which cause the deadlock. The algorithm is triggered only when there is a potential for deadlock and only those nodes which are potentially deadlocked perform the algorithm. The algorithm does not affect other processes at the nodes.     

基于自动删除算法的分布式CFAR检测算法

研究分布式恒虚警(CFAR)检测系统在非均匀干扰背景中进行优化检测.针对多传感器分布式恒虚警检测系统在非均匀干扰背景中容易出现检测概率下降或者虚警率提高的问题,提出了一种基于自动删除算法的分布式恒虚警检测算法.算法是一种基于局部检测统计量的分布式CFAR检测算法,充分利用了局部检测器的观测信息,提高了检测性能,同时采用...     

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

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

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.     

Protocols for Deadlock Detection in Distributed Database Systems

In distributed databases, deadlocks may occur due to conflicts in data file lockings A system is in a deadlock if and only if there is a directed cycle in its demand graph. However, due to the inherent communication delay in a distributed system, it is not easy to construct a consistent demand graph for a distributed system. In this paper, three deadlock detection protocols are discussed. The first protocol uses two communication phases. The second protocol uses a single communication phase. Based on the second protocol, a one-phase hierarchical deadlock detection protocol is developed.     

Locking and Deadlock Detection in Distributed Data Bases

This paper descrbes two protocols for the detection of deadlocks in distributed data bases–a hierarchically organized one and a distributed one. A graph model which depicts the state of execution of all transactions in the system is used by both protocols. A cycle in this graph is a necessary and sufficient condition for a deadlock to exist. Nevertheless, neither protocol requires that the global graph be built and maintained in order for deadlocks to be detected. In the case of the hierarchical protocol, the communications cost can be optimized if the topology of the hierarachy is appropriately chosen.     

基于门限自适应的分布式检测融合算法

贝叶斯检测融合策略是一种比较传统的分布式检测融合方法,必须给定待检测现象的先验概率和各局部传感器的虚警概率和漏检概率,而在现实应用中,统计量是未知的或者是随时间变化的.因此,研究了一种纽曼一皮尔逊准则下的门限自适应分布式检测系统的融合算法.算法可根据观测数据,自动在线调整门限,使得局部传感器检测达到最佳,从而提高系统的检测性能.计算机仿真的结果表明,算法能较快地收敛,相对局部传感器,融合中心的检测性能也明显地有了提高.     

一种基于依赖分析的并发程序潜在死锁检测算法

死锁是并发程序特有的一种运行时错误,由于并发程序在执行时的不确定性,死锁的检测和定位是非常困难的.本文提出了一种基于依赖分析的并发程序潜在死锁检测算法,该算法是一种静态分析算法,能检测并发程序中是否存在潜在死锁,并能定位死锁发生时各线程可能被挂起的语句节点.本文给出了算法的形式化定义和时间复杂度分析,实验测试结果表明算法是正确且有效的.     

A New Link Failure Resilient Priority Based Fair Mutual Exclusion Algorithm for Distributed Systems

This paper aims towards designing a new token-based mutual exclusion algorithm for distributed systems. In some of the earlier work, token based algorithms for mutual exclusion are proposed for the distributed environment assuming inverted tree topology. In a wireless setup, such a stable, hierarchical topology is quite unrealistic due to frequent link failures. The proposed token-based algorithm works for processes with assigned priorities on any directed graph topology with or without cycles. The proposed algorithm, in spite of considering priorities of processes, ensures liveness in terms of token requests from low priority processes. Moreover, the algorithm keeps control message traffic reasonably low. The simulation results exhibit the performance of the proposed algorithm under varied contexts besides presenting a comparative performance with other recent algorithms for mutual exclusion like FAPP (Fairness Algorithm for Priority Process).     

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

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

基于窗口统计量的水下分布式目标检测算法

针对水声传感器网络对水下目标检测时面临的节点数目、布放位置随机、检测性能时变、缺乏入侵目标先验模型的问题,将对点目标的假设检测推广到对最优海域窗口的假设检测,提出了一种基于最优窗口统计量的融合检测规则,近似推导出了算法系统级的检测性能,并给出了仿真对比实验.结果表明：在满足滑动窗口同目标辐射信号区域近似匹配的条件下,基于最优窗口统计量的融合检验规则可以获得良好的系统级检测性能,与已有的非参数类投票计数融合规则相比,相同信噪比下,基于最优窗口统计量的融合规则目标检测性能更好.     

A Novel Parallel Deadlock Detection Algorithm and Hardware for Multiprocessor System-on-a-Chip

Given the projected dramatic increase in the number of processors and resources in a system-on-a-chip, a quadratic increase in the likelihood of deadlock is predicted due to complex system behavior. To deal with this issue, we here present a novel parallel hardware-oriented deadlock detection algorithm with O(l) deadlock detection and 0(min(m,n)) preparation, where m and n are the numbers of processes and resources, respectively. Our contributions are (i) the first O(l) deadlock detection hardware implementation and (ii) a new algorithmic method of achieving 0(min(m,n)) overall run-time complexity. We implement our algorithm in Verilog HDL and demonstrate that deadlock detection always takes only two clock cycles regardless of the size of a system (i.e., m and n).     

基于等待图模型的死锁检测新算法

本文提出了一种在等待图中检测回路的线性时间算法，它通过搜索回边来判定等待图中回路的存在性。     

一种基于优先级的网格调度算法

容错机制中基于任务数量的平均调度策略在处理跨度和服务质量方面存在不足,为此,提出一种基于优先级的网格调度算法,进而给出层次式集群系统的设计方案。在任务调度过程中引入任务剩余执行时间、任务价值密度、费用预算以及处理跨度的概念,以缩短任务处理跨度,提高服务质量。实验结果表明,与原机制调度策略和Max-Min算法相比,该算法在任务完成率、价值实现率和处理速率方面具有优势。利用该算法对原机制进行改进,能够有效提高系统的任务执行效率。     

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

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