论文标题
轻松的队列和读/写操作的堆栈
Relaxed Queues and Stacks from Read/Write Operations
论文作者
论文摘要
考虑到异步共享内存系统，其中任何数量的进程可能崩溃，此工作可以标识并正式定义了仅使用读/写操作实现的，这些队列和堆栈的放松可能是无障碍物或无封闭的。设置可连接性和间隔可连接性用于正式指定弛豫，并精确确定保留原始顺序行为的执行子集。放松可以通过不同的操作将项目返回不止一次，但仅在同时发生的情况下；我们称这种属性多重性。堆栈实现是无需等待的，而队列实现是非阻滞。间隔 - 线条定位性用于描述以多种状态的队列，并具有额外的放松，即Dequeue操作可以返回弱空，这意味着队列可能是空的。我们提出了一个并发队列的无读/编写无等待间隔可线化算法。据我们所知，这项工作是第一个提供多样性和无虚弱概念的形式化的作品，这些概念只能在读/写寄存器之上实施。
Considering asynchronous shared memory systems in which any number of processes may crash, this work identifies and formally defines relaxations of queues and stacks that can be non-blocking or wait-free while being implemented using only read/write operations. Set-linearizability and Interval-linearizability are used to specify the relaxations formally, and precisely identify the subset of executions which preserve the original sequential behavior. The relaxations allow for an item to be returned more than once by different operations, but only in case of concurrency; we call such a property multiplicity. The stack implementation is wait-free, while the queue implementation is non-blocking. Interval-linearizability is used to describe a queue with multiplicity, with the additional relaxation that a dequeue operation can return weak-empty, which means that the queue might be empty. We present a read/write wait-free interval-linearizable algorithm of a concurrent queue. As far as we know, this work is the first that provides formalizations of the notions of multiplicity and weak-emptiness, which can be implemented on top of read/write registers only.
