ランポートのベーカリーアルゴリズム

ランポートのベーカリーアルゴリズムは、コンピュータ科学者のレスリー・ランポートが並行システムの形式的正しさに関する長年の研究の一環として考案したコンピュータアルゴリズムであり、相互排除によって複数のスレッド間で共有されるリソースの使用における安全性を向上させることを目的としています。

コンピュータサイエンスでは、複数のスレッドが同じリソースに同時にアクセスすることは珍しくありません。2つ以上のスレッドが同じメモリ位置に書き込みを試みたり、あるスレッドが書き込みを完了する前に別のスレッドがメモリ位置を読み取ったりすると、データ破損が発生する可能性があります。ランポートのベーカリーアルゴリズムは、複数のスレッドが同時にコードの重要なセクションに進入するのを防ぎ、データ破損のリスクを排除するために設計された、多くの相互排他アルゴリズムの1つです。

アルゴリズム

類推

ランポートは、入口に番号発行機を設置し、各顧客に固有の番号を付与するパン屋を構想しました。顧客が入店するたびに番号は1ずつ増加します。グローバルカウンターには、現在接客中の顧客の番号が表示されます。他の顧客は、店員が現在の顧客の接客を終えて次の番号が表示されるまで、列に並んで待つ必要があります。顧客が買い物を終えて番号札を処分すると、店員は番号を1つ増やし、次の顧客が接客できるようになります。その顧客が再び買い物をするには、番号発行機から別の番号札を引く必要があります。

この類推によれば、「顧客」は、グローバル変数から取得された 文字iで識別されるスレッドです。

コンピュータアーキテクチャの制限により、ランポートのアナロジーの一部には若干の修正が必要です。複数のスレッドが要求した際に、同じ番号nを取得する可能性があります。これは（アルゴリズムの目的である相互排他性をまず解決しない限り）避けられません。したがって、スレッド識別子iは優先度でもあると仮定します。iの値が小さいほど優先度が高く、優先度の高いスレッドが最初にクリティカルセクションに入ります。

クリティカルセクション

クリティカルセクションとは、リソースへの排他アクセスを必要とし、一度に1つのスレッドのみが実行できるコード部分です。パン屋の例えで言えば、顧客がパン屋と取引している間、他のスレッドは待機しなければなりません。

スレッドがクリティカルセクションに入る場合、自分の番かどうかを確認する必要があります。他のすべてのスレッドの番号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 ))

スレッドがクリティカルなジョブを終了すると、その番号が削除され、非クリティカル セクションに入ります。

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

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

この部分は、お釣りを財布に戻すなど、買い物後に発生する動作に似ています。

アルゴリズムの実装

定義

ランポートの原著論文では、入力変数はを選択することとして知られており、次の条件が適用されます。

  • [i]を選択する単語と番号[i]はプロセスiのメモリにあり、最初はゼロです。
  • 数値[i]の値の範囲は無制限です。
  • プロセスはいつでも失敗する可能性があります。失敗すると、直ちに非クリティカルセクションに移動して停止すると仮定します。その際、メモリからの読み取りで任意の値が返される期間が発生する可能性があります。最終的には、メモリからの読み取りはすべてゼロになります。

コード例

擬似コード

この例では、すべてのスレッドが同じ「main」関数Threadを実行します。実際のアプリケーションでは、スレッドごとに異なる「main」関数が実行されることがよくあります。

元の論文と同様に、スレッドはクリティカルセクションに入る前に自身をチェックすることに注意してください。ループ条件はfalseと評価されるため、大きな遅延は発生しません。 

// グローバル変数の宣言と初期値入力：bool = { false }の配列[ 1. . NUM_THREADS ] ;数:整数の配列[ 1. . NUM_THREADS ] = { 0 };ロック(整数i ) {[ i ] = trueと入力すると、数値[ i ] = 1 + max (数値[ 1 ], ...,数値[ NUM_THREADS ] )。[ i ] = falseと入力する;(整数j = 1 ; j < = NUM​​_THREADS ; j ++ ) {// スレッド j が番号を受け取るまで待機します。while ( Entering [ j ]) { /* 何もしない */ }// より小さい番号または同じ番号を持つすべてのスレッドが終了するまで待機します// 番号は高いが優先度が高い場合は、作業を終了します。while (( Number [ j ] != 0 ) && (( Number [ j ], j ) < ( Number [ i ], i ))) { /* 何もしない */ }}}ロック解除(整数i ) {数[ i ] = 0 ;}スレッド(整数i ) {while ( true ) {ロック( i );// クリティカル セクションはここに記述します...ロックを解除する( i );// 非クリティカルセクション...}}

各スレッドは自身のストレージに書き込みのみを行い、共有されるのは読み取りのみです。このアルゴリズムが、比較とスワップなどの低レベルの「アトミック」操作に基づいていないことは注目に値します。元の証明では、同じストレージセルへの重複した読み取りと書き込みの場合、書き込みのみが正しいことが示されています。読み取り操作は任意の数値を返す可能性があります。したがって、このアルゴリズムは、同期プリミティブを持たないメモリ、例えば2台のコンピュータ間で共有される単純なSCSIディスク上での排他制御の実装に使用できます。

