BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR2003-446
ENTRY:: October 24, 2004
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Efficient and Practical Constructions of LL/SC Variables
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Jayanti, Prasad
AUTHOR:: Petrovic, Srdjan
DATE:: June 2003
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR2003-446.pdf
ABSTRACT:: 
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.
END:: ncstrl.dartmouthcs//TR2003-446