C++ atomic compare_and_exchange方法困惑

neodreamerus

我知道gcc提供了如下内建函数，
__sync_bool_compare_and_swap, 在x86上会编译成 lock cmpxchg指令
可对内存进行原子访问。

这个函数的原型是
bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)
type是整数，比如int。

如果用C来表示这个函数做的事情，应该是这样的：

1. 
   
2. 
   
3. bool  __sync_bool_compare_and_swap(int* ptr, int oldval, int newval) {
   
4. 
   
5.      if (*ptr == oldval) {
   
6.            *ptr = newval;
   
7.             return true;
   
8.      } else return false;
   
9. }
   
10. 
    

复制代码

这也是通常的CAS实现的语义。这个函数可以用来实现无锁。

在C++11中，有一个atomic库，里面的atomic<T>模板类，
其中有方法叫 compare_exchange_weak/strong.
关于weak和strong的差别我理解了，可以看这里 http://www.cplusplus.com/referen ... are_exchange_strong。

我的问题是，这个方法的语义看起来和 CAS不太一样。
这个方法的运行结果用C表示大概是这样的：

1. 
   
2. 
   
3. bool  atomic_compare_exchange(int* ptr, int* oldval, int newval) {
   
4. 
   
5.      if (*ptr == *oldval) {
   
6.            *ptr = newval;
   
7.             return true;
   
8.      } else {
   
9.             *oldval = *ptr;
   
10.             return false;
    
11.      }
    
12. }
    
13. 
    

复制代码

我看了后很困惑，我查了一些资料，也是说这个方法是用来实现无锁的，通常放在一个while中循环直到返回true.
问题是，这个方法如果第一次调用是false的话，第二次调用肯定是true了。

neodreamerus

回复 1# neodreamerus


网上收了一阵后有点明白了， std::atomic 实现的CAS 和 __sync_bool_compare_and_swap确实有点不一样，
但是能实现相同的效果。

找到一个使用 std::atomic 实现无锁链表的简单例子。学习一下。

1. 
   
2. 
   
3. #include <atomic>
   
4. 
   
5. template<typename T>
   
6. class List {
   
7. public:
   
8.   void append(const T& value);   // see below
   
9. 
   
10. private:
    
11.   struct Node {
    
12.     T data;
    
13.     Node *next;
    
14.   };  
    
15. 
    
16.   std::atomic<Node*> head;
    
17. };
    
18. 
    
19. template<typename T>
    
20. void List<T>::append(const T& value)
    
21. {
    
22.   Node *newNode = new Node { value };
    
23.    
    
24.   Node* headNode;
    
25.   do {
    
26.     headNode = head;
    
27.     newNode->next = head;
    
28.   } while (!std::atomic_compare_exchange_weak(&head, &headNode, newNode));
    
29.   // or while (!head.compare_exchange_weak(headNode, newNode));
    
30. }
    
31. 
    
32. int main()
    
33. {
    
34.   List<int> li;
    
35.   li.append(10);
    
36. }
    
37. 
    

复制代码

zhouzhenghui

就是一个返回最新值，一个没有返回的区别，返回的话，后续可以少一个load操作，也许但不一定有加快速度的几率。

bruceteen

第二个实现最好吧
第一个实现，在失败后，你还得手工重置oldval=*ptr，否则以后全是失败