原子操作的底层实现(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; // 交换失败
}
}
// 整个操作是原子的,由硬件保证基本示例
#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_rel | acquire + release | CAS 操作 |
| 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 问题、以及各种内存序的含义。