Editing Peterson's algorithm

{{Short description|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.<ref name="original">G. L. Peterson: "Myths About the Mutual Exclusion Problem", ''Information Processing Letters'' 12(3) 1981, 115–116</ref> While Peterson's original formulation worked with only two processes, the algorithm can be generalized for more than two.<ref>As discussed in ''Operating Systems Review'', January 1990 ("Proof of a Mutual Exclusion Algorithm", M Hofri).</ref>

== The algorithm ==
The algorithm uses two variables: <code>flag</code> and <code>turn</code>. A <code>flag[n]</code> value of <code>true</code> indicates that the process <code>n</code> wants to enter the [[critical 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 setting <code>turn</code> to <code>0</code>.
[[File:Peterson's Algorithm.svg|thumb|Peterson's algorithm]]

{|
|colspan="2"| <syntaxhighlight lang=cpp>
volatile bool flag[2] = {false, false};
volatile int turn;
</syntaxhighlight>
|-
| <syntaxhighlight lang=cpp>
P0:      flag[0] = true;
P0_gate: turn = 1;
         while (flag[1] && turn == 1)
         {
             // busy wait
         }
         // critical section
         ...
         // end of critical section
         flag[0] = false;
</syntaxhighlight>
| <syntaxhighlight lang=cpp>
P1:      flag[1] = true;
P1_gate: turn = 0;
         while (flag[0] && turn == 0)
         {
             // busy wait
         }
         // critical section
         ...
         // end of critical section
         flag[1] = false;
</syntaxhighlight>
|}

The algorithm satisfies the three essential criteria to solve the critical-section problem. The while condition works even with preemption.<ref name="original" />

The three criteria are [[mutual exclusion]], progress, and bounded waiting.<ref name="Silberschatz.p194">Silberschatz. Operating Systems Concepts: Seventh Edition. John Wiley and Sons, 2005, Page 194.</ref>

Since <code>turn</code> 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.<ref name="raynal">{{cite book |title=Concurrent Programming: Algorithms, Principles, and Foundations |first=Michel |last=Raynal |authorlink=Michel Raynal |publisher=Springer Science & Business Media |year=2012 |isbn=978-3642320279}}</ref>{{rp|22}}

=== Mutual exclusion ===
{{Main|Mutual exclusion}}
P0 and P1 can never be in the critical section at the same time. If P0 is in its critical section, then <code>flag[0]</code> is true. In addition, either <code>flag[1]</code> is <code>false</code> (meaning that P1 has left its critical section), or <code>turn</code> is <code>0</code> (meaning that P1 is just now trying to enter the critical section, but graciously waiting), or P1 is at label <code>P1_gate</code> (trying to enter its critical section, after setting <code>flag[1]</code> to <code>true</code> but before setting <code>turn</code> to <code>0</code> and busy waiting). So if both processes are in their critical sections, then we conclude that the state must satisfy <code>flag[0]</code> and <code>flag[1]</code> and <code>turn = 0</code> and <code>turn = 1</code>. No state can satisfy both <code>turn = 0</code> and <code>turn = 1</code>, 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.<ref name="Schneider.p185">F. B. Schneider, ''On Concurrent Programming'', Springer Verlag, 1997, pages 185–196.</ref>)

=== 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.<ref name="Silberschatz.p194"/> 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.{{r|Silberschatz.p194}}{{r|raynal}}{{rp|11}} In Peterson's algorithm, a process will never wait longer than one turn for entrance to the critical section.

=== {{anchor|Filter algorithm}}Filter algorithm: Peterson's algorithm for more than two processes ===
[[File:Snapshot of filter algorithm (Peterson's algorithm for more than 2 processes) in progress.png|thumb|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).]]
The filter algorithm generalizes Peterson's algorithm to {{math|''N'' > 2}} processes.<ref name="art">{{cite book |title=The Art of Multiprocessor Programming |first1=Maurice |last1=Herlihy |authorlink1=Maurice Herlihy |first2=Nir |last2=Shavit |authorlink2=Nir Shavit |publisher=Elsevier |year=2012 |pages=28–31 |isbn=9780123977953}}</ref> Instead of a boolean flag, it requires an integer variable per process, stored in a single-writer/multiple-reader (SWMR) atomic [[Register machine|register]], and {{math|''N''&nbsp;−&nbsp;1}} additional variables in similar registers. The registers can be represented in [[pseudocode]] as [[Array data type|array]]s:

 level : array of N integers
 last_to_enter : array of N − 1 integers

The {{mono|level}} variables take on values up to {{math|''N''&nbsp;−&nbsp;1}}, each representing a distinct "waiting room" before the critical section.{{r|art}} Processes advance from one room to the next, finishing in room {{math|''N''&nbsp;−&nbsp;1}}, which is the critical section. Specifically, to acquire a lock, process {{mvar|i}} executes{{r|raynal}}{{rp|22}}

 i ← ProcessNo
 '''for''' ℓ '''from''' 0 '''to''' N − 1 '''exclusive'''
     level[i] ← ℓ
     last_to_enter[ℓ] ← i
     '''while''' last_to_enter[ℓ] = i '''and''' there exists k ≠ i, such that level[k] ≥ ℓ
         '''wait'''

To release the lock upon exiting the critical section, process {{mvar|i}} sets {{mono|level[i]}} to −1.

That this algorithm achieves mutual exclusion can be proven as follows. Process {{mvar|i}} exits the inner loop when there is either no process with a higher level than {{mono|level[i]}}, so the next waiting room is free; or, when {{mono|i ≠ last_to_enter[ℓ]}}, so another process joined its waiting room. At level zero, then, even if all {{mvar|N}} processes were to enter waiting room zero at the same time, no more than {{math|''N''&nbsp;−&nbsp;1}} will proceed to the next room, the final one finding itself the last to enter the room. Similarly, at the next level, {{math|''N''&nbsp;−&nbsp;2}} will proceed, [[Mathematical induction|etc.]], until at the final level, only one process is allowed to leave the waiting room and enter the critical section, giving mutual exclusion.{{r|raynal}}{{rp|22–24}}

Unlike the two-process Peterson algorithm, the filter algorithm does not guarantee bounded waiting.{{r|raynal}}{{rp|25–26}}

==Note==
When working at the [[Computer hardware|hardware]] level, Peterson's algorithm is typically not needed to achieve atomic access. Most modern processors have special instructions, which, by locking the [[memory bus]], can be used to guarantee [[Atomicity (programming)|atomicity]] and provide [[mutual exclusion]] in [[Symmetric multiprocessing|SMP]] systems. Examples include [[test-and-set]] (<code>XCHG</code>) and [[compare-and-swap]] (<code>CMPXCHG</code>) on [[x86]] processors and [[load-link/store-conditional]] on [[DEC Alpha|Alpha]], [[MIPS architecture|MIPS]], [[PowerPC]], and other architectures. These instructions are intended to provide a way to build [[Synchronization (computer science)|synchronization]] primitives more efficiently than can be done with pure shared memory approaches.

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]]).{{Citation needed|date=May 2015}}

== See also ==
* [[Dekker's algorithm]]
* [[Eisenberg & McGuire algorithm]]
* [[Lamport's bakery algorithm]]
* [[Szymański's algorithm]]
* [[Semaphore (programming)|Semaphores]]

==Footnotes==
{{reflist}}

==External links==
*https://elixir.bootlin.com/linux/v5.6.19/source/arch/arm/mach-tegra/sleep-tegra20.S#L120 Example of Peterson's algorithm formerly being used in the linux kernel ([https://github.com/torvalds/linux/commit/d90bdb72bb42 removed] in v5.7).

{{DEFAULTSORT:Peterson's Algorithm}}
[[Category:Concurrency control algorithms]]
[[Category:Articles with example C code]]