分布式系统中互斥算法

01

—

    在集中式算法中，一般需要一个协调者。每个程序在访问临界资源的时候，需要先给协调者发送一个请求。如果当前临界资源没有使用者，则授权该程序使用该资源。如果有程序使用该资源，则给后来请求该资源的请求加入等待队列。如果资源被释放，则立即通知等待队列里面的其他程序使用。

     这种算法叫做集中式算法，因为依赖于中央服务器。从上面过程可以看出，一个程序完成一次临界资源的访问，需要给协调者发送一次请求，然后协调者向请求者发放授权，使用完资源后，向协调者释放资源的请求。此过程一共需要三次交互。

      从上面可以看成，集中式算法简单，易于实现，但是中心服务器需要处理的消息随着应用程序的增多而线性增长。此外，单一的中心服务器也容易引发单点故障。

    比如，使用Redis实现分布式锁，就类似于该算法。每个Redis客户端都会先去查询以下某个key，如果存在就认为有其他进程在使用某资源。如果访问完该资源，该客户端会删除key。

协商算法

     协商算法，一般每个程序都有自己的一个id。该算法的每一个使用资源的程序都需要向其他所有的程序发送请求，一般采用组播方式。若其他n-1个程序不使用该资源，则发送同意消息允许这个程序使用资源。如果某个程序也需要使用资源，则去自己缓存队列里面查看是否有其他程序请求，如果有就允许其他人先使用，正所谓先来先用。

     从上面流程大概可以看出，当需要访问临界资源的程序变多，则容易产生“信令风暴”，如果收到的请求大于自己的业务，则可能导致程序本身不可用。

    当某一个程序因为故障无法发送同意消息时，可能造成其他程序等待。这样分布式系统的可用性更差。解决办法一般是检测到这个程序故障，则无需等待其发送确认消息（超时确认机制）。这种分布式系统一般用在稳定的节点数量，且变动不频繁。

03

—