Scalable spin locks for multiprogrammed systems

Synchronization primitives for large shared-memory multiprocessors need to minimize latency and contention. Software queue-based locks address these goals, but suffer if a process near the end of the queue waits for a preempted processes ahead of it. To solve this problem, the authors present two queue-based locks that recover from in-queue preemption. The simpler, faster lock employs an extended kernel interface that shares information in both directions across the user-kernel boundary. Results from experiments with real and synthetic applications on SGI and KSR multiprocessors demonstrate that high-performance software spin locks are compatible with multiprogramming on both large-scale and bus-based machines