一种贪心策略的更高效的请求集生成算法＊

李美安，陈志党，王春申

(内蒙古农业大学 计算机科学与技术学院，内蒙古 呼和浩特 010018)

基于请求集的分布式互斥算法作为Maekawa算法[1]的推广，近年来得到了人们的广泛关注，人们提出了许多各具特色的算法来构建请求集，以降低分布式互斥算法的消息复杂度或者提高分布式互斥算法在其他方面的性能，例如李美安通过循环编码产生请求集的方式，得出一种消息复杂度较低、容错性能高且同步时间短的对称分布式互斥算法[2]，但由于该算法的初始化节点数较少，因此算法的时间复杂度还是比较高。为了改善请求集生成算法的性能，陈志党在该算法的基础上，提出了一种通过提高请求集初始化节点的数量的方式来改善请求集生成算法，即折半循环编码算法[3]，从而更快、更优地产生请求集，使算法的时间复杂度大幅度降低。

1 系统模型

设系统的节点数为N，并从0～N-1对节点编号，第i个节点的ID号为i-1。假定系统的节点与通信均可靠，各节点没有共享存储器和共同的物理时钟，节点间依靠消息进行异步通信，并且无法预知消息通信时间延迟。

1.1 对称请求集产生的条件

用SN表示包含N个节点的分布式系统，Si表示系统中 ID号为 i的节点，Ri表示节点 Si的请求集，k、n等为常数。

MAEKAWA M提出了对称请求集应满足的四个条件，即：

A1：∀i，j∈[0，N-1]，Ri∩Rj≠φ。即任意两个节点的请求集交集不为空。

A2：∀i∈[0，N-1]，Si∈Ri。 即任 意 节点 的请求 集包含该节点本身。

A3：∀i，j∈[0，N-1]，i≠j，|Ri|=|Rj|=k。 即每个节点的请求集长度相同，都包含k个节点。

A4：∀i∈[0，N-1]，|{Rj|Si∈Rj，j∈[0，N-1]}|=k，即任一节点都属于k个请求集。

满足条件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行第一次出现没有交点。

2.2 请求集生成算法描述

(1)令 2k≤⎿N/2」，求出k，将系统第 0 个节点的码字a0中 20-1，21-1，…，2k-1(1≤k＜N)位初始 化为 1，并令T[0]=1。

(2)对第 0 行向右进行循环右移 i位(0≤i＜「N/2⏋)得到第i行，判断第0行和第i行是否有交点，如果有交点，令 T[i]=1，i++，转(2)，否则转(3)。

(3)若第 0行和第 i行没有交点，则 count=i，遍历第0行中 a[0][j]=0(j|0≤j＜N)的所有情况，在第 0行中置 a[0][j]=1，并令 T[i]=1，求以上各种情况下 count的最大值，并在count取最大值时，在第一行所对应的节点j处，令 a[0][j]=1为插入节点，转(2)。

(4)直到 T 前「N/2⏋行都为 1 或者 count＞「N/2⏋时，算法结束。

2.3 请求集产生算法的实例实现

以请求集个数N=13为例，图1～图 4描述了各节点请求集的求取过程。

由于 22＜「13/2⏋＜23，所 以 a[0][0]=1，a[0][1]=1，a[0][3]=1，T[0]=1。

图1 初始化

图2 第一步令a[0][2]=1，count=4

图3 第三步令a[5][4]=1，count=5

图4 第六步 算法结束

首先初始化，利用循环右移的方法，当到第四行的时候和第一行没有节点，如图 1，则遍历第 0行令 a[0][2]=0，并令 T[2]=1，继续利用循环右移，得到 count=4，如图2所示。依次类推，当a[0][9]=1时，count=7，由于前T「N/2⏋行都为 1，如图 4所示，则算法结束。

3 性能分析

分布式互斥请求集生成算法的性能度量主要有三个指标：请求集长度、时间复杂度和空间复杂度。本文将分别分析这些指标。

3.1 请求集长度说的

表1比较了几种典型分布式互斥算法所产生的请求集长度，其中Bin-cyclic代表折半循环编码算法。

表1 几种分布式互斥算法的请求集大小的比较

3.2 时间复杂度

3.3 空间复杂度

由于折半循环算法引入了对称请求集的概念，只计算前「N/2⏋行和第0行有交点即可。空间复杂度为O(N2/2)，而本算法只是在贪心策略的基础上，依据贪心策略对可纳入节点通过局部求最优的方式来生成请求集，所以，空间复杂度与折半循环算法一样。

[1]MAEKAWA M.A Nalgorithm formutualexclusion 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.