Read-Optimized Lock-Free Locks

Lock-free concurrent algorithms guarantee system-wide progress even when individual threads are delayed or suspended. Despite this desirable property, designing efficient lock-free algorithms remains notoriously difficult, limiting their practical applicability.
Lock-free locks aim to address this challenge by providing the abstraction of atomic critical sections while preserving lock-freedom. Prior work introduced a practical implementation of this abstraction. However, the resulting construction is primarily suited to fine-grained locking and can cause redundant work when multiple helpers execute the same critical section.
This research introduces a new lock-free lock construction based on two-phase speculative execution. In the first phase, helper threads execute the critical section locally and record its updates in a local write set. The helpers then compete to publish their results, but only one write set can be successfully published. Once a write set has been published, all helpers adopt it and apply its updates to shared memory. This separation between speculative execution and the application of its results limits redundant work. We also present a merged lock that supports both the prior construction and our phased construction through a single interface, allowing programmers to choose the execution mode best suited to their workload.
We prove the correctness and lock-freedom of the proposed construction and experimentally evaluate its performance against the prior lock-free lock construction and a conventional blocking spin lock. The results show that our approach offers performance advantages for long, read-heavy critical sections.

M.Sc. student under the supervision of Dr. Naama Ben-David.