Universal constructions for multi-object operations
James Horton Anderson, Mark J. Moir · 1995
We present wait-free and lock-free universal constructions that allow operations to access multiple objects atomically. Such constructions provide functionality similar to nested critical sections in conventional, lockbased systems. In such a system, two critical sections might be nested, for example, to swap the contents of two shared bu ers. Using our constructions, such a transfer can be done in a wait-free or a lock-free manner. Our universal constructions are based upon multiword synchronization primitives. In the rst part of the paper, we present wait-free implementations of such primitives from one-word primitives. These implementations allow processes that access disjoint words to execute in parallel. Previous implementations of multi-word primitives either overly restrict parallelism, or provide only lock-free execution. We also present several implementations involving one-word universal primitives that allow our constructions to be applied with greater exibility. In particular, we present timeoptimal, wait-free implementations of Load-Linked and Store-Conditional from Read and Compare-And-Swap, and vice versa, and implementations that eliminate the need to deal with spurious Store-Conditional failures. 1