A Practical Multi-word Compare-and-Swap Operation
A Practical Multi-word Compare-and-Swap Operation
复制标题
DOI：
10.1007/3-540-36108-1_18
复制
发表时间：
2002-10
期刊：
影响因子：
--
通讯作者：
T. Harris;K. Fraser;I. Pratt
中科院分区：
文献类型：
--
作者：
T. Harris;K. Fraser;I. Pratt
非阻塞数据结构的工作提出了使用比较和交换原语 CAS2 来扩展处理器设计，该原语作用于两个任意内存位置。经验表明，当前的操作（通常是单字比较和交换 (CAS1)）的表达能力不足以以有效的方式单独使用。在本文中，我们从 CAS1 构建了 CAS2，实际上，构建了一个任意多字比较和交换 (CASN)。我们的设计只需要当代系统上可用的原语，在每个更新的字中保留少量且恒定的空间（0 或 2 位），并允许同时发生非重叠更新。这提供了令人信服的证据，表明当前的原语不仅在 Herlihy 引入的理论意义上是通用的，而且在用作实际算法的基础方面也是通用的。这提供了一种简单的机制，用于部署以前需要 CAS2 的文献中介绍的许多有趣的非阻塞数据结构。
Work on non-blocking data structures has proposed extending processor designs with a compare-and-swap primitive,CAS2, which acts on two arbitrary memory locations. Experience suggested that current operations, typically single-word compare-and-swap (CAS1), are not expressive enough to be used alone in an efficient manner. In this paper we buildCAS2fromCAS1and, in fact, build an arbitrary multi-word compare-and-swap (CASN). Our design requires only the primitives available on contemporary systems, reserves a small and constant amount of space in each word updated (either 0 or 2 bits) and permits nonoverlapping updates to occur concurrently. This provides compelling evidence that current primitives are not only universal in the theoretical sense introduced by Herlihy, but are also universal in their use as foundations for practical algorithms. This provides a straightforward mechanism for deploying many of the interesting non-blocking data structures presented in the literature that have previously requiredCAS2.