Fast Local-Spin Abortable Mutual Exclusion with Bounded Space
Fast Local-Spin Abortable Mutual Exclusion with Bounded Space
复制标题
有界空间的快速局部自旋可中止互斥
DOI：
10.1007/978-3-642-17653-1_27
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Hyonho Lee
中科院分区：
文献类型：
--
作者：
Hyonho Lee
可中止互斥是互斥的一种变体，允许进程在等待进入临界区时中止其调用。本文提出了一个时间和空间都有界的FCFS可中止互斥算法，当至多有k个进程中止时，每次调用执行O（k2）RMA。我们定义了一个对象类型，S-HAD，从它很容易构造本地自旋可中止互斥算法。我们的主要贡献是一个waitfree实现的S-HAD对象。我们还开发了一个新的，waitfree内存回收方法，它概括了引用计数，以实现有界空间。最后的算法使用了O（N2）个共享变量，每个共享变量都有O（log N）位，其中N是进程的数量。
Abortable mutual exclusion is a variant of mutual exclusion, where processes are allowed to abort their invocations while waiting to enter the critical section. In this paper, we present an FCFS abortable mutual exclusion algorithm with bounded time and space, in which each invocation performs O(k2) RMAs if atmost k processes abort. We define an object type, S-HAD, from which it is easy to construct local-spin abortable mutual exclusion algorithms. Our main contribution is a waitfree implementation of an S-HAD object. We also develop a new, waitfree memory reclamation method, which generalizes reference counting, to achieve bounded space. The resulting algorithm uses O(N2) shared variables, each with O(log N) bits, where N is the number of processes.