CAS

CAS（Compare-And-Swap / Compare-And-Exchange，比较并交换）是并发编程中的一种原子操作，常用于实现无锁数据结构、原子计数器、自旋锁等。

在 C++ 中，CAS 主要通过 std::atomic 提供：

std::atomic<T>::compare_exchange_weak(...)
std::atomic<T>::compare_exchange_strong(...)

CAS 的基本思想

CAS 做的是：

如果当前值等于期望值，就把它改成新值；否则不修改，并返回失败。

可以用伪代码表示为：

bool CAS(address, expected, desired) {
    if (*address == expected) {
        *address = desired;
        return true;
    } else {
        expected = *address;
        return false;
    }
}

注意：在 C++ 中，如果 CAS 失败，expected 会被更新为当前实际值。

C++ 中的 CAS 用法

示例：

#include <atomic>
#include <iostream>

int main() {
    std::atomic<int> value{10};

    int expected = 10;
    int desired = 20;

    bool success = value.compare_exchange_strong(expected, desired);

    if (success) {
        std::cout << "CAS success, value = " << value.load() << '\n';
    } else {
        std::cout << "CAS failed, expected updated to " << expected << '\n';
    }

    return 0;
}

执行逻辑：

value == expected  // 10 == 10

成立，所以 value 被修改为 20，CAS 返回 true。

CAS 失败时 expected 会被修改

例如：

std::atomic<int> value{30};

int expected = 10;
int desired = 20;

bool success = value.compare_exchange_strong(expected, desired);

因为：

value != expected  // 30 != 10

所以 CAS 失败，并且：

expected == 30

也就是说，expected 会被更新为当前真实值。

compare_exchange_strong 和 compare_exchange_weak

C++ 提供两个版本：

compare_exchange_strong
compare_exchange_weak

compare_exchange_strong

语义更“强”，只要当前值等于 expected，通常就会成功。

atomic.compare_exchange_strong(expected, desired);

适合普通场景。

---

compare_exchange_weak

可能会出现伪失败，也就是：

即使当前值等于 expected，也可能返回 false。

这是为了适配某些 CPU 架构，提高性能。

因此 compare_exchange_weak 通常放在循环中使用：

std::atomic<int> value{0};

int expected = value.load();

while (!value.compare_exchange_weak(expected, expected + 1)) {
    // CAS 失败后，expected 会被更新为 value 当前值
}

不过上面这个写法有个问题：expected + 1 是基于旧表达式计算的。更常见写法是：

std::atomic<int> value{0};

int expected = value.load();
int desired;

do {
    desired = expected + 1;
} while (!value.compare_exchange_weak(expected, desired));

这相当于原子地执行：

value++;

当然实际中递增可以直接用：

value.fetch_add(1);

CAS 实现无锁加法示例

#include <atomic>
#include <iostream>
#include <thread>
#include <vector>

std::atomic<int> counter{0};

void increment() {
    int old_value = counter.load();
    int new_value;

    do {
        new_value = old_value + 1;
    } while (!counter.compare_exchange_weak(old_value, new_value));
}

int main() {
    std::vector<std::thread> threads;

    for (int i = 0; i < 10; ++i) {
        threads.emplace_back([] {
            for (int j = 0; j < 10000; ++j) {
                increment();
            }
        });
    }

    for (auto& t : threads) {
        t.join();
    }

    std::cout << counter.load() << '\n'; // 100000
}

这里多个线程会竞争修改 counter：

1. 线程读取旧值；
2. 计算新值；
3. 用 CAS 尝试写回；
4. 如果期间值被别的线程改了，CAS 失败；
5. 重新读取并重试。

CAS 的内存序

compare_exchange 可以指定内存序：

atomic.compare_exchange_strong(
    expected,
    desired,
    std::memory_order_success,
    std::memory_order_failure
);

例如：

flag.compare_exchange_strong(
    expected,
    true,
    std::memory_order_acq_rel,
    std::memory_order_acquire
);

常见内存序：

内存序	含义
memory_order_relaxed	只保证原子性，不保证同步顺序
memory_order_acquire	获取语义，防止后面的读写重排到前面
memory_order_release	释放语义，防止前面的读写重排到后面
memory_order_acq_rel	acquire + release
memory_order_seq_cst	最强顺序一致性，默认值

如果不指定，默认是：

std::memory_order_seq_cst

这是最安全但可能性能较低的选择。

CAS 的典型用途

CAS 常用于：

1. 原子计数器；
2. 自旋锁；
3. 无锁栈、队列；
4. 单例初始化；
5. 状态机切换；
6. 引用计数；
7. 实现更高级的同步原语。

例如简单自旋锁：

#include <atomic>

class SpinLock {
private:
    std::atomic<bool> locked{false};

public:
    void lock() {
        bool expected = false;
        while (!locked.compare_exchange_weak(expected, true,
                                             std::memory_order_acquire)) {
            expected = false;
        }
    }

    void unlock() {
        locked.store(false, std::memory_order_release);
    }
};

注意这里每次失败后要重置：

expected = false;

因为 CAS 失败时 expected 会被改成当前值。

CAS 的优点

CAS 的优点：

1. 原子操作，不需要互斥锁；
2. 可以用于实现无锁算法；
3. 避免线程阻塞和上下文切换；
4. 在低竞争场景下性能很好。

CAS 的问题

ABA 问题

CAS 只检查值是否等于 expected。

假设一个变量原来是 A：

线程1读取到 A
线程2把 A 改成 B
线程2又把 B 改回 A
线程1执行 CAS，发现还是 A，于是成功

但实际上数据已经被修改过了。

这就是 ABA 问题。

解决方式包括：

• 使用版本号；
• 使用 tagged pointer；
• 使用 std::shared_ptr 等管理生命周期；
• hazard pointer；
• epoch-based reclamation。

高竞争下可能反复失败

多个线程同时 CAS 同一个变量时，只有一个能成功，其它线程会失败重试。

所以高竞争场景下 CAS 可能导致：

• CPU 空转；
• 自旋消耗；
• 性能下降。

compare_exchange_weak 可能伪失败

所以它一般放在循环中使用。

总结

CAS 是一种原子“比较并交换”操作。

在 C++ 中主要通过：

std::atomic<T>::compare_exchange_weak
std::atomic<T>::compare_exchange_strong

使用。

核心逻辑是：

if (atomic_value == expected)
    atomic_value = desired;
else
    expected = atomic_value;

常见模式：

T expected = obj.load();
T desired;

do {
    desired = f(expected);
} while (!obj.compare_exchange_weak(expected, desired));

它是无锁编程的重要基础，但需要注意：

• expected 会在失败时被修改；
• weak 可能伪失败；
• 需要理解内存序；
• 可能有 ABA 问题；
• 高竞争时不一定比锁更快。