A Practical Wait-Free Multi-Word Compare-and-Swap Operation

Algorithms designed for current and future multi-core sys-tems, which are expected to experience an increase of the number of cores by 100x over the next decade, must ex-hibit strong scaling. The guarantee of progress provided by wait-free algorithms and the fine-grained synchroniza-tion methods used in their designs, make them desirable for achieving this goal. However, the design and development of advanced wait-free algorithms is often inhibited by the limitations of portable atomic hardware operations. Typ-ically these operations can manipulate a single address at a time, where many concurrent algorithms need to perform a series of operations on multiple addresses, requiring more advanced synchronization mechanisms such as a wait-free Multi-Word-Compare-and-Swap (MCAS). In this paper, we present the first practical MCAS design that is wait-free in all scenarios. This property holds even if interrupts consistently cause a thread to retry a portion of its operation. Our design is practical in that it is built from only portable atomic operations (e.g. atomic reads, atomic writes, compare-and-swap), 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). Our performance evaluation reveals that on average our wait-free MCAS algorithm performs 8.3 % faster than other practical approaches in all tested scenarios