Fairlocks- A High Performance Fair Locking Scheme

Over the past several decades, much research has been done in the area of modeling, simulating, and measuring the performance of locking primitives under conditions of low and high contention and with attention to memory locality of the locking data structures. Most of the existing locking primitives are not fair with respect to lock grants and can cause lock starvation among CPUs during high contention. Locking primitives proposed to eliminate lock starvation employ complex schemes to achieve fairness, resulting in poor performance under low contention. In this paper, we propose a new locking scheme, called fairlocks, which, on many architectures, is as fast as test-and-set locks during low contention, and maintains both fairness and data locality for lock grants