Summary

This is the first known correct software solution to the critical section problem for n-processes with a lower bound of n-1 turns presented by Eisenberg and McGuire.

Algorithm

All the n-processes share the following variables:

enum pstate = {IDLE, WAITING, ACTIVE};
pstate flags[n];
int turn;


The variable turn, is set arbitrarily to a number between 0 and n-1 at the start of the algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

.

The flags variable, for each process is set to WAITING whenever it intends to enter the critical section

Critical section

In concurrent programming a critical section is a piece of code that accesses a shared resource that must not be concurrently accessed by more than one thread of execution. A critical section will usually terminate in fixed time, and a thread, task or process will have to wait a fixed time to...

. flags takes either IDLE or WAITING or ACTIVE.


Initially the flags variable for each process is initialized to IDLE.



repeat {

/* announce that we need the resource */
flags[i] := WAITING;

/* scan processes from the one with the turn up to ourselves. */
/* repeat if necessary until the scan finds all processes idle */
index := turn;
while (index != i) {
if (flags[index] != IDLE) index := turn;
else index := (index+1) mod n;
}

/* now tentatively claim the resource */
flags[i] := ACTIVE;

/* find the first active process besides ourselves, if any */
index := 0;
while ((index < n) && ((index = i) || (flags[index] != ACTIVE))) {
index := index+1;
}

/* if there were no other active processes, AND if we have the turn
or else whoever has it is idle, then proceed. Otherwise, repeat
the whole sequence. */
} until ((index >= n) && ((turn = i) || (flags[turn] = IDLE)));
/* Start of CRITICAL SECTION */

/* claim the turn and proceed */
turn := i;

/* Critical Section Code of the Process */

/* End of CRITICAL SECTION */
/* find a process which is not IDLE */
/* (if there are no others, we will find ourselves) */
index := turn+1 mod n;
while (flags[index] = IDLE) {
index := (index+1) mod n;
}

/* give the turn to someone that needs it, or keep it */
turn := index;

/* we're finished now */
flags[i] := IDLE;

/* REMAINDER Section */