当前位置：首页 > news >正文

【分布式理论9】分布式协同：分布式系统进程互斥与互斥算法

news 来源：原创 2025/5/17 22:05:08

文章目录

- 一、互斥问题及分布式系统的特性
- 二、分布式互斥算法
- - 1. 集中互斥算法
  - - 调用流程
    - 优缺点
  - 2. 基于许可的互斥算法（Lamport 算法）
  - - 调用流程
    - 优缺点
  - 3. 令牌环互斥算法
  - - 调用流程
    - 优缺点
- 三、三种算法对比

在分布式系统中，多个应用服务可能会同时访问同一个资源，导致互斥问题的出现。例如，在分布式数据库环境中，多个事务可能同时尝试对同一行数据加锁，导致锁争抢，影响系统性能。为了避免互斥现象，并保证数据的一致性，引入了分布式锁机制。而支撑分布式锁的理论基础，就是分布式互斥算法。

一、互斥问题及分布式系统的特性

以现实生活中的例子来类比，假设有两个小孩想玩同一个玩具，但玩具只能由一个小孩使用，另一个小孩必须等待。这种情况类似于计算机系统中的互斥问题：

共享资源（玩具）只能由一个进程访问。
竞争该资源的进程必须遵循一定的顺序。
若资源被占用，其他进程必须等待。

在单机环境下，进程互斥问题可以通过线程同步等方式解决。但在分布式系统中，由于各个进程部署在不同的服务器上，互斥问题变得更为复杂，必须考虑以下特性：

互联网特性：分布式系统中的服务器通过网络连接，网络延迟、丢包等问题可能影响互斥操作。
没有统一时钟：不同服务器的时钟不同步，导致进程无法准确判断资源请求的先后顺序。
服务器和网络可能故障：当某个服务器或进程发生故障，其他服务器需要感知并进行相应处理。

二、分布式互斥算法

针对分布式系统的互斥问题，研究者提出了不同的互斥算法。这些算法适用于不同的场景，例如，某些算法适合小规模系统，而另一些则更适用于高并发环境。主要包括：

1. 集中互斥算法

集中互斥算法的核心思想是引入一个全局协调者（类似于老师管理玩具的使用），由协调者统一管理资源访问请求。

在这里插入图片描述

调用流程

进程向协调者发送资源访问请求。
协调者根据请求时间戳排队，并允许最先请求的进程访问资源。
进程访问资源后，向协调者发送释放通知。
协调者允许下一个进程访问资源。

在这里插入图片描述

优缺点

优点：实现简单，协调者能有效控制资源的访问。
缺点：
- 协调者可能成为系统瓶颈，影响性能。
- 协调者的单点故障会导致系统不可用。

2. 基于许可的互斥算法（Lamport 算法）

在集中互斥算法中是通过协调者记录先后顺序的，而在 Lamport 算法中，每个节点进程都会维护一个逻辑时钟，当系统启动时，所有节点上的进程都会对这个时钟进行初始化，每当节点进程向其他节点进程发起临界资源访问申请的时候，就会将这个逻辑时间戳加 1。

即该算法不依赖单个协调者，而是由各个进程相互协商资源访问权。

调用流程

进程向所有其他进程发送资源访问请求（REQUEST）。
其他进程收到请求后，将其加入本地队列，并根据逻辑时钟更新顺序。
当请求进程收到所有进程的许可（REPLY）后，即可访问资源。
访问完成后，进程向所有等待的进程发送释放消息（RELEASE），其他进程更新队列。

在这里插入图片描述

优缺点

优点：
- 解决了分布式系统时钟不同步的问题。
- 适用于进程较少的场景。
缺点：
- 需要进行大量消息传输，通信开销较大。
- 资源请求多时，系统响应可能变慢。

3. 令牌环互斥算法

令牌环算法类似于小孩们围成一圈，轮流传递一个令牌（Token），拿到令牌的孩子才能玩玩具。

如下图令牌环互斥算法中的所有节点进程构成一个环结构，每个节点进程都有一个唯一 ID 作为标识，且都会记录对应前驱节点和后继节点的地址。

令牌作为访问临界资源的许可证，会按照一定方向（顺时针、逆时针）在节点进程之间传递，收到令牌的节点进程有权访问临界资源，访问完成后将令牌传送给下一个进程；若拿到令牌的节点进程不需要访问临界资源，则直接把令牌传递给下一个节点进程。
在这里插入图片描述

调用流程

进程形成一个逻辑环，并按固定方向传递令牌。
持有令牌的进程可以访问资源。
访问完成后，进程将令牌传递给下一个进程。
若进程不需要访问资源，则直接传递令牌。

优缺点

优点：
- 令牌唯一，避免竞争冲突。
- 进程不会长时间等待，保证公平性。
缺点：
- 令牌丢失时，系统需要恢复令牌，增加复杂度。
- 进程数量变化时，需要重构令牌环。
- 即使没有进程访问资源，令牌仍在传递，造成资源浪费。

三、三种算法对比

算法	优点	缺点	适用场景	消息复杂度	故障恢复能力
集中互斥算法	实现简单，便于管理	协调者可能成为瓶颈，单点故障风险高	进程数量较少，资源访问请求不频繁	低	低（协调者故障导致不可用）
基于许可的算法	无单点故障，保证公平性	通信开销大，进程数量多时性能下降	进程较少，通信代价可接受的场景	高	中（进程故障会影响队列排序）
令牌环算法	令牌唯一，访问公平	令牌丢失影响系统，进程变化需重构环	资源访问频繁，系统规模较小	低	中（需要令牌恢复机制）

在实际应用中，分布式锁（如 Zookeeper、Redis 分布式锁）通常结合了这些算法的思想，以提高系统的性能和可靠性。选择合适的互斥方案，可以有效提升分布式系统的稳定性和数据一致性。

参考：
《分布式原理与实践-崔皓》

文章目录

一、互斥问题及分布式系统的特性

二、分布式互斥算法

1. 集中互斥算法

调用流程

优缺点

2. 基于许可的互斥算法（Lamport 算法）

调用流程

优缺点

3. 令牌环互斥算法

调用流程

优缺点

三、三种算法对比

相关文章：