Impossibility and universality results for wait-free synchronization
Impossibility and universality results for wait-free synchronization
复制标题
无等待同步的不可能性和普遍性结果
DOI：
10.1145/62546.62593
复制
发表时间：
1988
影响因子：
1.8
通讯作者：
M. Herlihy
中科院分区：
文献类型：
--
作者：
M. Herlihy
并发数据对象的无等待实现可以保证任何进程都可以在有限数量的步骤中完成任何操作，而不管其他进程的执行速度如何。从一个数据对象构造另一个数据对象的无等待实现的问题是原子读/写寄存器、多处理器体系结构和并发数据结构方面最近许多工作的核心。在本文的第一部分中，我们介绍了一种基于简化为共识协议的简单而通用的技术，用于证明“Y 不存在 X 的无等待实现”形式的陈述。我们派生了对象的层次结构，使得某一级别的对象没有相对较低级别的对象具有无等待实现。特别是，我们表明原子读/写寄存器是最近关注的焦点，它位于层次结构的底部：它们不能用于构造许多简单且熟悉的数据类型的无等待实现。此外，诸如测试和设置以及获取和添加之类的经典同步原语虽然比读取和写入更强大，但计算能力也很弱，就像标准消息传递原语一样。尽管如此，在本文的第二部分中，我们证明确实存在简单的通用对象，可以从中构造任何顺序对象的无等待实现。版权所有 © 1988 Maurice P. Herlihy 本文将发表在 1988 年 8 月第七届 ACM SIGACT-SIGOPS 分布式计算原理研讨会的会议记录中。这项研究由国防高级研究计划局 (DOD) 赞助，ARPA 订单号为 4976，合同号为 F33615-87-C-1499，并由以下机构监控：空军航空电子实验室赖特航空实验室航空系统部 (AFSC) 赖特-帕特森空军基地，俄亥俄州 45433-6543 本文件中包含的观点和结论属于作者的观点和结论，不应被解释为代表国防高级研究计划局或美国政府明示或暗示的官方政策。
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 atomic read/write registers, multiprocessor architectures, and concurrent data structures. In the first part of this paper, 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-and-set and fetch-and-add, while more powerful than read and write, are also computationally weak, as are the standard message-passing primitives. Nevertheless, in the second part of the paper, we show that there do exist simple universal objects from which one can construct a wait-free implementation of any sequential object. Copyright © 1988 Maurice P. Herlihy This paper will be published in the Proceedings of the Seventh ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, August 1988. This research was sponsored by the Defense Advanced Research Projects Agency (DOD), ARPA Order No. 4976 under contract F33615-87-C-1499 and monitored by the: Avionics Laboratory Air Force Wright Aeronautical Laboratories Aeronautical Systems Division (AFSC) Wright-Patterson AFB, OHIO 45433-6543 The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Defense Advanced Research Projects Agency or the US Government.