# Help understanding Petersons Algorithm for N Processes

https://en.m.wikipedia.org/wiki/Peterson%27s_algorithm

What I don't understand is how the algorithm is guaranteed to work when the processor or processors are switching between threads. What stops simultaneous advancement?

The rough intuition is that at least one contending process becomes stuck at each step of the stairway to heaven (AKA the critical section) when there are enough contenders present. Consequently there's at most one of them left at the top rung of the ladder.

Having said that, I do remember many students struggling with grasping the finer details. It is a subtle algorithm. What could help is to model and simulate it, say, in Promela, where you could also check exhaustively whether certain properties (expressed as runtime assertions or LTL formulas) hold for the model. See below for such a model. The spin homepage should get you started with that tool.

The properties of $$n$$-process Peterson's mutual exclusion algorithm as it is presented e.g. in M. Ben-Ari's textbook Principles of Concurrent and Distributed Programming (Second edition) depend on a few assumptions about the execution model. These relate to (a) what actions are atomic and (b) what progress is expected of enabled actions. Textbook assumptions aren't necessarily guaranteed in real-life implementations. The wikipedia page you mention has some warnings about that.

Here's an old Promela model I once made for Ben-Ari's version of the algorithm.

/* Peterson's solution to the mutual exclusion problem - 1981 */
/* Modeling insprired by Ben-Ari */
#define N 3
#define i _pid+1

inline critical_section() {
printf("%d in CS\n", _pid);
}
inline non_critical_section() {
printf("%d in non-CS\n", _pid);
do                            /* non-deterministically choose how
long to stay, even forever */
:: true ->
skip
:: true ->
break
od
}

byte en[N] = 0, last[N] = 0;

active[N] proctype p()
{
byte j,k;
do
:: non_critical_section();
for (j : 1 .. N) {
en[i-1] = j;
wap:     last[j-1] = i;
for (k : 1 .. N) {
if
:: k == i
:: k != i ->
(en[k-1] < j || last[j-1] != i)
fi
}
};
csp:   critical_section();
en[i-1] = 0;
od
}

ltl mutex { !<>(p[0]@csp && p[1]@csp) }
ltl dlf2   { [](p[0]@wap && p[1]@wap -> <>(p[0]@csp || p[1]@csp)) }
ltl dlf3   { [](p[0]@wap && p[1]@wap && p[2]@wap -> <>(p[0]@csp || p[1]@csp || p[2]@csp)) }
/* ltl dlf4   { [](p[0]@wap && p[1]@wap && p[2]@wap && p[3]@wap -> <>(p[0]@csp || p[1]@csp || p[2]@csp || p[3]@csp)) } */
ltl aud   { [](p[0]@wap && ([]!(p[1]@wap || p[2]@wap /*|| p[3]@wap */)) -> <>p[0]@csp) }
ltl ee1    { [](p[0]@wap -> <>p[0]@csp) }
ltl ee3    { [](p[2]@wap -> <>p[2]@csp) }


What I have not checked is whether the wikipedia page and Ben-Ari agree on what constitutes an $$n$$-process version of Peterson's mutual exclusion algorithm for 2 processes.

• The last-to-enter property is a bit confusing as you can enter the level and context switch prior to the "last to enter" register for that level being updated. It looks like the only effect would be the currently paused processes waiting longer. Commented Dec 31, 2023 at 21:23