Laziness Pays! Using Lazy Synchronization Mechanisms to Improve Non-Blocking
Constructions
Mark Moir
To appear at Nineteenth Annual
ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC
2000), Portland, Oregon, 16-19 July 2000
Abstract
We present a simple and efficient wait-free implementation for a new shared
object called Lazy Large Load-Linked/Store-Conditional (Lazy-LL/SC). This
object can be used to atomically modify a dynamically-determined set of
shared variables in a lock-free manner. The semantics of the Lazy-LL/SC
object is weaker than that of similar objects used by us previously to
design lock-free and wait-free constructions. The new object is still strong
enough to be used in these constructions, but can be implemented more efficiently.
We show how Lazy-LL/SC can be used to improve our previous lock-free and
wait-free universal constructions, and also how it can be used directly
to implement an even more efficient lock-free universal construction.