Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors John M. Mellor-Crummey and Michael L. Scott present scalable algorithms for spin locks and barriers that avoid memory and interconnect contention. These algorithms use locally-accessible flag variables, allowing processors to spin on separate flags and terminate spins with a single remote write. Spin locks achieve O(1) remote references per acquisition, while barriers achieve O(1) remote references per processor. These algorithms require only fetch-and-Φ operations and no special hardware beyond atomic memory reads and writes. They are compared with other busy-wait approaches on Sequent Symmetry and BBN Butterfly, showing that contention is not a major issue in large-scale shared-memory multiprocessors. The algorithms eliminate the need for costly special-purpose hardware and challenge "dance hall" architectures. The paper discusses various spin lock and barrier implementations, including test-and-set, ticket, array-based, and MCS locks, as well as software combining trees and dissemination barriers. These algorithms ensure fairness, reduce contention, and provide efficient synchronization in shared-memory multiprocessors.Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors John M. Mellor-Crummey and Michael L. Scott present scalable algorithms for spin locks and barriers that avoid memory and interconnect contention. These algorithms use locally-accessible flag variables, allowing processors to spin on separate flags and terminate spins with a single remote write. Spin locks achieve O(1) remote references per acquisition, while barriers achieve O(1) remote references per processor. These algorithms require only fetch-and-Φ operations and no special hardware beyond atomic memory reads and writes. They are compared with other busy-wait approaches on Sequent Symmetry and BBN Butterfly, showing that contention is not a major issue in large-scale shared-memory multiprocessors. The algorithms eliminate the need for costly special-purpose hardware and challenge "dance hall" architectures. The paper discusses various spin lock and barrier implementations, including test-and-set, ticket, array-based, and MCS locks, as well as software combining trees and dissemination barriers. These algorithms ensure fairness, reduce contention, and provide efficient synchronization in shared-memory multiprocessors.