Peterson's algorithm
Encyclopedia
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. 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.
The algorithm uses two variables, interested and turn. A interested[n] value of true indicates that the process wants to enter the critical section
. The variable turn holds the ID of the process whose turn it is. 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 setting turn to 0.
The algorithm does satisfy the three essential criteria to solve the critical section problem. The three criteria are mutual exclusion, progress, and bounded waiting.
critical section, then either interested[1] is false (meaning P1 has left its critical section) or turn is 0 (meaning P1 is just now trying to enter the critical section, but graciously waiting). In both cases, P1 cannot be in critical section when P0 is in critical section.
priority to the other process, this process will run to completion and set its flag to 0, thereby
allowing the other process to enter the critical section.
Some processors have special instructions, like test-and-set
or compare-and-swap
, that, 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 which 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.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for mutual exclusion
Mutual exclusion
Mutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...
that allows two 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.
The algorithm
//interested[2] is boolean; and turn is an integer interested[0] = false; interested[1] = false; turn; |
|
P0: interested[0] = true; turn = 1; while (interested[1] true && turn1){ // busy wait } // critical section ... // end of critical section interested[0] = false; |
P1: interested[1] = true; turn = 0; while (interested[0] true && turn0){ // busy wait } // critical section ... // end of critical section interested[1] = false; |
The algorithm uses two variables, interested and turn. A interested[n] value of true indicates that the process wants to enter the critical section
Critical section
In concurrent programming a critical section is a piece of code that accesses a shared resource that must not be concurrently accessed by more than one thread of execution. A critical section will usually terminate in fixed time, and a thread, task or process will have to wait a fixed time to...
. The variable turn holds the ID of the process whose turn it is. 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 setting turn to 0.
The algorithm does satisfy the three essential criteria to solve the critical section problem. The three criteria are mutual exclusion, progress, and bounded waiting.
Mutual exclusion
P0 and P1 can never be in the critical section at the same time: If P0 is in itscritical section, then either interested[1] is false (meaning P1 has left its critical section) or turn is 0 (meaning P1 is just now trying to enter the critical section, but graciously waiting). In both cases, P1 cannot be in critical section when P0 is in critical section.
Progress
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. This selection cannot be postponed indefinitely. 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
Bounded waiting means that "there exists a bound or limit on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted". In Peterson's Algorithm, a process will not wait longer than one turn for entrance to the critical section: After givingpriority to the other process, this process will run to completion and set its flag to 0, thereby
allowing the other process to enter the critical section.
Note
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
Test-and-set
In computer science, the test-and-set instruction is an instruction used to write to a memory location and return its old value as a single atomic operation. If multiple processes may access the same memory, and if a process is currently performing a test-and-set, no other process may begin...
or compare-and-swap
Compare-and-swap
In computer science, the compare-and-swap CPU instruction is a special instruction that atomically compares the contents of a memory location to a given value and, only if they are the same, modifies the contents of that memory location to a given new value...
, that, by locking the memory bus, can be used to provide mutual exclusion in SMP
Symmetric multiprocessing
In computing, symmetric multiprocessing involves a multiprocessor computer hardware architecture where two or more identical processors are connected to a single shared main memory and are controlled by a single OS instance. Most common multiprocessor systems today use an SMP architecture...
systems.
Most modern CPUs reorder memory accesses to improve execution efficiency (see memory ordering
Memory ordering
Memory ordering is a group of properties of the modern microprocessors, characterising their possibilities in memory operations reordering. It is a type of out-of-order execution. Memory reordering can be used to fully utilize different cache and memory banks.On most modern uniprocessors memory...
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
Memory barrier
Memory barrier, also known as membar or memory fence or fence instruction, is a type of barrier and a class of instruction which causes a central processing unit or compiler to enforce an ordering constraint on memory operations issued before and after the barrier instruction.CPUs employ...
instruction. Implementation of Peterson's and related algorithms on processors which 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
PowerPC
PowerPC is a RISC architecture created by the 1991 Apple–IBM–Motorola alliance, known as AIM...
processor in the Xbox 360
Xbox 360
The Xbox 360 is the second video game console produced by Microsoft and the successor to the Xbox. The Xbox 360 competes with Sony's PlayStation 3 and Nintendo's Wii as part of the seventh generation of video game consoles...
).
Most such CPUs also have some sort of guaranteed atomic operation, such as XCHG on x86 processors and Load-Link/Store-Conditional
Load-Link/Store-Conditional
In computer science, load-link and store-conditional are a pair of instructions that together implement a lock-free atomic read-modify-write operation....
on Alpha
DEC Alpha
Alpha, originally known as Alpha AXP, is a 64-bit reduced instruction set computer instruction set architecture developed by Digital Equipment Corporation , designed to replace the 32-bit VAX complex instruction set computer ISA and its implementations. Alpha was implemented in microprocessors...
, MIPS
MIPS architecture
MIPS is a reduced instruction set computer instruction set architecture developed by MIPS Technologies . The early MIPS architectures were 32-bit, and later versions were 64-bit...
, PowerPC
PowerPC
PowerPC is a RISC architecture created by the 1991 Apple–IBM–Motorola alliance, known as AIM...
, 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.
See also
- Dekker's algorithmDekker's algorithmDekker's algorithm is the first known correct solution to the mutual exclusion problem in concurrent programming. The solution is attributed to Dutch mathematician Th. J. Dekker by Edsger W. Dijkstra in his manuscript on cooperating sequential processes...
- Eisenberg & McGuire algorithmEisenberg & McGuire algorithm-Summary:This is the first known correct software solution to the critical section problem for n-processes with a lower bound of n-1 turns presented by Eisenberg and McGuire.-Algorithm:All the n-processes share the following variables:...
- Lamport's bakery algorithmLamport's bakery algorithmLamport's bakery algorithm is a computer algorithm devised by computer scientist Leslie Lamport, which is intended to improve the safety in the usage of shared resources among multiple threads by means of mutual exclusion....