View source for Eisenberg & McGuire algorithm

{{Short description|Solution to the critical section problem}}
{{multiple issues|
{{Refimprove|date=December 2010}}
{{notability|date=October 2017}}
}}
{{Use dmy dates|date=January 2021}}
{{TOC right}}
The '''Eisenberg & McGuire algorithm''' is an algorithm for solving the critical sections problem, a general version of the [[dining philosophers problem]]. It was described in 1972 by [[Murray A. Eisenberg]] and [[Michael R. McGuire]].

==Algorithm==

All the ''n''-processes share the following variables:
<syntaxhighlight lang="c">
enum pstate = {IDLE, WAITING, ACTIVE};
pstate flags[n];
int turn;
</syntaxhighlight>

The variable '''turn''' is set arbitrarily to a number between 0 and ''n''−1 at the start of the [[algorithm]].

The '''flags''' variable for each process is set to WAITING whenever it intends to enter the [[critical section]]. '''flags''' takes either IDLE or WAITING or ACTIVE.
<br />
Initially the '''flags''' variable for each process is initialized to IDLE.
<br />
<syntaxhighlight lang="ada" line="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 (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 */

</syntaxhighlight>

==See also ==
* [[Dekker's algorithm]]
* [[Peterson's algorithm]]
* [[Lamport's bakery algorithm]]
* [[Szymański's algorithm]]
* [[Semaphore (programming)|Semaphores]]

==References==
* http://portal.acm.org/citation.cfm?id=361895

==External links==
* https://web.archive.org/web/20120617015556/http://lcsee.wvu.edu/~jdmooney/classes/cs550/notes/tech/mutex/Eisenberg.html
* http://www.cs.csustan.edu/~john/Classes/Previous_Semesters/CS3750_OperatingSys_I/1999_04_Fall/Notes/nProcessSynch.html

{{DEFAULTSORT:Eisenberg and McGuire algorithm}}
[[Category:Concurrency control algorithms]]