CAS

CAS（Compare-And-Swap，更准确地说是 Compare-And-Exchange，比较并交换）是一种原子读-比较-条件写入操作：仅当原子对象仍等于期望值时才写入新值。它是无锁算法的基础工具，但不是比 mutex 更通用或必然更快的替代品。

基本语义

std::atomic<T> 提供以下成员函数：

1
2
3
4
5
6
bool compare_exchange_weak(T& expected, T desired,
                           std::memory_order success,
                           std::memory_order failure);
bool compare_exchange_strong(T& expected, T desired,
                             std::memory_order success,
                             std::memory_order failure);

也可省略内存序，默认使用 std::memory_order_seq_cst。expected 是输入输出参数：调用前提供希望匹配的值；失败后会被写成观察到的实际值。desired 是仅输入的目标值。成功时返回 true 并写入 desired；失败时返回 false，原子对象不变。

1
2
3
4
5
6
7
8
9
10
11
#include <atomic>
#include <iostream>

int main() {
    std::atomic<int> value{30};
    int expected = 10;
    const int desired = 20;
    if (!value.compare_exchange_strong(expected, desired)) {
        std::cout << "失败，实际值为: " << expected << '\n'; // 30
    }
}

等价伪代码（整体是不可分割的原子操作）：

1
2
3
4
5
6
if (object == expected) {
    object = desired;
    return true;
}
expected = object;
return false;

weak 与 strong

compare_exchange_weak 除了真实竞争失败外还允许伪失败：值相等时也可能返回 false。因此它几乎总是放在循环中。strong 不允许伪失败，适合只尝试一次的逻辑；循环中也可以使用它。实际性能差异依赖 CPU 与编译器，不能预设。

1
2
3
4
5
6
7
8
9
10
11
12
#include <atomic>

void increment(std::atomic<int>& counter) {
    int expected = counter.load();
    do {
        const int desired = expected + 1;
        // 失败时 expected 自动更新，下一轮据此重新计算 desired。
        if (counter.compare_exchange_weak(expected, desired)) {
            return;
        }
    } while (true);
}

递增不需要自定义逻辑时，counter.fetch_add(1) 更清楚。CAS 循环适用于“读取旧状态、计算新状态、仅当状态未变才提交”的更新。

内存序

原子性解决单个操作不被拆分；内存序解决跨线程对其他读写的可见性与排序。先以默认 seq_cst 保证正确，再在证明需要时收紧为更弱的序。

内存序 保证 典型用途
relaxed 仅原子性 独立统计计数
release 当前线程此前写入不会被重排到该操作之后 发布已初始化数据
acquire 当前线程随后读写不会被重排到该操作之前 读取已发布状态
acq_rel 同时具有 acquire 与 release 成功的读改写发布/获取
seq_cst 额外提供全局单一顺序 默认，最易推理

对于带双内存序的 CAS：成功序适用于读改写；失败序只进行读取，不能是 release 或 acq_rel，且不能比成功序更强。例如常见的发布状态转换：

1
2
3
4
5
6
bool expected = false;
if (ready.compare_exchange_strong(expected, true,
                                  std::memory_order_release,
                                  std::memory_order_relaxed)) {
    // 仅说明状态转换成功；要发布的数据必须在 release 操作之前写入。
}

接收方必须以 acquire 方式读取到该 release 写入的值，才形成发布-获取同步。内存序设计很容易出错；复杂状态或数据结构优先使用 mutex，相关基础见同步机制。

自旋与高竞争

CAS 失败后立即重试会消耗 CPU。低竞争、临界更新很短时它可能有效；高竞争或单核环境下，自旋可能比阻塞锁更差。必要时可在失败后退避、yield 或改用分片计数/互斥锁，但这些选择都应由压测决定。

下面的自旋锁仅用于理解 acquire/release，不推荐作为通用锁：它不保证公平，在持锁线程被抢占时会浪费 CPU，也不适合长临界区。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <atomic>

class SpinLock {
public:
    void lock() {
        for (;;) {
            bool expected = false;
            if (locked_.compare_exchange_weak(expected, true,
                                              std::memory_order_acquire,
                                              std::memory_order_relaxed)) {
                return;
            }
        }
    }

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

private:
    std::atomic<bool> locked_{false};
};

注意每次尝试都重新把 expected 设为 false；CAS 失败会改写它。实际工程还需要 RAII 守卫，避免异常路径忘记解锁。

ABA 与内存回收

CAS 只比较当前值是否相等。若线程 A 读到 A，线程 B 将其改为 B 再改回 A，线程 A 的 CAS 仍可能成功；这就是 ABA 问题。对指针结构，它还常与“节点已释放又被复用”的生命周期问题同时出现。

可选方案包括版本号/tagged pointer、hazard pointers、epoch-based reclamation 或改用成熟并发容器。std::shared_ptr 有时可帮助管理对象生命期，但不自动解决算法逻辑上的 ABA，且原子共享指针操作有其开销。

常见误区与实践建议

  • 不要把“原子”理解为“整个算法线程安全”；多个原子变量仍可能无法共同维持不变量。
  • is_lock_free() 为 false 不代表错误，只说明实现可能借助内部锁。
  • 无锁（lock-free）表示系统整体通常能推进，不保证每个线程都能在有限步完成；这与 wait-free 不同。
  • 不要为简单计数器手写 CAS 循环，优先 fetch_add；不要为复杂容器随意手写无锁结构。
  • 对性能结论进行真实负载基准测试，尤其关注竞争、缓存行和线程调度。