Dekker's algorithm

Dekker's algorithm is the first known correct solution to the mutual exclusion problem in concurrent programming for processes that communicate only through shared memory. Edsger Dijkstra attributed it to the Dutch mathematician Th. J. Dekker, in an unpublished paper on sequential process descriptions and in his manuscript on cooperating sequential processes. It lets two threads share a single-use resource without conflict. Each process raises a flag to announce that it wants to enter its critical section, and a shared turn variable decides who has priority when both want in; the process without priority lowers its flag and waits until the turn comes back to it. This avoids the strict alternation of a naive turn-taking scheme and guarantees mutual exclusion, freedom from deadlock and freedom from starvation. It needs no special atomic test-and-set instruction, which makes it portable, but it is limited to two processes, relies on busy waiting, and on modern out-of-order processors it needs memory barriers and careful handling of compiler optimization to stay correct.