Fast, scalable synchronization with minimal hardware support
Jae-Heon Yang, James H. Anderson · 1993
This paper concerns synchronization under read/write atomicity in shared memory multiprocessors.We present a new algorithm for N-process mutual exclusion that requires only read and write operations and that has 0(log2 IV) time complexity, where "time" is measured by counting remote memory references.The time complexity of this algorithm is better than that of all prior solutions to the mutual exclusion problem 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 exhibits scalable performance under heavy contention.In the second part of the paper, we discuss two extensions of our mutual exclusion algorithm.In the first extension, we modify the algorithm so that in the absence of contention only 0(1) memory references are required.In the second extension, the technique of software combining is introduced for the purpose of increasing concurrency when using the algorithm to implement combinable read-modifywrite operations.