Practical Lock-Free and Wait-Free LL/SC/VL Implementations Using 64-Bit CAS

The ideal semantics of the instructions LL/SC/VL (Load-Linked, Store-Conditional, Validate) are inherently immune to the ABA problem which is a fundamental problem that affects most lock-free algorithms. This paper presents practical lock-free and wait-free implementations of arbitrary-sized LL/SC/VL variables using 64-bit CAS (Compare-and-Swap). The implementations improve on Jayanti and Petrovic’s 64-bit wait-free implementations by reducing the space overhead per variable to a small constant, and not requiring advance knowledge of the maximum number of participating threads, while maintaining minimal amortized expected time and work complexities.