Fairlocks A High Performance Fair Locking Scheme.
S. Swaminathan, J. Stultz, Jürgen Vogel, Paul E. McKenney · 2002
Abstract 1 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. Keywords: locking synchronization performance, lock starvation 1. Introduction In order for parallel shared-memory multiprocessors to scale well, low lock contention levels must be maintained. However, existing code that experiences high lock contention must often be used as is until a redesigned version of the code becomes available. In addition, it may not be worthwhile to optimize code that executes infrequently (for example, handlers for rare error conditions). Primitives that increase data locality, while providing some fairness guarantees, can improve the performance of such code while simultaneously preventing unfairness and lock starvation. Moreover, the increase in instruction execution rate outstrips the reductions in global latencies among large-scale multiprocessors, as shown in Figure 1. The figure shows that memory accesses were less expensive than instructions in the early 80s; however, the Moore’s-law-driven increases in CPU core performance have outstripped those of memory, so that now literally hundreds of instructions can execute in the time required to complete a single memory access. This motivates the need for locking primitives that preserve memory locality or for some solution from the underlying processor architecture. Thus, some new architectures provide a solution to this problem by providing closely bound groups of CPUs, called “nodes,” with lower latencies within nodes than between nodes. Examples of such architectures include cache-coherent non-uniform memory-access (CC-NUMA)