multithreading - 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 取消引用。