Eisenberg & McGuire algorithm
 |
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
The variable turn is set arbitrarily to a number between 0 and n-1 at the start of the algorithm. The flag variable for each process is set to WAITING initially.[1]
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 (flag[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 */
flag[i] = IDLE;
/* REMAINDER Section */