Lamportpháng店算法

Lamport pháng 店算法是解決濟个執行緒並發訪問一个共享的單用戶資源的相斥問題的算法。由萊斯利 ・ 蘭波特發明。

算法

類比

Lamport 共這个並發控制的算法非常的直觀地類比做人客去 pháng 店採購。pháng 店一擺干焦會當接待一个人客的採購。已經知有 n 位人客欲入來 pháng 店採購，按照改序安排𪜶佇前台登記一个簽到號碼。該簽到號碼最次增加一。人客根據簽到號碼的由小到大的順序依次入店買貨。完成買的人客佇前台共伊簽到號碼歸零。若是完成買的人客欲閣再去買，著愛重新排隊。

這个類比內底的人客就佮執行緒比起來，啊若入店買貨就是進入臨界區獨占訪問該共享資源。因為計算機實現的特點，存在兩个執行緒得著仝款的簽到號碼的狀況，這是因為兩个執行緒差不多仝一个時陣咧申請排隊的簽到號碼，讀已經發出去的簽到號碼的情形，這兩个執行緒讀著的數據是仝款的，然後各自在讀的數據頂頭揣著上大值，閣加一做為家己的排隊簽到號碼。為此，該算法規定若兩个執行緒的排隊簽到號碼相等，則執行緒 id 號較細的具有優先權。

進入臨界區

已經提著排隊簽到號碼的執行緒，愛輪詢檢查家己敢會當入去臨界區。即檢查 n 一个執行緒中，家己敢有上細的零排隊簽到號碼；或者是家己是有上細的非零排隊簽到號碼的執行緒中，id 號上細的。

會當用偽代碼表示頂述檢查 :

` ` ` ( a , b ) < ( c , d ) ` ` `

等價於 :

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

非臨界區

一旦執行緒佇臨界區執行煞畢，需要共家己的排隊簽到號碼置做零，表示因為非臨界區.

算法實現

定義

• 數組 Entering [i] 為真，表示進程 i 當咧得著伊的排隊登記號；
• 數組 Number [i] 的值，這是進程 i 的當前排隊登記號。若值為零，表示進程 i 無參加排隊，無想著講這个該資源。規定這个數組元素的取值無上界。
• 當咧訪問臨界區的進程若失敗，規定伊進入足臨界區的，Number [i] 的值置零，也無影響其他進程訪問這互斥資源。

討論

逐个執行緒干焦寫伊家己的 Entering [i]、Number [i]，干焦讀取其他執行緒的這兩个數據項。

這个算法無需要是硬體的原子 ( atomic ) 操作實現，即伊會當純軟體實現。

使用 Entering 數組是必須的。準講是無使用 Entering 數組，就可能出現這款情形：設進程 i 優先級懸於進程 j ( 即 ` i < j ` )，兩个進程得著仝款的排隊登記號 ( Number 數組的元素值相等 )。進程 i 咧寫 ` Number [i] ` 進前，予優先級低的進程 j 搶頭路得著 CPU 時間片，這陣進程 j 讀會著的 ` Number [i] ` 為零，所以進程 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 .