比较交换可以使用CompareAndSwap实现吗？

假设比较并交换（或CAS）从来没有失败不合逻辑，可CompareExchange与中科院实施？比较交换可以使用CompareAndSwap实现吗？

CompareExchange两者取指针，预期值，并且新的值和设置原子由指针参考的新值存储，如果它的预期值相匹配。两者之间的区别是，CompareExchange返回的存储器区域的前一值和比较并交换返回一个布尔值指示成功或失败。

这是琐碎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？我见过的所有尝试都有竞争条件或不保证无锁性质。我不相信这是可能的。

来源

2010-03-17 Dan Olson

我不明白它是如何可能的。对于CAS失败的情况，您需要单独的操作来获取以前的值。这种单独的操作相对于CAS而言不会是原子的。

你可以有一部分的方式：

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

是这种情况，你有问题，其中CAS失败。获取*p以查找以前的值相对于CAS而言不会是原子的，因此您要么具有竞争条件，要么必须锁定CAS和*p取消引用。

来源

2010-03-17 16:31:01

我们在这里思考的是，我不认为有可能在没有竞争条件的情况下无锁地确定* p。 – 2010-03-17 21:51:27

你可以，它是无锁的，但它不是免费的等待：

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

的想法是，* P从CompareExchange回国后的修改是从两者之间的修改不能区分IFS。

同样，可以实现基于CAS原子交换和原子读取和OP，但它不会是无等待。

来源

2011-08-30 12:40:44

我支持。是的，返回的值是没有必要在导致最后CAS失败的价值，但它并没有真的事，只要它从'expected'不同。 – 2011-08-31 21:42:40

比较交换可以使用CompareAndSwap实现吗？

回答

相关问题