Dekker's algorithm
|
|
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
See also
External links
- Source code for Dekker's algorithm (http://www.csee.wvu.edu/~jdm/classes/cs356/notes/mutex/Dekker.html)