Efficient and practical constructions of LL/SC variables
Prasad Jayanti, Srdjan Petrović · 2003
Over the past decade, a pair of synchronization instructions known as LL/SC has emerged as the most suitable set of instructions to be used in the design of lock-free algorithms. However, no existing multiprocessor system supports these instructions in hardware. Instead, most modern multipro-cessors support instructions such as CAS or RLL/RSC (e.g. POWER4, MIPS, SPARC, IA-64). This paper presents two efficient algorithms that implement 64-bit LL/SC from 64-bit CAS or RLL/RSC. Our re~ults are summarized as fol-lows. We present a practical algorithm for implementing a 64-bit LL/SC object from 64-bit CAS or RLL/RSC objects. Our result shows, for the first time, a practical way of simu-lating a 64-bit LL/SC memory word using 64-bit CAS mem-ory words (or 64-bit RLL/RSC memory words), incurring only a small constant space overhead per process and a small constant factor slowdown. Although our first solution performs correctly in any practical system, its theoretical correctness depends on un-bounded sequence numbers. We present a bounded algo-rithm that implements a 64-bit LL/SC object from 64-bit CAS or RLL/RSC objects, and has the same time and space complexities as the first algorithm. This and the previous algorithm improve on existing im-plementations of LL/SC objects by Anderson and Moir in 1995, and Moir in 1997. 1.