Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site imagen.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!decwrl!sun!saber!imagen!geof
From: geof@imagen.UUCP (Geoffrey Cooper)
Newsgroups: net.sources.bugs,net.sources.d
Subject: Re: P & V Algorithms needed
Message-ID: <310@imagen.UUCP>
Date: Mon, 17-Mar-86 15:40:07 EST
Article-I.D.: imagen.310
Posted: Mon Mar 17 15:40:07 1986
Date-Received: Wed, 19-Mar-86 04:48:30 EST
References: <2000005@ndm20> <300@imagen.UUCP> <1828@brl-smoke.ARPA> <1070@munnari.OZ>
Organization: IMAGEN Corporation, Santa Clara, CA 95052-8101
Lines: 63
Xref: watmath net.sources.bugs:742 net.sources.d:39

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

You are correct, the scheme that you outlined doesn't work.  The hint is
that the correct scheme isn't fair.  Try this code:
    #define N <number of processors>
    #define TRUE 1
    #define FALSE 0

    shared boolean locks[N];

    lock(me)
        int me; /* my processor number */
    {
        int i;
    
        do {
            locks[me] = TRUE;
            for ( i = 0; i < me-1 && ! locks[i]; i++ );
            if ( i < me-1 ) locks[me] = FALSE;
        } while ( ! locks[me] );
    
        do {
            for ( i = me+1; i < N && ! locks[i]; i++ )
        } while ( i < N );
    }
    
    unlock(me)
        int me; /* my processor number */
    {
        locks[me] = FALSE;
    }

Gold star to Robert Elz.  I agree that there is a great similarity
with aloha contention (and csma/cd).  In these schemes, static priorities
are replaced by random backoff times.  This eliminates static priority
but gives only a probablistic (though high) chance of success.  The
probablistic schemes are also somewhat fairer under expected network
traffic than a static scheme would be.

Note that each processor writes to only one variable and reads from
all the others.  Thus test-and-set is not needed.  I developed this
algorithm one day in deciding whether read-modify-write cycles were
an absolute requirement for a bus architecture.  Interestingly, atomic
reads and writes are also unecessary, since no processor writes the
lock belonging to any other processor.  However, glitching of a value
from true to false and back is not allows.

I refer you to 3rd PODC Conference Proceedings, ACM 1984 (reprinted
in SIGOPS OS.review Oct. 85: "Solved Problems, Unsolved Problems, and
Nonproblems in Concurrency" by Leslie Lamport.  The 2-processor version
of the above is outlined as an oft-forgotten solved problem.  Actually,
there is a bug in the algorithm as presented in the paper, but it's
probably a typo.

As Chris Torek pointed out, a token contention scheme can also be used.
This is a "fairer" scheme, but does require active participation
on the part of all parties, even when they are not interested in the
state of the lock.

- Geof Cooper