Алгоритм Питерсона для взаимного исключения

Concurrent programming algorithm for mutual exclusion
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. It was formulated by Gary L. Peterson in 1981. While Peterson's original formulation worked with only two processes, the algorithm can be generalized for more than two.

P0 and P1 can never be in the critical section at the same time. If P0 is in its critical section, then flag[0] is true. 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). So if both processes are in their critical sections, then we conclude that the state must satisfy flag[0] and flag[1] and turn = 0 and turn = 1. No state can satisfy both turn = 0 and turn = 1, so there can be no state where both processes are in their critical sections. (This recounts an argument that is made rigorous in Schneider 1997.)

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. Most modern CPUs reorder memory accesses to improve execution efficiency (see memory ordering for types of reordering allowed). Such processors invariably give some way to force ordering in a stream of memory accesses, typically through a memory barrier instruction. 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. Note that reordering of memory accesses can happen even on processors that don't reorder instructions (such as the PowerPC processor in the Xbox 360). 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.