Dekker's algorithm

From Free net encyclopedia

Revision as of 19:10, 14 April 2006; view current revision
←Older revision | Newer revision→

Dekker's algorithm is a concurrent programming algorithm for mutual exclusion that allows two processes to share a single-use resource without conflict, using only shared memory for communication.

It avoids the strict alternation of a naïve turn-taking algorithm, and was one of the first mutual exclusion algorithms to be invented.

If both processes attempt to access the critical section at the same time, the algorithm will choose the process whose turn it is. If the other process is already modifying the critical section, it will wait for the process to finish.

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

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

    // critical section                   // critical section 
    turn := 1                             turn := 0
    f0 := false                           f1 := false

[edit]

Note

Many modern CPUs execute their instructions in an out-of-order fashion. This algorithm won't work on SMP machines equipped with these CPUs without the use of memory barriers.

Additionally, many optimizing compilers can perform transformations that will cause this algorithm to fail regardless of the platform. In many languages, it is legal for a compiler to detect that the flag variables f0 and f1 are never accessed in the loop. It can then remove the writes to those variables from the loop, using a process called Loop-invariant code motion. It would also be possible for many compilers to detect that the turn variable is never modified by the inner loop, and perform a similar transformation, resulting in a potential infinite loop. If either of these transformations are performed, the algorithm will fail, regardless of architecture.

[edit]