Editing Peterson's algorithm (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}}