Preemption-Safe Spinlocks: Leveraging Hardware Transactional Memory to Improve Lock Tail Latency

In the development of concurrent applications, locks are a commonly used mechanism for safely synchronizing accesses to shared data objects. However, they are susceptible to the lock holder preemption (LHP) and priority inversion problems when used in conjunction with certain scheduling techniques such as time slicing. In response, past research has proposed methods which generally fall into 2 categories. (1) Proposing to widen the kernel-process interface to facilitate informed scheduling decisions. (2) Lock-free algorithms, which provide synchronization without mutual exclusion. In this paper, we propose a new solution to this problem, the Preemption-Safe Spinlock (PSSL). PSSL is a spinlock that allows a thread waiting on the lock to make progress upon detection of a lock holder preemption event. PSSL uses hardware transactional memory (HTM) to ensure correctness amid a false detection. We evaluate PSSL through experiments using variants of a buffer-fill application with critical section lengths up to approximately 880,000 cycles long and up to 64 threads running on separate cores. Some of these experiments involve pinning a CPU-intensive thread to the same core as one of the worker threads to observe how the synchronization method responds to scheduler-induced LHP. PSSL's performance in these experiments is compared to that of spinlock, mutex, and Intel's HTM paired with different configurations of exponential backoff. We find that PSSL performs similarly to spinlock in experiments where LHP is negligible. In addition, PSSL offers up to a 15% speedup and a 30x reduction in tail latencies over spinlock when the probability of scheduler-induced LHP is high with 2 worker threads and 1 CPU-intensive thread.