導入
ランポートのベーカリー アルゴリズムは、アトミック操作を提供しない共有メモリを備えたマルチプロセッサ マシンの一般的なコンテキストで、レスリー ランポートによって発見された相互排他アルゴリズムです。
本来の形式では、クリティカル セクションに入る前にアクティブな待機を使用します。
ユーティリティ
ベーカリー アルゴリズムは、アトミックな操作を提供しないマシンや、一度に 1 つのメモリ操作 (読み取りまたは書き込み) のみを実行できる単純なマシンを含む、あらゆるマルチプロセッサ マシンで相互排他を実行するために使用できます。
ただし、最新のアーキテクチャはすべて、単一の操作で読み取りと書き込みの両方を組み合わせたアトミック操作 ( Test And Set 、 Fetch And Add 、またはCompare And Swapなど) を提供します。これらにより、相互排他をより効率的に実装できます。
したがって、ベーカリーのアルゴリズムは現在、主に理論的および教育的な関心を集めています (詳細については、このセクションをお読みください)。
アルゴリズム
このアルゴリズムは、N 個のスレッドの相互排他を保証します。N は事前に固定されています。
スレッドは同等の識別子 (通常は整数) (つまり、順序関係を持つセットの要素、合計であると想定) を持たなければなりません。
このアルゴリズムには、N 個の要素を含む 2 つの配列を保存するために使用される共有メモリ領域も必要です。
- 1 つ目は、 CHOICEと呼ばれるブール値の配列です。
- 2 番目は、 COUNTERと呼ばれる自然整数の配列です。
この最後の表では、特定の値 0 は、ワイヤがクリティカル セクションに入ることを望まないことを示します。他の値は潜在的なチケット番号を表します。
共有配列に対する読み取りおよび書き込み操作をアトミックに実行する必要はありません。理解を容易にするために、読者はまずこれらの操作がアトミックであると仮定し、次にこの点の妥当性について説明するセクションを参照してください。
このアルゴリズムは、さまざまなスレッドの相対的な実行速度については何も想定しません。これにより、一度に 1 つのスレッドだけがクリティカル セクションを実行するようになります。デッドロックや飢餓が発生することはありません。
初期化
アルゴリズムを使用する前に、共有配列を次のように初期化する必要があります。
すべての COUNTER ボックスを 0 に初期化します。すべての CHOICE ボックスを 0 (または FALSE) に初期化します。
クリティカルセクションへのエントリー
次のコードは、クリティカル セクションに入ろうとしているスレッドによって実行されます。 ID はその識別子を指定します。
第一段階
コードのこの部分は、チケットを割り当てることを目的としています。原則は、すでに割り当てられているすべての番号を調べて、他の番号よりも大きい新しい番号を割り当てることです。
' チケット割り当てフェーズの開始 CHOICE[ID] = 1 MAX = 0 ' 他スレッドからのチケットの最大値の計算 FOR J = 0 TO N - 1 DO CJ = COUNTER[J] IF MAX < CJ THEN MAX = CJ END IF END FOR J ' 新しいチケットの割り当て COUNTER [ID] = MAX + 1 ' チケット割り当てフェーズの終了 CHOICE[ID] = 0
ただし、複数のスレッドがこのフェーズのコードを同時に実行することは可能です。その後、同じ最大値の計算を実行して、自分自身に同じチケットを割り当てることができます。このケースは次のフェーズで考慮されます。
一般に、読み取りと書き込みがアトミックであると想定しない場合、最初のフェーズを同時に実行するスレッドが異なるチケット値を取得する可能性さえあります。ただし、これらの値は、最初のフェーズへのチケットの割り当てが開始される前に 2 番目のフェーズに到達した他のスレッドからのチケットの値より必然的に大きくなります。
第二段階
この段階は、上で展開したアナロジーでは、順番を待つことに対応します。アイデアは、他のすべてのスレッドを調べて、それらのスレッドのチケット番号が低いかどうかをテストすることです。その場合、最初にクリティカル セクションに移動する必要があります。
「すべてのスレッドでループ FOR J = 0 TO N - 1 DO」 対象のスレッド (J) がチケットの割り当てを完了するまで待ちます。 WHILE CHOICE[J] == 1 DO ' (1) NOTHING END WHILE ' 現在のスレッド (ID) が考慮されているスレッド (J) よりも優先されるのを待ちます。 AS COUNTER[J] <> 0 AND ' (2) (COUNTER[J] < COUNTER[ID] OR ' (3) (COUNTER[J] == COUNTER[ID] AND J < ID)) ' (4) DO Jにとっては何も終わっていない
チケットの比較は、(3) で示される行で行われます。前に説明したように、2 つのスレッドが同じチケットを割り当てることが可能です。この場合、最も高い優先順位は、最小の識別子を持つものです (行 (4) を参照)。したがって、優先順位はペア (COUNTER[J], J) の辞書編集順に従って評価されます。実際にクリティカル セクションに入ることを希望するワイヤのみが考慮されます (行 (2) を参照)。
アルゴリズムが適切に機能するために重要な点であり、おそらく最も理解が難しい点の 1 つは、他のスレッドの古いチケット値が誤って考慮されることを避けるために CHOICE テーブルを使用することです (行(1) ））。 2 つのスレッド J と ID (J < ID) が最初のフェーズ ループを同時に実行し、同じチケット番号が割り当てられているとします。簡単にするために、他のすべてのワイヤはクリティカル セクションの外側にあり、クリティカル セクションに入ろうとしていないと考えます。また、スレッド ID が第 2 フェーズを実行している間、スレッド J はまだ第 1 フェーズのチケット更新操作を実行していないと仮定します (COUNTER [J] = MAX + 1 が実行されていない)。最後に、CHOICE[J] の値の待機ループを削除したとします (行 (1))。この場合、ID スレッドは CHOICE[J] の値を考慮せずに、0 である COUNTER[J] (行 (2)) を読み取ります。この値 0 は、ワイヤ J がクリティカル セクションの外側にあり、クリティカル セクションに入ろうとしていないことを意味すると考えられます。スレッド ID は、スレッド ID が J よりも優先されると推定し、クリティカル セクションに入ります。スレッド J は実行を継続し、COUNTER[J] を更新し、第 2 フェーズに入ります。次に、彼はスレッド ID と同じチケット番号を持っていることに気づき、それらの ID を比較します。 J < ID なので J が優先されます。それで彼はクリティカルセクションに入ってしまいます。最後に、この場合、ワイヤ J と ID は両方ともクリティカル セクションに入る可能性があり、これはまさにアルゴリズムが回避しようとするものです。
クリティカルセクションの終了
クリティカル セクションを終了すると、現在のスレッド (ID) は単に以下のコードを実行します。 COUNTER[ID] は0にリセットされ、スレッド ID がクリティカル セクションに存在せず、アクセスしようとしていないことを他のスレッドに示します。
カウンター[ID] = 0