Recoverable user-level mutual exclusion

Abstract

Mutual exclusion primitives based on user-level atomic instructions (often called spin locks) have proven to be much more efficient than operating-system semaphores in situations where the contention on the semaphore is low. However, many of these spin lock schemes do not permit registration of ownership to be carried aut atomically with acquisition, potentially leaving the ownership undetermined if a process dies (or makes very slow progress) at a critical point in the registration code. We present an algorithm which can ensure the successful registration of ownership of a spin lock, regardless of where processes fail. Thus, our spin lock implementation is 'recoverable'. The determination of a spin lock's ownership can potentially be used to restore resources protected by the spin lock to consistency and then release the spin lock. Other processes using the lock can then continue to function normally, improving fault resiliency for the application. Our algorithm provides very fast lock acquisition when the acquisition is uncontested (comparable in speed to a simple test-and-set based spin lock), and we prove it works even on the weak memory consistency models implemented by many modern multiprocessor computer systems.