Was reading up about Petri Nets and chanced on this cool piece of code: This wonderful algorithm is a software-only 2-process mutual exclusion algorithm. Though it is not the first software-only 2-process mutual exclusion algorithm (Dekker’s in 1965 was the first; Peterson’s was in 1981), it is the most compact one.
I’ve put comments in the code below to explain how it works.
Let’s examine the algorithm’s properties :
1. Safety : At any time, at most one process is allowed to be in the Critical Section. In brief, when 2 processes try to enter the critical section simultaneously, in the ensuing race condition to set turn = process (line 7), the process that “wins” is stuck in the while loop, letting the other interested process enter the Critical Section.
2. Fairness : Both processes should have an equal chance of acquiring the lock on the critical section, since the race condition is impartial. (However, the algorithm is not necessarily fair in the sense that both processes execute their Critical Section an equal number of times over long periods of time. That is an analysis that is more involved.)
3. Liveness : When one or more processes have expressed their intentions to enter the Critical Section, one of them eventually enters. (See explanation above).
4. Freedom from Starvation: In addition to these properties, the following is a desirable property: Any process that expresses its intention to enter the critical section will be able to do so in finite time. This is also true for Peterson’s algorithm. Once the process that has entered the critical section leaves, interested[other] becomes FALSE for the blocked process, allowing it to enter the critical section.
O======O======O======O======O======O
1 int turn;
2 int interested[2];
/*
The two processes have ids process = 0 and process = 1.
*/
3 void enter_region(int process) {
4 int other;
5 other = 1 – process;
6 interested[process] = TRUE;
7 turn = process;
/*
1. If interested[other] == FALSE, there is no competition from the other process
(say, due to it being slow), and we enter the critical section.
2. If interested[other] == TRUE, but turn is still == us, then the other process
must have executed line 6 but not yet line 7. In this case, we block in the while
loop. The other process process then sets turn to itself, then
basically turn == process will become false, and we enter the critical section.
(leave_region() ensures that the other process gets to enter the critical section later.
Thus, the algorithm is fair.)
(If the first process “loses” the race to line 7, and the 2nd one wins, the same reasoning
as above applies (, but w.r.t. the 2nd process,) since the code is symmetric.)
*/
8 while ( turn == process && interested[other] == TRUE ) ;
}
void leave_region(int process) {
interested[process] = FALSE;
/*
If the other process is blocked in enter_region(), this releases it
from the while loop on line 8, allowing it to acquire the lock.
*/
}
O======O======O======O======O======O
) The thing with UNIX is : you gotta know the history to know why things work(?) the way they do.
