デッカーのアルゴリズム

デッカーのアルゴリズムはオランダ人数学者 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