[gclist] Re: MP synchonization without atomic instructions

[Hans Boehm]

Apologies for pushing my own stuff, but you might also want to look at

Boehm, Demers, and Uhler, "Implementing multiple locks using Lamport's mutual
exclusion algorithm"

ACM Letters on Programming Languages and Systems, Vol.2, No. 1-4 (March-Dec.
1993), pp. 46-58.  (This is the last ever issue of LOPLAS.)

The abstract can be found at
http://www.acm.org/pubs/toc/Abstracts/1057-4514/176479.html

This does not present a fundamentally new synchronization algorithm.  It does
make the observation that you can implement N locks for M processes in N+M
instead of N*M space.  I think this is essential for any practical system,
though there may be a few high-contention locks that require different
treatment, as pointed out by the Yang and Anderson paper, among others.
(Does anyone know how Lamport modified with some sort of exponential backoff
compares to algorithms like Yang and Anderson?  Are hierarchical locks really
necessary if I don't care about worst case bounds?)

It also seems to me that the optimal synchronization scheme is highly
dependent on the target.  In particular, if the number of threads may exceeed
the number of processors, you have to be very careful that attempts at fairness
don't force many additional context switches, among other issues.

Hans

-- 
Hans-Juergen Boehm
boehm@mti.sgi.com