论文标题
可塑性可追回的相互排斥
Recoverable Mutual Exclusion with Abortability
论文作者
论文摘要
非易失性主内存（NVRAM）技术的最新进展刺激了针对过程崩溃弹性的算法的研究。本文是我们会议论文\ cite {jayanti：rmeabort}的完整版本，该论文介绍了支持可贩运性的第一个可回收相互排除（RME）算法。我们的算法仅使用读，写和CAS操作，这些操作通常由多处理器支持。它满足FCF和其他标准属性。 我们的算法也是自适应的。 On DSM and Relaxed-CC multiprocessors, a process incurs $O(\min(k, \log n))$ RMRs in a passage and $O(f+ \min(k, \log n))$ RMRs in an attempt, where $n$ is the number of processes that the algorithm is designed for, $k$ is the point contention of the passage or the attempt, and $f$ is the number of times that $ P $在尝试期间崩溃。在严格的CC多处理器上，通过和尝试复杂性为$ O（n）$和$ O（f+n）$。 Attiya等。证明，使用任何相互排除算法，如果算法仅使用读，写入和CAS操作\ cite {attiya：lbound}，则过程中至少会在段落中产生至少$ω（\ log n）$ rmrs。这种下限意味着我们算法的最坏情况RMR复杂性对于DSM和松弛的CC多处理器是最佳的。
Recent advances in non-volatile main memory (NVRAM) technology have spurred research on designing algorithms that are resilient to process crashes. This paper is a fuller version of our conference paper \cite{jayanti:rmeabort}, which presents the first Recoverable Mutual Exclusion (RME) algorithm that supports abortability. Our algorithm uses only the read, write, and CAS operations, which are commonly supported by multiprocessors. It satisfies FCFS and other standard properties. Our algorithm is also adaptive. On DSM and Relaxed-CC multiprocessors, a process incurs $O(\min(k, \log n))$ RMRs in a passage and $O(f+ \min(k, \log n))$ RMRs in an attempt, where $n$ is the number of processes that the algorithm is designed for, $k$ is the point contention of the passage or the attempt, and $f$ is the number of times that $p$ crashes during the attempt. On a Strict CC multiprocessor, the passage and attempt complexities are $O(n)$ and $O(f+n)$. Attiya et al. proved that, with any mutual exclusion algorithm, a process incurs at least $Ω(\log n)$ RMRs in a passage, if the algorithm uses only the read, write, and CAS operations \cite{Attiya:lbound}. This lower bound implies that the worst-case RMR complexity of our algorithm is optimal for the DSM and Relaxed CC multiprocessors.
