Nonblocking k-Compare-Single-Swap
Nonblocking k-Compare-Single-Swap
复制标题
非阻塞 k 比较单交换
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
N. Shavit
中科院分区：
文献类型：
--
作者：
Victor Luchangco;Mark Moir;N. Shavit
目前的文献提供了两个极端的非阻塞软件同步支持并发数据结构的设计：复杂的设计的特定结构的基础上单位置的操作，如比较和交换（CAS），和通用的多位置事务存储器的实现。虽然前者有时是有效的，但它们总是难以扩展和推广。后者是灵活和通用的，但成本高。本文的目的是在一个中间地带：合理有效的多位置操作，是一般的，足以减少设计困难的算法的基础上CAS单独。我们提出了一个无障碍的实现原子k-位置比较单位置交换（KCSS）操作。KCSS通过克服设计中的关键算法困难，允许对链接数据结构进行简单的非阻塞操作：确保在操作指针时，数据结构的相邻部分保持不变。我们的算法是有效的，在常见的无争用的情况下：一个成功的k位置KCSS操作只需要两个CAS操作，两个商店，和2k noncached加载时，没有争用。因此，我们相信我们的研究结果有助于有效和灵活的非阻塞操作列表为基础的数据结构在今天的架构。
The current literature offers two extremes of nonblocking software synchronization support for concurrent data structure design: intricate designs of specific structures based on single-location operations such as compare-and-swap (CAS), and general-purpose multilocation transactional memory implementations. While the former are sometimes efficient, they are invariably hard to extend and generalize. The latter are flexible and general, but costly. This paper aims at a middle ground: reasonably efficient multilocation operations that are general enough to reduce the design difficulties of algorithms based on CAS alone.We present an obstruction-free implementation of an atomic k-location-compare single-location-swap (KCSS) operation. KCSS allows for simple nonblocking manipulation of linked data structures by overcoming the key algorithmic difficulty in their design: making sure that while a pointer is being manipulated, neighboring parts of the data structure remain unchanged. Our algorithm is efficient in the common uncontended case: A successful k-location KCSS operation requires only two CAS operations, two stores, and 2k noncached loads when there is no contention. We therefore believe our results lend themselves to efficient and flexible nonblocking manipulation of list-based data structures in today’s architectures.