首页 > 代码库 > 基于请求的分布式互斥算法

基于请求的分布式互斥算法

2024-08-18 05:44:50   219人阅读

 一个悲剧的文章，研究的东西确实比较老，但是因为这些研究，让我对分布式的底层的关系有了更加清晰的认识，也算是不枉此功。

下面贴出来核心的部分。

  1. 引言

    分布式系统中的一组进程可能会同时访问一个资源或者同时执行一个给定的函数，我们称这些资源或者函数为临界区（Critical Section），若不加控制的话，会造成资源或者环境的不一致的现象。保证任何给定时刻只允许一个进程或者给定的进程去执行临界区的算法称为互斥算法。互斥也可以称为并发控制。

    这个问题最早由Dijkstra[1]在1965年提出。互斥可以基于硬件也可以基于软件。本文局限于软件实现。

    传统的单机独立系统上的进程互斥的方法有互斥锁，条件变量，读写锁，共享内存，信号量等。单机系统的互斥也有很多有益的探索。最早给出这个问题解决方案的算法是Dekker[2]算法，首次基于共享内存的方法控制两个进程并发访问同一个共享的用户资源而不发生冲突。随后的Peterson[3]算法提出了更为简便的方法，采用全局数组和全局变量的结合，可以轻松的推广到N个进程互斥的情况。

    分布式环境中，共享变量和局部内核都不能被用于实现互斥。消息传递是实现互斥的唯一的方法[4]。

    分布式互斥算法可以分为集中式算法（Centralized Algorithm）和分布式算法（Distributed Algorithm），其中分布式算法又可以分为[19]基于令牌的算法（Token Based Algorithm）和基于请求的算法（Permission Based Algorithm）。

    集中式算法选取一个进程作为协调者，接受请求和分发授权，协调者维护一个FIFO队列，按照队列的先后顺序分发授权，这样做的好处是公平，而且逻辑简单，容易实现。但是进程并不能区分协调者失效还是忙碌，即使失效也没有重新选举的方法。除此之外协调者显然也是系统性能的瓶颈。

    基于令牌的算法中，进程按照给定的逻辑结构组合在一起，全局有一个令牌（Token）数据结构，获取这个数据结构才能去执行临界区。令牌的唯一性保证了互斥的实现。基于请求的算法相对于基于令牌的算法，平均的带宽更大，但是基于令牌的算法的令牌丢失或者失效，需要执行非常复杂的选举机制和状态恢复机制。所以基于请求的算法可能更符合分布式的环境。

    本文主要研究基于请求的分布式算法。为了方便讨论把互斥协议，互斥定理，基本假设，评价标准等首先统一，在此基础上给出一些有代表性算法的基本目标和实现思路，然后给出算法的伪代码的实现，最后分析算法的带宽的对比，并且讨论了分布式互斥算法的最新的发展和未来。
  2. 协议与约定
    1. 执行临界区

      执行临界区需要依据下面的协议：

      Enter()//进入临界区，可能阻塞

      Access(CS)//执行临界区

      Exit()//离开临界区
    2. 互斥基本性质

      根据文献[4]和[5]互斥的基本要求有下面的性质：

      性质1:安全性，在临界区一次最多有一个进程可以执行，这是互斥算法的本质要求。

      性质2:活性，进入和离开临界区的请求最终成功执行，不存在饥饿和死锁，亦即每个请求站点都能在有限的时间内得到执行临界区的机会。

      性质3:顺序性或者公平性，如果一个进入CS的请求发生在先，那么进入CS时仍按照此顺序，每个进程都获得公平的机会执行临界区。先后是基于逻辑时间戳[6]。
    3. 一致性假设

      为统一的给出算法描述，给出下面的假设，若在算法中没有具体的说明，都按照下面的假设执行。

      基本假设：

      （1）假设有N个站点，称为S，第i个站点称为Si，其中i=1,2,…,N；

      （2）站点Si上运行一个进程Pi，其中i=1,2,…,N；无特殊说明站点和进程同义；

      （3）每个进程仅有三种状态：请求(WANTED)，执行(HELD)，释放(RELEASED)；

      （4）消息的种类，请求(REQUEST)，应答(REPLY)，通知(RELEASE)；

      （5）假设进程通信采用消息传递，信道可靠，有重传等通信协议，无拜占庭错误；

      （6）假设不发生崩溃或者丢失，网络延时随机，但是有限；

      （7）假设网络无分割，节点全连通；

      （8）假设系统无统一物理时钟，进程逻辑时间戳采用Lamport逻辑时间戳[6]，越小优先级越高；

      （9）假设网络连接非对称（Pi到Pj通不能保证相反也通）且不传递（Pi到Pj通且Pj到Pk通不能推导出Pi到Pk通）；

      （10）假设进程独立，不依赖其他进程转发消息；

      （11）一般无死锁或者饥饿；
    4. 互斥算法性能评价指标

      指标1.消息复杂度也称为带宽：进程执行一次完整的临界区需要的消息数；

      指标2.同步延迟SD：上一个进程离开临界区到下一个进程执行临界区的时间间隔；

      指标3.响应时间：一个请求消息发出到请求的临界区执行结束的时间间隔；

      指标4.系统吞吐量：假设E是平均临界区的执行时间，那么吞吐量=1/(SD+E);

      带宽越小，延时越短，响应时间越短，吞吐量越大，算法的性能表现的越好。文章给出每个算法的可能的带宽作为评价算法性能的主要指标。
  3. 基于请求的分布式互斥算法

    进程在进入临界区前先会向需要请求的进程发送一个请求，在得到可以满足互斥的性质的许可的回复之后，执行临界区。下面按照算法的发展历程，从朴素到复杂，分别介绍，并给出有代表性算法的详细逻辑。


    1. Lamport算法

      该算法[7]某种程度上开创了分布式互斥算法的先河，提出了正确的解决分布式问题的基本的假设与思路，后续的解决方案基本上都是在此算法的基础上进行改进与优化。

      算法中的每个进程维护一个按照顺序进入临界区的队列，队列按照Lamport时间戳排列。在进入临界区前先向所有的其他进程请求，在离开临界区的时候向所有的其他进程发送释放消息。

      伪代码如下：
      if(Pi:state=HELD) then
{执行临界区}
else 
    {Pi delete <Ti,Pi> in queue}
{Multicast (N-1) RELEASE}
{Pi:state=RELEASED}
    if(Pj receive RELEASE) then
        {delete <Ti,Pi> in queue}
        if(Pj:state=RELEASED) then
            if(想执行临界区) then
