基于C++11CAS实现无锁队列

1.什么是 CAS？

CAS操作——Compare & Set，或是 Compare & Swap，现在几乎所有的CPU指令都支持CAS的原子操作，X86下对应的是 CMPXCHG 汇编指令。有了这个原子操作，我们就可以用其来实现各种无锁（lock free）的数据结构。

这个操作用C语言来描述就是下面这个样子：（代码来自 Wikipedia的Compare And Swap词条）意思就是说，看一看内存 *reg里的值是不是 oldval，如果是的话，则对其赋值 newval。

int compare_and_swap (int* reg, int oldval, int newval) 
{ 
int old_reg_val = *reg; 
if (old_reg_val == oldval) 
{ *reg = newval; } 
return old_reg_val; 
}

我们可以看到， old_reg_val 总是返回，于是，我们可以在 compare_and_swap 操作之后对其进行测试，以查看它是否与 oldval相匹配，因为它可能有所不同，这意味着另一个并发线程已成功地竞争到 compare_and_swap 并成功将 reg 值从 oldval 更改为别的值了。

这个操作可以变种为返回bool值的形式（返回 bool值的好处在于，可以调用者知道有没有更新成功）：

// test
bool compare_and_swap (int *addr, int oldval, int newval) 
{ if ( *addr != oldval ) 
{ return false; } *addr = newval; 
return true; }

与CAS相似的还有下面的原子操作：

Fetch And Add，一般用来对变量做 +1 的原子操作
Test-and-set，写值到某个内存位置并传回其旧值。汇编指令BST
Test and Test-and-set，用来低低Test-and-Set的资源争夺情况

最后总结下CAS，是一个概念，这个操作必须是原子的。

2.在实际的C/C++程序中，CAS的各种实现版本如下

1）GCC的CAS GCC4.1+版本中支持CAS的原子操作

bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...) type __sync_val_compare_and_swap (type *ptr, type oldval type newval, ...)

2）Windows的CAS 在Windows下，你可以使用下面的Windows API来完成CAS：（完整的Windows原子操作可参看MSDN的InterLocked Functions） InterlockedCompareExchange ( __inout LONG volatile *Target, __in LONG Exchange, __in LONG Comperand);

3) C++11中的CAS

C++11中的STL中的atomic类的函数可以让你跨平台

template< class T >
bool atomic_compare_exchange_weak( std::atomic* obj,T* expected, T desired );
template< class T >
bool atomic_compare_exchange_weak( volatile std::atomic* obj,T* expected, T desired );

3.CAS需要硬件支持吗？

必须有硬件支持，原子性本质：CAS 需要 单指令或硬件监控机制 保证操作的不可分割性，

软件无法直接模拟，若无硬件支持，无法在多核/多线程环境下保证原子性（例如，软件模拟的“CAS”可能被中断或并发修改破坏）。

4.不同 CPU 架构通过专用指令实现 CAS 的原子性

架构	指令	机制
x86/x64	`LOCK CMPXCHG`	通过 `LOCK` 前缀强制总线锁定，保证多核原子性。
ARM	`LDREX` + `STREX`	基于独占访问标记（Exclusive Monitor），由硬件监控内存访问的原子性。

我们可以通过工具 Compiler Explorer 进行验证。目前只是验证X86平台上的指令。

#include <atomic>
#include <iostream>void test_atomic_ops(std::atomic<bool>& flag) {// 1. load() 操作bool val1 = flag.load(std::memory_order_relaxed);// 2. store() 操作flag.store(true, std::memory_order_relaxed);// 3. exchange() 操作bool old_val = flag.exchange(false, std::memory_order_relaxed);// 4. compare_exchange_weak() 操作bool expected = false;flag.compare_exchange_weak(expected, true, std::memory_order_relaxed);
}int main() {std::atomic<bool> flag{false};test_atomic_ops(flag);return 0;
}