Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/12/84; site desint.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!ittatc!dcdwest!sdcsvax!sdcrdcf!trwrb!desint!geoff
From: geoff@desint.UUCP (Geoff Kuenning)
Newsgroups: net.sources.d
Subject: Re: P & V Algorithms needed
Message-ID: <180@desint.UUCP>
Date: Mon, 17-Mar-86 01:45:10 EST
Article-I.D.: desint.180
Posted: Mon Mar 17 01:45:10 1986
Date-Received: Tue, 18-Mar-86 08:38:26 EST
References: <2000005@ndm20> <300@imagen.UUCP> <1828@brl-smoke.ARPA>
Reply-To: geoff@desint.UUCP (Geoff Kuenning)
Organization: SAH Consulting, Manhattan Beach, CA
Lines: 68

In article <1828@brl-smoke.ARPA> gwyn@brl.ARPA writes:

> I have never heard of a mutual exclusion scheme that did not
> at root depend on the existence of an interlocked test-and-set
> operation of some kind.  I would be interested in hearing some
> details about other schemes if they exist.

Dijkstra invented one way back in 1965 [1] that depends only on atomic
loads and stores.  It has been extended by Knuth and later others [2]
to prevent starvation.

[1] Dijkstra, E.W.  Solution of a problem in concurrent programming
control.  Comm. ACM 8, 9 (Sept. 1965), 569.
[2] Eisenberg, M.A. and McGuire, M.R.  Further comments on Dijkstra's
concurrent programming control problem.

The following algorithm is presented in [2];  it guarantees that each
requesting processor will receive the resource within N turns. (NOTES:  I
translated this from GOTO loops in Algol;  I have not tested it and it
is not certified.  The code as written assumes multiprocessors and uses
spin loops for busy waiting.)

	#define N	4	/* Number of processors */

	static char control[N];	/* Control array, starts all zero */
	static int whohasit = 0; /* Current owner of the resource */

	/* Acquire exclusive access to the resource for the i'th processor */
	void acquire_resource (i)
	    int i;		/* Processor number */
	    {
	    int j;		/* Loop index */

	    while (1)
		{
		control[i] = 1;	/* Request access to the resource */
		for (j = whohasit;  (j + 1) % N != whohasit;  j++)
		    {
		    if (j == i)	/* Have we reached ourselves? */
			break;
		    else if (control[j] != 0)
			j = whohasit; /* Somebody of higher priority */
				/* ..wants it, restart the search loop */
		    }
		control[i] = 2;	/* We think we have the resource now */
		for (j = 0;  j < N;  j++)
		    {
		    if (j != i  &&  control[j] == 2)
			break;	/* Somebody else thinks THEY have it */
		    }
		if (j != N)
		    continue;	/* Somebody else thinks they have it, retry */
		if (control[whohasit] != 0  &&  whohasit != i)
		    continue;	/* Somebody else really does have it */
		whohasit = i;	/* Now we really DO have it */
		return;
		}
	    }

	/* Release exclusive access to the resource */
	void release_resource (i)
	    {
	    control[i] = 0;
	    }
-- 

	Geoff Kuenning
	{hplabs,ihnp4}!trwrb!desint!geoff