Skip to content

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);
}