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.
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.
@cite_0
2099661831
Serialization of threads due to critical sections is a fundamental bottleneck to achieving high performance in multithreaded programs. Dynamically, such serialization may be unnecessary because these critical sections could have safely executed concurrently without locks. Current processors cannot fully exploit such parallelism because they do not have mechanisms to dynamically detect such false inter-thread dependences. We propose Speculative Lock Elision (SLE), a novel micro-architectural technique to remove dynamically unnecessary lock-induced serialization and enable highly concurrent multithreaded execution. The key insight is that locks do not always have to be acquired for a correct execution. Synchronization instructions are predicted as being unnecessary and elided. This allows multiple threads to concurrently execute critical sections protected by the same lock. Misspeculation due to inter-thread data conflicts is detected using existing cache mechanisms and rollback is used for recovery. Successful speculative elision is validated and committed without acquiring the lock. SLE can be implemented entirely in microarchitecture without instruction set support and without system-level modifications, is transparent to programmers, and requires only trivial additional hardware support. SLE can provide programmers a fast path to writing correct high-performance multithreaded programs.