//尝试获取临界区
                { Pj Multicast<Tj,Pj>}
                {Pj:state=WANTED}
                if(应答数=N-1) then
                    {state=HELD}
                    {执行临界区}
                else    
                    {state=WANTED; Time out Retry}
                end if
            else
                if(Pj receive REQUEST<Tk,Pk>) then
                    {add <Tk,Pk> to Queue}
{Reply Tj(>Tk) to Pk}
                end if
            end if
        end if
    end if
end if

      很明显该算法的带宽是3*(N-1)，一份发送组播，一份回复组播，一份释放组播。

    2. Ricart-Agrawala算法

      该算法[8]相对于上一个算法，队列也是维护着逻辑时间戳，但是在接收请求的时候，有对比的行为，相对来说不用靠接收释放消息去更新自己维护的队列了。这样每个临界区执行需要的平均消息传递的数量就会减少一次释放组播。

      伪代码如下：
      if(Pi:state=HELD) then 
    {执行临界区}
else
    //退出临界区
    {Pi:state=RELEASED}
    if(Pj想执行临界区) then
        { Pj Multicast <Tj,Pj>}
        {Pj:state=WANTED}
        if(应答数=N-1) then
            {state=HELD}
            {执行临界区}
        else
            {state=WANTED}
        end if
    end if
    if(Pk receive REQUEST<Tj,Pj>) then
        if(Pk:state=HELD or (Pk:state=WANTED and <Tk,Pk><<Tj,Pj>)) then
            {add REQUEST into Pk queue, no reply}
        else
            {REPLY<Tk,Pk>}
        end if
    end if 
end if

      所以该算法的带宽是2*(N-1)。

    3. Lodha-Kshemkalyani算法

      该算法[4]是Ricart-Agrawala算法的优化。算法的基本的思想是：当一个进程在等待执行临界区时，不需要从每个进程收到REPLY，取而代之是只需要从比它优先级高的进程收到REPLY就可以；当一个进程在离开临界区时，不需要对每个进程发送离开的消息，取而代之的是发送给拥有次高优先级的请求的进程就可以了。这样可以有效的减少算法的带宽。

      为了实现上面的思想，算法有下面的新增加的临时假设：

      临时假设（1）：每个请求都有个优先级ReqID，临界区的执行顺序按照优先级递减的顺序执行的。

      临时假设（2）：当且仅当Pi发出请求后收到Pj的请求并且在Pj发出请求后收到Pi的请求的时候，称Pi和Pj是并发的。

      临时假设（3）：对于每个进程i定义一个并发集CSet_i。

      临时假设（4）：算法并不使用基本的三种消息，而是实现REQUEST,REPLY,FLUSH这三种消息，每种消息赋予多个用途，这样可以减少带宽。

      临时假设（5）:为了实现互斥，每个进程有一个local_request_queue的数据结构，这个结构包含Pi的并发请求，并按照优先级排序。

      下面是算法的伪代码的实现：

      初始化状态：
