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!allegra!mit-eddie!genrad!decvax!decwrl!pyramid!hplabs!sdcrdcf!trwrb!desint!geoff
From: geoff@desint.UUCP (Geoff Kuenning)
Newsgroups: net.sources.d
Subject: Re: P & V Algorithms needed
Message-ID: <182@desint.UUCP>
Date: Mon, 17-Mar-86 23:21:44 EST
Article-I.D.: desint.182
Posted: Mon Mar 17 23:21:44 1986
Date-Received: Fri, 21-Mar-86 04:24:14 EST
References: <1828@brl-smoke.ARPA> <1070@munnari.OZ>
Reply-To: geoff@desint.UUCP (Geoff Kuenning)
Organization: SAH Consulting, Manhattan Beach, CA
Lines: 40

In article <1070@munnari.OZ> kre@munnari.OZ (Robert Elz) writes:

> What about CSMA/CD - an ethernet is a shared resource, with
> no interlocked test & set, yet it seems that its occasionally
> possible to get exclusive access to the thing...

Ethernet uses special hardware that can detect another signal during
transmission.  In effect, the exclusive access is detected after the
fact:  you get a different return code from the hardware if a
transmission was garbled by a collision, and must retry later to
get your exclusive access.  A random-timeout scheme increases the
probability that the net will be free at that later time.  The CPU
equivalent would be an instruction that interrupted if somebody else
tried to write simultaneously;  this is equivalent to a "test and set".

> 	look see if the other processor has the resource locked,
> 	if so, wait
> 
> 	set my lock bit
> 
> 	look see if the other processor has the resource locked,
> 	if so, reset my lock bit, and go back to the start
> 
> 	I own it.

This is basically Dijkstra's algorithm (see my earlier posting);  it has
been proven to be correct (if B checks A's bit before it has been set, B's
lock bit must have already been set and thus A is guaranteed to see it in
the test after A sets its lock bit).  The algorithm's only flaw is that
it can starve a processor in theory (though in practice it's rarely a
problem).  A bigger problem in multiprocessors driven off the same clock
is that it is possible for the algorithm to get into lock step and stick
both processors in the wait-for-the-other loop.  Anything that differs
between processors (interrupts, clock, DMA I/O) has the potential for
breaking this loop;  another way is to have each processor count it's
processor number down to zero before returning to the main loop.
-- 

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