Lamport麵包店算法

Lamport麵包店算法是解決多個執行緒並發訪問一個共享的單用戶資源的互斥問題的算法。 由萊斯利·蘭波特發明。

算法

類比

Lamport把這個並發控制算法非常直觀地類比為顧客去麵包店採購。麵包店一次只能接待一位顧客的採購。已知有N位顧客要進入麵包店採購，按照次序安排他們在前台登記一個簽到號碼。該簽到號碼逐次增加1。顧客根據簽到號碼的由小到大的順序依次入店購貨。完成購買的顧客在前台把其簽到號碼歸0。 如果完成購買的顧客要再次進店購買，就必須重新排隊。

這個類比中的顧客就相當於執行緒，而入店購貨就是進入臨界區獨占訪問該共享資源。由於計算機實現的特點，存在兩個執行緒獲得相同的簽到號碼的情況，這是因為兩個執行緒幾乎同時申請排隊的簽到號碼，讀取已經發出去的簽到號碼情況，這兩個執行緒讀到的數據是完全一樣的，然後各自在讀到的數據上找到最大值，再加1作為自己的排隊簽到號碼。為此，該算法規定如果兩個執行緒的排隊簽到號碼相等，則執行緒id號較小的具有優先權。

進入臨界區

已經拿到排隊簽到號碼的執行緒，要輪詢檢查自己是否可以進入臨界區。即檢查n個執行緒中，自己是否具有最小的非0排隊簽到號碼；或者自己是具有最小的非0排隊簽到號碼的執行緒中，id號最小的。

可以用偽代碼表示上述檢查:

(a, b) < (c, d)

等價於:

(a < c) or ((a == c) and (b < d))

非臨界區

一旦執行緒在臨界區執行完畢，需要把自己的排隊簽到號碼置為0，表示處於非臨界區.

算法實現

定義

• 數組Entering[i]為真，表示進程i正在獲取它的排隊登記號；
• 數組Number[i]的值，是進程i的當前排隊登記號。如果值為0，表示進程i未參加排隊，不想獲得該資源。規定這個數組元素的取值沒有上界。
• 正在訪問臨界區的進程如果失敗，規定它進入非臨界區，Number[i]的值置0，即不影響其它進程訪問這個互斥資源。

偽代碼

     // declaration and initial values of global variables
     Entering: array [1..NUM_THREADS] of bool = {};
     Number: array [1..NUM_THREADS] of integer = {};

  1  lock(integer i) {
  2      Entering[i] = true;
  3      Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]);
  4      Entering[i] = false;
  5      for (j = 1; j <= NUM_THREADS; j++) {
  6          // Wait until thread j receives its number:
  7          while (Entering[j]) { /* nothing */ }
  8          // Wait until all threads with smaller numbers or with the same
  9          // number, but with higher priority, finish their work:
 10          while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) { /* nothing */ }
 11      }
 12  }
 13  
 14  unlock(integer i) {
 15      Number[i] = 0;
 16  }
 17
 18  Thread(integer i) {
 19      while (true) {
 20          lock(i);
 21          // The critical section goes here...
 22          unlock(i);
 23          // non-critical section...
 24      }
 25  }

討論

每個執行緒只寫它自己的Entering[i]、Number[i]，只讀取其它執行緒的這兩個數據項。

這個算法不需要基於硬體的原子(atomic)操作實現，即它可以純軟體實現。

使用Entering數組是必須的。假設不使用Entering數組，那麼就可能會出現這種情況：設進程i的優先級高於進程j(即i<j)，兩個進程獲得了相同的排隊登記號(Number數組的元素值相等)。進程i在寫Number[i]之前，被優先級低的進程j搶先獲得了CPU時間片，這時進程j讀取到的Number[i]為0，因此進程j進入了臨界區. 隨後進程i又獲得CPU時間片，它讀取到的Number[i]與Number[j]相等，且i<j，因此進程i也進入了臨界區。這樣，兩個進程同時在臨界區內訪問，可能會導致數據腐爛(data corruption)。算法使用了Entering數組變量，使得修改Number數組的元素值變得「原子化」，解決了上述問題。

具體實現時，可以把上述偽代碼中的忙等待(busy wait)，換成交出執行緒的執行權，例如yield操作.

參見

• Peterson算法
• Szymanski算法
• 信號量

外部連結

• Wallace Variation of Bakery Algorithm （頁面存檔備份，存於網際網路檔案館） which overcomes limitations of Javascript language
• Lamport's Bakery Algorithm （頁面存檔備份，存於網際網路檔案館）
• Another JavaScript implementation by a.in.the.k

參考文獻

• On his publications page （頁面存檔備份，存於網際網路檔案館）, Lamport has added some remarks regarding the algorithm.