分布式互斥算法

1. 概述：什么是分布式互斥

假設有兩個小孩想玩同一個玩具（臨界資源），但玩具只有一個，必須保證一次只有一個人能夠玩。當一個小孩在玩時，另一個小孩只能原地等待，直到玩完才能輪到自己。這就是互斥（Mutual Exclusion）概念：任意時刻，只允許規定數量的進程（或節點）訪問臨界區，其余進程只能排隊等待。

臨界資源：在例子中即為玩具；在分布式系統中可能是某個文件、數據庫記錄、硬件設備等。
競態：多個進程同時爭奪同一個資源時發生競爭。
互斥：每次只允許一個進程進入臨界區，其他進程只能先等待。

在單機（單臺服務器）環境下，各進程共享同一臺機器的內存和時鐘，常用信號量、互斥鎖等機制即可實現。但在分布式系統中，進程分散在不同的網絡節點上，通信必須經過網絡，面臨以下幾個挑戰：

互聯網特性
- 不同節點通過網絡傳輸消息，會有網絡延遲、丟包或亂序等不確定性。
- 節點彼此沒有共享內存，只能依賴消息傳遞來協調對臨界資源的訪問。
沒有統一時鐘
- 各節點各自擁有物理時鐘，難以做到完全同步。
- 如果無法知道誰先誰后，就無法保證公平先來后到，需要引入邏輯時鐘或其他機制來解決。
節點或網絡故障
- 某個節點或鏈路出現故障時，如何檢測并進行故障恢復，才能保證系統依舊可用且不會長時間阻塞。

基于上述特性，分布式互斥算法應當滿足：

互斥性：任何時刻最多只有一個節點能夠進入臨界區。
無饑餓（無餓死）：每個請求都能在有限時間內得到滿足，不會無限期等待。
無死鎖：避免多個節點相互等待對方持有的資源，從而導致整體停滯。
公平性：先發出請求的節點應當先獲得訪問權，或至少不會被長期“插隊”。

2. 分布式互斥算法分類

常見的分布式互斥算法可分為三大類（本文重點介紹以下三種）：

集中互斥算法（Centralized Algorithm）
- 核心思想：引入一個全局 “協調者（Coordinator）”，所有節點的訪問請求都交由它來排序和授權。
基于許可的互斥算法（Permission-Based Algorithm）
- 核心思想：想要進入臨界區的節點，需要向系統中其他節點請求許可（Permission），只有獲得足夠許可后才能訪問。
- 代表算法：
  - Lamport 算法
  - Richard & Agrawal 算法
令牌環互斥算法（Token Ring Algorithm）
- 核心思想：在所有節點之間形成一個邏輯環，只有持有 “令牌（Token）” 的節點才能訪問臨界區，令牌在環上順序傳遞。

下面分別詳細講解三種算法的工作原理、消息流程與優缺點。

3. 集中互斥算法

3.1 核心思路

系統中預先選舉出一個節點作為 “協調者（Coordinator）”。
當某個進程（節點） Pi 想訪問臨界資源時，向協調者發送 REQUEST(Pi) 消息。
協調者維護一個本地的“請求隊列（按先后次序）”。
- 若此時沒有其他節點在使用資源，則直接向 Pi 發送 GRANT(Pi)，Pi 收到后即可進入臨界區。
- 若已有其他節點持有該資源，則把 Pi 的請求追加到隊列尾，等待前面的節點釋放后再處理。
當 Pi 使用完畢后，向協調者發送 RELEASE(Pi)，協調者收到后，從請求隊列中彈出下一個節點 Pj，并向其發送 GRANT(Pj)，Pj 再進入臨界區。

3.2 關鍵特性

互斥保證：協調者一次只能向一個節點發放 GRANT，確保只有一個節點能夠訪問。
先來后到：協調者將所有請求排隊，根據請求到達時間順序依次授權。
避免饑餓：如果某節點長時間占用或宕機，協調者可檢測超時并將其移出隊列（或讓其“自動釋放”），從而讓后續請求有機會執行。

3.3 消息交互流程（以兩個節點 P1、P2 為例，詳見圖 3-1）

圖 3-1：集中互斥算法消息流程示意P1                 協調者               P2
(1) REQUEST(P1) ──────→ 存入隊列：[(P1, TS1)]
(2) GRANT(P1) ←──────    ←────── REQUEST(P2)更新隊列：[(P1, TS1), (P2, TS2)]
(3) P1 進入臨界區
(4) RELEASE(P1) ──────→ 更新隊列：[(P2, TS2)]
(5) GRANT(P2) ←──────
(6) P2 進入臨界區
(7) RELEASE(P2) ──────→ 空隊列

