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

Research and Improvements on Phantom Deadlock Rate of Deadlock Detection Algorithms

作　　者：吴堃[1] 戴菡[1] 周竞扬[1] 陆桑璐[1] 陈道蓄[1] 谢立[1] 

机构地区：[1]南京大学计算机软件新技术国家重点实验室

出　　处：《计算机科学》2005年第6期193-198,共6页Computer Science

基　　金：国家高技术研究发展计划863项目(No.2001AA113050)

摘　　要：死锁处理是分布式系统中的关键问题,其中处理死锁最主要的手段为死锁检测。在评价死锁检测算法性能时伪死锁率被视为一项重要指标,故降低伪死锁率对提高算法性能有着促进作用,而目前大多数算法改进对伪死锁率关注较少。本文阐述了伪死锁研究的意义,并对若干种死锁检测算法的伪死锁率进行研究和模拟实验,认为现有的死锁算法可分为两类:环内检测和环无关检测。并分别通过减少冗余消息和本地死锁解决两种改进方法来降低目前算法的伪死锁率,最终实验表明算法性能获得较大提高。Deadlock detection and resolution is a quite important problem in distributed systems. But now all of the deadlock detection algorithms can cause false deadlock. It is necessary to reduce the false deadlock rate to improve the performance of the algorithms. This paper focuses on the research of the false deadlock. We analyze the factors af- fecting the false deadlock rate, and propose two improvements to reduce the false deadlock rate. To verify our ideas, simulation experiments are used,and the result is quite satisfied.

关 键 词：死锁检测算法 算法性能 分布式系统 关键问题 死锁处理 算法改进 模拟实验 改进方法 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论] TP393[自动化与计算机技术—计算机科学与技术]