Universal constructions for multi-object operations
Universal constructions for multi-object operations
复制标题
多对象操作的通用结构
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
Mark Moir
中科院分区：
文献类型：
--
作者：
James H. Anderson;Mark Moir
我们提出了无等待和无锁的通用结构，允许操作原子地访问多个对象。这样的构造提供类似于常规的基于锁的系统中的嵌套临界区的功能。在这样的系统中，两个临界区可以嵌套，例如，交换两个共享缓冲区的内容。使用我们的构造，这样的传输可以以无等待或无锁定的方式完成。我们的通用结构是基于多字同步原语。在本文的第一部分中，我们提出了从一个字的原语等原语无等待的实现。这些实现允许访问不相交单词的进程并行执行。以前的多字原语实现要么过度限制并行性，要么只提供无锁执行。我们还提出了几个实现涉及一个字的通用原语，使我们的建设，以更大的灵活性应用。特别是，我们提出了时间最优，无等待的实现的加载链接和存储条件从读取和比较和交换，反之亦然，和实现，消除了需要处理虚假的存储条件故障。
We present wait-free and lock-free universal constructions that allow operations to access multiple objects atomically. Such constructions provide functionality similar to nested critical sections in conventional, lockbased systems. In such a system, two critical sections might be nested, for example, to swap the contents of two shared buffers. Using our constructions, such a transfer can be done in a wait-free or a lock-free manner. Our universal constructions are based upon multiword synchronization primitives. In the first part of the paper, we present wait-free implementations of such primitives from one-word primitives. These implementations allow processes that access disjoint words to execute in parallel. Previous implementations of multi-word primitives either overly restrict parallelism, or provide only lock-free execution. We also present several implementations involving one-word universal primitives that allow our constructions to be applied with greater flexibility y. In particular, we present timeoptimal, wait-free implementations of Load-Linked and Store-Conditional from Read and Compare-And-Swap, and vice versa, and implementations that eliminate the need to deal with spurious Store-Conditional failures.