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

Research and Improvements on Phantom Deadlock Rate of Deadlock Detection Algorithms

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

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.