CAS操作与无锁编程原理
Compare-And-Swap(CAS)操作的原理是什么？C++中如何通过std::atomic实现CAS(compare_exchange_weak和compare_exchange_strong的区别)？CAS的ABA问题是什么以及如何解决？
回答
苦行僧
CAS原理：原子操作：bool CAS(T* ptr, T expected, T desired)——比较*ptr是否等于expected，是则写入desired并返回true，否则返回false。
C++实现：
std::atomic<int> val{0};
int expected = 0;
// weak可能在虚假失败时返回false(性能更好，适合循环)
while (!val.compare_exchange_weak(expected, 1)) {}
// strong保证操作结果(无虚假失败)
val.compare_exchange_strong(expected, 1);
weak vs strong：weak允许虚假失败(spurious failure)——即使值匹配也可能返回false(某些平台上LL/SC指令的特性)。weak在循环中使用，strong在只需要一次尝试时使用。
ABA问题：线程1读A→被调度出；线程2将A改为B再改回A；线程1恢复后CAS比较通过(值还是A)，但A指向的内存已不同(指针场景)。
ABA解决方案：
- 标记指针(Tagged Pointer)：指针+版本号原子打包(
atomic<uintptr_t>)，每次改指针递增版本号 - 垃圾回收/Hazard Pointer：延迟回收被并发线程引用的节点
- RCU(Read-Copy-Update)：读时不加锁，写时复制
- C++的
std::atomic<std::shared_ptr<T>>(C++20)可解决部分问题
经典应用：无锁栈(lock-free stack)、无锁队列、引用计数、自旋锁。