Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxn!ihnp4!houxm!whuxl!whuxlm!akgua!gatech!seismo!munnari!mulga!jas
From: jas@mulga.UUCP
Newsgroups: net.sources.d
Subject: Re: P & V Algorithms needed
Message-ID: <1119@mulga.OZ>
Date: Sun, 16-Mar-86 01:13:13 EST
Article-I.D.: mulga.1119
Posted: Sun Mar 16 01:13:13 1986
Date-Received: Tue, 18-Mar-86 01:15:30 EST
References: <2000005@ndm20> <300@imagen.UUCP> <1828@brl-smoke.ARPA> <1070@munnari.OZ>
Reply-To: jas@mulga.OZ (John Shepherd)
Organization: Computer Science, University of Melbourne
Lines: 36

In article <1070@munnari.OZ> kre@munnari.OZ (Robert Elz) writes:
>...
>The important properties are the ability to detect that a collision
>has occurrred, and the ability to go back and start again.
>...
>	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 algorithm looks like a simplified version of the Dekker's
algorithm that they always give in undergraduate concurrent
programming courses.
In that context it is considered to have two problems which arise
because you aren't allowed to assume anything about the relative
speeds of the processes:
(1) deadlock, maybe your scheme fixes this most of the time
	(I say "maybe" because while it's very unlikely that deadlock
	will occur, it is still possible in some degenerate cicumstances)
(2) starvation, one process never gets a go, because the other one always
	manages to do its tests first; once again, in reality, while this
	is possible, it is *highly* unlikely.

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

Just use generalised Dekker's algorithm, or one of the improved versions
published recently.

jas