Peterson's algorithm

Peterson's algorithm (or Peterson's solution) is a concurrent programming algorithm for mutual exclusion that allows two or more processes to share a single-use resource without conflict, using only shared memory for communication.

In addition, either flag[1] is false (meaning that P1 has left its critical section), or turn is 0 (meaning that P1 is just now trying to enter the critical section, but graciously waiting), or P1 is at label P1_gate (trying to enter its critical section, after setting flag[1] to true but before setting turn to 0 and busy waiting).

[3][4]: 11  In Peterson's algorithm, a process will never wait longer than one turn for entrance to the critical section.

[4]: 25–26 When working at the hardware level, Peterson's algorithm is typically not needed to achieve atomic access.

Some processors have special instructions, like test-and-set or compare-and-swap, which, by locking the memory bus, can be used to provide mutual exclusion in SMP systems.

Implementation of Peterson's and related algorithms on processors that reorder memory accesses generally requires use of such operations to work correctly to keep sequential operations from happening in an incorrect order.

[citation needed] Most such CPUs also have some sort of guaranteed atomic operation, such as XCHG on x86 processors and load-link/store-conditional on Alpha, MIPS, PowerPC, and other architectures.

These instructions are intended to provide a way to build synchronization primitives more efficiently than can be done with pure shared memory approaches.

Peterson's algorithm
Snapshot of filter algorithm with 10 processes in progress. Last to enter are shown bold and underlined. (NB: Depending on scheduling, the last to enter may not be "correct".) At any time, updates to the table could be: the insertion of a new process at level 0, a change to the last to enter at a given level, or a process moving up one level (if it is not the last to enter OR there are no other processes at its own level or higher).