ランポートのパン屋のアルゴリズム
クリティカルセクションとは、リソースへの排他的アクセスを要するコードであり、一度に1個のスレッドだけが実行できる。パン屋のアナロジーで言えば、店員が1人しかいないので他の客が待たされるのに等しい。
あるスレッドがクリティカルセクションに入ろうとしたとき、最初に自分の順番かどうかを調べなければならない。スレッドは自分の番号が最も小さいことを確認するために他の全スレッドの番号をチェックする。他のスレッドが同じ番号を持っている場合、i が最も小さいスレッドが優先される。
擬似コードでは、この比較を以下の形式で書いている:
これは、以下の式に等しい:
スレッドがクリティカルな処理を終えたら、番号を削除して「非クリティカルセクション」に移行する。
非クリティカルセクションは、排他的アクセスを必要としないコード部分である。他のスレッドのリソースや実行に影響を与えないスレッド固有の計算を行う。
この部分をパン屋のアナロジーで言えば、買い物した後の行動(例えばお釣りを財布に戻すなど)に対応する。