论文部分内容阅读
在分布式系统中,对临界资源的访问是需要互斥进行的,所以分布式系统中最先要解决的问题是分布式互斥算法。分布式互斥算法主要分为两类,分别是基于竞争的和基于令牌的分布式互斥算法。基于竞争的分布式互斥算法具有消息复杂度较大,同步时间短,对称性比较好的特性,在分布式系统应用广泛。基于竞争的分布式互斥算法包括有局部互斥和全局互斥。全局互斥具有对称性好,但消息复杂度极大,限制了系统规模。局部互斥降低了消息复杂度,并能适应较大的系统规模,但增加了请求集生成算法在时间和空间上开销。局部互斥的运算过程有两步:第一步是请求集生成算法,第二步是请求集互斥算法。本文研究的方向是请求集生成算法。在基于竞争的分布式互斥算法中,保证算法生成的请求集长度最短、时间复杂度和空间复杂度最低,一直都是分布式互斥请求集生成算法研究者追求的目标。本文通过对基于竞争的分布式互斥算法的研究发现,当前对特定拓扑结构的分布式互斥算法研究比较充分。这类算法简单,但仅对特定系统节点比较适合,并且这些算法生成的请求集大多数为非对称请求集。因此,适合任意系统规模的普适请求集生成算法是现在研究重点。在保证请求集生成算法适合任意系统规模的同时,还能保证请求集结构简单和对称性,更是当前研究者追求的目标。循环请求集是满足上述两个条件的请求集。本文主要研究的基于重复数的最短循环请求集生成算法是一种循环请求集生成算法。在普适请求集成算法中,大多数算法都能较快的生成请求集,但算法的请求集长度较大。因此,普适请求集生成算法的研究目标是算法的请求集长度越来越短,时间复杂度和空间复杂度也越来也低。然而对请求集长度最短时(即请求集长度为N0.5),研究这种情况的算法不多,并且这些算法都是用类似穷搜的方法求解。本文提出了一种基于重复数的最短循环请求集生成算法,该算法目的是在保证请求集长度最短时,降低算法的时间复杂度和空间复杂度。该算法在循环松弛差集的思想上,以当前请求集中允许的最大重复数作为判断条件,向请求集中添加元素。通过对算法进一步的研究,本文提出了请求集上限的概念和优化方法。优化方法是当系统节点不存在最短循环请求集时,减少对最短这种情况的多余计算。与穷搜方法相比,本文提出的算法和优化方法在求解最短循环请求集时,使时间复杂度明显降低。本文的算法思想也为以后对最短循环请求集的研究提供了参考和帮助。