CompareExchange可以用CompareAndSwap来实现吗？

Question

假设 CompareAndSwap（或 CAS）永远不会意外失败，CompareExchange 可以用 CAS 实现吗？

CompareExchange 都接受一个指针、一个期望值和一个新值，并且如果它与期望值匹配，则自动将指针引用的内存设置为新值。两者的区别在于CompareExchange返回内存区域之前的值，而CompareAndSwap返回一个bool，表示成功或失败。

使用 CompareExchange 实现 CAS 很简单：

int CompareExchange (int* p, int expected, int newvalue);

bool CAS (int* p, int expected, int newvalue)
{
   return CompareExchange (p, expected, newvalue) != expected;
}

...但是可以使用 CAS 实现 CompareExchange 吗？我见过的所有尝试要么具有竞争条件，要么不保证无锁属性。我不相信这是可能的。

Answer 1

我不明白这怎么可能。对于 CAS 失败的情况，您需要单独的操作来获取之前的值。这个单独的操作相对于 CAS 来说不是原子的。

您可以部分解决：

int CompareExchnage(int *p, int expected, int newvalue)
{
    if (CAS(p, expected, newvalue))
        return expected;
    else
        ???;
}

在您遇到问题的情况下，CAS 会失败。使用 *p 查找前一个值相对于 CAS 而言不是原子的，因此您要么存在竞争条件，要么必须锁定 CAS 和 *p 取消引用。

Answer 2

可以，而且它是无锁的，但它不是无等待的：

int CompareExchange(int *p, int expected, int newvalue)
{
    for (;;) {
        oldValue = *p;
        if (oldValue != expected)
            return oldValue;
        if (CAS(p, expected, newvalue))
            return expected;
    }
}

其思想是，从 CompareExchange 返回后对 *p 的修改与两个 if 之间的修改没有区别。

同样，你可以基于CAS实现原子交换和原子取操作，但它不会是免等待的。