Peterson's algorithm

Peterson's algorithm, also called Peterson's solution, is a concurrent programming algorithm for mutual exclusion. It lets two or more processes share a single-use resource without conflict while communicating only through shared memory, so no special hardware instruction is required. Gary L. Peterson formulated it in 1981. His original version worked with just two processes, and it can be generalized to more. The algorithm uses two shared variables: a flag for each process, set to true when that process wants to enter its critical section, and a turn variable that records whose turn it is to wait. A process may enter if the other does not want to, or if the other has politely given it priority by setting turn. The method satisfies the three essential criteria for solving the critical-section problem, which are mutual exclusion, progress and bounded waiting. Because turn can hold only two values it can be replaced by a single bit, so the algorithm needs only three bits of memory.