Scalable Spin Locks for Multiprogrammed Systems

Synchronization primitives for large scale multiprocessors need to provide low latency and low contention to achieve good performance. Queue-based locks (implemented in software with fetch_and_\Phi instructions) can greatly reduce contention and improve overall performance by arranging for processors to spin only on local locations. Unfortunately, queued locks exhibit poor behavior in the presence of multiprogramming: a process near the end of the queue, in addition to waiting for any process that is preempted during its critical section, must also wait for any preempted processes ahead of it in the queue. To solve this problem, we present two queue-based locks that recover from in-queue preemption. The first lock employs the kernel interface of the NYU Symunix project. The second employs an extended interface that shares information in both directions across the user-kernel boundary, resulting in simpler code and better performance. Experiments with these locks in both real and synthetic applications on SGI and KSR multiprocessors confirm the feasibility of high-performance software locks on systems that are both very large and multiprogrammed