导　　师： 吴春明

学科专业： 081203

授予学位： 硕士

作　　者： ;

机构地区： 浙江大学

摘　　要： 随着网络技术的不断发展,分布式系统得到了广泛的研究与应用。互斥问题是分布式系统设计时的关键问题,它保证并发进程正确的访问临界资源。由于分布式系统中网络带宽有限,且临界资源的数目是固定的,因此研究设计网络负载轻、临界资源利用率高的分布式互斥算法具有重要的意义。 分布式互斥算法根据实现互斥的策略可以分为基于令牌的算法和基于许可的算法,本文分别介绍了这两类中的典型算法,并分析比较了它们的优缺点。令牌算法实现简单,比较适用于环形网络和无线网络。但是该算法需要发送消息较多,且同步延迟较大,临界资源利用率不高。对此本文提出一种新的基于令牌的互斥算法,新的算法中通过采用基于令牌请求的策略,减少了消息数,并且令牌不再按照逻辑环的顺序循环传递,而是根据节点请求顺序传递,降低了同步延迟。在基于许可的算法中,本文详细介绍了Maekawa算法。Maekawa算法首次提出了仲裁集的概念,互斥的范围从以往算法的全局互斥缩小为局部互斥,显著的降低了发送消息的数量。但是Maekawa算法实现较为复杂,且同步延迟较多。针对Maekawa算法的缺点,本文对其进行了改进。改进后的算法将Maekawa仲裁集与令牌策略进行结合,令牌持有节点收到请求以后,直接将令牌发送至请求节点,降低了算法同步延迟。最后,对这两个算法进行了模拟仿真,结果表明新算法的性能相比同类算法有了明显的改善。 With the development of network technology, distributed system has been widely researched and used. Mutual exclusion is an important problem in distributed system It guarantees concurrent processes access critical resources correctly. As the network bandwidth of distributed system is limited and the number of critical resources is fixed, so it has great significance to design some distributed mutual exclusion algorithms that is network light-loaded and has a highly usage rate of critical resources. Based on the realization strategy of mutual exclusion, distributed mutual exclusion algorithm can be categorized into two types: token-based algorithm and permission-based algorithm. This paper introduces some typical distributed mutual exclusion algorithms and then analyzes each one's merits and drawbacks. Token algorithm is simple and can be used in ring network and mobile network. But in this algorithm, so many messages need to be sent for one access of critical resources; the synchronize delay is also very high. This paper presents a new token-based mutual exclusion algorithm. By using token requesting strategy, the new algorithm reduces the number of messages need to be sent. It also introduces a token direct sending strategy to reduce the sync delay. Among permission-base algorithms, the article describes Maekawa algorithm in detail. Maekawa algorithm is the first algorithm that proposes the concept of quorum, with which the mutex area can be reduced from global system to local area. So the message complexity of Maekawa drops significantly. However, Maekawa algorithm is complicated and has a high sync delay. This paper has some improvement for the shortcomings of Maekawa algorithm. The improved algorithm combines Maekawa quorum and token strategy sets, the token holding node sends token directly to the requesting node after receiving the request so the sync delay is reduced. Finally, the simulation results of these two algorithms show that the proposed algorithms mark improvement compared with other similar algorithms.

关 键 词： 分布式系统 互斥 令牌 请求 临界资源 仲裁集

分 类 号： [TP338.8]

领　　域： [自动化与计算机技术] [自动化与计算机技术]