Loading article…
ピーターソンのアルゴリズム（またはピーターソンのソリューション）は、2つ以上のプロセスが通信に共有メモリのみを使用して、競合することなく単一使用のリソースを共有できるようにする相互排他制御の並行プログラミング アルゴリズムです。これは、1981年にゲイリー・L・ピーターソンによって策定されました。[1]ピーターソンの元の定式化は2つのプロセスでのみ機能しましたが、アルゴリズムは3つ以上のプロセスに一般化できます。[2]
アルゴリズム
flagこのアルゴリズムは、と という2 つの変数を使用しますturn。flag[n]の値は、trueプロセスがクリティカル セクションにn入ることを望んでいることを示します。 P1 がクリティカル セクションturnに入りたくない場合、または P1 がを に設定して P0 に優先順位を付けた場合、プロセス P0 のクリティカル セクションへの進入が許可されます0。
このアルゴリズムは、クリティカルセクション問題を解決するための3つの必須基準を満たしています。while条件はプリエンプションがあっても機能します。[1]
3つの基準は相互排除、進捗、制限付き待機である。[3]
は2つの値のうちの1つをとることができるのでturn、1ビットで置き換えることができ、アルゴリズムに必要なメモリは3ビットだけである。[4] : 22
相互排除
P0 と P1 が同時にクリティカル セクションに入ることはできません。P0 がクリティカル セクション内にある場合、はflag[0]真です。さらに、はflag[1](falseつまり、P1 がクリティカル セクションを離れた)、turnは0(つまり、P1 がちょうどクリティカル セクションに入ろうとしているが、丁寧に待機している)、または P1 がラベルにある(に設定した後、 に設定してビジー待機する前P1_gateに、クリティカル セクションに入ろうとしている) のいずれかです。したがって、両方のプロセスがクリティカル セクション内にある場合、状態はおよびおよびおよびを満たしている必要があると結論付けられます。と の両方を満たす状態は存在しないため、両方のプロセスがクリティカル セクション内にある状態はあり得ません。(これは、Schneider 1997 で厳密に行われた議論を再現したものです。 [5] )
flag[1]trueturn0flag[0]flag[1]turn = 0turn = 1turn = 0turn = 1
進捗
進行状況は次のように定義されます。クリティカル セクションで実行中のプロセスがなく、いくつかのプロセスがクリティカル セクションに入ることを望んでいる場合、残りのセクションで実行されていないプロセスのみが、どのプロセスが次にクリティカル セクションに入るかの決定に参加できます。プロセスまたはスレッドの場合、残りのセクションはクリティカル セクションに関連しないコードの一部であることに注意してください。この選択は無期限に延期することはできません。[3]他のプロセスがクリティカル セクションに入ることを示すフラグを設定した場合、プロセスはすぐにクリティカル セクションに再入することはできません。
制限された待機
制限付き待機、または制限付きバイパスとは、プロセスがクリティカルセクションに入ることを示した後に別のプロセスによってバイパスされる回数が、システム内のプロセス数の関数によって制限されることを意味します。[3] [4] ：11 ピーターソンのアルゴリズムでは、プロセスはクリティカルセクションに入るために1ターン以上待機することはありません。
フィルタアルゴリズム: 2つ以上のプロセスに対するピーターソンのアルゴリズム
_in_progress.png/500px-Snapshot_of_filter_algorithm_(Peterson's_algorithm_for_more_than_2_processes)_in_progress.png)
フィルタアルゴリズムは、ピーターソンのアルゴリズムをN > 2プロセスに一般化します。[6]ブールフラグの代わりに、プロセスごとに1つの整数変数が必要で、これはシングルライター/マルチリーダー（SWMR）アトミックレジスタに格納され、 N − 1個の追加変数が同様のレジスタに格納されます。レジスタは、疑似コードで配列として表すことができます。
レベル: N 個の整数の配列 last_to_enter : N − 1 個の整数の配列
レベル変数は最大N − 1までの値を取り、それぞれがクリティカルセクションの前の個別の「待合室」を表します。[6]プロセスは1つの部屋から次の部屋へと進み、クリティカルセクションである部屋N − 1で終了します。具体的には、ロックを取得するために、プロセスiは[4]を実行します。22
i ← ProcessNo
ℓは0からN − 1を除く
レベル[i] ← ℓ
最後に入力した文字[ℓ] ← i
last_to_enter[ℓ] = iであり、 k ≠ iが存在するので、level[k] ≥ ℓ
wait
クリティカルセクションを終了したときにロックを解除するには、プロセスiはlevel[i]を-1に設定します。
このアルゴリズムが相互排他性を実現することは、次のように証明できる。プロセスi は、レベル[i]より高いレベルのプロセスが存在しない場合、つまり次の待合室が空いている場合、またはi ≠ last_to_enter[ℓ]の場合、別のプロセスが待合室に入る場合、内側のループから出る。レベル 0 では、N 個のプロセスすべてが同時に待合室 0 に入るとしても、N − 1 個しか次の部屋に進むことができず、最後の 1 個が最後に部屋に入ることになる。同様に、次のレベルではN − 2 個が進み、最終レベルでは 1 つのプロセスだけが待合室を出てクリティカル セクションに入ることができ、相互排他性が得られる。[4] : 22–24
2プロセスピーターソンアルゴリズムとは異なり、フィルタアルゴリズムは制限された待機を保証しません。[4] ：25–26
注記
ハードウェアレベルで作業する場合、通常、アトミック アクセスを実現するために Peterson のアルゴリズムは必要ありません。一部のプロセッサには、テスト アンド セットや比較アンドスワップなどの特別な命令があり、メモリ バスをロックすることで、 SMPシステム で相互排他性を提供するために使用できます。
最近の CPU のほとんどは、実行効率を向上させるためにメモリ アクセスを並べ替えます (許可されている並べ替えの種類については、メモリの順序付けを参照してください)。このようなプロセッサは、通常、メモリ バリア命令を通じて、メモリ アクセスのストリーム内で順序付けを強制する何らかの方法を必ず提供します。メモリ アクセスを並べ替えるプロセッサで Peterson のアルゴリズムや関連するアルゴリズムを実装するには、通常、連続した操作が間違った順序で行われないように、このような操作を正しく使用する必要があります。メモリ アクセスの並べ替えは、命令を並べ替えないプロセッサ ( Xbox 360のPowerPCプロセッサなど) でも発生する可能性があることに注意してください。[引用が必要]
このような CPU のほとんどには、 x86プロセッサやAlpha 、 MIPS 、 PowerPCなどのアーキテクチャでのロードリンク/ストア条件など、何らかの保証されたアトミック操作もあります。これらの命令は、純粋な共有メモリ アプローチよりも効率的に同期プリミティブを構築する方法を提供することを目的としています。
XCHG
参照
脚注
- ^ ab GLピーターソン：「相互排除問題に関する神話」、情報処理レター12（3）1981、115-116
- ^ 1990 年 1 月の Operating Systems Reviewで議論されているように(「相互排除アルゴリズムの証明」、M Hofri)。
- ^ abc Silberschatz. オペレーティングシステムの概念: 第 7 版。John Wiley and Sons、2005 年、194 ページ。
- ^ abcde Raynal, Michel (2012).並行プログラミング: アルゴリズム、原理、基礎. Springer Science & Business Media. ISBN 978-3642320279。
- ^ FB Schneider、「並行プログラミングについて」、Springer Verlag、1997年、185〜196ページ。
- ^ ab Herlihy, Maurice ; Shavit, Nir (2012). The Art of Multiprocessor Programming . Elsevier. pp. 28–31. ISBN 9780123977953。
外部リンク
- https://elixir.bootlin.com/linux/v5.6.19/source/arch/arm/mach-tegra/sleep-tegra20.S#L120 以前 Linux カーネルで使用されていた Peterson のアルゴリズムの例 (v5.7 で削除)。