无锁队列设计与ABA问题解决 ​

面试考点 ​

无锁队列是并发编程的经典面试题。面试官考察你是否理解 CAS(Compare-And-Swap)操作原理、无锁队列的入队/出队算法、ABA 问题的本质及其解决方案(标签指针、风险指针、引用计数),以及无锁 vs 有锁的性能权衡。

核心概念 ​

无锁队列不使用互斥锁来保护共享数据,而是依靠原子操作(特别是 CAS)来实现线程安全。CAS 的语义是"如果当前值等于预期值,就替换为新值,否则什么都不做"。这是一个原子操作,不会被其他线程打断。无锁的好处是避免了锁导致的上下文切换、优先级反转和死锁问题。

ABA 问题是无锁编程中最经典的陷阱:一个值从 A 变成 B 再变回 A,CAS 认为值没有变过,但实际上中间发生了变化,可能导致数据结构损坏。

基本示例 ​

cpp
#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 有锁的权衡。