主题
CAS 底层与无锁自旋
cpp
// 编译: g++ -std=c++11 -O2 -pthread 8.CAS底层.cpp -o cas_demo
#include <atomic>
#include <cassert>
#include <cstdint>
#include <cstdio>
#include <thread>
#include <vector>
// CAS 原理 —— 比 old、换 now、失败回写 old
// 伪代码:
template<typename T>
bool CAS(T* addr, T& old, T now)
{
if (*addr == old) // old为期望的旧值,addr为当前值
{
*addr = now; // 相等 -> 写入 now,返回 true
return true;
}
else
{
old = *addr; // 不相等 -> old 被回写为当前值
return false;
}
}
// - "比较 + 交换"整体原子,中间不会被其他线程插入。
static void demo_basic_cas() {
std::atomic<int> x{0};
int old = 0; // 期望旧值
// 相等 -> 成功
bool ok = x.compare_exchange_strong(old, 1); // old=0, now=1
std::printf("CAS(x==0 -> 1) : ok=%d, x=%d\n", ok, x.load());
// 不相等 -> 失败,old 被回写为当前值 1
old = 0; // 故意写错
ok = x.compare_exchange_strong(old, 2); // old=0, now=2
std::printf("CAS(x==0 -> 2) : ok=%d, x=%d, old=%d(被回写)\n",
ok, x.load(), old);
}
// weak vs strong —— 唯一区别是"相等时是否允许伪失败"
// strong:*this == old 时【一定成功】 单次 CAS 用
// weak :*this == old 时【可能伪失败】返回 false(值没变)。
// 所以通常放在 do-while 循环里。
//
// 为什么会有伪失败?
// - x86:CAS 是一条 lock cmpxchg,不会伪失败,weak/strong 代码基本一样。
// - ARM/PowerPC:LL/SC 架构,SC 可能失败(即使值没变)。
// strong 内部套循环重试;weak 把重试交给外层循环。
static void demo_weak_strong() {
std::atomic<int> x{0};
// strong:单次 CAS,失败就放弃
int old = 0;
bool ok = x.compare_exchange_strong(old, 1); // old=0, now=1
std::printf("strong 单次 CAS : ok=%d, x=%d\n", ok, x.load());
// weak:循环重试(标准写法)
old = x.load();
int now;
do {
now = old + 1; // 基于 old 算 now
} while (!x.compare_exchange_weak(old, now)); // old 失败时被回写
std::printf("weak 循环 CAS : x=%d\n", x.load());
// 口诀:
// 单次 CAS 用 strong
// 循环 CAS 用 weak
}
static void demo_loop_cas() {
std::printf("\n========== 循环 CAS 实战demo ==========\n");
std::atomic<int> counter{0};
auto worker = [&counter]() {
for (int i = 0; i < 1000; ++i) {
int old = counter.load(std::memory_order_relaxed);
int now;
do {
now = old + 1;
} while (!counter.compare_exchange_weak(
old, now,
std::memory_order_relaxed,
std::memory_order_relaxed));
}
};
std::vector<std::thread> ts;
for (int i = 0; i < 4; ++i) ts.emplace_back(worker);
for (auto& t : ts) t.join();
std::printf("4 线程 × 1000 次 CAS 自增 : counter=%d(应为 4000)\n",
counter.load());
assert(counter.load() == 4000);
}
// ============================================================================
// ABA 问题与 tagged pointer
// ----------------------------------------------------------------------------
// CAS 只比较"值",不比较"版本"
// 值从 A -> B -> A 后,CAS 会误以为"没变过"。
// 解决:把"版本号 + 值"打包成一个 64 位整数一起 CAS。
// ============================================================================
static void demo_aba() {
std::printf("\n========== 第4节:ABA 问题 ==========\n");
std::atomic<int> val{1};
int old = 1; // 期望旧值
val.store(2); // 别的线程改成 2
val.store(1); // 又改回 1
bool ok = val.compare_exchange_strong(old, 100); // old=1, now=100
std::printf("值经历 1->2->1 后 CAS(1->100) : ok=%d, val=%d\n",
ok, val.load());
std::printf("-> CAS 只看当前值,不知道中间变过(ABA)\n");
// tagged pointer:高 32 位版本号,低 32 位值
std::atomic<uint64_t> tagged{0};
auto pack = [](uint32_t ver, uint32_t v) {
return (static_cast<uint64_t>(ver) << 32) | v;
};
tagged.store(pack(0, 1));
uint64_t old_tagged = pack(0, 1); // old = (ver=0, val=1)
tagged.store(pack(1, 2));
tagged.store(pack(2, 1));
// now = (ver=3, val=100),版本号对不上会失败
ok = tagged.compare_exchange_strong(old_tagged, pack(3, 100));
std::printf("tagged CAS : ok=%d(版本号对不上,ABA 被识破)\n", ok);
}