原子操作的底层实现(CAS) ​

面试考点 ​

原子操作和 CAS 是并发编程面试的核心话题。面试官考察你是否理解 CAS 的工作原理、compare_exchange_weak 和 strong 的区别、内存序(memory order)的含义、以及无锁编程的基本套路。

核心概念 ​

CAS(Compare-And-Swap)是一条 CPU 指令(如 x86 的 LOCK CMPXCHG),它原子地完成"比较并交换"操作:如果变量的当前值等于期望值,就把它改为新值,否则什么都不做。CAS 是所有无锁数据结构的基础。

CAS 的伪代码 ​

bool CAS(variable, expected, desired) {
    if (variable == expected) {
        variable = desired;
        return true;   // 交换成功
    } else {
        expected = variable;  // 更新 expected 为当前值
        return false;  // 交换失败
    }
}
// 整个操作是原子的,由硬件保证

基本示例 ​

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

// ============================
// 示例1:std::atomic 基本操作
// ============================

void atomic_basic_demo() {
    std::atomic<int> counter{0};

    // load:原子读取
    int val = counter.load();

    // store:原子写入
    counter.store(42);

    // exchange:原子交换,返回旧值
    int old = counter.exchange(100);
    std::cout << "exchange 前: " << old << " 后: " << counter.load() << std::endl;

    // fetch_add:原子加法,返回旧值
    old = counter.fetch_add(10);
    std::cout << "fetch_add 前: " << old << " 后: " << counter.load() << std::endl;

    // fetch_sub:原子减法
    counter.fetch_sub(5);

    // 运算符重载(等价于 fetch_add/fetch_sub)
    counter++;
    counter--;
    counter += 10;
}

// ============================
// 示例2:CAS 操作(compare_exchange)
// ============================

void cas_demo() {
    std::atomic<int> value{100};

    int expected = 100;
    int desired = 200;

    // compare_exchange_strong:只在值真的不匹配时才失败
    bool success = value.compare_exchange_strong(expected, desired);
    std::cout << "CAS 成功: " << success
              << " value=" << value.load()
              << " expected=" << expected << std::endl;
    // 输出: CAS 成功: 1 value=200 expected=100

    // 再次尝试,expected 还是 100,但 value 已经是 200
    expected = 100;
    success = value.compare_exchange_strong(expected, 300);
    std::cout << "CAS 成功: " << success
              << " value=" << value.load()
              << " expected=" << expected << std::endl;
    // 输出: CAS 成功: 0 value=200 expected=200
    // 失败时 expected 被更新为 value 的当前值
}

// ============================
// 示例3:CAS 循环——无锁计数器
// ============================

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

void lock_free_increment(int times) {
    for (int i = 0; i < times; i++) {
        int old_val = global_counter.load(std::memory_order_relaxed);
        // CAS 循环:不断尝试直到成功
        while (!global_counter.compare_exchange_weak(
                   old_val, old_val + 1,
                   std::memory_order_relaxed)) {
            // 失败时 old_val 已被更新为当前值,直接重试
        }
    }
}

void cas_loop_demo() {
    global_counter.store(0);
    const int threads_count = 8;
    const int per_thread = 10000;

    std::vector<std::thread> threads;
    for (int i = 0; i < threads_count; i++) {
        threads.emplace_back(lock_free_increment, per_thread);
    }
    for (auto& t : threads) t.join();

    std::cout << "最终计数: " << global_counter.load()
              << " (期望: " << threads_count * per_thread << ")" << std::endl;
}

// ============================
// 示例4:compare_exchange_weak vs strong
// ============================

/*
compare_exchange_weak:
  - 即使 value == expected 也可能返回 false(虚假失败)
  - 在某些架构上(如 ARM 的 LL/SC)更高效
  - 必须放在循环中使用

compare_exchange_strong:
  - 只有在 value != expected 时才返回 false
  - 不需要循环(如果不需要重试的话)
  - 内部可能有自己的循环来排除虚假失败

选择建议:
  - 在 CAS 循环中:用 weak(性能更好)
  - 不在循环中、只做一次尝试:用 strong
*/

// ============================
// 示例5:内存序
// ============================

/*
C++ 提供 6 种内存序:

memory_order_relaxed  -- 只保证原子性,不保证顺序
memory_order_consume  -- 数据依赖排序(实践中很少用)
memory_order_acquire  -- 读操作:保证后续读写不会重排到此之前
memory_order_release  -- 写操作:保证之前的读写不会重排到此之后
memory_order_acq_rel  -- 同时具有 acquire 和 release 语义
memory_order_seq_cst  -- 顺序一致性(默认,最严格)
*/

// 生产者-消费者模式中的 acquire-release 示例
std::atomic<bool> data_ready{false};
int shared_data = 0;

