A Practical Multi-Word Compare-and-Swap Operation

Abstract. Work on non-blocking data structures has proposed extend-ing processor designs with a compare-and-swap primitive, CAS2, which acts on two arbitrary memory locations. Experience suggested that cur-rent operations, typically single-word compare-and-swap (CAS1), are not expressive enough to be used alone in an eÆcient manner. In this pa-per we build CAS2 from CAS1 and, in fact, build an arbitrary multi-word compare-and-swap (CASN). Our design requires only the primitives avail-able on contemporary systems, reserves a small and constant amount of space in each word updated (either 0 or 2 bits) and permits non-overlapping updates to occur concurrently. This provides compelling ev-idence that current primitives are not only universal in the theoretical sense introduced by Herlihy, but are also universal in their use as foun-dations for practical algorithms. This provides a straightforward mecha-nism for deploying many of the interesting non-blocking data structures presented in the literature that have previously required CAS2.