|
デッカーのアルゴリズムはオランダ人数学者 T・J・デッカーの考案した相互排他のためのアルゴリズムである。これにより、共有メモリによる通信のみで、2つのプロセスが1つのリソースを競合することなく共有することができる。 厳密に交互にとっていく素朴なアルゴリズムを避けて発明された世界初の相互排他アルゴリズムの1つである。 ふたつのプロセスが同時に同じクリティカルセクションにアクセスしようとしたとき、このアルゴリズムはどちらのプロセスがアクセス権を得るかを決定する。もしもう一方のプロセスが既にクリティカルセクションに変更を加えていたら、その完了を待つ。 f0 := false f1 := false turn := 0 // or 1 p0: f0 := true p1: f1 := true while f1 = true // Start of Critical Section ・・・ // End of Critical Section turn := 1 turn := 0 f0 := false f1 := false ==注意事項== 最近の多くのCPUは命令をアウト・オブ・オーダー実行する。このアルゴリズムは、そのようなCPUを使用したマルチプロセッサマシンではメモリバリアがないと動作しない。 さらに、多くの最適化コンパイラはこのコードを変化させてしまい、プラットフォームがどうであれ、動作できなくなる。多くの言語では、フラグ変数 ''f0'' と ''f1'' がループ内で全くアクセスされないことを検出する。また多くのコンパイラは ''turn'' という変数が内側のループ内で更新されないことも検出して変換してしまい、結果として無限ループを形成してしまうだろう。このような変換をされると、このアルゴリズムはアーキテクチャに寄らず動作できなくなる。（訳注：英語版では以上の記述が不正確であるとしてノートで議論されている。具体的には最適化以前に変数がレジスタに置き換わってしまうのを妨げないと意味がないというもの）。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「デッカーのアルゴリズム」の詳細全文を読む スポンサード リンク
|