A FAST, SCALABLE MUTUAL EXCLUSION ALGORITHM

This paper is concerned with synchornization under read/write atomicit y in shared memory multi-processors. We present a new algorithm for N- process mutual exclusion that requires only read and write operations and that has O(logN) time complexity, where ''time'' is measured by co unting remote memory references. The time complexity of this algorithm is better than that of all prior solutions to the mutual exclusion pr oblem that are based upon atomic read and write instructions; in fact, the time complexity of most prior solutions is unbounded. Performance studies are presented that show that our mutual exclusion algorithm e xhibits scalable performance under heavy contention. In fact, its perf ormance rivals that of the fastest queue-based spin locks based on str ong primitives such as compare-and-swap and fetch-and-add. We also pre sent a modified version of our algorithm that generates only O(1) memo ry references in the absence of contention.