无锁队列设计与ABA问题解决
面试考点
无锁队列是并发编程的经典面试题。面试官考察你是否理解 CAS(Compare-And-Swap)操作原理、无锁队列的入队/出队算法、ABA 问题的本质及其解决方案(标签指针、风险指针、引用计数),以及无锁 vs 有锁的性能权衡。
核心概念
无锁队列不使用互斥锁来保护共享数据,而是依靠原子操作(特别是 CAS)来实现线程安全。CAS 的语义是"如果当前值等于预期值,就替换为新值,否则什么都不做"。这是一个原子操作,不会被其他线程打断。无锁的好处是避免了锁导致的上下文切换、优先级反转和死锁问题。
ABA 问题是无锁编程中最经典的陷阱:一个值从 A 变成 B 再变回 A,CAS 认为值没有变过,但实际上中间发生了变化,可能导致数据结构损坏。
基本示例
#include <iostream>
#include <atomic>
#include <thread>
#include <vector>
#include <optional>
#include <memory>
#include <cassert>
// ============================
// CAS 操作基础
// ============================
/*
CAS(Compare-And-Swap)伪代码:
bool CAS(T* addr, T expected, T desired) {
// 以下三步是原子的
if (*addr == expected) {
*addr = desired;
return true; // 成功
}
return false; // 失败,expected 被更新为当前值
}
C++ 中对应 std::atomic::compare_exchange_weak/strong
*/
// ============================
// 示例1:简单无锁栈(有 ABA 问题)
// ============================
// 这个实现存在 ABA 问题,仅用于说明原理
template<typename T>
class NaiveLockFreeStack {
struct Node {
T data;
Node* next;
Node(T val) : data(std::move(val)), next(nullptr) {}
};
std::atomic<Node*> head_{nullptr};
public:
// 入栈:CAS 循环
void push(T value) {
Node* new_node = new Node(std::move(value));
new_node->next = head_.load(std::memory_order_relaxed);
// CAS 循环:如果 head 没变,就把 new_node 设为新 head
while (!head_.compare_exchange_weak(
new_node->next, // expected(CAS 失败时被更新)
new_node, // desired
std::memory_order_release,
std::memory_order_relaxed
)) {
// CAS 失败:head 被其他线程修改了
// new_node->next 已被自动更新为当前 head
// 重试
}
}
// 出栈:CAS 循环(有 ABA 问题!)
std::optional<T> pop() {
Node* old_head = head_.load(std::memory_order_relaxed);
while (old_head) {
// 读取 old_head->next
// 问题:如果此时 old_head 被其他线程 pop 后又 push 回来
// old_head 地址相同但 next 可能已经不同了
Node* next = old_head->next;
if (head_.compare_exchange_weak(
old_head, next,
std::memory_order_release,
std::memory_order_relaxed
)) {
T data = std::move(old_head->data);
delete old_head;
return data;
}
// CAS 失败:old_head 已被自动更新,重试
}
return std::nullopt;
}
~NaiveLockFreeStack() {
while (pop().has_value()) {}
}
};
// ============================
// ABA 问题详解
// ============================
/*
ABA 问题场景(以栈为例):
初始状态:head → A → B → C
线程1:开始 pop()
读取 old_head = A
读取 next = B
--- 线程1 被抢占 ---
线程2:pop() 成功,弹出 A
head 变为 → B → C
线程2:pop() 成功,弹出 B
head 变为 → C
线程2:push(A),把 A 放回(可能是内存复用,地址相同)
head 变为 → A → C
线程1 恢复:
CAS(&head, A, B)
head 仍然是 A(地址相同),CAS 成功!
head 变为 → B
但 B 已经被释放了!→ 悬垂指针,未定义行为
核心问题:CAS 只比较值(地址),不知道中间发生了什么变化
*/
// ============================
// 示例2:标签指针解决 ABA
// ============================
// 把指针和一个计数器打包在一起,用 128 位 CAS
// 每次修改指针时计数器加 1,即使指针值相同,计数器也不同
template<typename T>
class TaggedLockFreeStack {
struct Node {
T data;
Node* next;
Node(T val) : data(std::move(val)), next(nullptr) {}
};
// 标签指针:指针 + 版本号
struct TaggedPtr {
Node* ptr;
uintptr_t tag; // 版本计数器
TaggedPtr() : ptr(nullptr), tag(0) {}
TaggedPtr(Node* p, uintptr_t t) : ptr(p), tag(t) {}
bool operator==(const TaggedPtr& other) const {
return ptr == other.ptr && tag == other.tag;
}
};
// 需要 128 位原子操作(x86-64 支持 CMPXCHG16B)
std::atomic<TaggedPtr> head_{TaggedPtr()};
public:
void push(T value) {
Node* new_node = new Node(std::move(value));
TaggedPtr old_head = head_.load(std::memory_order_relaxed);
TaggedPtr new_head;
do {
new_node->next = old_head.ptr;
new_head = TaggedPtr(new_node, old_head.tag + 1);
// tag 每次递增,即使 ptr 相同,tag 也不同
} while (!head_.compare_exchange_weak(
old_head, new_head,
std::memory_order_release,
std::memory_order_relaxed
));
}
std::optional<T> pop() {
TaggedPtr old_head = head_.load(std::memory_order_relaxed);
TaggedPtr new_head;
do {
if (!old_head.ptr) return std::nullopt;
new_head = TaggedPtr(old_head.ptr->next, old_head.tag + 1);
// 即使 ptr 被 pop 再 push 回来(ABA),tag 已经不同了
// CAS 会失败,避免了 ABA 问题
} while (!head_.compare_exchange_weak(
old_head, new_head,
std::memory_order_release,
std::memory_order_relaxed
));
T data = std::move(old_head.ptr->data);
delete old_head.ptr;
return data;
}
~TaggedLockFreeStack() {
while (pop().has_value()) {}
}
};
// ============================
// 示例3:引用计数解决 ABA
// ============================
// 在释放节点前检查是否有其他线程还在引用它
template<typename T>
class RefCountLockFreeStack {
struct Node {
T data;
std::atomic<Node*> next;
std::atomic<int> external_refs; // 外部引用计数
Node(T val) : data(std::move(val)), next(nullptr), external_refs(0) {}
};
std::atomic<Node*> head_{nullptr};
public:
void push(T value) {
Node* new_node = new Node(std::move(value));
new_node->next.store(head_.load(std::memory_order_relaxed),
std::memory_order_relaxed);
while (!head_.compare_exchange_weak(
new_node->next, new_node,
std::memory_order_release,
std::memory_order_relaxed
)) {}
}
std::optional<T> pop() {
Node* old_head = head_.load(std::memory_order_relaxed);
while (old_head) {
// 增加引用计数,防止节点被释放
old_head->external_refs.fetch_add(1, std::memory_order_acquire);
// 重新读取 head,确认没有变化
Node* current_head = head_.load(std::memory_order_relaxed);
if (current_head != old_head) {
// head 已变,减引用计数,重试
old_head->external_refs.fetch_sub(1, std::memory_order_release);
old_head = current_head;
continue;
}
Node* next = old_head->next.load(std::memory_order_relaxed);
if (head_.compare_exchange_weak(
old_head, next,
std::memory_order_release,
std::memory_order_relaxed
)) {
T data = std::move(old_head->data);
// CAS 成功,减引用计数
// 如果引用计数为 1(只有自己在用),可以安全删除
if (old_head->external_refs.fetch_sub(1,
std::memory_order_release) == 1) {
delete old_head;
}
// 否则最后一个使用者会删除它
return data;
}
// CAS 失败,减引用计数,重试
old_head->external_refs.fetch_sub(1, std::memory_order_release);
}
return std::nullopt;
}
~RefCountLockFreeStack() {
while (pop().has_value()) {}
}
};
// ============================
// 示例4:Michael-Scott 无锁队列(简化版)
// ============================
// 经典的 MPMC 无锁队列算法
template<typename T>
class MSQueue {
struct Node {
T data;
std::atomic<Node*> next;
Node() : next(nullptr) {}
Node(T val) : data(std::move(val)), next(nullptr) {}
};
// 哨兵节点:简化边界条件
std::atomic<Node*> head_;
std::atomic<Node*> tail_;
public:
MSQueue() {
// 初始化:head 和 tail 都指向哨兵节点
Node* sentinel = new Node();
head_.store(sentinel, std::memory_order_relaxed);
tail_.store(sentinel, std::memory_order_relaxed);
}
~MSQueue() {
// 清理所有节点
Node* node = head_.load();
while (node) {
Node* next = node->next.load();
delete node;
node = next;
}
}
// 入队
void enqueue(T value) {
Node* new_node = new Node(std::move(value));
while (true) {
Node* tail = tail_.load(std::memory_order_acquire);
Node* next = tail->next.load(std::memory_order_acquire);
// 确认 tail 没有被其他线程修改
if (tail == tail_.load(std::memory_order_relaxed)) {
if (next == nullptr) {
// tail 是真正的最后一个节点
// 尝试把 new_node 链接到 tail->next
if (tail->next.compare_exchange_weak(
next, new_node,
std::memory_order_release,
std::memory_order_relaxed
)) {
// 成功,推进 tail 指针
tail_.compare_exchange_strong(
tail, new_node,
std::memory_order_release,
std::memory_order_relaxed
);
return;
}
} else {
// tail 落后了,帮忙推进
tail_.compare_exchange_weak(
tail, next,
std::memory_order_release,
std::memory_order_relaxed
);
}
}
}
}
// 出队
std::optional<T> dequeue() {
while (true) {
Node* head = head_.load(std::memory_order_acquire);
Node* tail = tail_.load(std::memory_order_acquire);
Node* next = head->next.load(std::memory_order_acquire);
if (head == head_.load(std::memory_order_relaxed)) {
if (head == tail) {
// 队列为空或 tail 落后
if (next == nullptr) {
return std::nullopt; // 空队列
}
// tail 落后了,帮忙推进
tail_.compare_exchange_weak(
tail, next,
std::memory_order_release,
std::memory_order_relaxed
);
} else {
// 读取数据(在 CAS 之前,因为 CAS 成功后节点可能被删)
T data = next->data;
// 尝试推进 head
if (head_.compare_exchange_weak(
head, next,
std::memory_order_release,
std::memory_order_relaxed
)) {
delete head; // 释放旧哨兵
return data;
}
}
}
}
}
};
// ============================
// 使用演示
// ============================
void demo() {
MSQueue<int> queue;
// 多线程入队
std::vector<std::thread> producers;
for (int i = 0; i < 4; i++) {
producers.emplace_back([&queue, i]() {
for (int j = 0; j < 100; j++) {
queue.enqueue(i * 100 + j);
}
});
}
for (auto& t : producers) t.join();
// 单线程出队验证
int count = 0;
while (queue.dequeue().has_value()) {
count++;
}
std::cout << "出队元素数: " << count << "(期望 400)" << std::endl;
}
void tagged_stack_demo() {
TaggedLockFreeStack<int> stack;
std::vector<std::thread> threads;
for (int i = 0; i < 4; i++) {
threads.emplace_back([&stack, i]() {
for (int j = 0; j < 50; j++) {
stack.push(i * 50 + j);
}
for (int j = 0; j < 50; j++) {
stack.pop();
}
});
}
for (auto& t : threads) t.join();
std::cout << "标签指针栈测试完成" << std::endl;
}
int main() {
std::cout << "=== MS 无锁队列 ===" << std::endl;
demo();
std::cout << "\n=== 标签指针栈 ===" << std::endl;
tagged_stack_demo();
return 0;
}ABA 问题解决方案对比
| 方案 | 原理 | 优点 | 缺点 |
|---|---|---|---|
| 标签指针 | 指针+版本号,128位CAS | 简单直接 | 需要硬件支持双字CAS |
| 风险指针 | 线程公布正在使用的指针 | 内存回收确定性好 | 实现复杂,每线程开销 |
| 引用计数 | 引用为0时才释放 | 不需要双字CAS | 原子计数有开销 |
| 延迟回收(RCU) | 等所有线程离开临界区再释放 | 读端零开销 | 写端延迟高 |
| 内存池复用 | 不释放节点,只放回池 | 避免地址复用 | 内存不回收 |
无锁 vs 有锁
| 特性 | 有锁(mutex) | 无锁(lock-free) |
|---|---|---|
| 死锁风险 | 有 | 无 |
| 优先级反转 | 有 | 无 |
| 线程崩溃影响 | 可能锁死 | 不影响其他线程 |
| 竞争低时性能 | 更好(无原子操作开销) | 略差 |
| 竞争高时性能 | 差(上下文切换) | 好(自旋重试) |
| 实现复杂度 | 低 | 高 |
| 正确性验证 | 相对容易 | 极其困难 |
常见问题
什么是 lock-free 和 wait-free 的区别?
lock-free 保证系统整体在做进展:至少有一个线程在有限步内完成操作(其他线程可能在自旋重试)。wait-free 保证每个线程都在有限步内完成操作。wait-free 更强但更难实现。大多数无锁数据结构是 lock-free 的。
compare_exchange_weak 和 strong 有什么区别?
weak 版本在某些平台上可能虚假失败(即使值相等也返回 false),但在循环中使用时更高效。strong 版本不会虚假失败,但可能稍慢。在 CAS 循环中用 weak,在单次尝试中用 strong。
无锁数据结构一定比有锁的快吗?
不一定。在低竞争场景下,mutex 的开销很小(只是一个原子操作),而无锁算法需要更复杂的原子操作序列。在高竞争场景下,无锁通常更好,因为避免了上下文切换。选择取决于实际的竞争程度和性能测量。
适用场景
- 高频交易系统(延迟敏感)
- 实时系统(不能容忍优先级反转)
- 高并发消息队列
- 多生产者-多消费者场景
注意事项
- 内存序(memory_order)必须正确,否则在弱内存序平台上会出错
- ABA 问题必须解决,否则会导致数据结构损坏
- 无锁编程极其容易出错,没有经过充分验证不要用于生产
- 节点的内存回收是无锁编程最难的部分
- 优先使用经过验证的库(如 Boost.Lockfree、moodycamel::ConcurrentQueue)
总结
无锁队列用 CAS 原子操作替代互斥锁,避免了死锁和优先级反转。ABA 问题是无锁编程的经典陷阱:值从 A→B→A,CAS 误认为没有变化。解决方案有标签指针(指针+版本号做 128 位 CAS)、引用计数(引用为 0 才释放)、风险指针(线程公布正在使用的指针)。面试中要能解释 ABA 问题的场景、画出具体的线程交错示例、说明至少一种解决方案,以及讨论无锁 vs 有锁的权衡。