Lamport麵包店算法

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

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

基本介紹

  • 中文名:Lamport麵包店算法
  • 外文名:Lamport's bakery algorithm
算法,比喻,關鍵部,非關鍵部分,算法的實現,定義,代碼示,PlusCal代碼,討論,

算法

比喻

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的麵包店算法採用順序一致性記憶模型。很少(如果有的話)語言或多核處理器實現這樣的存儲器模型。因此,算法的正確實現通常需要插入柵欄來禁止重新排序。

相關詞條

熱門詞條

聯絡我們