多個行程的並行與協作是分散式系統的根本，這常意味著行程需要同時存取相同的資源。為了防止並行存取把資源弄壞或弄得不一致，需要能授予行程**互斥存取（mutually exclusive access）**的解法。本節檢視幾個較重要的分散式互斥演算法。（較新的綜述見 Saxena and Rai, 2003；較舊但仍有價值的是 Velazquez, 1993。）

總覽#

分散式互斥演算法可分為兩類：

• 權杖式（token-based）：行程之間傳遞一則特殊訊息——權杖（token）。權杖只有一個，持有者才能存取共享資源；用完把權杖傳給下一個行程，不想用就直接傳下去。
  • 優點：依行程的組織方式，很容易保證每個行程都輪得到資源（避免飢餓，starvation）；也容易避免多個行程互等的死結（deadlock），因此結構簡單。
  • 主要缺點相當嚴重：權杖遺失時（例如持有者當機），必須啟動一套複雜的分散式程序來確保產生新權杖——而且是唯一的權杖。
• 許可式（permission-based）：想存取資源的行程必須先取得其他行程的許可。授予許可的方式有很多種，以下逐一介紹。

集中式演算法#

最直接的做法是模擬單處理器系統：選出一個行程當協調者（coordinator）。

• 想存取共享資源的行程送請求訊息給協調者，說明想存取哪個資源並請求許可。若當下沒有其他行程在用該資源，協調者回覆授權，請求者即可進行。
• 若另一個行程（行程 2）此時也請求同一資源，協調者知道資源已被占用，不能授權。拒絕的方式視系統而定：可以不回覆（讓等待回覆的行程 2 阻塞），或回覆「permission denied」。無論何者，協調者把該請求排入佇列等待。
• 行程 1 用完資源後送訊息給協調者釋放獨占權；協調者從延遲佇列取出第一項並送出授權訊息。若那個行程還在阻塞，就解除阻塞去存取資源；若先前已收到明確拒絕，則需輪詢或稍後阻塞等待，看到授權後同樣可以進行。

這個演算法顯然保證互斥（協調者一次只放一個行程進去），也公平（請求依到達順序授權，沒有行程會永遠等待、無飢餓），且容易實作：每次使用資源只需三則訊息（請求、授權、釋放）。它的簡單使它在許多實務情境中是有吸引力的解法。

缺點：協調者是單點故障（single point of failure），一當機整個系統可能停擺。若行程送出請求後照慣例阻塞，它分不清「協調者死了」與「permission denied」——兩種情況都等不到訊息。此外在大型系統中，單一協調者可能成為效能瓶頸。儘管如此，簡單帶來的好處在許多情況下仍勝過潛在缺點；而且分散式解法未必更好，下一個例子就說明了這點。

去中心化演算法#

單一協調者常是糟糕的做法。Lin et al. (2004) 提出一個可在 DHT 系統上執行的投票演算法，本質上是這樣擴充集中式做法的：

• 假設每個資源被複製 n 份，每個副本有自己的協調者控制並行存取。
• 行程要存取資源時，必須取得 m > n/2 個協調者的多數同意票。與集中式不同，這裡假設協調者拒絕時（因為已把許可給了別的行程）會告知請求者。
• 若取得的票不足 m，行程隨機退避（back off）一段時間後再試。

這個方案讓原本的集中式解法不再那麼怕單一協調者故障。其假設是：協調者當機後會快速復原，但忘記當機前投過的票——等於協調者會在任意時刻重置。風險在於：重置後的協調者忘了先前已授權某行程，復原後可能錯誤地再授權另一個行程。

令 p 為協調者在時間區間 Δt 內重置的機率，可算出 m 個協調者中有 k 個重置的機率 P[k]。由於至少要 2m − n 個協調者重置才會破壞投票機制的正確性，違反正確性的機率就是 k 從 2m − n 到 m 的 P[k] 總和。

感受一下數量級：假設 DHT 系統中每個節點一次參與約 3 小時，Δt 取 10 秒（對單一行程想存取共享資源而言是保守值；很長的占用需要別的機制）。取 n = 32、m = 0.75n，違反正確性的機率小於 10⁻⁴⁰——肯定小於任何資源本身的可用性。

實作上，Lin 等人利用 DHT：資源以唯一名稱 rname 為人所知，第 i 個副本命名為 rname-i，再用已知的雜湊函數算出唯一鍵。因此任何行程都能從資源名稱產生 n 個鍵，逐一查出負責各副本（並控制其存取）的節點。

這個方案的問題：當很多節點搶同一個資源時，使用率會急遽下降——競爭者太多，最後誰都湊不齊足夠的票，資源反而閒置。解法可見 Lin et al. (2004)。

分散式演算法#

對許多人來說，「機率上正確」還不夠好，因此研究者尋找確定性的分散式互斥演算法。第一個出自藍波特 1978 年那篇時鐘同步論文；Ricart and Agrawala (1981) 將其改良得更有效率，以下介紹他們的方法。

前提是系統中所有事件有全序——任兩個事件（如訊息）誰先發生必須毫無歧義。前一節的藍波特演算法正是達成此排序的一種方式，可用來為分散式互斥提供時間戳記。

演算法如下：

• 行程想存取共享資源時，建立一則訊息，內含資源名稱、自己的行程編號、目前（邏輯）時間，然後送給其他所有行程（概念上也包括自己）。假設訊息傳送可靠、不遺失。
• 行程收到別人的請求訊息時，依自己相對該資源的狀態分三種情況：
  1. 接收者沒在存取該資源、也不想存取：回覆 OK。
  2. 接收者已擁有該資源的存取權：不回覆，把請求排入佇列。
  3. 接收者也想存取但尚未取得：比較來訊的時間戳記與自己送給大家的那則訊息的時間戳記，最低者贏。來訊較低就回 OK；自己的較低就把來訊排入佇列、什麼也不送。