int My_Sequence_Number_i(简称MSN_i)=0
array of boolean RV_i_[j]=0,其中j=1,...,N
queue of ReqID Local_Request_Queue_i=NULL(简称LRQ)
int Highest-Sequence_Number_seen_i(简称HSN_i)=0
对于任意的进程：
if(RV_i_[k]=1,k=1,2,...,N；且进程Pi的REQUEST在 LRQ_i队列中的队首) then
    {return CheckExecuteCS:TRUE}
else
    {return CheckExecuteCS:FALSE}
end if

主逻辑：
if(Pi:state=HELD) then
    {执行临界区}
else
    //退出临界区
    {send FLUSH(Ri) to next process in LQR_i}
    {send REPLY(Ri) to the process being delayed}
    {Pi:state=RELEASED}
    if(Pj,Pk:state=RELEASED) then
        if(Pj want to Enter(CS)) then
            {MSN_j=HSN_j+1}
            {LRQ_j=NULL}
            {generate REQUEST(Rj)，其中Rj=(MSN_j,j)}
            {add it into LRQ_i}
            {send REQUEST to all other proccess}
            {RV_j_[K]=0,k={1,...,N}-{j},RV_j_[j]=1}
            if(receive REPLY(Rk)) then
                {RV_j_[K]=1}
                {delete request process higher priority then Rk in queue LRQ_j}
                if(CheckExecuteCS) then
                    {执行临界区}
                end if
            end if
        end if
        if(Pk receive REQUEST(Rj)，其中Rj=(SN,j)) then
            HSN_k=MAX(HSN_k,SN)
            if(Pk want to Enter(CS)) then
                if(RV_k_[j]=0) then
                    {add into LRQ_k, set RV_j_[j]=1}
                    if(CheckExecuteCS) then
                        {执行临界区}
                    end if
                else
                if(RV_k_[j]=1) then
                    {no reply until Pi:Exit(CS)}
                end if
            else
            if(Pk do not ask for Enter(CS)) then
                {send REPLY(Rk) to Pj，其中Rk表示Pk最后一个被满足的请求的ReqID}
            end if
        else
        if(Pk receive FLUSH(Ri) from Pi) then
            {RV_k_[i]=1}    
            {delete all the processes higher priority than Ri in queue LRQ_k}
            if(CheckExecuteCS) then
                {执行临界区}
            end if
        end if
    end if
end if

      进程为了执行临界区要发送N-1条请求，但是回复的消息的数目是N-|CSet_i|。当|CSet_i|等于1的时候说明所有的请求被依次满足，Pi将不会发送FLUSH消息，那么也不会有消息数目的减少，此时的带宽是2*(N-1)，这是最坏的情况。当|CSet_i|大于等于2的时候，若不存在优先级低于Ri的请求，也不会发送FLUSH消息，那么带宽是2N-1-|CSet_i|；若至少存在一个低于Ri的请求，那么会发送一个FLUSH消息，此时的带宽是2N-|CSet_i|。这两种情况还要考虑并发，并发的数目可能是0-N个。那么这两种情况的带宽最小的可能分别是N-1和N。综上所述，该算法的带宽的范围是N-2*(N-1)。


    4. Carvalho-Roucairol算法

      该算法[9]还是对Ricart-Agrawala算法进行优化。基本的思想是对已经拥有许可的并且没有申请优先级更高的请求的进程，再次进入临界区的时候不用发送请求也不用接收回答。

      算法的伪代码如下：

      if(Pi:state=HELD) then 
    {执行临界区}
else
    //离开临界区
    {Pi:state=RELEASED}
    if(Pj Mulyicast <Tj,Pj>) then
        {Pj:state=WANTED}
        if(应答=N-1-K)  then
//其中K是其拥有权限且未发出优先级更高的请//求的进程的数量0<k<N-1
            {state=HELD}
        else
            {state=WANTED}
        end if
    end if
    if(Pk reveive REQUEST<Tj,Pj>) then
        if(Pk:state=HELD or (Pk:state=WANTED and <Tk,Pk><<Tj,Pj>)) then
            {add the request into queue of Pk, no reply}
        else
            {REPLY<Tk,Pk>}
        end if
    end if 
