Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!think!harvard!seismo!umcp-cs!chris
From: chris@umcp-cs.UUCP (Chris Torek)
Newsgroups: net.sources.d
Subject: Re: P & V Algorithms needed
Message-ID: <287@umcp-cs.UUCP>
Date: Sat, 15-Mar-86 03:08:02 EST
Article-I.D.: umcp-cs.287
Posted: Sat Mar 15 03:08:02 1986
Date-Received: Sun, 16-Mar-86 09:46:41 EST
References: <2000005@ndm20> <300@imagen.UUCP> <1828@brl-smoke.ARPA>
Organization: U of Maryland, Computer Science Dept., College Park, MD
Lines: 35

In article <1828@brl-smoke.ARPA> gwyn@brl-smoke.UUCP 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.

Here is one that, while probably completely useless in practice,
does not require a test-and-set scheme:

Assign a shared address as the `owner' address.  It contains the
index number of the CPU owning the resource being locked.  If a
CPU owns it but does not want it, it increments it, modulo the
number of CPUs.  If a CPU does not own the resource, it continuously
reads the location until its index appears.  Unfortunately, this
requires that each CPU busy wait for the resource, and that each
check the owner address very often so as to keep the resource
owner moving.

If you are willing to dedicate a CPU as a `lock server', the
algorithm can be changed to this:  In addition to the current owner,
there is a request address; and there is a distinguished `idle'
index.  If a CPU does not own the resource, but wants it, it puts
its own index into the request address (continuously, alternating
with reading the owner address until its index shows up).  When a
CPU that owns the resource is done with it, it writes the idle
index into the owner address.  The idle-index CPU's job is to hold
on to the resource until someone else wants it.  Again this requires
a busy wait, but processors that neither own nor want the resource
are not required to look at the owner address.  To cut down on
memory contention, one can make the idle-index CPU very slow, but
this increases latency.
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 1415)
UUCP:	seismo!umcp-cs!chris
CSNet:	chris@umcp-cs		ARPA:	chris@mimsy.umd.edu