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.