Reciprocating Locks

Abstract

We present Reciprocating Locks, a novel mutual exclusion locking algorithm, targeting cache-coherent shared memory (CC), that enjoys a number of desirable properties. The doorway arrival phase and the Release operation both run in constant-time. Waiting threads use local spinning and only a single waiting element is required per thread, regardless of the number of locks a thread might hold at a given time. While our lock does not provide strict FIFO admission, it bounds bypass and has strong anti-starvation properties. The lock is compact, space efficient, and has been intentionally designed to be readily usable in real-world general purpose computing environments such as pthreads, or C++. We show the lock exhibits high throughput under contention and low latency in the uncontended case. Under sustained contention, Reciprocating Locks generate less coherence traffic than MCS and CLH. The performance of Reciprocating Locks is competitive with and often better than the best state-of-the-art scalable queue-based spin locks.