  We formulate a modular approach to the design and analysis of a particular
class of mutual exclusion algorithms for shared memory multiprocessor systems.
Specifically, we consider algorithms that organize waiting processes into a
queue. Such algorithms can achieve O(1) remote memory reference (RMR)
complexity, which minimizes (asymptotically) the amount of traffic through the
processor-memory interconnect. We first describe a generic mutual exclusion
algorithm that relies on a linearizable implementation of a particular
queue-like data structure that we call MutexQueue. Next, we show two
implementations of MutexQueue using O(1) RMRs per operation based on
synchronization primitives commonly available in multiprocessors. These
implementations follow closely the queuing code embedded in previously
published mutual exclusion algorithms. We provide rigorous correctness proofs
and RMR complexity analyses of the algorithms we present.
