ランポートのパン屋のアルゴリズム
From Wikipedia, the free encyclopedia
ランポートのパン屋のアルゴリズム（ランポートのパンやのアルゴリズム）とは、レスリー・ランポートが考案した相互排他のためのアルゴリズムである。マルチスレッド処理などのロバストさを相互排他（ミューテックス）によって強化することを目的としている。
マルチスレッドなシステムにおいて、2つ以上のスレッドから同時に同一のリソースにアクセスすることがしばしば起きる。しかし例えば、2つ以上のスレッドがそれぞれ「リード・モディファイ・ライト」を同一の対象に相互排他なしに行えばデータは意図しない状態になり得るし、あるスレッドが複数のデータをアトミックでなく書き込んでいる途中に別のスレッドがそれを読み込んでも一貫性の損なわれたデータを読み込む可能性がある。ランポートのパン屋のアルゴリズムは数ある相互排他アルゴリズムのひとつで、並列スレッドが同時にクリティカルセクションに入ることを防いでデータ破壊の危険性を排除する。
「パン屋」の由来
ランポートは、番号札発行機が入り口にあるパン屋を想像した。それによって個々の客にユニークな番号を割り当てるのである。客が入店する度に番号が 1 ずつ増えていく。番号表示機があって、現在応対中の客の番号が表示される。他の客は列に並んで待ち、パン屋の店員が現在の客の応対を終えると、次の番号が表示される。買い物の際、客は番号札を返して欲しいものを得るが、新たな番号を得ずに買い物を続けることはできない。
コンピュータでは「客」がスレッドに対応し、広域変数で表される i で識別される。
コンピュータアーキテクチャには限界があるため、ランポートのアナロジーの一部は若干変更を加える必要がある。複数のスレッドが同時に要求すると、同じ番号を与えられる可能性があり、これを防ぐことはできない。従って、スレッド識別子である i が優先順位も表すものと見なす。i の値が小さいスレッドは優先順位が高く、先にクリティカルセクションに入ることができる。
クリティカルセクション
クリティカルセクションとは、リソースへの排他的アクセスを要するコードであり、一度に1個のスレッドだけが実行できる。パン屋のアナロジーで言えば、店員が1人しかいないので他の客が待たされるのに等しい。
あるスレッドがクリティカルセクションに入ろうとしたとき、最初に自分の順番かどうかを調べなければならない。スレッドは自分の番号が最も小さいことを確認するために他の全スレッドの番号をチェックする。他のスレッドが同じ番号を持っている場合、i が最も小さいスレッドが優先される。
擬似コードでは、この比較を以下の形式で書いている:
(a, b) < (c, d)
これは、以下の式に等しい:
(a < c) or ((a == c) and (b < d))
スレッドがクリティカルな処理を終えたら、番号を削除して「非クリティカルセクション」に移行する。
非クリティカルセクション
非クリティカルセクションは、排他的アクセスを必要としないコード部分である。他のスレッドのリソースや実行に影響を与えないスレッド固有の計算を行う。
この部分をパン屋のアナロジーで言えば、買い物した後の行動（例えばお釣りを財布に戻すなど）に対応する。