P & V Algorithms needed

[UNIX 4.2 BSD]

/*
	From unix-sources-request at BRL.ARPA Fri Mar 14 19:27:55 1986
	From: Doug Gwyn  <gwyn at brl-smoke.arpa>
	Subject: Re: P & V Algorithms needed
	To: unix-sources at brl-smoke.arpa
	
	In article <300 at imagen.UUCP> geof at 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).

It's the other way around Doug. First you set your own flag, then look at
whether anyone else set their flags. `Shoot first & ask questions later.'
When either guy finds someone elses flag set, they back off & try later
(everyone equal), or possibly the lowest (or highest) guy spins waiting
for the other guys to accede (priority access).

		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.
	
You just did. In fact, I have heard it called `Dijkstra's algorithm.'
Unfortunately, it can become unwieldy with a high collision rate,
somewhat like ethernet.

	Your buddy,

			Root Boy Jim (Cottrell)		<rbj at cmr>
*/