Loading article…
ランポートのベーカリーアルゴリズムは、コンピュータ科学者のレスリー・ランポートが並行システムの形式的正当性に関する長年の研究の一環として考案したコンピュータアルゴリズムであり、相互排他によって複数のスレッド間での共有リソースの使用における安全性を向上させることを目的としています。
コンピュータサイエンスでは、複数のスレッドが同時に同じリソースにアクセスすることはよくあります。2つ以上のスレッドが同じメモリ位置に書き込もうとしたり、あるスレッドが別のスレッドが書き込みを完了する前にメモリ位置を読み取ったりすると、データ破損が発生する可能性があります。ランポートのベーカリーアルゴリズムは、同時実行されるスレッドがコードの重要なセクションに同時にアクセスすることを防ぎ、データ破損のリスクを排除するために設計された、数多くの相互排他アルゴリズムの1つです。
ランポートは、入り口に番号札発行機を設置し、顧客一人ひとりに固有の番号を割り当てるパン屋を構想した。顧客が入店するたびに番号は1ずつ増えていく。カウンターには、現在対応中の顧客の番号が表示される。他の顧客は、パン職人が現在の顧客の対応を終え、次の番号が表示されるまで列に並んで待たなければならない。顧客が買い物を終え、番号札を捨てると、店員は番号を増やし、次の顧客に対応できるようにする。次の顧客は、再び買い物をするために、番号札発行機から別の番号を引かなければならない。
この類推によれば、「顧客」はグローバル変数から取得した文字iで識別されるスレッドである。
複数のスレッドが同じ番号nを要求する可能性があります。これは（アルゴリズムの目的である相互排他問題を解決しない限り）避けられません。そのため、スレッド識別子iは優先度も表すものとみなします。iの値が小さいほど優先度が高く、優先度の高いスレッドが最初にクリティカルセクションに入ります。これは、最も早く番号を要求した顧客に番号チケットを渡すことに相当します。
クリティカルセクションとは、リソースへの排他的アクセスを必要とし、一度に1つのスレッドしか実行できないコードの部分のことです。パン屋の例えで言えば、顧客がパン屋と取引をしている間、他の顧客は待たなければならない状況を指します。
スレッドがクリティカルセクションに進入しようとする場合、まず自分の番かどうかを確認する必要があります。他のすべてのスレッドの番号nをチェックし、自分のnが最小であることを確認します。もし他のスレッドのnが同じ場合は、nが最小のスレッドが最初にクリティカルセクションに進入します。
擬似コードでは、スレッドaとbのこの比較は次のように記述できます。
// n a をスレッドaの顧客番号とし、 // i a - スレッドaのスレッド番号、次に (n a , i a ) < (n b , i b )
これは以下と同等です。
(n a < n b ) または ((n a == n b ) かつ (ia < i b ))
スレッドが重要な処理を終えると、その番号が削除され、非重要な処理セクションに入ります。
非クリティカルセクションとは、排他的アクセスを必要としないコードの部分です。これは、他のスレッドのリソースや実行に干渉しない、スレッド固有の計算処理を表します。
この部分は、買い物の後に行われる行動、例えばお釣りを財布に戻すといった行動に似ています。
ランポートの原著論文では、入力変数は の選択として知られており、以下の条件が適用されます。
この例では、すべてのスレッドが同じ「メイン」関数Thread を実行します。実際のアプリケーションでは、異なるスレッドが異なる「メイン」関数を持つことがよくあります。
元の論文と同様に、スレッドはクリティカルセクションに入る前に自身をチェックすることに注意してください。ループ条件は偽と評価されるため、大きな遅延は発生しません。
// グローバル変数の宣言と初期値入力:配列[ 1. . NUM_THREADS ]のbool = { false };数値:整数の配列[ 1. . NUM_THREADS ] = { 0 };ロック（整数i ）{[ i ] = trueを入力します。Number [ i ] = 1 + max ( Number [ 1 ], ..., Number [ NUM_THREADS ]);[ i ] = falseを入力します。for ( integer j = 1 ; j <= NUM_THREADS ; j ++ ) {// スレッド j が番号を受け取るまで待機します。while ( Entering [ j ]) { /* 何もしない */ }// より小さい番号または同じ番号のすべてのスレッドが終了するまで待機します// 番号だが、優先度が高いので、作業を完了する:while (( Number [ j ] != 0 ) && (( Number [ j ], j ) < ( Number [ i ], i ))) { /* 何もしない */ }}}unlock (整数i ) {数値[ i ] = 0 ;}スレッド（整数i ）{while ( true ) {ロック（i ）// クリティカルセクションはここに記述します...ロック解除（i ）// 非クリティカルセクション...}}各スレッドは自身のストレージにのみ書き込みを行い、読み取りのみが共有されます。このアルゴリズムが、比較交換などの低レベルの「アトミック」操作の上に構築されていないことは注目に値します。元の証明では、同じストレージセルへの重複する読み取りと書き込みの場合、書き込みのみが正しければよいことが示されています。読み取り操作は任意の数値を返すことができます。したがって、このアルゴリズムは、同期プリミティブを持たないメモリ（例えば、 2台のコンピュータ間で共有される単純なSCSIディスク）上で相互排他を実装するために使用できます。
変数Enteringの必要性は、7 行目から 13 行目にかけて「ロック」がないため、明らかではないかもしれません。しかし、変数が削除され、2 つのプロセスが同じ値を計算したとしますNumber[i]。優先度の高いプロセスが を設定する前にプリエンプトされた場合Number[i]、優先度の低いプロセスは、他のプロセスがゼロの値を持っていることを認識し、クリティカル セクションに入ります。その後、優先度の高いプロセスはNumber[i]、優先度の低いプロセスに対して が等しいことを無視し、同様にクリティカル セクションに入ります。結果として、2 つのプロセスが同時にクリティカル セクションに入る可能性があります。ベーカリー アルゴリズムは、Entering変数を使用して、6 行目の代入がアトミックであるかのように見せます。プロセスiは、プロセスjがiと同じ値を選択する場合、ゼロに等しい値を見ることはありません。
擬似コードをシングルプロセスシステムまたは協調マルチタスク環境で実装する場合、「何もしない」セクションを、オペレーティングシステムに次のスレッドにすぐに切り替えるよう通知するコードに置き換える方が良いでしょう。このプリミティブはしばしば と呼ばれますyield。
ランポートのベーカリーアルゴリズムは、逐次一貫性メモリモデルを前提としています。現代の言語やマルチコアプロセッサで、このようなメモリモデルを実装しているものはほとんどありません。そのため、このアルゴリズムを正しく実装するには、通常、並べ替えを禁止するフェンスを挿入する必要があります。[ 1 ]
Nをプロセスの数と定義し、Nは自然数であると仮定します。
定数N N \in Nat と仮定します P をプロセスの集合 {1, 2, ... , N} と定義する。
P == 1..N 変数 num と flag はグローバル変数として宣言されています。
--アルゴリズム AtomicBakery { 変数 num = [i \in P |-> 0]、flag = [i \in P |-> FALSE]; 以下は、通常の辞書式順序で<<num[j], j>>が<<num[i], i>>以下であるLL(j, i)場合に真であると定義します。
define { LL(j, i) == \/ num[j] < num[i] \/ /\ num[i] = num[j] /\ j =< i } P の各要素に対して、ローカル変数 unread、max、nxt を持つプロセスがあります。連続するラベル p1、...、p7、cs 間のステップはアトミックとみなされます。id をセット S の非決定論的に選択された要素に設定し、その後 body を実行するステートメントがあります。ステートメント await expr を含むステップは、expr の値がTRUEの場合にのみ実行できます。(x \in S) { body }
プロセス (p \in P) 変数が SUBSET P 内に読み込まれていません。 最大 \in Nat、 nxt \in P; { p1: while (TRUE) { 未読 := P \ {self} ; max := 0; flag[self] := TRUE; p2: while (未読 # {}) { (i \in unread) { unread := unread \ {i}; if (num[i] > max) { max := num[i]; } } }; p3: num[self] := max + 1; p4: flag[self] := FALSE; 未読 := P \ {self} ; p5: while (unread # {}) { (i \in unread) { nxt := i ; }; ~ flag[nxt] を待機します。 p6: await \/ num[nxt] = 0 \/ LL(self, nxt) ; unread := unread \ {nxt}; } ; cs: スキップ; \* クリティカルセクション; p7: num[self] := 0; }} } AtomicIntegerArray クラスを使用する理由は、その組み込みのアトミック操作のためではなく、get メソッドと set メソッドが volatile な読み書きのように機能するためです。Javaメモリ モデルでは、これにより書き込みがすべてのスレッドから即座に参照可能になります。
AtomicIntegerArray ticket = new AtomicIntegerArray ( threads ); // スレッドのチケット、n - スレッド数// Javaは'ticket'の各要素を0で初期化しますAtomicIntegerArray entering = new AtomicIntegerArray ( threads ); // スレッドが行に入ったときに 1 を返す// Javaは'entering'の各要素を0に初期化しますpublic void lock ( int pid ) // スレッドID{開始します。( pid 、1 )を設定します。int max = 0 ;for ( int i = 0 ; i < threads ; i ++ ){int current = ticket.get ( i ) ;if (現在値>最大値){最大値=現在の値;}}ticket.set ( pid , 1 + max ) ;開始します。( pid 、0 )を設定します。for ( int i = 0 ; i < ticket . length (); ++ i ){if ( i != pid ){while ( entering.get ( i ) == 1 ) { Thread.yield ( ); } //他のスレッドがチケットを取得するまで待機するwhile ( ticket . get ( i ) != 0 && ( ticket . get ( i ) < ticket . get ( pid ) ||( ticket.get ( i ) == ticket.get ( pid ) && i < pid ) ) ){ Thread.yield ( ) ; }}}// クリティカルセクションはここに記述します...}public void unlock ( int pid ){ticket.set ( pid , 0 ) ;}