第 1 步：P1 向協調者發送 REQUEST(P1)，時間戳記為 TS1。協調者將 (P1, TS1) 加入本地隊列。
第 2 步：發現隊列僅有 P1，直接向 P1 返回 GRANT(P1)。此時 P1 進入臨界區。
第 3 步：P2 請求到達，發送 REQUEST(P2)，時間戳記為 TS2（TS2 > TS1）。協調者將 (P2, TS2) 加入隊列尾。
第 4 步：P1 使用完成后，發送 RELEASE(P1)。協調者將 P1 從隊列中移除，只剩 (P2, TS2)，于是向 P2 發放 GRANT(P2)。
第 5 步：P2 收到 GRANT 進入臨界區，使用完后再通知 RELEASE(P2)，隊列空。

3.4 優缺點分析

優點
1. 實現簡單，理解直觀；
2. 每次臨界區訪問僅需 3 次消息：REQUEST → GRANT → RELEASE。
缺點
1. 單點故障：協調者若發生故障，整個系統無法繼續；
2. 擴展性差：協調者會成為性能瓶頸，隨著節點數增多，排隊和消息處理壓力變大；
3. 協調者可能出現宕機或網絡隔離，需要額外的故障檢測與選舉機制。

4. 基于許可的互斥算法

當系統規模擴大時，如果依賴單一協調者，瓶頸和單點故障問題更嚴重。基于許可的互斥算法沒有集中節點，而是由各個節點之間互相“投票”或“許可”來決定誰先進入臨界區。典型代表有 Lamport 算法和 Richard & Agrawal 算法，它們都基于邏輯時鐘與請求隊列來保證先來后到與互斥。

4.1 Lamport 算法

4.1.1 核心思想

邏輯時鐘（Logical Clock）
- 每個節點 Pi 維護一個本地邏輯時鐘 Li，初始值為 0。
- 當 Pi 發出臨界區請求時，先執行 Li = Li + 1，并將新的 Li 作為時間戳 TSi 發送給其他節點。
- 當 Pj 接收到一條請求消息（或 RELEASE）時，先將本地時鐘更新為 Lj = max(Lj, TSi) + 1，再處理消息。
請求隊列（Request Queue）
- 每個節點維護一個本地請求隊列，隊列中元素為 (節點ID, 時間戳)，按時間戳從小到大排序。如時間戳相等，則按照節點 ID 從小到大排序。
- 當 Pi 發出 REQUEST(Pi, TSi) 時，會將自己這一請求加入本地隊列，并向其它所有節點廣播 REQUEST(Pi, TSi)。
- 當 Pj（j ≠ i）收到 REQUEST(Pi, TSi) 后：
  1. 更新本地邏輯時鐘：Lj = max(Lj, TSi) + 1；
  2. 將 (Pi, TSi) 插入本地請求隊列；
  3. 向 Pi 發送一條 REPLY(Pj, Lj)（表明已許可）。
進入臨界區的條件
- Pi 只有在以下兩種條件同時滿足時，才可進入臨界區：
  1. 本地隊列中排在最前（時間戳最小且 ID 最小）；
  2. 已收到來自所有其他節點的 REPLY 消息。
