A Wait-Free Multi-Word Compare-And-Swap Operation

Keywords

CAS; Concurrent; Lock-free; MCAS; Multi-word compare-and-swap; Non-blocking; Wait-free

Abstract

The number of cores in future multi-core systems are expected to increase by 100 fold over the next decade. The fine-grained synchronization methods found in wait-free algorithm designs makes them desirable for these future systems. Unfortunately, such designs are often inhibited by the limitations of portable atomic hardware primitives. Typically these primitives can only operate on a single address at a time, while concurrent algorithms often need to operate on multiple addresses. To support such algorithms we present a practical wait-free Multi-word-compare-and-swap. The wait-free property ensures that each thread completes its operation in a finite number of steps, even if it is continuously interrupted. Our approach uses a progress assurance scheme that allows a blocked thread to announce that it is unable to make progress. This differs from traditional lock-free helping techniques where a thread will only help complete an operation that is in conflict with its own. Our design is practical in that it is built from only portable atomic operations, it is efficient in its utilization of memory (i.e. requiring only a single bit to be reserved from each word, not requiring use of explicit memory barriers, and requiring only four words per address in the operation), and has a wait-free progress guarantee. When tested in a high contention scenario with 64 threads executing updates on a single multi-word object, our wait-free design performs on average 77.1 % more operations than other practical approaches. Over all tested scenarios, our design performs on average 8.3 % more operations.

Publication Date

8-1-2015

Publication Title

International Journal of Parallel Programming

Volume

43

Issue

4

Number of Pages

572-596

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/s10766-014-0308-7

Socpus ID

84927123337 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84927123337

This document is currently not available here.

Share

COinS