Peterson's algorithm (orPeterson's solution) is aconcurrent programming algorithm formutual exclusion that allows two or more processes to share a single-use resource without conflict, using only shared memory forcommunication. It was formulated byGary L. Peterson in 1981.[1] Peterson's original algorithm worked with only two processes; it can be generalized for more than two.[2]
The algorithm uses two variables:flag andturn. Aflag[n] value oftrue indicates that the processn wants to enter thecritical section. Entrance to the critical section is granted for process P0 if P1 does not want to enter its critical section or if P1 has given priority to P0 by settingturn to0.
volatileboolflag[2]={false,false};volatileintturn; | |
P0:flag[0]=true;P0_gate:turn=1;while(flag[1]&&turn==1){// busy wait}// critical section...// end of critical sectionflag[0]=false; | P1:flag[1]=true;P1_gate:turn=0;while(flag[0]&&turn==0){// busy wait}// critical section...// end of critical sectionflag[1]=false; |
The algorithm satisfies the three essential criteria to solve the critical-section problem. The while condition works even with preemption.[1]
The three criteria aremutual exclusion, progress, and bounded waiting.[3]
Sinceturn can take on one of two values, it can be replaced by a single bit, meaning that the algorithm requires only three bits of memory.[4]: 22
P0 and P1 can never be in the critical section at the same time. If P0 is in its critical section, thenflag[0] is true. In addition, eitherflag[1] isfalse (meaning that P1 has left its critical section), orturn is0 (meaning that P1 is just now trying to enter the critical section, but graciously waiting), or P1 is at labelP1_gate (trying to enter its critical section, after settingflag[1] totrue but before settingturn to0 and busy waiting). So if both processes are in their critical sections, then we conclude that the state must satisfyflag[0] andflag[1] andturn = 0 andturn = 1. No state can satisfy bothturn = 0 andturn = 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.[5])
Progress is defined as the following: if no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in making the decision as to which process will enter its critical section next. Note that for a process or thread, the remainder sections are parts of the code that are not related to the critical section. This selection cannot be postponed indefinitely.[3] A process cannot immediately re-enter the critical section if the other process has set its flag to say that it would like to enter its critical section.
Bounded waiting, orbounded bypass, means that the number of times a process is bypassed by another process after it has indicated its desire to enter the critical section is bounded by a function of the number of processes in the system.[3][4]: 11 In Peterson's algorithm, a process will never wait longer than one turn for entrance to the critical section.
_in_progress.png)
The filter algorithm generalizes Peterson's algorithm toN > 2 processes.[6] Instead of a boolean flag, it requires an integer variable per process, stored in a single-writer/multiple-reader (SWMR) atomicregister, andN − 1 additional variables in similar registers. The registers can be represented inpseudocode asarrays:
level : array of N integerslast_to_enter : array of N − 1 integers
Thelevel variables take on values up toN − 1, each representing a distinct "waiting room" before the critical section.[6] Processes advance from one room to the next, finishing in roomN − 1, which is the critical section. Specifically, to acquire a lock, processi executes[4]: 22
i ← ProcessNofor ℓfrom 0to N − 1exclusive level[i] ← ℓ last_to_enter[ℓ] ← iwhile last_to_enter[ℓ] = iand there exists k ≠ i, such that level[k] ≥ ℓwait
To release the lock upon exiting the critical section, processi setslevel[i] to −1.
That this algorithm achieves mutual exclusion can be proven as follows. Processi exits the inner loop when there is either no process with a higher level thanlevel[i], so the next waiting room is free; or, wheni ≠ last_to_enter[ℓ], so another process joined its waiting room. At level zero, then, even if allN processes were to enter waiting room zero at the same time, no more thanN − 1 will proceed to the next room, the final one finding itself the last to enter the room. Similarly, at the next level,N − 2 will proceed,etc., until at the final level, only one process is allowed to leave the waiting room and enter the critical section, giving mutual exclusion.[4]: 22–24
Unlike the two-process Peterson algorithm, the filter algorithm does not guarantee bounded waiting.[4]: 25–26
On modern, Peterson's algorithm (as shown here)fails to provide mutual exclusion. Additional declarations and/or instructions can make it work (although different methods using the language features and/or new machine instructions can accomplish mutual exclusion more efficiently). Computers have been made far more complex since 1981; they no longer execute instructions in lockstep. Most compilers change the order of operations in ways that produce the same results faster, but they do not consider the interaction of concurrent operations that access the same data. CPUs reorder instructions within their execution pipelines. CPUs pre-read memory contents, cache memory contents, and delay and combine writes. Multiple CPU cores can access the same memory with true concurrency. Multiple CPUs can have separate caches that can delay synchronization. Any of these can break Peterson's algorithm.[7] To allow usable mutual exclusion in this new environment, machine instructions have been added, such asmemory barrier and atomic read-and-modify operations. These instructions let things "catch up" when necessary. Programming languages have added features that invoke these instructions. In several languages, declaring a variablevolatile produces executable code that accesses the variable more carefully.
Peterson's algorithm is typically not needed to ensure atomic access. In earlier processors and operating systems, it sufficed to disable interrupts immediately before a critical section and then re-enable interrupts after it was complete. Most modern processors have special instructions that provide ways to buildsynchronization primitives more efficiently than can be done with pure shared-memory approaches. These instructions, by locking thememory bus, can be used to guaranteeatomicity and providemutual exclusion insymmetric multiprocessing systems. Examples includetest-and-set (XCHG) andcompare-and-swap (CMPXCHG) onx86 processors andload-link/store-conditional onAlpha,MIPS,PowerPC, and other architectures.
Most modern CPUs reorder memory accesses to improve execution efficiency (seememory ordering for types of reordering allowed). Such processors invariably provide some way to force ordering in a stream of memory accesses, typically through amemory 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. Reordering of memory accesses can happen even on processors that don't reorder instructions (such as thePowerPC processor in theXbox 360).[citation needed]