In article 7384@hubcap.clemson.edu, gottlieb@allan.ultra.nyu.edu (Allan Gottlieb) writes:
In article <1992Dec14.133731.18997@hubcap.clemson.edu> engler@cs.arizona.edu (Dawson R. Engler) writes:
>> I need the algorithm for an efficient software lock that does not use
>> atomic instructions (except perhaps assignment). Fairness is unnecessary:
>> in the situation I need this for, ~90% of the accesses are by the same
>> process, and if the accesses are by someone else, they are allowed to
>> have extra overhead.
>> ...
>
> I would suggest peterson's algorithm. For two processes it is simply
> Code for process 1 Code for process 2
> ------------------ ------------------
> P1Wants <- TRUE P2Wants <- TRUE
> Turn <- P2 Turn <- P1
> while P2Wants and Turn=P2 while P1Wants and Turn=P1
>
> critical section critical section
>
> P1Wants <- FALSE P2Wants <- FALSE
>
> (the while loops have empty bodies)
>
> For N processes (plus a proof and references) see Hofri's article in
> Operating Systems Review January 90.
>
> Allan Gottlieb
It might be of interest to note that the above algorithm (and many similar ones)
assume that memory operations are sequentially consistent (SC). There is a significant
performance advantage for systems that provide SC memory only when needed. These
weaker memory models generally require ordering or synchronization instructions
to appear SC.
For example, if Peterson's algorithm were used on a Sparc based multiprocessor,
without using an atomic instruction (swap, test-and-set or compare-and-swap), you
would still need ordering instructions. In the current version 8, this means adding a store-barrier instruction *and* a "swap" that is used as a load-barrier (it is not possible to implement this particular algorithm without "swap" or "ldstub" on V8
machines). Eventually, in the next version of the Sparc architecture, a generalized
ordering directive (membar) can be used to implement Peterson's Algorithm correctly
in all supported memory models (TSO, PSO and RMO).
[ The idealized Sparc assembly code below was verified with a tool that can prove
assertions for small pieces of code for all future Sparc based
multiprocessors. The critical section increments a shared variable [A] such
that lack of mutual exclusion would allow a sequence of events that results in
A != 2. Given that all possible execution paths are considered, A == 2 is a
usefull assertion that the critical section is properly guarded. ]
