CAS实现无锁队列

---

悲观锁：阻塞线程，等待锁释放，发生上下文切换

乐观锁：修改时检查，失败则不断重试

汇编原子操作：

int inc(int* value, int add) {
	int old;
    __asm__ volatile (
         "lock; xaddl %2, %1;"   // 指令1：lock; 指令2: xaddl, 操作数占位符：%1, %2
         : "=a" (old)            // 输出：结果放入通用寄存器eax
         : "m" (*value), "a" (add)   // 输入：操作数1（内存），操作数2（寄存器eax）
         : "cc", "memory"            // 编译方式，内存
     );
    return old;
}

CAS

c++标准库提供了原子操作模板atomic

原子性：计算机执行的一条不可分割的指令

原理：compare-and-swap

• 读取旧值A
• 比较新值V
• 交换新值B
• 返回true，否则false

C++STL提供一组跨平台的CAS操作

bool std::atomic<T>::compare_exchange_weak(T &expected, T desired);
bool std::atomic<T>::compare_exchange_strong(T &expected, T desired);

优势

1. 一种乐观锁，非阻塞，不需要额外开销
2. 有硬件实现，不需要互斥

问题：

1. ABA问题：在CAS期间，A->B->A，CAS检查不出来，可实现带时间戳的类型
2. 多线程同时更新导致循环时间过长