end if

      容易知道该算法的带宽是0到2*(N-1)。

    5. Raynal算法

      这个算法[10]设计的目的不是为了优化带宽，而是为了展示这种设定或者这种设定的性质能够作为分布式算法设计的有用的工具。本算法中的进程排列的数据结构是单向环状结构。

      每个进程维护一个变量Xi，初始化为Ai，其中Xk被初始化为1，所以可以执行临界区。，若是i号进程请求N-1个进程，得到的N-1个REPLY(j,Xj)，这个进程计算，要是T=Q/Ai，那么这个进程可以执行临界区，否则的话更新Xi=(Xi*Ai/Aj)，这里的j=(i+1) mod N，这样的设置可以使得逻辑环变成Pk,pk+1,..,p1,p1,..,pk结构。这里的证明请参考原始论文。

      下面是算法完整的伪代码描述：

      if(Xk=1 && Xk:state=WANTED) then
    {执行临界区;state=HELD}
else
    {send CS to next process}
{update Xk; Multi cast RELEASE; STATE=RELEASED}
    if(X(k+1):state=RELEASED) then
        {send CS to next process，updateX(K+1)}
//这里不更新也不传递会出现死锁
    else 
    if(X(k+1):state=WANTED) then
        {Multi cast (N-1) REQUESTs}
        if(receive (N-1) REPLY(j,Xj)) then
            {Calc T，means the sum of all Xj}
            if(T=Q/Ai) then
                {执行临界区;state=HOLD}
            else
                {wait, resend the REQUEST}
            end if
        else
            {接收组播回复消息失败}
        end if
    else 
    if(x(k+1):state=HELD)
    then
        {no REPLY}
    else 
        {REPLY}
    end if
end if

      最差的情况下，带宽是2*(N-1)*(N-1)，就是释放临界区时相反的方向的第一个进程最终拿到临界区的执行权。

    6. Raynal算法改进

      文献[18]在原始算法的基础上，提出了一种改良的算法，能够有效的避免死锁并且一定程度上减小带宽，在原来的假设的基础上，每个进程维护一个局部变量，指明了去哪里请求临界区，当节点i不请求临界区，但是下一个获取权限的节点，更新Xi并把这个权限直接传递下去，避免了死锁。更新之后，发送消息INFORM(i,Xi)给N-1个节点，K节点收到消息，检查T时候和Q/Ak是否相等。如果相等，并且在请求，就进入临界区，否则的话传递临界区的权限，这样传递带宽最坏的情况下是(N-1)*(N-1)。

      算法的伪代码描述如下：
      if(Xk=1并且Xk:state=WANTED)  then
    {执行临界区;state=HELD}
else
    {send the CS to the next process}
{update Xk}
{Multi cast (N-1) INFORM(k,Xk)}
{STATE=RELEASE}
    if(X(k+1):state=RELEASE)  then
        {send the CS to next process，update Xk}
    else 
        if(X(k+1):state=WANTED)  then
            {给特定有权限的进程发送请求}
            if(收到回复) then
                {计算T的值，也就是Xj的和}
                if(T=Q/Ai)  then
                    {执行临界区;state=HOLD}
                else
                    {等待，再重新发送请求}
                end if
            else
                {接受回复失败}
            end if
        end if
    else    
        if(x(k+1):state=HELD)  then
            if(没执行完)  then
                {不回答}
            else 
                {回答}
            end if
        end if
    end if
end if

       

    7. Maekawa算法

      为了降低请求的带宽，这个算法[11]率先提出了基于子集请求而不是基于全集请求的互斥算法。有时候这类算法也称为基于仲裁团的互斥算法。

      该类算法增加一个很重要的基本假设：在进程接收到请求的回答之前，不能再发送请求。所以我们在下面的伪代码中增加了一个布尔类型的VOTED状态。为真的话，表示进程已经投票过了，暂时不能回复。一个仲裁团(Quorum)是一个集合。一个圈子(Coterie)是集合的集合。在一个圈子C中的Q满足相交性和最小性。其中相交性指对于任意的g,h属于C,g和h的交集不为空；最小性指圈子C中的任意的g和h不存在包含或者被包含的关系。

      仲裁团构造的算法有多种多样，构造算法对算法带宽的影响的研究室这类算法研究的热点。本算法利用投影平面理论构造了大小为的仲裁团。

      结合上面的性质，算法对于Pi关联的仲裁团Hi做出下面的约束，对于任意进程：Pi属于Hi；Hi和Hj的交集不为空，两个仲裁团至少有一个公共成员；为了公平起见，每个进程有同样大小的仲裁团，也就是|Hi|=K；任何Pi都包含在K个不同的仲裁团中，意味着所有站点在授权其他站点的时候有平等的责任。

      算法的伪代码如下：

      if(Pi:state=HELD) then
    {执行临界区}
