分布式系统中死锁检测方法研究

发布时间：2020-11-07 09:34

　　 分布式系统在提供强大服务能力的同时也面临着可靠性、安全性和复杂性等挑战。因资源分配与需求产生冲突而产生的死锁,在分布式系统中是一种较常见的软件错误。若不能及时处理系统中出现的死锁,则可能出现用户体验下降、计算结果错误和系统效率下降甚至崩溃等问题。常见死锁处理方式包括:预防、避免和检测解决。相对于死锁预防和死锁避免,死锁检测和解决不仅简单高效而且可行性较高。然而,不同于集中式系统,分布式系统具有无共享内存、无全局时钟以及软硬件失效概率较高等特点。这增加了分布式系统中死锁处理的复杂度。同时,作为运行在系统中的应用进程,用于死锁检测和解决的进程需要在保证死锁检测和解决结果正确性的同时注重效率。通过对现有分布式系统中死锁检测算法的研究和分析发现,现有算法多侧重于研究单个进程发起死锁检测时的算法正确性和效率问题。然而,在真实分布式系统中,死锁涉及到的多个进程可能并行发起死锁检测。当多个进程并行检测系统中同一个死锁时,可能出现诸如死锁重复检测和解决导致的伪死锁、非最优死锁解决方案以及算法效率等问题。同时,现有算法大多未考虑计算节点或进程部分或完全失效时的容错问题。再者,诸如移动无线网络系统、移动代理系统和移动边缘计算系统等具有移动性特点的分布式系统中的死锁检测和解决问题还未被充分研究。本文通过研究和分析现有分布式系统中死锁检测算法存在的不足,针对现有算法在并行死锁检测情况下的正确性、效率、容错能力和扩展性的不足提出了相应优化方法。本文主要研究成果如下:(1)提出了一种基于优先级的分布式并行死锁检测优化算法。在所提出的算法中,高优先级死锁检测进程重用低优先级进程已收集的死锁相关信息,以减少低优先级进程重复转发探针消息。同时,为减少所传输消息中携带的数据总量,所提出的算法在每个发起死锁检测的进程正常终止之前不传输死锁相关信息。最后,通过改进的优先级比较策略,算法可选出唯一的死锁检测进程执行死锁相关信息收集、死锁检测和解决以保证算法正确性。相比已有算法,新算法在保证并行死锁检测结果正确的同时,也提高了算法效率。(2)提出了一种基于领导人选举策略的分布式容错并行死锁检测算法。针对分布式系统中死锁检测时进程间通信失效引起的算法无法正常运行问题,提出了一种能够容忍一定范围内死锁检测进程间通信失效的容错算法。在所提出的算法中,死锁检测进程通过维护进程间失效记录和中央控制进程推荐列表,并根据进程优先级推荐新中央控制进程控。新算法在单进程死锁检测情况下保留了集中式死锁检测算法效率的同时提供了一定的容错能力。同时,该算法在多进程并行死锁检测情况下也具有较高的效率。(3)提出了一种面向移动代理系统中单资源模型的分布式并行死锁检测算法。在所提出的算法中,死锁检测代理采用渐进式收集死锁代理相关信息的方式提升算法效率。通过基于改进的优先级比较策略和延迟回复策略减少死锁检测代理在系统中的移动次数和代理移动时携带的数据总量。同时,新算法通过改进的优先级策略保证并行死锁检测和解决结果的正确性。(4)提出了一种面向移动代理系统中一般化资源模型的分布式并行死锁检测算法。所提出的算法利用权值均分技术、扩散计算技术和改进的延迟回复策略以提升算法效率。同时,为保证死锁检测和解决结果的正确性,新算法也使用了基于优先级的比较策略以避免死锁重复检测和解决。新算法在保证死锁检测和解决结果正确性和效率的基础上扩展了算法的适用范围。本文对所提出算法的正确性(即算法活性和安全性)进行了非形式化证明和基于TLA+(Temporal Logic of Actions)的形式化验证。验证结果表明,本文所提出的各算法均满足活性和安全性要求。同时,通过理论性能分析和仿真实验对部分现有死锁检测算法与所提出的算法进行了性能比较。比较结果显示,本文所提出的算法在整体上具有较高的效率。
【学位单位】：北京交通大学
【学位级别】：博士
【学位年份】：2018
【中图分类】：TP338.8
【部分图文】：

