基于Token追踪的分布式互斥算法  

A DISTRIBUTED MUTUAL EXCLUSION ALGORITHM BASED ON TOKEN CHASING

作　　者：鄢勇[1] 

机构地区：[1]华中理工大学计算机科学系,武汉430074

出　　处：《计算机学报》1993年第9期648-654,共7页Chinese Journal of Computers

摘　　要：本文首先提出一切合实际的互斥信件量度量方法,该方法不仅考虑请求结点所发的信息数,同时还考虑信件的存储转发次数,然后针对任一拓扑结构,在充分利用局部信息与已知信息的基础上,给出了互斥信件量为0～2(n—1)(n为结点数)的有效互斥算法,该算法不仅在互斥信件量上是目前最优的,而且充分体现了分布式算法设计的一个重要原则,充分利用一切已知信息作为未来决策的依据。This paper first presents a more practical measure of the communication complexity of mutual exclusion,which considers both the number of requesting letters sent by a requesting processor and the number of the store-forwords of the intermediate processors.Then a token-chasing mutual algorithm which has the least number of communication letters compared with the previous methods is proposed.A distinguished feature of the algorithm is that it takes enough use of the known information to predict the future actions,and can be used for any topological structures.

关 键 词：共享资源 分布式互斥 算法 TOKEN 

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