else
    //释放临界区
    {send RELEASE给其仲裁团Hi中所有的进程}
    {state=RELEASE}
    if(Pj组播WANTED给仲裁团中的所有进程) then
        {Pj:state=WANTED}
        if(应答=K) then
            {state=HELD}
        else
            {state=WANTED}
        end if
    else
    if(Pj receive RELEASE) then
        if(请求队列非空) then
            {删除队列对头Pk，将应答发送给Pk}
            {VOTED=YES}
        else
            {VOTED=FALSE}
        end if
    else
    if(Pj接受到来自Pk的请求) then
        if(state=HELD或者VOTED=TRUE) then
            {将来自Pk的请求放在队列，不予应答}
        else
            {发送应答给Pk}
            {VOTED=TRUE}
    end if
end if

      算法的带宽是3*根号下N，分别是一份请求REQUEST，一份回答REPLY，和一份释放RELEASE。改算法的缺点是容易因为相互等待而出现死锁。文献[4]给出了一种死锁的处理方法。

    8. Maekawa算法死锁处理

      为了妥善处理死锁，需要添加三个状态FAILED，INQUIRE，YIELD。

      伪代码如下所示：

      if(Pj收到Pi的REQUEST) then
    if(Pj已经发送REPLY给Pk) then
        {Pi的请求阻塞}
        if(Pi的请求有更低的优先级) then
            do {Pj发送FAILED(j)给Pi}
        else
            do {Pj发送INQUIRE(j)给Pk}
            if(Pk接收到仲裁团中的一个进程的FAILED消息 或者 Pk曾发送过一个YIELD(K)消息但是没收到REPLY) then
                {Pk发送一个YIELD(K)消息给Pj}
                {Pj将Pk的请求放在一个适当的位置，给队列首的站点发送一个REPLY(j)}
            end if
        end if
    end if
end if

      增加这些额外的消息处理死锁，可能需要在没有死锁的情况下也发送这些消息，这种情况下带宽的最坏的情况变成了5*根号下N。

    9. Sanders算法

      这个算法[12]提供了一种通用的互斥算法，用信息结构描述一些集合，每个进程在进入临界区之前都要向这些集合请求信息或者许可。集合分为三种，信息集合：Ii；请求集合：Ri；状态集合：Si。这些集合满足下面的两个条件：

      第一个：Ii是Ri的子集；

      第二个：对任意的i和j，要么满足在Ii和Ij之间要有非空的交集，要么满足j属于Ri并且i属于Rj。如果j是Si的成员且i是Ij的成员的话，Si取决于Ii。

      该算法依据逻辑时间戳，增加了一个变量CSSTAT去表示进程对临界区的了解，这个变量可以展示临界区空闲或者包含了一个Si中的进程的标志，这个进程已经收到了GRANT但是没收到RELEASE消息，也就是等待临界区释放并进入的进程号。

      算法的伪代码如下：

      if(i:state=HELD) then
    {执行临界区}
else
    {发送RELEASE消息给Ii中的所有的进程}
    {Ii中的进程把各自的CSSTAT设置，表示临界区现在空闲}
    while(队列中下一个进程k不是Sk的成员并且队列不为空的时候)
    {授权给请求进程k}
    if(k是Sk的成员) then
        {设置CSSTAT显示进程正在执行临界区}
    end if
    if(j:state=RELEASE)
    then
        if(j向Rj中的所有进程发送REQUEST请求) then
            {j:state=WANTED}
            if(j是Sj中的元素的话) then
                {设置CSSTAT指示临界区正在被执行}
            else
            if(接收Rj中的所有的GRANT话) then
                {j:state=HELD}
            else
                {j:state=WANTED}
            end if
        end if
        if(j接收到REQUEST消息) then
            {保存到自己维护的队列中}
            if(临界区不空闲j的逻辑时间戳比CSSTAT表示的进程的逻辑时间戳大) then
                {给请求进程发送失败消息}
            else
            if(CSSTAT是FREE的) then
                {发送GRANT消息给队列中的第一个进程假设为t，更新队列}
                if(t属于Sj) then
                    {设置CSSTAT指示临界区正在被执行}
                end if
            end if
        else
        if(j接收到RELEASE消息) then
            {设置CSSTAT为空}
            {发送GRANT消息给队列中的第一个进程假设为t，更新队列}
            if(t属于Sj) then
                {设置CSSTAT指示临界区正在被执行}
            end if
        end if
    end if