void producer() {
    shared_data = 42;  // 普通写入
    // release 保证 shared_data 的写入在 store 之前完成
    data_ready.store(true, std::memory_order_release);
}

void consumer() {
    // acquire 保证 data_ready 为 true 后,能看到 shared_data 的值
    while (!data_ready.load(std::memory_order_acquire)) {
        // 自旋等待
    }
    std::cout << "shared_data = " << shared_data << std::endl;  // 保证是 42
}

void memory_order_demo() {
    std::thread t1(producer);
    std::thread t2(consumer);
    t1.join();
    t2.join();
}

// ============================
// 示例6:无锁栈的 push(CAS 典型应用)
// ============================

template<typename T>
class LockFreeStack {
    struct Node {
        T data;
        Node* next;
        Node(const T& d) : data(d), next(nullptr) {}
    };

    std::atomic<Node*> head{nullptr};

public:
    void push(const T& value) {
        Node* new_node = new Node(value);
        new_node->next = head.load(std::memory_order_relaxed);
        // CAS 循环:把 new_node 设为新的 head
        while (!head.compare_exchange_weak(
                   new_node->next, new_node,
                   std::memory_order_release,
                   std::memory_order_relaxed)) {
            // 失败时 new_node->next 被更新为 head 的当前值
            // 直接重试
        }
    }

    bool pop(T& result) {
        Node* old_head = head.load(std::memory_order_relaxed);
        while (old_head != nullptr &&
               !head.compare_exchange_weak(
                   old_head, old_head->next,
                   std::memory_order_acquire,
                   std::memory_order_relaxed)) {
            // 重试
        }
        if (old_head == nullptr) return false;
        result = old_head->data;
        delete old_head;  // 简化处理,实际要考虑 ABA 问题
        return true;
    }
};

void lock_free_stack_demo() {
    LockFreeStack<int> stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);

    int val;
    while (stack.pop(val)) {
        std::cout << val << " ";
    }
    std::cout << std::endl;
    // 输出: 3 2 1(后进先出)
}

int main() {
    std::cout << "=== 基本操作 ===" << std::endl;
    atomic_basic_demo();

    std::cout << "\n=== CAS 操作 ===" << std::endl;
    cas_demo();

    std::cout << "\n=== 无锁计数器 ===" << std::endl;
    cas_loop_demo();

    std::cout << "\n=== 内存序 ===" << std::endl;
    memory_order_demo();

    std::cout << "\n=== 无锁栈 ===" << std::endl;
    lock_free_stack_demo();

    return 0;
}

内存序对比 ​

内存序保证适用场景
relaxed只保证原子性计数器、统计
acquire后续读写不重排到前面消费者端的读取
release之前读写不重排到后面生产者端的写入
acq_relacquire + releaseCAS 操作
seq_cst全局顺序一致(默认)简单场景,性能要求不极端时

常见问题 ​

CAS 循环为什么用 weak 而不是 strong?

在 ARM 等架构上,CAS 用 LL/SC(Load-Linked/Store-Conditional)指令实现。LL/SC 可能因为中断、缓存行竞争等原因虚假失败。weak 不排除虚假失败,所以在这些架构上编译出的代码更简单。反正 CAS 循环本身就会重试,虚假失败不影响正确性。

什么是 ABA 问题?

线程 1 读取值 A,被挂起。线程 2 把值改为 B,又改回 A。线程 1 恢复,CAS 看到值还是 A,认为没有变化。但实际上中间发生了变化。解决方法:使用带版本号的 CAS、hazard pointer、或引用计数。

relaxed 和 seq_cst 的性能差距大吗?

在 x86 上差距不大(x86 的内存模型本身比较强)。在 ARM 等弱内存模型的架构上差距明显,relaxed 不需要内存屏障指令,seq_cst 需要完整的屏障。

适用场景 ​

  • 无锁计数器和统计
  • 无锁队列和栈
  • 自旋锁的实现
  • 标志位和状态机

注意事项 ​

  • CAS 循环中用 weak,单次尝试用 strong
  • 默认 seq_cst 最安全,性能要求高时再降级
  • 无锁编程比看起来难得多,要注意 ABA 问题
  • std::atomic 的 is_lock_free() 可以检查是否真正无锁
  • 不要对不支持原子操作的类型使用 std::atomic

总结 ​

CAS 是原子操作的核心,由 CPU 指令保证原子性。C++ 通过 std::atomic 的 compare_exchange_weak/strong 提供 CAS 操作。CAS 循环是无锁编程的基本模式:读取当前值、计算新值、CAS 替换,失败则重试。内存序控制多线程间的可见性,从 relaxed(最宽松)到 seq_cst(最严格)。面试中要能写出 CAS 循环、解释 weak 和 strong 的区别、说明 ABA 问题、以及各种内存序的含义。