实现无锁栈/队列
面试考点
无锁栈和队列是手撕代码面试中的高阶题目。面试官考察你是否能用 CAS 循环实现 push/pop、理解 memory_order 的选择、识别 ABA 问题并给出解决方案,以及无锁数据结构的内存回收策略。
核心概念
无锁栈用一个原子指针 head 指向栈顶。push 时创建新节点指向当前 head,然后 CAS 把 head 换成新节点;pop 时读取 head 和 head->next,CAS 把 head 换成 next。所有操作在 CAS 失败时重试,不使用互斥锁。无锁队列用两个原子指针 head 和 tail 分别指向队首和队尾,入队操作 CAS tail->next,出队操作 CAS head。
基本示例
#include <iostream>
#include <atomic>
#include <thread>
#include <vector>
#include <optional>
#include <cassert>
#include <chrono>
#include <functional>
// ============================
// 无锁栈
// ============================
template<typename T>
class LockFreeStack {
struct Node {
T data;
Node* next;
Node(T val) : data(std::move(val)), next(nullptr) {}
};
std::atomic<Node*> head_{nullptr};
// 待删除节点计数和链表(简化的延迟回收)
std::atomic<unsigned> threads_in_pop_{0};
std::atomic<Node*> to_be_deleted_{nullptr};
// 尝试删除待回收的节点
void try_reclaim(Node* old_head) {
// 如果只有当前线程在 pop,可以安全删除
if (threads_in_pop_.load() == 1) {
// 取走整个待删除链表
Node* nodes_to_delete = to_be_deleted_.exchange(nullptr);
// 再次确认没有其他线程在 pop
if (!--threads_in_pop_) {
// 安全:删除所有待回收节点
delete_nodes(nodes_to_delete);
} else if (nodes_to_delete) {
// 有其他线程进来了,把链表放回去
chain_pending_nodes(nodes_to_delete);
}
delete old_head;
} else {
// 有其他线程在 pop,延迟删除
chain_pending_node(old_head);
--threads_in_pop_;
}
}
// 删除节点链表
static void delete_nodes(Node* nodes) {
while (nodes) {
Node* next = nodes->next;
delete nodes;
nodes = next;
}
}
// 把节点链挂到待删除链表
void chain_pending_nodes(Node* first, Node* last) {
last->next = to_be_deleted_.load();
while (!to_be_deleted_.compare_exchange_weak(
last->next, first)) {}
}
void chain_pending_nodes(Node* nodes) {
Node* last = nodes;
while (Node* next = last->next) {
last = next;
}
chain_pending_nodes(nodes, last);
}
void chain_pending_node(Node* node) {
chain_pending_nodes(node, node);
}
public:
LockFreeStack() = default;
// 禁止拷贝
LockFreeStack(const LockFreeStack&) = delete;
LockFreeStack& operator=(const LockFreeStack&) = delete;
~LockFreeStack() {
// 清空栈
while (pop()) {}
// 清空待删除节点
delete_nodes(to_be_deleted_.load());
}
// 入栈:CAS 循环
void push(T value) {
Node* new_node = new Node(std::move(value));
// 新节点的 next 指向当前栈顶
new_node->next = head_.load(std::memory_order_relaxed);
// CAS:如果 head 没变,把它换成 new_node
// 失败时 new_node->next 被自动更新为当前 head,继续重试
while (!head_.compare_exchange_weak(
new_node->next, // expected(失败时自动更新)
new_node, // desired
std::memory_order_release,
std::memory_order_relaxed
)) {
// 空循环体:CAS 失败自动重试
}
}
// 出栈:CAS 循环 + 延迟回收
std::optional<T> pop() {
// 标记当前线程正在 pop
++threads_in_pop_;
Node* old_head = head_.load(std::memory_order_relaxed);
while (old_head &&
!head_.compare_exchange_weak(
old_head,
old_head->next,
std::memory_order_acquire,
std::memory_order_relaxed
)) {
// CAS 失败:old_head 自动更新,重试
}
if (!old_head) {
--threads_in_pop_;
return std::nullopt; // 栈空
}
T data = std::move(old_head->data);
try_reclaim(old_head); // 尝试回收节点
return data;
}
bool empty() const {
return head_.load(std::memory_order_relaxed) == nullptr;
}
};
// ============================
// 无锁队列(Michael-Scott 算法)
// ============================
template<typename T>
class LockFreeQueue {
struct Node {
std::optional<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:
LockFreeQueue() {
// 初始化:哨兵节点,head 和 tail 都指向它
Node* sentinel = new Node();
head_.store(sentinel, std::memory_order_relaxed);
tail_.store(sentinel, std::memory_order_relaxed);
}
~LockFreeQueue() {
// 从 head 开始逐个删除
Node* node = head_.load();
while (node) {
Node* next = node->next.load();
delete node;
node = next;
}
}
// 禁止拷贝
LockFreeQueue(const LockFreeQueue&) = delete;
LockFreeQueue& operator=(const LockFreeQueue&) = delete;
// 入队
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->next 为空,尝试把新节点挂上去
if (tail->next.compare_exchange_weak(
next, new_node,
std::memory_order_release,
std::memory_order_relaxed
)) {
// 挂成功了,尝试推进 tail
// 即使这一步 CAS 失败也没关系
// 其他线程会帮忙推进
tail_.compare_exchange_strong(
tail, new_node,
std::memory_order_release,
std::memory_order_relaxed
);
return;
}
} else {
// tail 落后了(其他线程已经挂了新节点但还没推进 tail)
// 帮忙推进 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) {
// head == 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 成功后 head 节点可能被其他线程释放
if (next && next->data.has_value()) {
T data = std::move(*next->data);
// 推进 head
if (head_.compare_exchange_weak(
head, next,
std::memory_order_release,
std::memory_order_relaxed
)) {
delete head; // 释放旧哨兵
return data;
}
}
}
}
}
}
bool empty() const {
Node* head = head_.load(std::memory_order_acquire);
Node* next = head->next.load(std::memory_order_acquire);
return next == nullptr;
}
};
// ============================
// 性能对比测试
// ============================
template<typename Stack>
double benchmark_stack(int num_threads, int ops_per_thread) {
Stack stack;
auto start = std::chrono::high_resolution_clock::now();
std::vector<std::thread> threads;
for (int t = 0; t < num_threads; t++) {
threads.emplace_back([&stack, ops_per_thread]() {
for (int i = 0; i < ops_per_thread; i++) {
stack.push(i);
}
for (int i = 0; i < ops_per_thread; i++) {
stack.pop();
}
});
}
for (auto& t : threads) t.join();
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
return duration.count();
}
// ============================
// 测试
// ============================
void test_stack() {
std::cout << "--- 无锁栈测试 ---" << std::endl;
LockFreeStack<int> stack;
// 单线程
for (int i = 0; i < 5; i++) {
stack.push(i);
}
while (auto val = stack.pop()) {
std::cout << *val << " ";
}
std::cout << std::endl;
// 多线程正确性
std::atomic<int> push_sum{0};
std::atomic<int> pop_sum{0};
std::vector<std::thread> threads;
for (int t = 0; t < 4; t++) {
threads.emplace_back([&stack, &push_sum, t]() {
for (int i = 0; i < 1000; i++) {
int val = t * 1000 + i;
stack.push(val);
push_sum += val;
}
});
}
for (auto& t : threads) t.join();
threads.clear();
for (int t = 0; t < 4; t++) {
threads.emplace_back([&stack, &pop_sum]() {
while (auto val = stack.pop()) {
pop_sum += *val;
}
});
}
for (auto& t : threads) t.join();
std::cout << "push 总和: " << push_sum
<< ", pop 总和: " << pop_sum
<< (push_sum == pop_sum ? " (一致)" : " (不一致!)")
<< std::endl;
}
void test_queue() {
std::cout << "\n--- 无锁队列测试 ---" << std::endl;
LockFreeQueue<int> queue;
// 单线程 FIFO 验证
for (int i = 0; i < 5; i++) {
queue.enqueue(i);
}
while (auto val = queue.dequeue()) {
std::cout << *val << " "; // 应该是 0 1 2 3 4
}
std::cout << std::endl;
// 多生产者多消费者
std::atomic<int> total_enqueued{0};
std::atomic<int> total_dequeued{0};
std::vector<std::thread> producers, consumers;
for (int t = 0; t < 4; t++) {
producers.emplace_back([&queue, &total_enqueued]() {
for (int i = 0; i < 1000; i++) {
queue.enqueue(i);
total_enqueued++;
}
});
}
for (auto& t : producers) t.join();
for (int t = 0; t < 4; t++) {
consumers.emplace_back([&queue, &total_dequeued]() {
while (auto val = queue.dequeue()) {
total_dequeued++;
}
});
}
for (auto& t : consumers) t.join();
std::cout << "入队: " << total_enqueued
<< ", 出队: " << total_dequeued
<< (total_enqueued == total_dequeued ? " (一致)" : " (不一致!)")
<< std::endl;
}
void test_performance() {
std::cout << "\n--- 性能测试 ---" << std::endl;
int threads = 4;
int ops = 100000;
double ms = benchmark_stack<LockFreeStack<int>>(threads, ops);
std::cout << "无锁栈: " << threads << " 线程 x " << ops
<< " 操作 = " << ms << "ms" << std::endl;
}
int main() {
test_stack();
test_queue();
test_performance();
return 0;
}无锁栈 vs 无锁队列
| 特性 | 无锁栈 | 无锁队列(MS算法) |
|---|---|---|
| 结构 | 单链表 + 1 个原子指针 | 单链表 + 2 个原子指针 |
| 顺序 | LIFO | FIFO |
| push/enqueue | CAS head | CAS tail->next + 推进 tail |
| pop/dequeue | CAS head | CAS head |
| 哨兵节点 | 不需要 | 需要(简化边界条件) |
| 帮助推进 | 不需要 | 需要(tail 可能落后) |
| 实现复杂度 | 较低 | 较高 |
memory_order 选择
| 操作 | memory_order | 原因 |
|---|---|---|
| push 的 CAS 成功 | release | 保证新节点的写入对其他线程可见 |
| push 的 CAS 失败 | relaxed | 只需要更新 expected |
| pop 的 head 加载 | relaxed/acquire | 后续读取 next 需要看到最新值 |
| pop 的 CAS 成功 | acquire | 保证读到 data 的最新值 |
| threads_in_pop 递增 | 默认(seq_cst) | 保证顺序一致性 |
常见问题
无锁栈的 pop 为什么需要延迟回收?
pop 成功后不能立即 delete 旧 head 节点,因为其他线程可能正在读这个节点的 next 指针。如果立即删除,其他线程读到的是悬垂指针。延迟回收通过引用计数或 threads_in_pop 计数器,在确认没有其他线程访问时才安全删除。
MS 队列中为什么要"帮忙推进 tail"?
入队分两步:1) CAS tail->next 挂新节点;2) CAS tail 指向新节点。如果线程在第 1 步成功后、第 2 步之前被抢占,tail 就落后了。其他线程发现 tail->next 不为空时,会帮忙把 tail 推进到 next,保证算法的正确性。
compare_exchange_weak 和 strong 在这里怎么选?
在循环中用 weak(可能虚假失败但更高效),在单次尝试中用 strong(不会虚假失败)。栈的 push/pop 循环中用 weak,队列帮忙推进 tail 时用 weak(失败了下次循环再推),入队成功后推进自己的 tail 用 strong。
适用场景
- 高频交易系统的消息分发
- 游戏引擎的任务队列
- 日志系统的异步缓冲
- 内存分配器的空闲块管理
注意事项
- 内存回收是无锁编程最难的部分,生产中用风险指针或 epoch-based 方案
- ABA 问题在使用裸指针的 CAS 中存在,需要标签指针或引用计数解决
- memory_order 必须正确,否则在 ARM 等弱内存序平台上会出错
- 无锁不等于无等待(lock-free vs wait-free)
- 优先使用经过验证的库而非自己实现
总结
无锁栈用一个原子 head 指针和 CAS 循环实现 push/pop,关键难点是 pop 后的节点回收。无锁队列(Michael-Scott 算法)用哨兵节点和两个原子指针,入队 CAS tail->next 后推进 tail,出队 CAS head。面试中要能手写无锁栈的 push/pop,画出 ABA 问题的线程交错场景,解释 memory_order 的选择,以及讨论内存回收策略。