Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!think!harvard!seismo!mcvax!ukc!kcl-cs!glasgow!taylor
From: taylor@glasgow.glasgow.UUCP (Jem Taylor)
Newsgroups: net.sources.d
Subject: Re: P & V Algorithms needed
Message-ID: <451@glasgow.glasgow.UUCP>
Date: Mon, 17-Mar-86 17:24:55 EST
Article-I.D.: glasgow.451
Posted: Mon Mar 17 17:24:55 1986
Date-Received: Fri, 21-Mar-86 05:30:44 EST
References: <2000005@ndm20> <300@imagen.UUCP> <1828@brl-smoke.ARPA>
Reply-To: taylor@glasgow.UUCP (Jem Taylor)
Organization: Comp Sci Dept, Glasgow Univ, Scotland
Lines: 38

In article <1828@brl-smoke.ARPA> gwyn@brl.ARPA writes:
>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 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).

Alternatively :
	Start with all flags clear.
	A sets its flag and *then* examines the other flags, finds
		them clear and enters.
	B concurrently sets it's flag and then examines the others,
		finds A set, and does not enter ...

What can B now do ? Busy wait on the other flags ... but if C also joins
in, there will be an exclusive deadlock even when A leaves the section 
and clears it's flag, since flags for B and C will still be set.

Taking a tip from Ethernet, B (and C etc) could pause for some random 
interval (after first clearing it's flag) and try again from the beginning. 
As long as B's and C's delays are not (systematically) the same, one of 
them will enter the section eventually.

Such a scheme has the provisos of good performance only under light
to moderate load, and of unfairness, that Ethernet is known for - but 
(I'm told) Ethernet works.

-Jem Taylor

				"Aerodynamically speaking, bees can't fly"