Efficient non-blocking K-compare-single-swap operation

摘要

The design of nonblocking linked data structures using single-location synchronization primitives such as compare-and-swap (CAS) is a complex affair that often requires severe restrictions on the way pointers are used. One way to address this problem is to provide stronger synchronization operations, for example, ones that atomically modify one memory location while simultaneously verifying the contents of others. We provide a simple and highly efficient nonblocking implementation of such an operation: an atomic k-word-compare single-swap operation (KCSS). Our implementation is obstruction-free. As a result, it is highly efficient in the uncontended case and relies on contention management mechanisms in the contended cases. It allows linked data structure manipulation without the complexity and restrictions of other solutions. Additionally, as a building block of some implementations of our techniques, we have developed the first nonblocking software implementation of load-linked/store-conditional that does not severely restrict word size.

主权项

1. A non-transitory computer-readable storage medium storing one or more instruction sequences executable on a multiprocessor to implement a multi-compare, single-swap synchronization operation that is linearizable non-blocking,
the multi-compare, single-swap synchronization operation takes as input:
expected contents of a plurality of targeted memory locations; anda new value for one of the plurality of targeted memory locations; the multi-compare, single-swap synchronization operation is configured to perform:
determining whether contents of the plurality of targeted memory locations match the expected contents of the plurality of targeted memory locations; andmodifying, at most, the one of the plurality of targeted memory locations; and said determining and said modifying are performed atomically.