デッカーのアルゴリズムとは? わかりやすく解説

Weblio 辞書 > 固有名詞の種類 > 製品 > コンピュータ > その他コンピュータ製品 > 排他制御 > デッカーのアルゴリズムの意味・解説 

デッカーのアルゴリズム

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/03/06 07:05 UTC 版)

デッカーのアルゴリズムオランダ人数学者 T・J・デッカーの考案した相互排他のためのアルゴリズムである。これにより、共有メモリによる通信のみで、2つのプロセスが1つのリソースを競合することなく共有することができる。

厳密に交互にとっていく素朴なアルゴリズムを避けて発明された世界初の相互排他アルゴリズムの1つである。

ふたつのプロセスが同時に同じクリティカルセクションにアクセスしようとしたとき、このアルゴリズムはどちらのプロセスがアクセス権を得るかを決定する。もしもう一方のプロセスが既にクリティカルセクションに変更を加えていたら、その完了を待つ。

 f0 := false
 f1 := false
 turn := 0   // or 1

 p0: f0 := true                      p1: f1 := true
     while f1 = true {                   while f0 = true {
         if turn ≠ 0 {                      if turn ≠ 1 {
             f0 := false                         f1 := false
             while turn ≠ 0 {                   while turn ≠ 1 {
             }                                   }
             f0 := true                          f1 := true
         }                                   }
     }                                   }

     // Start of Critical Section 
       ・・・            
     // End of Critical Section 
    
     turn := 1                           turn := 0
     f0 := false                         f1 := false

注意事項

最近の多くのCPUは命令をアウト・オブ・オーダー実行する。このアルゴリズムは、そのようなCPUを使用したマルチプロセッサマシンではメモリバリアがないと動作しない。

さらに、多くの最適化コンパイラはこのコードを変化させてしまい、プラットフォームがどうであれ、動作できなくなる。多くの言語では、フラグ変数 f0f1 がループ内で全くアクセスされないことを検出する。また多くのコンパイラは turn という変数が内側のループ内で更新されないことも検出して変換してしまい、結果として無限ループを形成してしまうだろう。このような変換をされると、このアルゴリズムはアーキテクチャに寄らず動作できなくなる。(訳注:英語版では以上の記述が不正確であるとしてノートで議論されている。具体的には最適化以前に変数がレジスタに置き換わってしまうのを妨げないと意味がないというもの)。

PCI-Expressなどのバスは、読み書きの順序を変更してしまう場合がある。書いた後に読む場合は読む前までに書かれるなどの性質を利用して実装する必要がある場合がある。

関連項目

外部リンク





固有名詞の分類


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「デッカーのアルゴリズム」の関連用語

デッカーのアルゴリズムのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



デッカーのアルゴリズムのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのデッカーのアルゴリズム (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS