分布式系统中死锁与互斥问题研究

《分布式系统中死锁与互斥问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分布式系统中死锁与互斥问题研究⑧重庆大学硕士学位论文(学术学位)学生姓名：翟厚臻指导教师：柴毅教授专业：控制科学与工程学科门类：工学重庆大学自动化学院二0一三年四月Researchonthedead．．10ckandmutualexclusionofDistributedSystem④AThesisSubmittedtoChongqingUniversity⋯-InPartialFulfillmentoftheRequirementfortheMaster’SDegreeofEngineeringBy

2、，Zhai，HouzhenSupervisedbyProf．Chai，YiSpecialty：ControlScienceandEngineeringCollegeofAutomationofChongqingUniversity,Chongqing，ChinaApril2013中文摘要摘要分布在网络中的各个进程的协同工作是分布式实时系统中非常受关注的一个方向，通常分布式系统中使用同步与并发控制来实现各个进程的协同工作。同步与并发控制的目的在于解决多个用户间的活动之间的切换，保护一个用户的活动不受另一

3、个用户的活动影响，以及对相互依赖的若干活动进行同步等问题。本文将重点研究分布式系统中多个进程要求访问共享资源时，如果保证临界区资源的互斥利用，以及分布式死锁避免与解决的有关问题。本文研究了分布式管理信息系统的建模和架构方法，结合系统的同步与并发控制的关键问题，分别针对死锁问题和进程互斥问题提出了两种较为先进的算法。本文在研究和分析当前较为主流的死锁检测算法的基础上，提出一种分布式系统中基于OR请求模型下的改进型基于探针的死锁检测算法。该算法的基本思想是在一个树形拓扑结构中由算法发起节点发出一个探针，沿

4、着特定的方向依次传递，探针中包含着每个节点的路径链，通过其路径链信息分析是否存在死锁，并将死锁进程踢出进程集。该算法通过探针的逐步传递，建立一个分布式检索树，探针发起节点通过接收其他节点的回复报文来构建一个减损等待图(RWFG)从而检测死锁的存在。探针发起节点所接收到的信息被运用于推断各个节点之间的祖先一子孙关系，由此发起节点又可以使用这些依赖信息，检测死锁的存在。本文在研究和分析当前较为主流的互斥算法的基础上，针对进程优先级以及互斥算法的性能的问题，对PeymanNeamatollahi等提出的基于

5、知情节点的互斥算法进行了改进。基于知情节点的互斥算法的基本思想是在一个二维卷绕式阵列的拓扑结构中，申请获取资源的进程发出请求报文沿着特定的方向寻找令牌持有节点，并且将令牌持有节点分为显式和隐式两种，同时通过两个准则大大提高了算法的性能。在上述算法的基础上，本文提出一种多层级的知情节点算法，即将上述的二维拓扑结构拓展成有多个层级的二位阵列，该算法在上述算法的优越的性能基础上区分了各节点优先级，并且性能表现在轻负载时比原算法更加优越。该算法基于令牌，即只有持有令牌的进程才可以访问临界区，算法可以保证完全的

6、分布式互斥。而另一方面，也能够证明它可以使的每一个请求进入临界区的进程都在可以在有限的时间内访问到临界区，这一点也是至关重要的。最后本文在VSS综合管理系统中实现了上述的死锁检测算法以及互斥算法，系统运行情况良好，并且通过对报文数目的统计验证了算法的正确性以及优越性。关键词：分布式系统、信息管理系统、同步与并发控制、死锁检测、互斥算法重庆大学硕士学位论文II英文摘要ABSTRACTOneofthemostimportantproblemsofdistributedreal-timesystemsish

7、owtomaketheprocesseswhichspreadoveradistributednetworktoworktogether．PeopleoftenuseConcurrencyandSynchronizationcontroltheorytorealizeit．ThepurposeofSynchronizationandConcurrencycontroliStoswitchbetweenmulti．clients’activitiesprotectoneprocessfromanothe

8、r’Sinfluencewhileexecuting，andsynchronizeprocesses’activitieswhicharecorrelativedependence。Thisdissertationwillresearchtheproblemthatwhiletherearemanyprocessesrequestingthesharedresourcessimultaneously,howtoguaranteecriticalsecti