共查询到20条相似文献,搜索用时 15 毫秒
1.
《IEEE transactions on pattern analysis and machine intelligence》1985,(8):820-821
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. 相似文献
2.
《IEEE transactions on pattern analysis and machine intelligence》1980,(5):435-440
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. 相似文献
3.
4.
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(n2+ 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. 相似文献
5.
传统的分布式死锁解决方案不适合于实体在网络中自由移动的MAS系统.本文描述了一种移动Agent系统的分布式死锁算法,使用专职Agent从事死锁检测和解决.该方案的特点是地点参考、拓扑独立、容错、异步操作.文中建立了StochasticPetri Net模型,并使用仿真试验给出它和Diffusion Computation算法的性能比较. 相似文献
6.
7.
一种基于依赖分析的并发程序潜在死锁检测算法 总被引:1,自引:0,他引:1
死锁是并发程序特有的一种运行时错误,由于并发程序在执行时的不确定性,死锁的检测和定位是非常困难的.本文提出了一种基于依赖分析的并发程序潜在死锁检测算法,该算法是一种静态分析算法,能检测并发程序中是否存在潜在死锁,并能定位死锁发生时各线程可能被挂起的语句节点.本文给出了算法的形式化定义和时间复杂度分析,实验测试结果表明算法是正确且有效的. 相似文献
8.
《IEEE transactions on pattern analysis and machine intelligence》1982,(6):554-557
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. 相似文献
9.
《IEEE transactions on pattern analysis and machine intelligence》1979,(3):195-202
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. 相似文献
10.
Sukhendu Kanrar Samiran Chattopadhyay Nabendu Chaki 《Journal of Network and Systems Management》2013,21(1):1-24
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). 相似文献
11.
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). 相似文献
12.
13.
网络漏洞扫描器是一个用来自动检查本地或远程主机的安全漏洞的程序.依据漏洞检测的要求和实现的特点,构造一个分布式扫描任务调度模型,提出相应的扫描任务分配算法.该算法将扫描任务分配到与被检测主机同在一个子网的扫描服务器中执行,或将扫描任务尽可能均衡地分配到各个扫描服务器中,从而提高漏洞检测系统的运行效率.最后,从理论上证明该模型和算法的可行性和优越性. 相似文献
14.
无线传感器网络中的目标监测广泛应用于军事、生态、医疗、安全等领域,具有极强的现实研究意义.传统集中式目标监测算法对融合节点依赖性高、网络健壮性弱、二元决策机制导致误报率高,而且算法对网络覆盖的依赖会导致监测报警盲点的存在.因而,提出了基于信用度的分布式目标监测k-CD算法.算法首先根据邻居信用度对自身信用度进行调整,然后在发现目标的节点之间形成一个虚拟的节点集来完成信用度匹配决策融合,并且通过触发式移动节点来解决网络覆盖导致的盲点问题.仿真结果表明,相对于经典的多数投票决策(MV)算法,k-CD算法平均能在提高35%的监测准确率的同时降低62%的误报率,在不同的网络覆盖情况下网络生命周期也平均能得到44%的延长. 相似文献
15.
16.
17.
基于Petri网合成与化简的分布式数据库系统并发控制的死锁检测 总被引:5,自引:0,他引:5
利用模块化设计的思想,首先为分布式数据库系统中各事务的每一种操作(读锁、写锁、解锁)构造一个基本的加权Petri网模型,并给出了加权Petri网共享合成的概念、然后利用共享合成技术,动态地构造各站点的加权Petri网模型,以适应系统的动态变化.此外,本文利用Petri网的化简技术,极大地简化了各站点的Petri网模型,之后利用同步合成技术构造出整个系统的Petri网模型,较好地解决了Petri网的可达性分析中可能出现的状态“爆炸”问题.最后给出了判断整个系统是否出现死锁的充分必要条件. 相似文献
18.
《IEEE transactions on pattern analysis and machine intelligence》1983,(3):371-371
The two-phase deadlock detection protocol in the above paperl detects false deadlocks. This is contrary to what the authors claim. The false detection o. f deadlocks is shown using a counterexample. 相似文献
19.
This article proposes a novel parallel, hardware-oriented deadlock detection algorithm for multiprocessor system-on-chips. The proposed algorithm takes full advantage of hardware parallelism in computation and maintains information needed by deadlock detection through classifying all resource allocation events and performing class specific operations, which together make the overall run-time complexity of the new method O(1). We implement the proposed algorithm in Verilog HDL and demonstrate in the simulation that each algorithm invocation takes at most four clock cycles in hardware. 相似文献
20.
提出了一种传感器网络异常检测算法,与传统的基于相邻节点数据对比的检测算法不同,该算法首先在节点内分析数据的时间相关性,仅在发生异常时,上传至簇头节点,分析空间相关性;对于不确定的异常数据,在相邻分簇内,计算数据的相关性.还给出了采用直方图计算均值和分析相关性的方法.实验表明,该算法减少了通信量,提高了异常检测的准确率. 相似文献