end if

      根据论文的描述算法的带宽是|Ii-{i}|+2*|Ri-{i}|。

    10.  Agrawal-EI Abbadi算法

      该算法[13]引入了树状结构去构造仲裁团。任意的站点可以被选择为根节点(真实的实现中需要先指定一个根节点)，相应的有两个任意的站点可以被选择为它的子节点，接着这些节点还可以选择自己的两个子节点，以此类推。
      为了方便讨论，假设所有的站点可以组成一个K级完全二叉树，根节点在K级，叶子节点在0级。总共有2^(K+1)-1个节点。从根节点到叶子节点，站点的个数等于叶子的级数K+1。
      算法采用了两个函数GetQuorm(Tree)函数和GrantsPermission(site)函数构造树状结构仲裁团(详细的过程参见原始论文)。
      树结构中的所有的从根节点到叶子节点的进程可以构成一个仲裁集。如果路径的某些节点失败了，可以用两个从失败节点的子节点到叶子节点的路径代替。但是如果叶子节点的进程失败了，那么这个路径的集合就不能再用作仲裁集了。
      算法的伪代码如下：

      if(Pi:state=HELD) then
    {执行临界区}
else
{释放临界区：向仲裁团中的所有的进程发送RELINQUISH消息}
    {Pi:state=RELEASED}
    if(Pj,Pk:state=RELEASE) then
        if(Pj希望进入临界区) then
            {send REQUEST 给它所在的结构中的所有的进程}
            {Pj:state=WANTED}
            if(Pj收到INQUIRE消息) then
                if(收到所有的站点的REPLY) then
                    {执行临界区}
                    {Pj:state=HELD}
                else
                    {发送YIELD消息给发送INQUIRE的进程(Pk)}
                end if    
            end if
        end if
        if(Pj收到RELINQUISH消息) then
            {把发送释放消息的请求进程从自己的请求队列中移除}
        end if
        if(Pk收到新的REQUEST消息) then
            if(新的请求进程的时间戳小于自己的队列中队首(Pj)的时间戳) then
                {向队首请求对应的进程发送INQUIRE消息}
                if(收到YIELD) then
                    {将新的请求放在队列的队首，并发送一个REPLY消息}
                else
                    {不回复}
                end if
            else
                {维护到自己的队列中，不回复}
            end if
        end if
    end if
end if

      此算法没有失败的情况下的带宽是O(Log(N))。当存在某些可以容忍的失败的情况下需要的带宽是(N+1)/2。

      算法对节点失败有一定的容忍程度，但是如果失败的节点超过log(N)的时候算法可能不能生成树状的仲裁集了。也就没法正确执行算法了。

    11. Singhal算法

      普通的互斥算法都是静态的方式去实现互斥，该算法[14]能有效的挖掘系统中不断变换的环境因素，实现算法性能的优化。

      算法的基本实现是：如果少数的站点频繁的启用互斥，而其他站点不经常启用互斥。那么频繁站点没必要在每次请求临界区的时候都寻求其他低频站点的许可，只要得到其他的频繁站点的许可就行了。

      本质上该算法是一种自适应的互斥算法。随着进程通过收发消息对系统状态的了解，该算法的信息结构将随着时间不断演化。为了具体描述这种自适应的数据结构，称包含Pi在执行临界区请求时候必须请求的站点的集合是请求集，记作Ri；称包含Pi在执行完临界区后必须给他们发送许可的站点的集合为通知集，记作Ii。

      对于任意的两个进程i和j，它们的Ri和Rj没有交集，这样可以满足互斥的要求。

      Ri会把给i发送请求的进程加到集合里面，也会把i发送完请求的进程从集合中拿出去。

      在接收请求时候，如果i在请求并且i的请求的时间戳更小，或者i在执行临界区，Ii会把请求进程放进去。

      对于i发送请求的进程，在释放临界区的时候，Ii会把这样的进程拿出去。

      每个站点Si维护一个逻辑时钟Ci。

      本算法也实现了自己的三个属性为布尔值的状态：Requesting表示请求，Executing表示执行，My_priority表示站点的请求比当前进入的请求有更高的优先级。

      算法的伪代码的实现如下：

      初始化：对于Si有
Ri={S1,S2,...,S(i-1),S(i)}；Ii={Si}；Ci=0；
Requesting=Excuting=False
主逻辑：
if(Pi:state=HELD) then
    do {执行临界区}
