摘  要： 在折半循环编码算法的基础上，依据贪心策略对可纳入节点进行局部求最优的方式来生成请求集的算法，从而使算法的请求集长度下降了一个数量级，接近。
关键词： 初始化；折半循环编码；局部贪心策略；请求集

　基于请求集的分布式互斥算法作为Maekawa算法[1]的推广，近年来得到了人们的广泛关注，人们提出了许多各具特色的算法来构建请求集，以降低分布式互斥算法的消息复杂度或者提高分布式互斥算法在其他方面的性能，例如李美安通过循环编码产生请求集的方式，得出一种消息复杂度较低、容错性能高且同步时间短的对称分布式互斥算法[2]，但由于该算法的初始化节点数较少，因此算法的时间复杂度还是比较高。为了改善请求集生成算法的性能，陈志党在该算法的基础上，提出了一种通过提高请求集初始化节点的数量的方式来改善请求集生成算法，即折半循环编码算法[3]，从而更快、更优地产生请求集，使算法的时间复杂度大幅度降低。
　由于折半循环算法只是简单地提高了算法的时间复杂度和空间复杂度，算法没有对请求集的长度有所提高，所生成的请求集长度仍然保持在之间，因此本文在贪心策略的基础上，依据贪心策略对可纳入节点进行局部求最优的方式，来生成请求集的算法，从而更快、更优地产生请求集。
1 系统模型
　设系统的节点数为N，并从0~N-1对节点编号，第i个节点的ID号为i-1。假定系统的节点与通信均可靠，各节点没有共享存储器和共同的物理时钟，节点间依靠消息进行异步通信，并且无法预知消息通信时间延迟。

　满足条件A1～A4的请求集称为对称请求集，能够生成对称请求集的算法称为对称请求集生成算法，利用对称请求集实现分布式互斥的算法称为对称分布式互斥算法。
1.2 请求集产生算法的相关概念
　为了减少在生成请求集过程中的循环次数，本文提出了松弛循环差集的定义、贪心算法定义以及循环请求集与松弛差集等价的定理。
　定义(贪心策略)：贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。
　定理 循环请求集与松弛差集等价。
　在循环编码算法中已经证明，循环编码所产生的请求集满足MAEKAWA M所提出的四个条件，其产生的请求集是对称请求集，而松弛差集算法中证明了循环请求集与松弛差集等价的定理，因此，松弛循环差集所产生的请求集也是对称请求集。而本算法是在松弛差集算法的基础上进行的改进，即通过增加初始化请求集的长度来缩短算法的时间复杂度，以求更快地找到所求请求集，因此，本算法所产生的请求集也是对称请求集。

1.3 贪心策略理论
1.3.1 贪心选择性质
　贪心选择性质是指应用同一规则f，将原问题变为一个相似的、但规模更小的子问题，此后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程。
1.3.2 局部最优解
　贪心策略通常是自顶向下进行的。第一步为一个贪心选择，将原问题变成一个相似的、但规模更小的问题，而后的每一步都是当前看似最佳的选择。这种选择可能依赖于已作出的所有选择，但不依赖有待于做的选择或子问题的解。
　从求解的全过程来看，每一次贪心选择都将当前问题归纳为更小的相似子问题，而每一个选择都仅做一次，无重复回溯过程。因此，贪心法有较高的时间效率。
2 请求集产生的算法的描述与实现
2.1 数据结构
　设系统的节点数为N，系统请求集方阵AN是N×N的方阵，其行列编号均为0~N-1，AN第i行表示系统的第i个节点的请求集码字，用ai表示，aij表示AN的第i行第j列元素，它的值表示节点j在第i个节点的请求集码字中是否被选中，aij为1表示选中，为0表示没被选中。
　为了判断是否产生请求集，引进标记数组TN，它具有N个分量，每个分量对应AN的一行，该分量为1表示AN对应行和第0行有交点((a0&ai)！=0)，反之，则说明没有交点。
表示状态数组T：长度为N的数组。T[i]=1用来表示差集i在请求集中已被表示，T[ i]=0表示差集i在请求集中没被表示。
　最小重复记录字count：用来表示第j行(1≤j<[N/2])和第0行第一次出现没有交点。

 
3.3 空间复杂度
    由于折半循环算法引入了对称请求集的概念，只计算前「N/2?骎行和第0行有交点即可。空间复杂度为O(N2/2)，而本算法只是在贪心策略的基础上，依据贪心策略对可纳入节点通过局部求最优的方式来生成请求集，所以，空间复杂度与折半循环算法一样。
    公平、健壮和易于实现的分布式互斥算法是研究人员追求的最终目标，本文在陈志党提出的折半循环编码算法的基础上，依据贪心策略对可纳入节点进行局部求最优的方式来生成请求集的算法，从而产生更优的请求集，使算法的请求集长度下降到，空间复杂度可近似为O(N2/2)，时间复杂度为O(N/2)，因此本算法易于实际应用。
参考文献
[1] MAEKAWA M. A Nalgorithm for mutual exclusion in decentralized systems[J]. ACM Transactions on Computer Systems， 1985，3(2)：145-159.
[2] 李美安，刘心松，王征.一种基于松弛循环差集的高性能分布式互斥算法[J].电子学报，2007，35(1)：58-63.
[3] 陈志党，李美安.一种新的分布式互斥请求集生成算法[J].微计算机信息，2010(3-9)：211-212.
[4] 申二威，李美安.一种改进的高效分布式互斥请求集生成算法[J].微计算机信息，2010(8-24)：201-20.