Misplaced Pages

Eisenberg & McGuire algorithm

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Solution to the critical section problem
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages)
This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.
Find sources: "Eisenberg & McGuire algorithm" – news · newspapers · books · scholar · JSTOR (December 2010) (Learn how and when to remove this message)
The topic of this article may not meet Misplaced Pages's general notability guideline. Please help to demonstrate the notability of the topic by citing reliable secondary sources that are independent of the topic and provide significant coverage of it beyond a mere trivial mention. If notability cannot be shown, the article is likely to be merged, redirected, or deleted.
Find sources: "Eisenberg & McGuire algorithm" – news · newspapers · books · scholar · JSTOR (October 2017) (Learn how and when to remove this message)
(Learn how and when to remove this message)

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: 

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

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.
Initially the flags variable for each process is initialized to IDLE. 

    repeat {
		/* announce that we need the resource */
		flags := 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 != IDLE) index := turn;
			else index := (index+1) mod n;
		}
		/* now tentatively claim the resource */
		flags := ACTIVE;
		/* find the first active process besides ourselves, if any */
		index := 0;
		while ((index < n) && ((index = i) || (flags != 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 = 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 = IDLE) {
		index := (index+1) mod n;
	}
	/* give the turn to someone that needs it, or keep it */
	turn := index;
	/* we're finished now */
	flags := IDLE;
    /* REMAINDER Section */

See also

References

External links

Category: