P & V Algorithms needed

[Robert Elz]

In article <1828 at brl-smoke.ARPA>, gwyn at brl-smoke.ARPA (Doug Gwyn) 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.

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...

The important properties are the ability to detect that a collision
has occurrred, and the ability to go back and start again.

I have used this scheme in the more conventional case of
two processors with shared memory, and no test&set to
do interlocking, the algorithm goes like this ..

	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.

The "wait" can be a busy wait, or it can mean just try for the
resource sometime later, whichever is appropriate.  The "go back
to the start" step should have some random delay associated with it
to avoid continuous collisions (deadlock).

I'd be interested to know if anyone can discover any way that
this can be defeated (very interested, since this algorithm
is actually in use, right now, on some hardware I have here...).

I haven't actually thought this through for a case of N processors,
N > 2, but I can't immediately see any reason it wouldn't function,
after all, ethernets work with more than 2 processors...

Robert Elz		kre at munnari.oz		seismo!munnari!kre

ps: I am moving this discussion into net.sources.d where it belongs