不仅具有重要科学研宄价值也具有较强实际应用价值。??本文研宄的课题来源于中国国家自然科学基金面上项目，“资源导向型对等网??络下服务发现与服务组合的研究”（项目编号６１２７２３５３）和中国国家自然科学基金??海外杰出青年合作项目，“数据密集型系统中软件的错误检测、故障恢复和优化”??（项目编号６１４２８２０１）。课题的研究目的是为大型对等网络下的Ｗｅｂ服务应用提??供可靠的运行环境。课题的研宄目标是：根据分布式系统应用的特点，以提升分布??式系统中错误检测准确性和效率为前提，提出面向分布式系统的错误检测和故障??容错方法，为构建高可靠Ｗｅｂ服务或相应分布式应用奠定基础。??１．２分布式系统架构??分布式系统是一组通过网络连接并互相协作以解决特定任务的计算机以及运??行在其上的软件组成的系统。系统中各计算机上应用程序之间通过传递消息来共??享信息和协调任务［１３Ｌ图１－１给出了分布式系统的整体架构示意图。??Ｃｏｍｐｕｔｅｒ?１?Ｃｏｍｐｕｔｅｒ?２?Ｃｏｍｐｕｔｅｒ?ｉ?Ｃｏｍｐｕｔｅｒ?ｍ?Ｃｏｍｐｕｌｅｒ?ｎ??｜?■?■?｜?｜?■?－ｉ?「■?ｉ?ｒ?Ｉ????

图１－２分布式系统中资源请求模型分类??Ｆｉｇ．?１－２?Ｃｌａｓｓｉｆｉｃａｔｉｏｎ?ｏｆ?ｒｅｓｏｕｒｃｅ?ｒｅｑｕｅｓｔ?ｍｏｄｅｌｓ?ｉｎ?ｄｉｓｔｒｉｂｕｔｅｄ?ｓｙｓｔｅｍｓ??图１－２给出了分布式系统中资源请求模型分类。根据引起死锁的资源类型可将??资源请求模型分为：资源模型和通信模型［１８］。根据应用进程申请资源的数量以及??进程可以继续运行时资源所需逻辑关系，文献［１９］将上述两种资源模型细分为：??（１）

?ｂ）?ｃ）??图１－３常用死锁表示图，其中，ａ）任务资源图；ｂ）二分图；ｃ）通用资源图??Ｆｉｇ．?１－３?Ｄｅａｄｌｏｃｋ?ｇｒａｐｈ?ｒｅｐｒｅｓｅｎｔａｔｉｏｎｓ，?ｗｈｅｒｅ，?ａ）?ｔａｓｋ?ｒｅｓｏｕｒｃｅ?ｇｒａｐｈ；?ｂ）?ｂｉｐａｒｔｉｔｅ?ｇｒａｐｈ；?ｃ）?ｇｅｎｅｒａｌ??ｒｅｓｏｕｒｃｅ?ｇｒａｐｈ??图１－３?ｃ）表示由进程程ｐ＃ｐ２及可重用资源ＲＲｊ?＝?｛ｒｒ＾ｒｉ＾，?．．．，ｒｒｘ｝和一组可消??耗资源ＣＲｊ?＝?｛ｃｒｉ，ｃｒ２，ｃｒｙ｝组成的一般化资源等待图。每个可重用资源ＲＲＰ其成员??数为正整数。每个可消耗资源ＣＲｐ其生产者是进程集Ｐ的非空子集。一般化资源??等待图中的边分为三种类型：??（１）
【参考文献】

相关期刊论文 前2条

1 梅宏;王千祥;张路;王戟;;软件分析技术进展[J];计算机学报;2009年09期

2 王汝传,徐小龙,郑晓燕,孙知信;移动代理安全机制模型的研究[J];计算机学报;2002年12期

相关博士学位论文 前1条

1 程欣;面向环和结的分布式死锁检测算法研究[D];哈尔滨工业大学;2006年

相关硕士学位论文 前1条

1 陈鹏;分布式数据库死锁检测算法研究[D];重庆大学;2004年

本文编号：2873761