分布式系统互斥算法研究

发布时间：2023-04-16 23:35

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

【文章页数】：66 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第1章 绪论
    1.1 研究背景
        1.1.1 分布式系统概述
        1.1.2 分布式互斥问题
    1.2 分布式互斥算法分类
        1.2.1 按照互斥实现策略分类
        1.2.2 按照节点职能分类
        1.2.3 按照层次分类
    1.3 分布式互斥算法研究历史与现状
    1.4 论文组织结构
第2章 主流分布式互斥算法介绍
    2.1 系统模型
    2.2 算法评价标准
        2.2.1 正确性评价
        2.2.2 算法性能评价
    2.3 分布式互斥算法介绍
        2.3.1 基于令牌传递的分布式互斥算法
        2.3.2 Lamport算法
        2.3.3 Richard&Agrawal算法
        2.3.4 Maekawa算法
    2.4 几种分布式互斥算法的比较
    2.5 本章小结
第3章 一种新的基于令牌的分布式互斥算法
    3.1 构造逻辑环
        3.1.1 旅行商问题
        3.1.2 利用改进的TSP求解算法构建逻辑环
    3.2 算法描述
        3.2.1 算法步骤
        3.2.2 消息与数据结构
        3.2.3 伪代码描述
    3.3 算法正确性证明与性能分析
        3.3.1 正确性证明
        3.3.2 算法性能分析
    3.4 本章小结
第4章 改进的Maekawa算法
    4.1 Maekawa仲裁集算法示例
    4.2 改进算法
        4.2.1 改进算法描述
        4.2.2 算法步骤
        4.2.3 消息与数据结构
        4.2.4 伪代码描述
    4.3 算法正确性证明与性能分析
        4.3.1 正确性证明
        4.3.2 算法性能分析
    4.4 算法容错性扩展
    4.5 本章小结
第5章 仿真实验与结论
    5.1 基于令牌的互斥算法的仿真实验
        5.1.1 实验场景
        5.1.2 仿真实验结果
    5.2 改进的Maekawa算法的仿真实验
        5.2.1 实验场景
        5.2.2 仿真实验结果
    5.3 本章小结
第6章 总结与展望
    6.1 主要内容
    6.2 今后的工作
参考文献
攻读硕士学位期间主要的研究成果
致谢



本文编号：3792112