Reciprocating Locks

We present Reciprocating Locks, a novel mutual exclusion locking algorithm, targeting cache-coherent shared memory, that enjoys a number of desireable properties. The doorway arrival phase and the Release operation both run in constant-time. Waitings thread 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 still 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 the linux kernel, pthreads, or C++. We show the lock exhibits high throughput under contention and low contention in the uncontended case. The performance of Reciprocating Locks is competitive with and often better than the best state-of-the-art scalable spin locks.