基于请求集与动态令牌的一种对称分布式互斥算法  

High performance distributed mutual exclusion algorithm based on quorum and dynamic token

作　　者：李美安[1] 刘心松[1] 王征[1] 

机构地区：[1]电子科技大学计算机科学与工程学院,四川成都610054

出　　处：《通信学报》2006年第4期124-130,共7页Journal on Communications

摘　　要：提出了一种新的分布式互斥算法。该算法通过在基于竞争或请求集的分布式互斥算法中引入动态令牌的概念以及改变某些消息例如应答(reply)、释放(release)等消息的传送方向以及增加各类型消息的信息量将Makawa类算法的消息复杂度从O(3K～5K)降低到O(2K～4K),同时将算法的同步延迟从2T降低至T,并将算法的节点容错能力提高到N?2并保持算法无饥饿,无死锁。通过实际运行和对比,具有较高的使用价值。A new algorithm has been proposed to resolve the distributed mutual exclusion problem. In this algorithm, through introducing the dynamic token concept and changing the functions or transfer directions of some other messages such as reply, release in the distributed mutual exclusion algorithms based on quorum or competition, the message complexity of Makawa type algorithms can be reduced from O（3K-5K） to O（2K-4K） and the synchronization delay from 2T to T. At the same time, the site fault-tolerant ability of this distributed mutual exclusion algorithm can be increased to N-2. and this algorithm is still deadlock and starvation free as all other Makawa type algorithms. Trough running this algorithm in practice and compare it＇s output with other algorithms, we know this algorithm is very useful in distributed operation system.

关 键 词：分布式操作系统 互斥算法 设计 性能比较 

分 类 号：TP316[自动化与计算机技术—计算机软件与理论]