ランポートのパン屋のアルゴリズム

ランポートのパン屋のアルゴリズム（ランポートのパンやのアルゴリズム）とは、レスリー・ランポートが考案した相互排他のためのアルゴリズムである。マルチスレッド処理などのロバストさを相互排他（ミューテックス）によって強化することを目的としている。

マルチスレッドなシステムにおいて、2つ以上のスレッドから同時に同一のリソースにアクセスすることがしばしば起きる。しかし例えば、2つ以上のスレッドがそれぞれ「リード・モディファイ・ライト」を同一の対象に相互排他なしに行えばデータは意図しない状態になり得るし、あるスレッドが複数のデータをアトミックでなく書き込んでいる途中に別のスレッドがそれを読み込んでも一貫性の損なわれたデータを読み込む可能性がある。ランポートのパン屋のアルゴリズムは数ある相互排他アルゴリズムのひとつで、並列スレッドが同時にクリティカルセクションに入ることを防いでデータ破壊の危険性を排除する。

アルゴリズム

「パン屋」の由来

ランポートは、番号札発行機が入り口にあるパン屋を想像した。それによって個々の客にユニークな番号を割り当てるのである。客が入店する度に番号が 1 ずつ増えていく。番号表示機があって、現在応対中の客の番号が表示される。他の客は列に並んで待ち、パン屋の店員が現在の客の応対を終えると、次の番号が表示される。買い物の際、客は番号札を返して欲しいものを得るが、新たな番号を得ずに買い物を続けることはできない。

コンピュータでは「客」がスレッドに対応し、広域変数で表される i で識別される。

コンピュータアーキテクチャには限界があるため、ランポートのアナロジーの一部は若干変更を加える必要がある。複数のスレッドが同時に要求すると、同じ番号を与えられる可能性があり、これを防ぐことはできない。従って、スレッド識別子である i が優先順位も表すものと見なす。i の値が小さいスレッドは優先順位が高く、先にクリティカルセクションに入ることができる。

クリティカルセクション

クリティカルセクションとは、リソースへの排他的アクセスを要するコードであり、一度に1個のスレッドだけが実行できる。パン屋のアナロジーで言えば、店員が1人しかいないので他の客が待たされるのに等しい。

あるスレッドがクリティカルセクションに入ろうとしたとき、最初に自分の順番かどうかを調べなければならない。スレッドは自分の番号が最も小さいことを確認するために他の全スレッドの番号をチェックする。他のスレッドが同じ番号を持っている場合、i が最も小さいスレッドが優先される。

擬似コードでは、この比較を以下の形式で書いている:

(a, b) < (c, d)

これは、以下の式に等しい:

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

スレッドがクリティカルな処理を終えたら、番号を削除して「非クリティカルセクション」に移行する。

非クリティカルセクション

非クリティカルセクションは、排他的アクセスを必要としないコード部分である。他のスレッドのリソースや実行に影響を与えないスレッド固有の計算を行う。

この部分をパン屋のアナロジーで言えば、買い物した後の行動（例えばお釣りを財布に戻すなど）に対応する。

アルゴリズムの実装

擬似コード

     // 広域変数の宣言と初期値
     Enter, Number: array [1..N] of integer = {0};
     
  1  Thread(i) {
  2      while (true) {
  3          Enter[i] = 1;
  4          Number[i] = 1 + max(Number[1], ..., Number[N]);
  5          Enter[i] = 0;
  6          for (j = 1; j <= N; j++) {
  7              while (Enter[j] != 0) {
  8                  // スレッド j が番号を得るまで待つ
  9              }
 10              while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) {
 11                  // 小さい番号を持つスレッドや自分と同じだが高い優先順位の
 12                  // スレッドが処理を終えるのを待つ
 13              }
 14          }
 15          // クリティカルセクション...
 16          Number[i] = 0;
 17          // 非クリティカルセクション...
 18      }
 19  }

注:スレッドはクリティカルセクションに入る前に自分自身も含めてチェックしているが、その場合の条件は常に false となるので、遅延は発生しない。

議論

個々のスレッドは広域変数のうち自身に関わるものだけに書き込み、他のスレッドに対応する部分は読み込むだけである。注目すべき点は、これがコンペア・アンド・スワップなどの低レベルの「アトミック」な操作を前提としていない点である（訳注：一見して max() が心配になるが、上述されているように同じ番号を得る可能性を考慮したアルゴリズムなので max() がアトミックである必要は無い）。本来の証明では、同一メモリ位置へのリードとライトが同時に行われた場合、ライトだけが必ず正しい動作をすると仮定している。このときのリードは任意の数を返す。従って、同期プリミティブを持たないメモリ上でこのアルゴリズムを実装することが可能である。例えば2台のコンピュータで単純に共有されているSCSIディスクなどが考えられる。

変数 Enter の必要性は 7行～13行に「ロック」がないため明確ではないように思われるかもしれない。UCDAVIS: Bakery Algorithm にあるように、Enterが無いと複数のスレッドが同時にクリティカルセクションに入ってしまう可能性が出てくる。

外部リンク

Wallace Variation of Bakery Algorithm JavaScript言語での実装（英語）