P & V Algorithms needed
UNIX 4.2 BSD
root at icst-cmr
Tue Mar 18 11:44:24 AEST 1986
/*
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>
*/
More information about the Comp.sources.unix
mailing list