Xref: utzoo comp.lang.c:10499 comp.arch:5037
Path: utzoo!attcan!uunet!mcvax!ukc!cam-cl!scc
From: scc@cl.cam.ac.uk (Stephen Crawley)
Newsgroups: comp.lang.c,comp.arch
Subject: Re: volatile (in comp.lang.c)
Message-ID: <206@gannet.cl.cam.ac.uk>
Date: 30 May 88 15:57:27 GMT
References: <20345@pyramid.pyramid.com> <833@mcdsun.UUCP> <1988May23.003847.1114@utzoo.uucp> <21821@amdcad.AMD.COM>
Sender: news@cl.cam.ac.uk
Reply-To: scc@cl.cam.ac.uk (Stephen Crawley)
Organization: U of Cambridge Comp Lab, UK
Lines: 50
Posted: Mon May 30 16:57:27 1988

In article <21821@amdcad.AMD.COM> rpw3@amdcad.UUCP (Rob Warnock) writes:
>There is a perfectly respectable mutual exclusion technique which can be
>used on multi-processor machines, which requires no special hardware, and
>requires only that writes of a small integer are atomic. (The "small integer"
>has to be able to hold a processor number.) In the two-processor case, this
>is called "Dekker's Algorithm".  (For large numbers of processors, it is
>called "expensive"!  ;-}  ;-}  )
>
>Rob Warnock
>Systems Architecture Consultant

A more recent solution to the mutual exclusion is NOT expensive for multiple
processors:

  "A Fast Mutual Exclusion Algortithm"
  Leslie Lamport, Nov 14 1985.
  Report #5, DEC Systems Research Centre

The review at the beginning of the report (by Butler Lampson) says it 
better than I can:

"   To build a useful computer system from a collection of processors that
communicate by sharing memory, but lack any atomic operation more complex
than a memory read or write, it is necessary to implement mutual exclusion
by using only these operations.  Solutions to this problem have been known
for twenty years, but they are linear in the number of processors.  Lamport
presents a new algorithm which takes constant time (five writes and two
reads) in the absence of contention, which is the normal case.  To achieve
this performance it sacrifices fairness [*], which is probably unimportant in
practical applications.
    The paper gives an informal argument that the algorithm's performance
in the absence of contention is optimal [!!], and a fairly formal proof
of safety and freedom from deadlock, using a slightly modified Owicki-Gries 
method.  The proofs are extremely clear, and use very little notation."

[All typo's in the above are mine!]

[* The body of the report notes that there is a variation of the algorithm
   that is starvation free, at the cost of one extra memory reference in
   the absence of contention.]

In case you want to rush out and buy a copy, the address for DEC SRC is
given as 

    Digital Systems Research Center
    130 Lytton Avenue
    Palo Alto, California 94301


-- Steve