The algorithm
The algorithm uses two variables:flag
and turn
. A flag /code> value of true
indicates that the process n
wants to enter the critical section
In concurrent programming, concurrent accesses to shared resources can lead to unexpected or erroneous behavior, so parts of the program where the shared resource is accessed need to be protected in ways that avoid the concurrent access. One way to ...
. Entrance to the critical section is granted for process P0 if P1 does not want to enter its critical section and if P1 has given priority to P0 by setting turn
to 0
.
The algorithm satisfies the three essential criteria to solve the critical-section problem. The while condition works even with preemption.
The three criteria are mutual exclusion, progress, and bounded waiting.Silberschatz. Operating Systems Concepts: Seventh Edition. John Wiley and Sons, 2005, Page 194.
Since turn
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.
Mutual exclusion
P0 and P1 can never be in the critical section at the same time. If P0 is in its critical section, then flag /code> is true. In addition, either flag /code> 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 /code> 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 /code> and flag /code> 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.F. B. Schneider. On Concurrent Programming, Sringer Verlag, 1997, Pages 185–196.)
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. 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. 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, or bounded 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. In Peterson's algorithm, a process will never wait longer than one turn for entrance to the critical section.
Filter algorithm: Peterson's algorithm for more than two processes
The filter algorithm generalizes Peterson's algorithm to processes. Instead of a boolean flag, it requires an integer variable per process, stored in a single-writer/multiple-reader (SWMR) atomic register
Register or registration may refer to:
Arts entertainment, and media Music
* Register (music), the relative "height" or range of a note, melody, part, instrument, etc.
* ''Register'', a 2017 album by Travis Miller
* Registration (organ), th ...
, and additional variables in similar registers. The registers can be represented in pseudocode
In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine re ...
as array
An array is a systematic arrangement of similar objects, usually in rows and columns.
Things called an array include:
{{TOC right
Music
* In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...
s:
level : array of N integers
last_to_enter : array of N − 1 integers
The variables take on values up to , each representing a distinct "waiting room" before the critical section. Processes advance from one room to the next, finishing in room , which is the critical section. Specifically, to acquire a lock, process executes
i ← ProcessNo
for ℓ from 0 to N − 1 exclusive
level ← ℓ
last_to_enter ← i
while last_to_enter = i and there exists k ≠ i, such that level ≥ ℓ
wait
To release the lock upon exiting the critical section, process sets to −1.
That this algorithm achieves mutual exclusion can be proven as follows. Process exits the inner loop when there is either no process with a higher level than , so the next waiting room is free; or, when , so another process joined its waiting room. At level zero, then, even if all processes were to enter waiting room zero at the same time, no more than will proceed to the next room, the final one finding itself the last to enter the room. Similarly, at the next level, will proceed, etc.
''Et Cetera'' ( or (proscribed) , ), abbreviated to ''etc.'', ''etc'', ''et cet.'', ''&c.'' or ''&c'' is a Latin expression that is used in English to mean "and other similar things", or "and so forth". Translated literally from Latin, means 'an ...
, until at the final level, only one process is allowed to leave the waiting room and enter the critical section, giving mutual exclusion.
The algorithm can also be shown to be starvation-free, meaning that all processes that enter the loop eventually exit it (assuming that they don't stay in the critical section indefinitely). The proof proceeds by induction from downward. A process at is in the critical section and by assumption will exit it. At all lower levels , it is impossible for a process to wait forever, since either another process will enter the waiting room, setting and "liberating" ; or this never happens, but then all processes that are also in the waiting rooms must be at higher levels and by the inductive hypothesis, they will eventually finish the loop and reset their levels, so that for all , and again exits the loop.
Starvation freedom is in fact the highest liveness Properties of an execution of a computer program —particularly for concurrent and distributed systems— have long been formulated by giving ''safety properties'' ("bad things don't happen") and ''liveness properties'' ("good things do happen").
...
guarantee that the algorithm gives; unlike the two-process Peterson algorithm, the filter algorithm does not guarantee bounded waiting.
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 In computer science, the test-and-set instruction is an instruction used to write (set) 1 to a memory location and return its old value as a single atomic (i.e., non-interruptible) operation. The caller can then "test" the result to see if the stat ...
or compare-and-swap
In computer science, compare-and-swap (CAS) is an atomic instruction used in multithreading to achieve synchronization. It compares the contents of a memory location with a given value and, only if they are the same, modifies the contents of tha ...
, 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 Memory ordering describes the order of accesses to computer memory by a CPU. The term can refer either to the memory ordering generated by the compiler during compile time, or to the memory ordering generated by a CPU during runtime.
In modern mic ...
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
In computing, a memory barrier, also known as a membar, memory fence or fence instruction, is a type of barrier instruction that causes a central processing unit (CPU) or compiler to enforce an ordering constraint on memory operations issued b ...
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
PowerPC (with the backronym Performance Optimization With Enhanced RISC – Performance Computing, sometimes abbreviated as PPC) is a reduced instruction set computer (RISC) instruction set architecture (ISA) created by the 1991 Apple Inc., App ...
processor in the Xbox 360
The Xbox 360 is a home video game console developed by Microsoft. As the successor to the original Xbox, it is the second console in the Xbox series. It competed with Sony's PlayStation 3 and Nintendo's Wii as part of the seventh generation ...
).
Most such CPUs also have some sort of guaranteed atomic operation
In concurrent programming, an operation (or set of operations) is linearizable if it consists of an ordered list of invocation and response events (event), that may be extended by adding response events such that:
# The extended list can be re-e ...
, such as XCHG
on x86
x86 (also known as 80x86 or the 8086 family) is a family of complex instruction set computer (CISC) instruction set architectures initially developed by Intel based on the Intel 8086 microprocessor and its 8088 variant. The 8086 was introd ...
processors and load-link/store-conditional
In computer science, load-linked/store-conditional (LL/SC), sometimes known as load-reserved/store-conditional (LR/SC), are a pair of instructions used in multithreading to achieve synchronization. Load-link returns the current value of a memory ...
on Alpha
Alpha (uppercase , lowercase ; grc, ἄλφα, ''álpha'', or ell, άλφα, álfa) is the first letter of the Greek alphabet. In the system of Greek numerals, it has a value of one. Alpha is derived from the Phoenician letter aleph , whic ...
, MIPS, PowerPC
PowerPC (with the backronym Performance Optimization With Enhanced RISC – Performance Computing, sometimes abbreviated as PPC) is a reduced instruction set computer (RISC) instruction set architecture (ISA) created by the 1991 Apple Inc., App ...
, 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 algorithm Dekker's algorithm is the first known correct solution to the mutual exclusion problem in concurrent programming where processes only communicate via shared memory. The solution is attributed to Dutch mathematician Th. J. Dekker by Edsger W. Dijks ...
* Eisenberg & McGuire algorithm
The Eisenberg & McGuire algorithm is an algorithm for solving the critical sections problem, a general version of the dining philosophers problem. It was described in 1972 by Murray A. Eisenberg and Michael R. McGuire.
Algorithm
All the ''n'' ...
* Lamport's bakery algorithm
Lamport's bakery algorithm is a computer algorithm devised by computer scientist Leslie Lamport, as part of his long study of the formal correctness of concurrent systems, which is intended to improve the safety in the usage of shared resource ...
* Szymański's algorithm
* Semaphores
Footnotes
External links
*https://elixir.bootlin.com/linux/latest/source/arch/arm/mach-tegra/sleep.S Peterson's algorithm implementation
{{DEFAULTSORT:Peterson's Algorithm
Concurrency control algorithms
Articles with example C code