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