|
|
Dekker's AlgorithmDekker'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 nave 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 DO WHILE f0 DO IF turn != 0 THEN IF turn != 1 THEN f0 := false; f1 := false; WHILE turn != 0 DO WHILE turn != 1 DO END; END; f0 := true; f1 := true; END END END; END { critical section } { critical section } turn := 1; turn := 0; f0 := false; f1 := false; See also External links *Source code for Dekker's algorithm
|
 |