分布式互斥算法的研究与改进

论文摘要

在分布式系统中,分布在不同计算机上的多个并发进程访问临界资源的时候经常会产生资源竞争问题,有可能导致临界资源被错误的改写或不当的使用,破坏临界资源的正确性和完整性。正因如此,必须实现分布式的并发进程之间的同步与互斥,协调各并发进程访问临界资源,保证临界资源的正确性和系统的一致性。 本文对分布式同步与互斥问题进行了分析和研究,在评价了一些现有的分布式互斥算法之后,对一种基于令牌的算法——Goscinski算法的进行了改进。为了证明改进算法具有较好的性能,本文对改进算法的性能进行了详细的分析与计算,并且与Goscinski算法及其他算法进行了对比。 分布式互斥算法旨在解决分布式系统的同步与互斥问题,应该具备在真实系统中的容错能力,本文针对系统中可能出现的错误与故障为改进算法设计了相应的容错方案。 本文最后应用改进算法及几个其他算法分别模拟了分布式并发进程同步访问临界资源的过程,通过实验证实了改进算法具有较好的性能。

论文目录

• 第一章 绪论
• 1.1 研究背景
• 1.2 本文的主要内容和组织结构
• 1.2.1 主要内容
• 1.2.2 本文的组织结构
• 第二章 分布式互斥算法的研究与分析
• 2.1 分布式互斥算法的环境假设
• 2.2 分布式互斥算法评估标准
• 2.2.1 正确性评估标准
• 2.2.2 性能评估标准
• 2.3 分布式互斥算法的举例与分析
• 2.3.1 基于许可的算法
• 2.3.2 基于令牌的算法
• 2.4 本章小节
• 第三章 改进的Goscinski算法
• 3.1 改进思想及改进方案
• 3.2 改进算法的详细描述
• 3.2.1 基本要素
• 3.2.1 详细描述
• 3.2.3 进程的状态及状态转换
• 3.2.4 改进算法的伪语言表示
• 3.3 改进算法的性能分析
• 3.3.1 平均消息数
• 3.3.2 同步延迟
• 3.3.3 响应时间
• 3.3.4 综合比较
• 3.4 改进算法正确性证明
• 3.4.1 公平证明
• 3.4.2 无饥饿证明
• 3.4.3 无死锁证明
• 3.5 改进算法在真实网络中的容错方案
• 3.5.1 请求消息丢失
• 3.5.2 管理进程出错
• 3.5.3 辅助进程出错
• 3.5.4 令牌丢失
• 3.6 本章小结
• 第四章 算法在分布式环境下的性能对比实验
• 4.1 实验环境
• 4.1.1 硬件环境
• 4.1.2 软件环境
• 4.2 实验内容
• 4.3 实验结果
• 4.4 本章小节
• 第五章 结束语
• 5.1 总结
• 5.2 进一步工作
• 参考文献
• 致谢
• 硕士期间发表的论文清单