%T Efficient and Practical Constructions of LL/SC Variables
%A Prasad Jayanti
%A Srdjan Petrovic
%R Technical Report TR2003-446
%I Dartmouth College, Computer Science
%C Hanover, NH
%D June 2003
%U http://www.cs.dartmouth.edu/reports/TR2003-446.pdf
%X
 Over the past decade, LL/SC have emerged as the most suitable
 synchronization instructions for the design of lock-free algorithms.
 However, current architectures do not support these instructions;
 instead, they support either CAS or RLL/RSC (e.g. POWER4, MIPS, SPARC, IA-64). To bridge this gap, this paper presents two efficient wait-free
 algorithms for implementing 64-bit LL/SC objects from 64-bit CAS or
 RLL/RSC objects.
    Our first algorithm is practical: it has a small, constant time complexity (of 4 for LL and 5 for SC) and a space overhead of only 4 words per process. This algorithm uses unbounded sequence numbers.
 For theoretical interest, we also present a more complex bounded algorithm
 that still guarantees constant time complexity and O(1) space overhead per process.
    The LL/SC primitive is free of the well-known ABA problem that afflicts CAS. By efficiently implementing LL/SC words from CAS words,
 this work presents an efficient general solution to the ABA problem.