Szymanski算法是由計算機科學家Boleslaw Szymanski博士設計的互斥算法，它具有許多有利的性質，包括線性等待，和擴展解決了Leslie Lamport發布的開放問題是否存在每個過程具有恆定通信位數的算法，其滿足Lamport所構想的每個合理的公平性和容錯性要求（Lamport的解決方案使用n因子通信變數與Szymanski的5）。
基本介紹
- 中文名：Szymanski算法
- 外文名：Szymański's algorithm
算法
該算法模擬在一個有入口和出口的候診室。入口門最初打開，出口門關閉。 請求大致在同一時間進入臨界區的所有過程進入候診室; 最後一個關閉了入口門並打開了出口門。 然後，過程逐個進入臨界區（如果臨界區允許，則進入較大的組）。 離開關鍵部分的最後一個過程關閉出口門並重新打開入口門，因此下一批過程可能會進入。
實現包括每個進程都有一個標誌變數，該變數由該進程寫入並由所有其他進程讀取（這種單寫入器屬性對於高效的高速快取使用是合乎需要的）。 通過讀取所有過程的標誌來計算入口門的狀態。 偽碼如下：
#Entry protocol
flag[self] ← 1
await(all flag[1..N] ∈ {0, 1, 2})
flag[self] ← 3 #Standing in doorway
if any flag[1..N] = 1:
flag[self] ← 2 #Waiting for other processes to enter await(any flag[1..N] = 4)
flag[self] ← 4 #The door is closed
await(all flag[1..self-1] ∈ {0, 1})
await(all flag[self+1..N] ∈ {0, 1, 4}) #Ensure everyone in the waiting room has #realized that the door is supposed to be closed
flag[self] ← 0
請注意，“所有”和“任何”測試的順序必須是統一的。
儘管有直觀的解釋，但該算法並不容易證明是正確的，但由於其有利的性質，需要證明其正確性，並且已經提出了多個證據。