else
    do {释放临界区}
    for(Ii中的每个Pk其中k≠i)
        {Ii=Ii-{Pk}}
        {发送REPLY(Ci,i)消息给Pk}
        {Ri=Ri+{Pk}}
    end for
    {Pi:state=RELEASED}
    if(Pj,Pk:state=RELEASE) then
        if(Pj希望进入临界区) then
            {Requesting=true}
            {send REQUEST(Cj,j) 给Rj中的所有的进程}
            
            if(Pj收到Pk的Requset(Ck,k)) then
                {更新自己的时间戳}
                if(站点的请求(Pj)比当前进入的请求(Pk)有更高的优先级) then
                    {Pj:My_priority=True}
                    {Ij=Ij+{Pk}}
                else
                    {发送REPLY(Cj,j)消息给Pk}
                    if(Pk不属于Sj) then
                        {Rj=Rj+{Pk}}
                        {发送REQUEST(Cj,j)消息给Pk}
                    end if
                end if
            end if                
            {Requesting=False}
            if(收到Rj所有的进程的REPLY) then
                {根据回复的C更新时间戳并且把收到回复的进程从Ri中移除}
                {Executing=True}
                {执行临界区}
                    if(Pj收到Pk的Requset(Ck,k))
                    then
                        {Ij=Ij+{Pk}}
                    end if
                {Executing=False}
                    if(Pj收到Pk的Requset(Ck,k))
                    then
                        {Rj=Rj+{Pk}}
                        {send REPLY(Cj,j) to Pk}
                    end if
            else
                {根据回复的C更新时间戳并且把收到回复的进程从Ri中移除，继续等待回复}
            end if    
        end if
    end if
