Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!think!harvard!seismo!brl-adm!brl-smoke!gwyn
From: gwyn@brl-smoke.ARPA (Doug Gwyn )
Newsgroups: net.sources.d
Subject: Re: P & V Algorithms needed
Message-ID: <1828@brl-smoke.ARPA>
Date: Fri, 14-Mar-86 19:10:22 EST
Article-I.D.: brl-smok.1828
Posted: Fri Mar 14 19:10:22 1986
Date-Received: Sun, 16-Mar-86 09:26:40 EST
References: <2000005@ndm20> <300@imagen.UUCP>
Reply-To: gwyn@brl.ARPA
Organization: Ballistic Research Lab (BRL)
Lines: 30

In article <300@imagen.UUCP> geof@imagen.UUCP (Geoffrey Cooper) writes:
>Mutex locking among N processors can be implemented using N single bit
>variables.  The only restriction is that it be possible to write any
>one variable without affecting the others.  It is not necessary that
>reads and writes be atomic.
>
>The algorithm works by having one variable associated with each
>processor.  Each processor writes to its own variable and reads the
>variables of all others.  Fairness is assumed not to be at issue.

If I understand you correctly, this scheme does not work.  Consider:
	Start with all flags clear.
	Processor A wants to enter a critical region,
		so it starts to set the A-flag (after
		reading all the other processor flags
		and finding them all clear).
	Concurrently, processor B wants to enter the
		same critical region, so it starts to
		read the processor flags to see if
		some other processor is in the region.
		In particular, it tries to read the
		A-flag.
	Dependent on the outcome of a timing race, it
		is now possible for both processors
		to be executing in the critical region.

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.