Abstract Synchronization Without Contention

Conventional wisdom holds that contention due to busy-wait synchronization is a major obstacle to scalability and accept-able performance in large shared-memory multiprocessors. We argue the contrary, and present fast, simple algorithms for contention-free mutual exclusion, reader-writer control, and barrier synchronization. These algorithms, based on widely available fetch-and- @ instructions, exploit local access to shared memory to avoid contention. We compare our algo-rithms to previous approaches in both qualitative and quan-titative terms, presenting their performance on the Sequent Symmetry and BBN Butterfly multiprocessors. Our results highlight the importance of local access to shared memory, provide a case against the construction of so-called "dance hall " machines, and suggest that special-purpose hardware support for synchronization is unlikely to be cost effective on machines with sequentially consistent memory.