- 當 Pi 進入臨界區并使用完畢后，向所有節點廣播 RELEASE(Pi, TSi’)（TSi’ = Li + 1），各節點收到后：
  1. 更新本地邏輯時鐘：Lj = max(Lj, TSi') + 1；
  2. 從本地請求隊列中刪除 (Pi, …)；
這樣，排在下一位的節點即可進入臨界區。

4.1.2 消息流程示意（圖 4-1）

圖 4-1：Lamport 算法消息交互（3 個節點 P1、P2、P3）P1                        P2                        P3
（1）L1= L1+1；TS1=1請求：REQUEST(P1,1) ──→更新 L2=max(L2,1)+1=2本地隊列插入 (P1,1)←── REPLY(P2,2)更新 L3=max(L3,1)+1=2本地隊列插入 (P1,1)←── REPLY(P3,2)（2）P1 收齊 P2、P3 的 REPLY，且自己在 3 個節點隊列中排第一→ 進入臨界區（3）使用完畢：L1 = L1 + 1 = 2；廣播 RELEASE(P1,2)P2、P3 更新時鐘并刪除 (P1,1)（4）此時本地隊列中可能有 (P2,2)、(P3,2) 等請求根據時間戳和節點 ID 排序，讓下一位進入

消息數量：每次進入臨界區需發送
- n – 1 條 REQUEST（廣播給其它節點），
- n – 1 條 REPLY（每個節點一個），
- n – 1 條 RELEASE（廣播）。
  共計 3(n ? 1) 條消息。

4.1.3 特點與適用場景

優點
1. 無集中節點，無單點故障；
2. 基于時間戳排序，保證先到先得，具有公平性；
3. 不存在死鎖或循環等待。
缺點
1. 通信開銷較大：消息數隨節點數線性增長，適合節點規模較小、臨界資源請求頻率相對較低的場景；
2. 每個節點需維護本地請求隊列，存儲開銷為 O(n)。

4.2 Richard & Agrawal 算法

4.2.1 算法思路

Richard & Agrawal 算法是在 Lamport 算法基礎上的改進，目的是減少消息開銷，將原本的 RELEASE 與 REPLY 合并，以降低通信量。主要思路如下：

發送請求
- 當 Pi 想進入臨界區時：
  1. 將本地邏輯時鐘 Li = Li + 1，得到時間戳 TSi；
  2. 將 (Pi, TSi) 插入本地請求隊列；
  3. 向其它所有節點廣播 REQUEST(Pi, TSi)。
接收請求并判斷
- Pj（j ≠ i）收到 REQUEST(Pi, TSi) 后：
  1. 更新本地邏輯時鐘 Lj = max(Lj, TSi) + 1；
  2. 若 Pj 當前 沒有正在等待或占用臨界資源，則立即給 Pi 回復 REPLY(Pj, Lj)；
  3. 若 Pj 正在等待或訪問臨界資源，則比較 (TSj, Pj) 與 (TSi, Pi)：
    - 若 (TSi, Pi) 排在前面（時間戳更小或時間戳相同且 ID 較小），則等待，并暫時不回復；
    - 否則（即 Pj 的請求優先級更高），向 Pi 立刻回復 REPLY(Pj, Lj)，但 Pj 本地繼續排隊。
  4. 將 (Pi, TSi) 插入本地請求隊列，按時戳排序。
進入臨界區的條件
- Pi 必須從所有 n – 1 個節點都收到 REPLY，并且在自己本地隊列中排在最前；
- 方能進入臨界區。
使用完成后
- Pi 進入臨界區使用完成后，將 (Pi, …) 從本地隊列中刪除，并向本地隊列（如果有）最前面的下一個節點發送 “偽 REPLY”（即代替 RELEASE 的作用），讓該節點嘗試進入。
- 其余節點在收到 “偽 REPLY” 時，也會將 (Pi, …) 從自己的本地隊列中刪除，并檢查本地隊列頭部，如果自己排在最前且已收到所有許可，就可進入臨界區。

4.2.2 消息流程示意（圖 4-2）

圖 4-2：Richard & Agrawal 算法消息流程（3 個節點 P1、P2、P3）P1                        P2                        P3
（1）L1 = L1 + 1；TS1 = 1請求：REQUEST(P1,1) ──→ 更新 L2 = max(L2,1)+1 = 2本地隊列插入 (P1,1)P2 無本地請求 → 立即 REPLY(P2,2)←──更新 L3 = max(L3,1)+1 = 2本地隊列插入 (P1,1)P3 無本地請求 → 立即 REPLY(P3,2)←──（2）P1 收到 P2、P3 的 REPLY，且本地隊列頭為 (P1,1)→ 進入臨界區（3）使用完畢：刪除本地隊列中 (P1,1)，向本地隊列中后續進程 “發送 REPLY”  —— 假設本地隊列后續為 (P2,2)，則發送 REPLY(P2, …)，允許 P2 進入。（4）其余節點收到 P1 的刪除信號后，也將 (P1,1) 從本地隊列刪除  若本地隊列頭為自己且已收到所有許可，則進入臨界區。

4.2.3 特點與對比

消息開銷
- 相比 Lamport 算法的 3(n ? 1)，Richard & Agrawal 算法每次只需 2(n ? 1) 條消息：
  1. 一輪 REQUEST 給其他 n ? 1 個節點；
  2. 收到的 n ? 1 條 REPLY 即可進入；
  3. 使用完成后，節點會“順便”觸發對下一個隊列頭的 REPLY （合并了原來的 RELEASE）；
優點
1. 與 Lamport 算法相比，消息量減少，通信效率更高；
2. 依舊使用時間戳排序，保證先來后到，公平性較好；
缺點
1. 相對于集中式或令牌環算法，存儲開銷仍為 O(n)；
2. 需要維護本地請求隊列、邏輯時鐘，算法邏輯略微復雜；
適用場景
- 中等規模（節點數不太大）且資源競爭不太頻繁的場景；
- 希望在去中心化的同時盡量減少通信開銷。

5. 令牌環互斥算法

5.1 核心思路

系統中將所有節點按某種順序構成一個邏輯環（Ring）。
整個系統中僅保有一個 “令牌（Token）”，它代表了訪問臨界區的唯一許可。
只有持有令牌的節點才能進入臨界區，使用完畢后必須將令牌傳給環上的下一個節點。
若節點收到令牌但不需要訪問臨界區，則直接將令牌傳給下一個。

只要令牌在系統內部一直循環傳遞，就能保證：

互斥性：同時只有一個令牌，自然只有一個節點能進入臨界區；
公平性：令牌按固定順序依次傳遞，每個節點都能輪到；
消息開銷可控：令牌在環上每傳遞一次，記為 1 條消息；若環上有 n 個節點，則令牌完整繞行一圈需 n 條消息，平均到每個請求上的消息開銷約為 n/2。

5.2 消息流程示意（圖 5-1）

圖 5-1：5 個節點構成的令牌環示意P1 → P2 → P3 → P4 → P5 → P1（循環）（1）假設初始令牌在 P1，若 P1 需要訪問：  P1 收到令牌 → 進入臨界區 → 使用完畢 → 發送 TOKEN → P2  （2）若 P2 在收到令牌時不需要訪問，則直接 “轉發” 令牌：  P2 將令牌發送給 P3 → …  （3）若 P3 需要訪問，則：  P3 收到令牌 → 進入臨界區 → 使用完畢 → 發送 TOKEN → P4（4）依此循環，令牌永遠在環上移動，每個節點最終都能獲得令牌。

消息數：每次令牌傳遞算作 1 條消息。若某個節點從請求到實際獲得令牌需要等待 k 步，則消息數為 k （直到令牌傳到為止）。

5.3 特點與缺點

優點
1. 無需廣播，僅在相鄰兩節點之間傳遞令牌，通信開銷較小；
2. 保證了先來后到的“輪詢”機制，公平性好；
3. 不存在死鎖：只要令牌不丟失，節點始終能輪到。
缺點
1. 令牌丟失風險：若持有令牌的節點宕機或網絡隔離，令牌就會丟失，整個系統無法訪問臨界區，需額外機制檢測并重建令牌；
2. 環重構復雜：節點加入或退出都會破壞原有環，需要重新組織環拓撲，且重構過程中無法使用臨界資源；
3. 延遲受環大小影響：若環上節點數較多，則令牌傳遞到某一節點的延遲線性增大，不適合大規模場景；
適用場景
- 節點數量有限（小規模系統），資源訪問頻率高且使用時間短；
- 網絡相對可靠、節點變動較少的場景。

6. 三種算法對比小結

算法名稱	消息開銷	互斥保證	公平性	單點故障	擴展性	適用場景
集中互斥算法	3 條（REQUEST→GRANT→RELEASE）	絕對互斥	先來后到	存在單點故障	較差	小規模、對延遲要求不高的場景
Lamport 算法	3(n ? 1) 條	無單點故障	嚴格基于時間戳	無單點故障	中等	節點數不多、資源請求較頻繁的場景
Richard & Agrawal 算法	2(n ? 1) 條	無單點故障	基于時間戳	無單點故障	中等	想在 Lamport 基礎上減少消息量的場景
令牌環互斥算法	每次令牌傳遞 1 條 → 平均 n/2 條	無單點故障（若令牌丟失則宕機）	輪詢公平	令牌丟失視為故障	較差（環受拓撲限制）	小規模、節點變動少、資源訪問頻繁且快的場景

6.1 選型建議

系統規模很小（節點數 ≤ 10）且對延遲要求不高
- 可以考慮集中互斥算法：實現最簡單，但要保證協調者高可用；
系統規模中等（節點數約 10 – 50），去中心化，又希望保證較高公平性
- 可優先選擇 Richard & Agrawal 算法，由于消息量比 Lamport 算法少，且同樣保證先來后到；
系統規模小且臨界資源訪問速度快、頻率高
- 令牌環互斥適合：令牌在環上快速循環，通信開銷低，但必須保障令牌不會丟失，環重構開銷也要評估；
系統需要高度容錯、節點可能頻繁增刪
- Lamport 算法更易于動態擴展，不用維護環結構，但通信成本更高；