end if

      低负载情况下，大部分的时候系统中只有一个或者没有临界区的请求，那么每次执行临界区的需要的平均的REQUEST消息是(0+1+2+...+(N-1))/N=(N-1)/2，因为有一个REPLY与其对应，所以每次执行临界区需要的消息个数是(N-1)

      高负载情况下，所有的进程始终会挂起一个临界区的请求，这种情况下，站点等待自己的REPLY的时候会接收到(N-1)/2个REQUEST请求，但是进程只有在比这些请求有更高的优先级的时候才能发送REQUEST，所以在等待自己的REPLY时候还会平均发送(N-1)/4个REQUEST，那么站点在获得临界区之前,系统存在的REQUEST为(N-1)*3/4，因为有一个REPLY消息和它对应，所以系统的带宽是3*(N-1)/2。

  4. 对比与总结
    1. 　　算法的带宽的对比

      根据上面的分别的描述可以总结出来下面的带宽的对比的表格：

      表1  基于请求的分布式互斥算法带宽对比

      算法

      带宽

      数据结构

      Lamport算法

      3*(N-1)

      无

      Ricart-Agrawala算法

      2*(N-1)

      无

      Lodha-Kshemkalyani算法

      N到2*(N-1)

      无

      Carvalho-Roucairol算法

      0到2*(N-1)

      无

      Raynal算法

      2*(N-1)^2

      Prime Number

      Raynal算法改进

      (N-1)^2

      Prime Number

      Maekawa算法

      3*SQRT(N)

      仲裁团

      Maekawa带死锁处理算法

      5*SQRT(N)

      仲裁团

      Sanders算法

      |Ii-{i}|+2*|Ri-{i}|

      基于仲裁团

      Agrawal-El Abbadi算法

      O(Log(N))或(N+1)/2

      树状仲裁团

      Singhal算法

      (N-1)到3*(N-1)/2

      动态信息结构

      上面介绍的各种分布式互斥算法基本上按照性能逐渐优化的方式进行讨论的。从开始的三份消息传输，到后来的指定的进程相互传递，到固定的数据结构辅助，到只请求一个特定的集合，到最后的变结构的算法，可以清楚的看到在减少带宽方便的优化的效果。

      文献[20]给出了这些算法的更加细致的分类，将基于请求的算法分为基于投票的算法（Voting-based）和基于小团体（Coterie-based）的算法。其中每种算法分为静算法和动态算法。静态算法指不记录执行临界区的历史，节点不保存系统现在的状态信息；动态算法指节点追踪系统现有的状态，算法有根据这些信息做出决策的机制。这些分类为进一步细化基于请求的互斥算法给出了正确的指引。

    2. 未来的挑战

      随着业务场景的复杂化，越来越多的分布式的环境正在逐渐代替现在的集中式的环境。这些互斥算法虽然在理论上非常朴素，但是在真实的分布式环境中可以表现的非常的复杂。所以对现有的算法的优化或者提出新的互斥算法依然具有很强的现实意义。

      例如，文献[21]提出了一种组合了基于请求和基于令牌的组合算法；上面算法涉及的投票的权重都一样称为统一投票（uniform voting）,文献[22]首先提出了一种变权重的算法。文献[23]结合神经网络算法实现互斥。

      由于真实的分布式环境会出现各种有悖于文中假设的情况，可以预见的是未来的基于请求的分布式互斥算法的将会更多的考虑到节点失效和节点超时的处理，以增强系统的容错性。

      此外尝试允许多个进程同时执行临界区的K-互斥[24]问题也是该领域研究的最新的热点。

  5. 参考文献

    [1]       Dijkstra E W. Solution of a Problem in Concurrent Programming Control[J]. Communications of the Acm, 2014, 8(1):289-294.

    [2]       Dijkstra E W. Co-operating sequential processes[J]. Origin of Concurrent Programming, 1968:43--112.

    [3]       Peterson G L. Myths about the mutual exclusion problem[J]. Information Processing Letters, 1981, 12(3): 115-116.

    [4]       Kshemkalyani A D, Singhal M. Distributed computing: principles, algorithms, and systems[M]. Cambridge University Press, 2011.

    [5]       Coulouris G F, Dollimore J, Kindberg T. Distributed systems: concepts and design[M]. pearson education, 2005.

    [6]       Lamport L. Time, Clocks, and the Ordering of Events in a Distributed System.” CACM 21 (7): 558-565[J]. Communications of the Acm, 1978, 21:558-565.

    [7]       Lamport L. A New Solution of Dijkstra‘s Concurrent Programming Problem.[J]. Communications of the Acm, 1974, 17(8):453-455.

    [8]       RICART, G.and AGRAWALA, A. K., "Author response to ‘on mutual exclusion in computer networks‘ by Carvalho and Roucairol,"Communications of the ACM, vol. 26, no. 2, feb. 1983, pp. 147-148.

    [9]       Carvalho O. On Mutual Exclusion in Computer Networks[J]. Communications of the Acm, 1983, 26(2):146-147.

    [10]    Raynal M. Prime numbers as a tool to design distributed algorithms[J]. Information Processing Letters, 1989, 33(1):53-58.

    [11]    Maekawa M. A \sqrtN$ Algorithm for Mutual Exclusion in Decentralized Systems[J]. Acm Trans on Computer Systems, 1985, 3:145--159.

    [12]    Sanders B A. The information structure of distributed mutual exclusion algorithms[J]. Acm Transactions on Computer Systems, 1987, 5(3):284-299.

    [13]    Agrawal D, Abbadi A E. An Efficient and Fault-Tolerant Solution for Distributed Mutual Exclusion[J]. Acm Transactions on Computer Systems, 1991, 9(1):1-20.

    [14]    Singhal M. A dynamic information-structure mutual exclusion algorithm for distributed systems[J]. IEEE Transactions on Parallel & Distributed Systems, 1992, 3(1):121-125.

    [15]    Tanenbaum A S, Van Steen M. Distributed systems: principles and paradigms[M]. Englewood Cliffs: Prentice hall, 2002.

    [16]    Attiya H, Welch J. Distributed computing: fundamentals, simulations, and advanced topics[M]. John Wiley & Sons, 2004.

    [17]    Lynch N A. Distributed algorithms[M]. Morgan Kaufmann, 1996.

    [18]    Velazques M G. A survey of distributed mutual exclusion algorithms[M]. Colorado State Univ., 1993.

    [19]    Raynal M. A Simple Taxonomy for Distributed Mutual Exclusion Algorithms.[J]. Acm Sigops Operating Systems Review, 1991, 25(2):47-50.

    [20]    Saxena P C, Rai J. A survey of permission-based distributed mutual exclusion algorithms[J]. Computer Standards & Interfaces, 2003, 25(2):159-181.

    [21]    Mizuno M, Neilsen M L, Rao R. A token based distributed mutual exclusion algorithm based on quorum agreements[C]// International Conference on Distributed Computing Systems. 1991:361--368.

    [22]    Gifford D K. Weighted voting for replicated data[C]// ACM Symposium on Operating Systems Principles. ACM, 1979:150--162.

    [23]    Singhal M. A Heuristically-Aided Algorithm for Mutual Exclusion in Distributed Systems[J]. IEEE Transactions on Computers, 1989, 38(5):651-662.

    [24]    Raymond K. A distributed algorithm for multiple entries to a critical section[J]. Information Processing Letters, 1989, 30(4):189-193.

    于2016年4月20日

基于请求的分布式互斥算法


联系
我们