Lamport麵包店算法

Lamport的麵包店算法是由計算機科學家Leslie Lamport設計的計算機算法，旨在通過互斥提高多執行緒之間共享資源的使用安全性。

在計算機科學中，多個執行緒通常同時訪問相同的資源。 如果兩個或多個執行緒嘗試寫入相同的記憶體位置，或者如果一個執行緒在另一個執行緒完成寫入之前讀取記憶體位置，則可能發生數據損壞。 Lamport的麵包店算法是眾多互斥算法中的一種，旨在防止並發執行緒同時進入關鍵代碼段以消除數據損壞的風險。

基本介紹

• 中文名：Lamport麵包店算法
• 外文名：Lamport's bakery algorithm

算法

比喻

Lamport在其入口處構想了一家帶有編號機的麵包店，因此每位客戶都會獲得一個唯一的編號。當顧客進入商店時，數字會增加一。全局計數器顯示當前正在服務的客戶的編號。所有其他客戶必須排隊等待，直到麵包師完成為當前客戶提供服務並顯示下一個號碼。當顧客完成購物並且已經處理了他或她的號碼時，店員遞增號碼，允許下一個顧客被送達。該客戶必須從編號機中抽取另一個號碼才能再次購物。

根據類比，“客戶”是由全局變數獲得的字母i標識的執行緒。

由於計算機體系結構的局限性，Lamport的一些部分類比需要稍加修改。有多個執行緒可能會在請求時獲得相同的數字n;這是無法避免的。因此，假設執行緒標識符i也是優先權。較低的i值表示較高的優先權，具有較高優先權的執行緒將首先進入臨界區。

關鍵部

關鍵部分是需要獨占訪問資源的代碼部分，並且一次只能由一個執行緒執行。在麵包店比喻中，當客戶與麵包師交易時，其他人必須等待。

當一個執行緒想要進入臨界區時，它必須檢查輪到它了。它應該檢查每個其他執行緒的數量n，以確保它具有最小的執行緒。如果另一個執行緒具有相同的編號，則具有最小i的執行緒將首先進入臨界區。

在偽代碼中，執行緒a和b之間的比較可以採用以下形式編寫：

(na, ia) < (nb, ib) // ia - the customer number for thread a, na - the thread number for thread a

這相當於：

(ia < ib) or ((ia == ib) and (na < nb))

一旦執行緒結束其關鍵作業，它就會刪除它的編號並進入非關鍵部分。

非關鍵部分

非關鍵部分是不需要獨占訪問的代碼部分。它表示一些特定於執行緒的計算，不會干擾其他執行緒的資源和執行。此部分類似於購物後發生的操作，例如將更改放回錢包中。

算法的實現

定義

在Lamport的原始論文中，輸入變數稱為選擇，並且以下條件適用：

選擇[i]和數字[i]的單詞在進程i的存儲器中，並且最初為零。

number [i]的值範圍是無界的。

進程可能隨時失敗。我們假設當它失敗時，它立即進入非關鍵部分並停止。然後可能存在從其存儲器讀取給出任意值的時段。最終，從其記憶體中讀取的任何值都必須為零。

代碼示

偽代碼。在此示例中，所有執行緒都執行相同的“main”函式Thread。在實際套用中，不同的執行緒通常具有不同的“主要”功能。

請注意，與原始論文一樣，執行緒在進入臨界區之前會自行檢查。由於循環條件將評估為false，因此不會造成太多延遲。

  Entering: array [1..NUM_THREADS] of bool = {false};    Number: array [1..NUM_THREADS] of integer = {0};    lock(integer i) {            Entering[i] = true;            Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]); Entering[i] = false;for (integer j = 1; j <= NUM_THREADS; j++) {                                  // Wait until thread j receives its number:                         while (Entering[j]) { /* nothing */ }                          // Wait until all threads with smaller numbers or with the same          // number, but with higher priority, finish their work:                                                     while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) { /* nothing */ }      }  }                                    unlock(integer i) {                                     Number[i] = 0;  }  Thread(integer i) {      while (true) {          lock(i);                                                                   // The critical section goes here...          unlock(i);                                           // non-critical section...      }  }

PlusCal代碼

我們將N聲明為進程數，並假設N是自然數。

CONSTANT NASSUME N \in Nat

我們將P定義為集合{1,2，...，N}的過程。

P == 1..N

變數num和flag聲明為全局變數。

--algorithm AtomicBakery { variable num = [i \in P |-> 0], flag = [i \in P |-> FALSE];

討論

每個執行緒只寫自己的存儲，唯讀共享。值得注意的是，該算法不是建立在一些較低級別的“原子”操作之上，例如，比較並交換。原始證明表明，對於對同一存儲單元的重疊讀寫，只有寫入必須正確。讀操作可以返回任意數字。因此，該算法可用於在缺少同步原語的存儲器上實現互斥，例如，在兩台計算機之間共享的簡單SCSI盤。

變數Entering的必要性可能並不明顯，因為第7行到第13行沒有“鎖定”。但是，假設變數被刪除，兩個進程計算相同的Number [i]。如果在設定Number [i]之前優先權較高的進程被搶占，則低優先權進程將看到另一個進程的數量為零，並進入臨界區;之後，高優先權進程將忽略較低優先權進程的相等Number [i]，並進入臨界區。結果，兩個進程可以同時進入臨界區。烘焙算法使用Entering變數使第6行的賦值看起來像原子;過程我將永遠不會看到一個數字等於零的進程j將選擇與i相同的數字。

在單個進程系統中或在協作式多任務處理中實現偽代碼時，最好將“不執行任何”部分替換為通知作業系統立即切換到下一個執行緒的代碼。這個原語通常被稱為yield。

Lamport的麵包店算法採用順序一致性記憶模型。很少（如果有的話）語言或多核處理器實現這樣的存儲器模型。因此，算法的正確實現通常需要插入柵欄來禁止重新排序。