分布式互斥算法
概述
分布式互斥算法是解决多个分布式进程竞争共享资源访问权的算法，确保同一时刻只有一个进程能够访问临界区，是分布式系统中的基本同步原语。
关键内容
- 问题定义：
- 多个进程竞争访问共享资源（临界区）
- 同一时刻只允许一个进程进入临界区
-
需要保证互斥性、无饥饿、公平性
-
Lamport算法：
- 基于逻辑时钟的全序关系
- 进程维护请求队列，按全序排序
- 使用三种消息：请求、确认、释放
-
通信开销：每次进入临界区需3(N-1)条消息
-
算法步骤：
- 请求资源：向所有进程广播带时间戳的请求
- 接收请求：加入本地队列并发送确认
- 进入临界区：当请求排在队列最前且收到足够确认时
-
释放资源：广播释放消息
-
局限性：
- 不容错：任何进程崩溃或消息丢失都会导致算法失效
- 高通信开销：O(N)消息复杂度
- 需要所有进程参与
来源
- 13-lamport-time-clocks — 详细描述了算法
- raw/books/计算机科学/13-lamport-time-clocks.md — 算法详细介绍
相关
- Lamport 逻辑时钟论文 — 首次提出
- 逻辑时钟 — 实现基础
- happened-before 关系 — 排序依据
- 分布式系统 — 应用领域
- 临界区 — 保护对象