Dekker's algorithm
Encyclopedia : D : DE : DEK : Dekker's algorithm
Dekker's algorithm is a concurrent programming algorithm for mutual exclusion due to 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.
f0 := false f1 := false turn := 0 // or 1p0: f0 := true p1: f1 := true while f1 } f0 := true f1 := true } } } }
// critical section // critical section turn := 1 turn := 0 f0 := false f1 := false
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. (this is potentially wrong - see discussion)
See also
External links
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.