分布式系统互斥算法研究

摘要

随着网络技术的不断发展，分布式系统得到了广泛的研究与应用。互斥问题是分布式系统设计时的关键问题，它保证并发进程正确的访问临界资源。由于分布式系统中网络带宽有限，且临界资源的数目是固定的，因此研究设计网络负载轻、临界资源利用率高的分布式互斥算法具有重要的意义。
　　 分布式互斥算法根据实现互斥的策略可以分为基于令牌的算法和基于许可的算法，本文分别介绍了这两类中的典型算法，并分析比较了它们的优缺点。令牌算法实现简单，比较适用于环形网络和无线网络。但是该算法需要发送消息较多，且同步延迟较大，临界资源利用率不高。对此本文提出一种新的基于令牌的互斥算法，新的算法中通过采用基于令牌请求的策略，减少了消息数，并且令牌不再按照逻辑环的顺序循环传递，而是根据节点请求顺序传递，降低了同步延迟。在基于许可的算法中，本文详细介绍了Maekawa算法。Maekawa算法首次提出了仲裁集的概念，互斥的范围从以往算法的全局互斥缩小为局部互斥，显著的降低了发送消息的数量。但是Maekawa算法实现较为复杂，且同步延迟较多。针对Maekawa算法的缺点，本文对其进行了改进。改进后的算法将Maekawa仲裁集与令牌策略进行结合，令牌持有节点收到请求以后，直接将令牌发送至请求节点，降低了算法同步延迟。最后，对这两个算法进行了模拟仿真，结果表明新算法的性能相比同类算法有了明显的改善。