Peterson's algorithm
|
|
Peterson'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.
f0 := 0
f1 := 0
last := 0
p0: f0 := 1 p1: f1 := 1
last := 0 last := 1
do { do {
} until f1 = 0 or last ≠ 0 } until f0 = 0 or last ≠ 1
// critical section // critical section
f0 := 0 f1 := 0
See also
de:Peterson-Algorithmus nl:Peterson's Mutual Exclusion Algorithm
The Peterson Algorithm and the Dekker Algorithm are mainly of theoretical interest -- a proof of concept -- in that computer hardware comes equipped with a Test-and-Set or equivalent instruction. A Test-and-Set instruction saves the contents of a memory location in a register and then sets a flag in the same memory location. Read and write occur atomicly. When the flag read from memory is set, an interrupt occurs. The interrupt handler returns control to the interrupting Test-and-Set instruction. This is a busy-wait or spin-lock using the interrupt mechanism. When the flag read from memory is clear, no interrupt occurs. The instructions following the Test-and-Set instruction are the Critical Section. The end of the Critical Section is signalled by clearing the aforementioned memory location, thereby allowing a different processor to enter the Critical Section.