C++11 CAS无锁函数compare_exchange_weak的使用

hada2006

　　关于C++11的并发指南可以看这个Blog。
　　这里主要想谈一下对compare_exchange_weak这个C++11用来实现CAS无锁算法函数的理解。

可以先看一下cplusplus给出的用这个函数实现无锁链表的例子:

// atomic::compare_exchange_weak example:
#include <iostream>       // std::cout
#include <atomic>         // std::atomic
#include <thread>         // std::thread
#include <vector>         // std::vector
// a simple global linked list:
struct Node { int value; Node* next; };
std::atomic<Node*> list_head (nullptr);
void append (int val) {     // append an element to the list
Node* oldHead = list_head;
Node* newNode = new Node {val,oldHead};
// what follows is equivalent to: list_head = newNode, but in a thread-safe way:
while (!list_head.compare_exchange_weak(oldHead,newNode))
newNode->next = oldHead;
}
int main ()
{
// spawn 10 threads to fill the linked list:
std::vector<std::thread> threads;
for (int i=0; i<10; &#43;&#43;i) threads.push_back(std::thread(append,i));
for (auto& th : threads) th.join();
// print contents:
for (Node* it = list_head; it!=nullptr; it=it->next)
std::cout << ' ' << it->value;
std::cout << '\n';
// cleanup:
Node* it; while (it=list_head) {list_head=it->next; delete it;}
return 0;
}
　　Possible output (the order may be different):

9 8 7 6 5 4 3 2 1 0
　　对函数参数和返回&#20540;的解释可以看原文，或翻译。
　　归纳一下这个函数的使用要点：

• 当前&#20540;与期望&#20540;相等时，修改当前&#20540;为设定&#20540;，返回true
  
• 当前&#20540;与期望&#20540;不等时，将期望&#20540;修改为当前&#20540;，返回false
  
• 这个函数可能在满足true的情况下仍然返回false，所以只能在循环里使用，否则可以使用它的strong版本
  

　　不过我觉得那个strong版本（compare_exchange_weak）应用场景的意义&#20284;乎不大，因为是一次执行，可以完全用atomic_flag的testandset操作代替。

而这个weak版本考虑到了硬件性能的最优化，在使用CAS时一般都只会用到它。

相比无锁链表或者无锁队列，更一般的用法应该是这样的：

1 auto max_val = getMaxValue();//获取&#20540;上界
2 auto now_val = getValue();//获取当前&#20540;
3 auto exp_val = now_val; //期望&#20540;为当前&#20540;
4 do {
5   if(exp_val == max_val) break; //到达上界退出循环
6 } while(!now_val.compare_exchange_weak(exp_val, exp_val &#43; 1))//从第2行到第5行代码可能被其他线程中断改变now_val的&#20540;
　　这段代码简要地说明了这个函数的使用方法，首先你要持有一个now_val，接着在企图修改这个&#20540;时，用CAS函数来判断这个&#20540;是否发生了改变，如果未改变则执行加1，若改变了则期望&#20540;随之改变为该当前&#20540;，直到循环判断到期望&#20540;与当前&#20540;相等，再执行加1操作。

可能你会觉得这不就是原子加1，用atomic自带的加法重载不就实现了。其实这里还有一个用处，也就是对期望&#20540;（或当前&#20540;）进行判断，比如当到达一个临界&#20540;以后就停止累加，原子加法没法将加1之后的判断也绑定到同一个原子操作中，也就没法实现这一点。而CAS的循环体中则可以实现一个“准改判断”——不满足条件就不允许修改当前&#20540;。
　　打个不恰当的比方，就像一个备胎等待老司机换胎，想着“下一个就轮到自己了”，结果发现下一个是别人，于是又想“下一个就是自己了”，“下一个就是自己了”...到最后橡胶老化被司机扔了...XD

Let my exciting burning magma fulfill the infinite void black hole.