一种改进的双令牌互斥算法  

An Improved Mutual Exclusion Algorithm with Dual Tokens

作　　者：吴小惠[1] 洪龙[1] 杨扬[2] 

机构地区：[1]南京邮电大学计算机学院,江苏南京210003 [2]中兴通讯股份有限公司,江苏南京210012

出　　处：《计算机技术与发展》2011年第4期40-43,共4页Computer Technology and Development

基　　金：中兴通讯重大科研基金(nj200909080002)

摘　　要：互斥是解决分布式系统中资源申请的相互冲突、实现资源共享的一种有效方法。文中对目前的一些互斥算法进行了介绍,并对集中式互斥算法和分布式互斥算法进行了讨论,并分析了其特点。在简要介绍令牌环算法和双令牌算法的思想和步骤后,提出一种改进的双令牌算法。详细叙述了改进算法的设计思想和实现步骤,对性能进行了分析并给出算法示例。讨论结果表明,与原有的双令牌算法相比,新算法可以以更高效率有效检测令牌丢失并实现令牌重构。Mutual exclusion in distributed systems is an effective method of solving the conflict with the application of resources and sharing resources.Some of the current mutual exclusion algorithms are introduced,and centralized mutual exclusion algorithm and distributed mutual exclusion algorithm and their characteristics are discussed.An improved algorithm for token loss detection was proposed after the simple token ring algorithm and the algorithm for token loss detection were raised.The improved algorithm＇s design and the steps of the implementation have been described,moreover,the analysis of the performance and an example was given.The discussion showed that the new algorithm can be more effective than the dual tokens algorithm in detecting token loss and token reconstruction.

关 键 词：互斥 双令牌 令牌丢失 令牌重构 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]