7 行目から 13 行目までには「ロック」がないので、変数EnteringNumber[i]の必要性は明らかでないかもしれません。しかし、変数が削除され、2 つのプロセスが同じ を計算したと仮定します。 を設定する前に、優先度の高いプロセスがプリエンプトされた場合Number[i]、優先度の低いプロセスは、もう一方のプロセスの数が 0 であることを確認し、クリティカル セクションに入ります。その後、優先度の高いプロセスはNumber[i]、優先度の低いプロセスが等しいことを無視し、クリティカル セクションに入ります。結果として、2 つのプロセスが同時にクリティカル セクションに入ることができます。ベーカリー アルゴリズムは、Entering変数を使用して、6 行目の割り当てがアトミックであるかのように見せます。プロセスiは、 iと同じ数を選択するプロセスjに対して、0 に等しい数を見ることはありません。

単一プロセスシステムまたは協調型マルチタスク環境で擬似コードを実装する場合、「何もしない」セクションを、オペレーティングシステムに次のスレッドにすぐに切り替えるよう通知するコードに置き換える方が適切です。このプリミティブは、しばしば と呼ばれますyield。

ランポートのベーカリーアルゴリズムは、逐次一貫性メモリモデルを前提としています。このようなメモリモデルを実装している言語やマルチコアプロセッサはほとんどありません。そのため、このアルゴリズムを正しく実装するには、通常、並べ替えを抑制するためにフェンスを挿入する必要があります。[ 1 ]

PlusCalコード

N をプロセスの数と宣言し、N は自然数であると仮定します。 

定数N N \in Nat と仮定

Pをプロセスの集合{1, 2, ..., N}として定義します。 

P == 1..N

変数 num と flag はグローバルとして宣言されています。 

--アルゴリズム AtomicBakery { 変数 num = [i \in P |-> 0]、フラグ = [i \in P |-> FALSE];

以下は、通常の辞書式順序で<<num[j], j>>が<<num[i], i>>以下の場合に限りLL(j, i)真であると定義します。 

定義 { LL(j, i) == \/ num[j] < num[i] \/ /\ num[i] = num[j] /\ j =< i }

P の各要素に対して、ローカル変数 unread、max、nxt を持つプロセスが存在します。連続するラベル p1、…、p7、cs 間のステップはアトミックとみなされます。ステートメントは、集合 S から非決定的に選択された要素に id を設定し、次に body を実行します。ステートメント await expr を含むステップは、expr の値がTRUE の場合にのみ実行できます。 (x \in S) { body }

プロセス (p \in P) SUBSET P内の変数は読み込まれません。 最大\in Nat、 次の \in P; { p1: while (TRUE) { 未読 := P \ {self} ; 最大値:= 0; フラグ[自分]:=TRUE; p2: while (未読 # {}) { (i \in 未読) の場合 { 未読 := 未読 \ {i}; num[i] > max の場合、 max := num[i]; } } }; p3: num[self] := max + 1; p4: フラグ[自己]:=FALSE; 未読 := P \ {self} ; p5: while (未読 # {}) { (i \in 未読) { nxt := i ; }; の場合 ~ フラグ[nxt]を待機します。 p6: 待機 \/ num[nxt] = 0 \/ LL(自分自身、次のもの) ; 未読 := 未読 \ {nxt}; } ; cs: skip ; \* クリティカルセクション; p7: num[self] := 0; }} }

Javaコード

AtomicIntegerArrayクラスを使用するのは、組み込みのアトミック操作のためではなく、getメソッドとsetメソッドがvolatile型の読み取り/書き込みのように動作するためです。Javaメモリモデルでは、これにより書き込みがすべてのスレッドから即座に参照可能になります。 

AtomicIntegerArray ticket = new AtomicIntegerArray ( threads ); // 行内のスレッドのチケット、n - スレッド数// Javaは「チケット」の各要素を0に初期化しますAtomicIntegerArray entering = new AtomicIntegerArray ( threads ); // 1 スレッドが行内に入るとき// Javaは'entering'の各要素を0に初期化しますpublic void lock ( int pid ) // スレッドID{入力します。set ( pid , 1 ) ;整数最大値= 0 ;for ( int i = 0 ; i <スレッド; i ++ ){int current =チケット.get ( i ) ;if (現在値>最大値){最大=現在の値;}}チケット.set ( pid , 1 + max ) ;入力します。set ( pid , 0 ) ;for ( int i = 0 ; i <チケット. length (); ++ i ){もし( i != pid ){while ( entering . get ( i ) == 1 ) { Thread . yield (); } // 他のスレッドがチケットを選択するまで待機しますticket.get ( i ) ! = 0の状態で、ticket.get ( i ) < ticket.get ( pid ) ||​​​​​(チケット. get ( i ) ==チケット. get ( pid ) && i < pid ))){スレッド.yield ( ); }}}// クリティカル セクションはここに記述します...}パブリックvoidロック解除（int pid ）{チケット.set ( pid , 0 ) ;}

参照

参考文献

「 https://en.wikipedia.org/w/index.php?title=Lamport%27s_bakery_algorithm&oldid=1332615171」より取得