Dekker's algorithm
From Wikipedia, the free encyclopedia
Dekker's algorithm is a concurrent programming algorithm for mutual exclusion derived by the Dutch mathematician T. J. Dekker 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. This is done by the use of two flags f0 and f1 which indicate an intention to enter the critical section and a turn variable which indicates who has priority between the two algorithms.
f0 := false
f1 := false
turn := 0 // or 1
p0: p1:
f0 := true 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
// non-critical section // non-critical section
Processes indicate an intention to enter the critical section which is tested by the outer while loop. If the other process has not flagged intent the critical section can be entered safely irrespective of the current turn. Mutual exclusion will still be guaranteed as neither process can become critical before setting their flag (implying at least one process will enter the while loop). This also guarantees progress as waiting will not occur on a process which has withdrawn intent to become critical. Alternatively, if the other process's variable was set the while loop is entered and the turn variable will establish who is permitted to become critical. Processes without priority will withdraw their intention to enter the critical section until they are given priority again (the inner while loop). Processes with priority will break from the while loop and enter their critical section.
Dekker's algorithm differs from Peterson's in its style of alternation. If a non-critical section of a process can be completed quickly enough such that the other process is never given the opportunity to check its new priority, the process's re-attempt to gain control of the critical section will be successful (the second process will not indicate intention to enter the critical section). This can happen repeatedly, and the second process will not progress. This of course requires a very unusual scheduling sequence. In contrast, Peterson's guarantees a strict alternation between processes if they request it (this is not to be confused with indefinite postponement).
[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.
To alleviate this problem, volatile variables should be marked as modifiable outside the scope of the currently executing context. For example, in Java, one would annotate these variables as 'volatile'.
