实现无锁栈/队列 ​

面试考点 ​

无锁栈和队列是手撕代码面试中的高阶题目。面试官考察你是否能用 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。

基本示例 ​

cpp
#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 个原子指针
顺序LIFOFIFO
push/enqueueCAS headCAS tail->next + 推进 tail
pop/dequeueCAS headCAS 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 的选择,以及讨论内存回收策略。