P & V Algorithms needed

[Geoffrey Cooper]

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

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