シマンスキーのアルゴリズム

Szymański の相互排除アルゴリズムは、コンピュータ科学者Bolesław Szymański博士が考案した相互排除アルゴリズムで、線形待機を含む多くの好ましい特性を持ち、^[1]^[2]、その拡張^{[3]により、}Leslie Lamportが投稿した未解決問題^{[4] 、} Lamport が考えたすべての妥当な公平性と耐障害性の要件を満たす、プロセスあたりの通信ビット数が一定であるアルゴリズムが存在するかどうかが解決されました (Lamport のソリューションではn階乗の通信変数が使用されましたが、Szymański のソリューションでは 5 でした)。

アルゴリズム

このアルゴリズムは、入口と出口を持つ待合室をモデルにしています。^[1]初期状態では、入口ドアは開いており、出口ドアは閉じています。クリティカルセクションへの入場を要求したすべてのプロセスは、ほぼ同時に待合室に入り、最後にクリティカルセクションに入場したプロセスが入口ドアを閉じ、出口ドアを開きます。その後、プロセスは1つずつ（またはクリティカルセクションが許可している場合は、より大きなグループで）クリティカルセクションに入ります。クリティカルセクションを最後に退出したプロセスは、出口ドアを閉じ、入口ドアを再び開きます。これにより、次の一連のプロセスが入場できるようになります。

実装は、各プロセスがそのプロセスによって書き込まれ、他のすべてのプロセスによって読み取られるフラグ変数を持つことで構成されます (この単一書き込みプロパティは、効率的なキャッシュの使用に適しています)。

フラグ変数は、次の 5 つの値/状態のいずれかになります。

0 はプロセスが非クリティカルセクションにあることを示します。
1プロセスがクリティカルセクションに入ることを望んでいることを示します (意図の宣言)。
2 は、プロセスが他のプロセスが door_in を通過するのを待機していることを示しています。
3 は、プロセスが待合室に入ったばかりであることを示します。
4 は、プロセスが door_out を通過してクリティカルセクションに入ったことを示します。

入口ドアの状態は、N個のプロセスすべてのフラグを読み取ることで計算されます。擬似コードを以下に示します。

# 入場プロトコル
flag [ self ]  ←  1                         # 待合室の外に立っています
await ( all  flag [ 1. . N ]  ∈  { 0 ,  1 ,  2 })      # ドアが開くのを待っています
flag [ self ]  ←  3 #                        いずれかの場合は出入り口に立っています
flag [ 1. . N ] = 1 : # 別のプロセスが入場を待っていますflag [ self ] ← 2 # 他のプロセスが入場するのを待っていますawait ( any flag [ 1. . N ] = 4 ) # プロセスが入場してドアを閉めるのを待っています                    
                          
                

flag [ self ]  ←  4                         # ドアが閉まっている
await ( all  flag [ 1. . self - 1 ]  ∈  { 0 ,  1 })    # 低いIDの全員が終了プロトコルを終了するのを待つ

# クリティカルセクション
# ...

# 退出プロトコル
await ( all  flag [ self + 1. . N ]  ∈  { 0 ,  1 ,  4 })  # 待合室にいる全員が
                                       ドアが閉まっていることを認識していることを確認する
flag [ self ]  ←  0  # 退出する。待合室にまだ誰もいない場合はドアを再び開ける

「すべて」と「いずれか」のテストの順序は均一でなければならないことに注意してください。直感的な説明にもかかわらず、このアルゴリズムの正しさを証明するのは容易ではありませんでした。しかし、その好ましい特性のため、正しさの証明が望ましく、複数の証明が提示されています。^[2]^[5]

参考文献

^ ab Szymański, Bolesław K. (1988). 「線形待機によるランポートの並行プログラミング問題への単純な解」第2回国際スーパーコンピューティング会議（ICS '88）の議事録。フランス、サン・マロ：ACM。pp. 621– 626. doi :10.1145/55364.55425. ISBN 978-0-89791-272-3. S2CID 18612278。
^ ab Manna, Zohar ; Pnueli, Amir (1990). 「マルチプロセスプログラムの検証演習」. 『美は私たちの仕事：エドガー・W・ダイクストラへの誕生日の挨拶』 . Springer Verlag. pp. 289– 301. ISBN 978-0-387-97299-2。
^ Szymański, Bolesław (1990). 「相互排除の再考」(PDF) .第5回エルサレム情報技術会議. エルサレム、イスラエル: 110–117 .
^ ランポート、レスリー (1986). 「相互排除問題 - パートII：論証と解決策」. Journal of the ACM . 33 (2): 327– 348. CiteSeerX 10.1.1.32.9808 . doi :10.1145/5383.5385. S2CID 7387839.
^ デ・ローバー、ウィレム＝ポール;デ・ブール、フランク。ハネマン、ウルリッヒ。フーマン、ジョゼフ。ラクネック、ヤシン。ポール、マネス。ツヴィアーズ、ヨブ (2001 年 11 月)。同時実行性の検証。理論コンピューターサイエンスのケンブリッジトラクトで54位。ケンブリッジ大学出版局。ISBN 978-0-521-80608-4。

参照

[Sz88-1] Szymański, Bolesław K. (1988). 「線形待機によるランポートの並行プログラミング問題への単純な解」第2回国際スーパーコンピューティング会議（ICS '88）の議事録。フランス、サン・マロ：ACM。pp. 621– 626. doi :10.1145/55364.55425. ISBN 978-0-89791-272-3. S2CID 18612278。

[ZA91-2] Manna, Zohar ; Pnueli, Amir (1990). 「マルチプロセスプログラムの検証演習」. 『美は私たちの仕事：エドガー・W・ダイクストラへの誕生日の挨拶』 . Springer Verlag. pp. 289– 301. ISBN 978-0-387-97299-2。

[Sz90-3] Szymański, Bolesław (1990). 「相互排除の再考」(PDF) .第5回エルサレム情報技術会議. エルサレム、イスラエル: 110–117 .

[LL86-4] ランポート、レスリー (1986). 「相互排除問題 - パートII：論証と解決策」. Journal of the ACM . 33 (2): 327– 348. CiteSeerX 10.1.1.32.9808 . doi :10.1145/5383.5385. S2CID 7387839.

[5] デ・ローバー、ウィレム＝ポール;デ・ブール、フランク。ハネマン、ウルリッヒ。フーマン、ジョゼフ。ラクネック、ヤシン。ポール、マネス。ツヴィアーズ、ヨブ (2001 年 11 月)。同時実行性の検証。理論コンピューターサイエンスのケンブリッジトラクトで54位。ケンブリッジ大学出版局。ISBN 978-0-521-80608-4。