• 送出請求後，行程等所有人都給了許可才進入。用完後，對佇列中所有行程回覆 OK 並清空佇列。

沒有衝突時演算法顯然可行。有衝突時——例如行程 0 以時間戳記 8、行程 2 以時間戳記 12 同時向所有人送請求：不感興趣的行程 1 對兩者都回 OK；0 和 2 都看到衝突並比較時間戳記，2 發現自己輸了，回 OK 授權給 0；0 把 2 的請求排入佇列並存取資源，用完後把 2 的請求移出佇列、送 OK 給 2，2 才進入。演算法可行的原因是：衝突時最低時間戳記勝出，而所有人對時間戳記的排序有共識。

若行程 2 更早送出請求、行程 0 在提出自己的請求前就已收到並授權給 2，情況會本質不同：0 提出請求時會注意到 2 正在存取資源，於是把 2 的請求排入佇列，而非回覆。

如同集中式演算法，互斥得到保證、無死結也無飢餓。每次進入需要的訊息數為 2(n − 1)（n 為系統中的行程總數），而且沒有單點故障。

不幸的是，單點故障被換成了 n 個故障點：任何一個行程當機、不回應請求，沉默會被（錯誤地）解讀為拒絕授權，從而封鎖所有行程後續進入任何臨界區的嘗試。n 個行程之一故障的機率至少是單一協調者故障的 n 倍——我們成功地把一個不怎麼樣的演算法，換成了比它糟 n 倍以上、還更耗網路流量的演算法。

補救方式與前面提過的技巧相同：收到請求時一律回覆（授權或拒絕）；請求或回覆遺失時，發送者逾時重試，直到收到回覆或斷定對方已死。被拒絕後，發送者應阻塞等待後續的 OK。

其他問題：

• 必須使用多播通訊原語，否則每個行程得自行維護群組成員名單（含加入、離開、當機）。此法最適合成員不變的小型行程群組。
• 集中式演算法的協調者可能成為瓶頸；這裡則是所有行程參與所有存取決策。若一個行程都撐不住負載，強迫所有人平行做一模一樣的事不太可能有幫助。

小改進是可能的，例如「要所有人同意」其實過頭了——只要能防止兩個行程同時存取即可，演算法可改為收集到簡單多數的許可就進入（當然，此變形中行程授權給某人後，在對方用完前不能再授權給別人）。

權杖環演算法#

另一條完全不同的確定性路線：在匯流排式網路（如 Ethernet，行程本無固有順序）上，以軟體建構一個邏輯環，每個行程被指定環上的一個位置。位置可依網路位址的數字順序或其他方式分配——順序本身不重要，重要的是每個行程知道自己的下一位是誰。

• 環初始化時，行程 0 拿到權杖。權杖以點對點訊息從行程 k 傳給行程 k + 1（模環大小），沿環循環。
• 行程從鄰居手上拿到權杖時，檢查自己是否需要存取共享資源：需要就進行，做完所有工作、釋放資源後，把權杖沿環傳下去。不允許用同一個權杖連續進入第二次。
• 拿到權杖但不感興趣就直接傳下去。沒人需要資源時，權杖就在環上高速空轉。

正確性顯而易見：任一瞬間只有一個行程持有權杖，所以只有一個行程能碰資源；權杖以明確定義的順序循環，飢餓不會發生——行程決定要存取資源後，最壞就是等其他每個行程都用過一輪。

這個演算法照例也有問題。權杖遺失就必須重生，但偵測遺失很困難：權杖兩次現身之間的時間沒有上界，一小時沒看到權杖不代表它丟了——可能有人還在用。

行程當機的復原倒是比其他方案容易：若要求收到權杖必須回送確認，鄰居遞交權杖失敗時就會發現死掉的行程，將其移出群組，把權杖越過死者傳給下一位（必要時再下一位）。當然，這要求每個行程都維護目前的環組態。

四種演算法的比較#

依三個關鍵屬性比較：每次存取並釋放資源所需的訊息數、進入前的延遲（以循序傳遞訊息計）、以及各自的問題：

• 集中式：每次進出臨界區 3 則訊息（請求、授權、釋放）、進入延遲 2 個訊息時間。最簡單也最有效率。問題：協調者當機。
• 去中心化：訊息數 3mk（每次嘗試對 m 個協調者各 3 則，k 為所需嘗試次數）、延遲 3mk 個訊息時間。問題：飢餓、低效率。
• 分散式：2(n − 1) 則訊息（n − 1 個請求加 n − 1 個授權）、延遲 2(n − 1) 個訊息時間。問題：任一行程當機都出事。
• 權杖環：訊息數 1 到 ∞——所有人都搶著進時，每次傳遞權杖就有一次進出，平均每次進入 1 則訊息；反之權杖可能空轉數小時沒人要，每次進入的訊息數無上界。延遲 0（權杖剛到）到 n − 1（權杖剛走）。問題：權杖遺失、行程當機。

除了去中心化演算法，所有演算法在當機面前都表現糟糕，必須引入特殊措施與額外複雜度來避免一次當機拖垮整個系統。諷刺的是，分散式演算法比集中式的還更怕當機。在以容錯為設計目標的系統中，這些演算法都不合用；只有在當機極少發生時，它們或許還行。去中心化演算法對當機較不敏感，但行程可能飢餓，且需要特殊措施保證效率。

（進入延遲的比較是以「資源使用時間很短、延遲以存取機制本身為主」的情況來看；若資源被長期占用，主導因素變成等其他人輪完。）