In this article we present Mutable Locks, a synchronization construct with the same execution semantic of traditional locks (such as spin locks or sleep locks), but with a self-tuned optimized trade off between responsiveness---in the access to a just released critical section---and CPU-time usage during threads' wait phases. It tackles the need for modern synchronization supports, in the era of multi-core machines, whose runtime behavior should be optimized along multiple dimensions (performance vs resource consumption) with no intervention by the application programmer. Our proposal is intended for exploitation in generic concurrent applications where scarce or none knowledge is available about the underlying software hardware stack and the actual workload, an adverse scenario for static choices between spinning and sleeping faced by mutable locks just thanks to their hybrid waiting phases and self-tuning capabilities.
@cite_0: Busy-wait techniques are heavily used for mutual exclusion andbarrier synchronization in shared-memory parallel programs.Unfortunately, typical implementations of busy-waiting tend to producelarge amounts of memory and interconnect contention, introducingperformance bottlenecks that become markedly more pronounced asapplications scale. We argue that this problem is not fundamental, andthat one can in fact construct busy-wait synchronization algorithms thatinduce no memory or interconnect contention. The key to these algorithmsis for every processor to spin on separate locally-accessible flag variables,and for some other processor to terminate the spin with a single remotewrite operation at an appropriate time. Flag variables may be locally-accessible as a result of coherent caching, or by virtue ofallocation in the local portion of physically distributed sharedmemory. We present a new scalable algorithm for spin locks that generates 0(1) remote references per lockacquisition, independent of the number of processors attempting toacquire the lock. Our algorithm provides reasonable latency in theabsence of contention, requires only a constant amount of space perlock, and requires no hardware support other than a swap-with-memoryinstruction. We also present a new scalable barrier algorithm thatgenerates 0(1) remote references perprocessor reaching the barrier, and observe that two previously-knownbarriers can likewise be cast in a form that spins only onlocally-accessible flag variables. None of these barrier algorithmsrequires hardware support beyond the usual atomicity of memory reads andwrites. We compare the performance of our scalable algorithms with othersoftware approaches to busy-wait synchronization on both a SequentSymmetry and a BBN Butterfly. Our principal conclusion is that contention due to synchronization need not be a problemin large-scale shared-memory multiprocessors. Theexistence of scalable algorithms greatly weakens the case for costlyspecial-purpose hardware support for synchronization, and provides acase against so-called “dance hall” architectures, in whichshared memory locations are equally far from all processors. — From the Authors' Abstract
Spin locks might lead to starvation since there is no assurance that a given thread wins the challenge eventually. The authors of @cite_0 introduce the queued spin lock to resolve this issue. It is a linked list where the first connected node is owned by the thread holding the lock, while others are inserted in a FIFO order by threads trying to access the critical section. Such threads spin on a boolean variable encapsulated in their individual nodes. This guarantees that each spinning thread repeatedly reads a memory cell different from other threads and a releasing thread updates a cacheline owned by a unique CPU-core, which significantly reduce the pressure on the cache management firmware.