WAIT-FREE SYNCHRONIZATION
WAIT-FREE SYNCHRONIZATION
复制标题
DOI：
10.1145/114005.102808
复制
发表时间：
1991-01-01
影响因子：
1.3
通讯作者：
HERLIHY, M
中科院分区：
文献类型：
--
作者：
HERLIHY, M
并发数据对象的无等待实现可以保证任何进程都可以在有限数量的步骤中完成任何操作，而不管其他进程的执行速度如何。 从一个数据对象构造另一个数据对象的无等待实现的问题是并发算法、并发数据结构和多处理器体系结构方面最近许多工作的核心。 首先，我们引入一种简单而通用的技术，基于简化为共识协议，用于证明“X by Y 不存在无等待实现”形式的陈述。 我们派生了对象的层次结构，使得某一级别的对象没有相对较低级别的对象具有无等待实现。 特别是，我们表明原子读/写寄存器是最近关注的焦点，它位于层次结构的底部：它们不能用于构造许多简单且熟悉的数据类型的无等待实现。 此外，经典的同步原语（例如 test&set 和 fetch&add）虽然比读和写更强大，但计算能力也很弱，就像标准的消息传递原语一样。 其次，我们证明确实存在简单的通用对象，可以从中构造任何顺序对象的无等待实现。
A wait-free implementation of a concurrent data object is one that guarantees that any process can complete any operation in a finite number of steps, regardless of the execution speeds of the other processes. The problem of constructing a wait-free implementation of one data object from another lies at the heart of much recent work in concurrent algorithms, concurrent data structures, and multiprocessor architectures. First, we introduce a simple and general technique, based on reduction to a consensus protocol, for proving statements of the form, "there is no wait-free implementation of X by Y." We derive a hierarchy of objects such that no object at one level has a wait-free implementation in terms of objects at lower levels. In particular, we show that atomic read/write registers, which have been the focus of much recent attention, are at the bottom of the hierarchy: they cannot be used to construct wait-free implementations of many simple and familiar data types. Moreover, classical synchronization primitives such as test&set and fetch&add, while more powerful than read and write, are also computationally weak, as are the standard message-passing primitives. Second, nevertheless, we show that there do exist simple universal objects from which one can construct a wait-free implementation of any sequential object.