Synchronization without contention

作者：John Mellor‐Crummey, Michael L. Scott · 年份：1991 · DOI：10.1145/106972.106999 · 被引用次数：141 · 研究领域：Distributed systems and fault tolerance、Parallel Computing and Optimization Techniques、Advanced Data Storage Technologies

Conventional wisdom holds that contention due to busy-wait synchronization is a major obstacle to scalability and acceptable 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 algorithms to previous approaches in both qualitative and quantitative 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.