论文标题
有效的多词比较和交换
Efficient Multi-word Compare and Swap
论文作者
论文摘要
无原子锁的多词比较和换档（MCAS）是设计并发算法的强大工具。然而，它的广泛使用受到限制，因为MCAS的无锁实现大量使用了昂贵的比较和交换（CAS）说明。现有的MCAS实现确实使用了每个K-CAS至少使用2K+1个案例。这导致了自然希望最大程度地减少实施MCA所需的案件数量。我们首先在本文中证明，不可能“包装”在小于k位置的k-word cas（k-cas）所需的信息。然后，我们提出第一个算法，该算法需要在常见的无害情况下每个呼叫k-cas的k+1个案例。我们实施算法，并表明它在大多数考虑的工作负载中的各种基准测试中都优于最先进的基线。我们还使用每个呼叫只有2个持久性围栏，提出了我们MCAS算法的可持久线性（持续记忆友好型）版本，而每个k-cas仍然只需要k+1个案例。
Atomic lock-free multi-word compare-and-swap (MCAS) is a powerful tool for designing concurrent algorithms. Yet, its widespread usage has been limited because lock-free implementations of MCAS make heavy use of expensive compare-and-swap (CAS) instructions. Existing MCAS implementations indeed use at least 2k+1 CASes per k-CAS. This leads to the natural desire to minimize the number of CASes required to implement MCAS. We first prove in this paper that it is impossible to "pack" the information required to perform a k-word CAS (k-CAS) in less than k locations to be CASed. Then we present the first algorithm that requires k+1 CASes per call to k-CAS in the common uncontended case. We implement our algorithm and show that it outperforms a state-of-the-art baseline in a variety of benchmarks in most considered workloads. We also present a durably linearizable (persistent memory friendly) version of our MCAS algorithm using only 2 persistence fences per call, while still only requiring k+1 CASes per k-CAS.
