10. 线程安全的数据结构：从栈到队列，再到无锁编程

线程安全的数据结构，说白了就是能让多个线程同时读写，还不出乱子的容器。我刚开始接触并发编程时，觉得这玩意儿不就是给每个操作加个锁嘛，有什么难的？后来在项目中踩过几次坑，才明白事情没那么简单。

10.1 线程安全的栈：最基础的并发容器

先聊聊栈。栈的特点是后进先出，操作就那么几个：push、pop、top、empty。但一旦涉及多线程，每个操作都得小心。

我见过最典型的错误写法是这样的：

// 错误示范：这样写线程不安全
std::stack<int> s;
void push(int v) {
    std::lock_guard<std::mutex> lk(mtx);
    s.push(v);
}
int pop() {
    std::lock_guard<std::mutex> lk(mtx);
    auto v = s.top();
    s.pop();
    return v;
}

问题出在哪？你想想看，如果两个线程同时调用pop，第一个线程刚拿到top值，还没来得及pop，第二个线程也调了top——这时候两个线程拿到的值是一样的。更糟的是，如果栈里只有一个元素，两个线程都调了top，然后一个pop了，另一个再pop就崩溃了。

⚠️ 我曾经踩过的坑： 别以为加锁就万事大吉。锁只保护了单个操作的原子性，但top和pop之间不是原子的。正确的做法是把top和pop合并成一个原子操作。

正确的线程安全栈应该这样设计：

template<typename T>
class threadsafe_stack {
    std::stack<T> data;
    mutable std::mutex mtx;
public:
    void push(T v) {
        std::lock_guard<std::mutex> lk(mtx);
        data.push(std::move(v));
    }

    std::shared_ptr<T> pop() {
        std::lock_guard<std::mutex> lk(mtx);
        if (data.empty()) return nullptr;
        auto sp = std::make_shared<T>(std::move(data.top()));
        data.pop();
        return sp;
    }

    bool empty() const {
        std::lock_guard<std::mutex> lk(mtx);
        return data.empty();
    }
};

这里有个小技巧：pop返回的是shared_ptr，而不是直接返回值。为什么？因为拷贝返回值本身也可能抛异常。用智能指针，就算拷贝失败，栈里的数据也不会丢。

10.2 线程安全的队列：生产者-消费者的核心

队列比栈稍微复杂一点。队列是先进先出，常用于生产者-消费者模型。我参与过一个日志系统，就是用线程安全队列来解耦日志写入和业务逻辑的。

先看一个基础版本：

template<typename T>
class threadsafe_queue {
    std::queue<T> data;
    mutable std::mutex mtx;
    std::condition_variable cv;
public:
    void push(T v) {
        std::lock_guard<std::mutex> lk(mtx);
        data.push(std::move(v));
        cv.notify_one();
    }

    T pop() {
        std::unique_lock<std::mutex> lk(mtx);
        cv.wait(lk, [this]{ return !data.empty(); });
        T v = std::move(data.front());
        data.pop();
        return v;
    }
};

这里用到了条件变量。当队列为空时，消费者线程会阻塞等待，直到生产者push了数据并通知。嗯，这里要注意：wait的第二个参数是个谓词，用来防止虚假唤醒。我在早期写代码时没加这个谓词，结果程序偶尔会从空队列里取数据，排查了好久才发现是虚假唤醒的问题。

💡 个人经验： 条件变量的wait一定要配合谓词使用。别偷懒，否则线上环境会给你颜色看。

10.3 无锁编程的初步探索

锁虽然好用，但性能开销不小。锁竞争会导致线程阻塞，严重时甚至引发优先级反转。我做过一个高频交易系统，锁的竞争直接拖慢了整个系统的吞吐量。那时候我开始研究无锁编程。

无锁编程的核心是CAS（Compare-And-Swap）操作。C++11提供了std::atomic，底层就是CAS。

举个最简单的例子：无锁计数器

std::atomic<int> counter{0};

void increment() {
    int old = counter.load();
    while (!counter.compare_exchange_weak(old, old + 1)) {
        // 如果CAS失败，old会被更新为当前值，继续重试
    }
}

compare_exchange_weak这个函数，说白了就是：如果当前值等于old，就把它改成old+1，返回true；否则把old更新为当前值，返回false。这个循环就是自旋锁的思想。

但无锁数据结构远不止这么简单。以无锁栈为例，它的核心思想是用原子指针来管理链表：

template<typename T>
class lockfree_stack {
    struct node {
        T data;
        node* next;
    };
    std::atomic<node*> head{nullptr};
public:
    void push(T v) {
        node* new_node = new node{std::move(v), nullptr};
        new_node->next = head.load();
        while (!head.compare_exchange_weak(new_node->next, new_node)) {
            // 重试直到成功
        }
    }
};

这里有个关键点：CAS操作的是head指针。如果多个线程同时push，只有一个能成功更新head，其他的会重试。这比用锁要轻量得多。

⚠️ 注意： 无锁编程有个大坑叫ABA问题。简单说就是：线程A读到指针P，然后被挂起；线程B把P释放了又分配了一个新节点，地址恰好也是P；线程A醒来后CAS成功，但此时P指向的内容已经变了。解决方法是使用带标记的指针（如std::atomic<std::uintptr_t>），或者用 hazard pointer。

10.4 知识体系总览

下面这张图总结了本章的核心脉络：

线程安全数据结构知识体系 线程安全栈 • push/pop原子化 • 返回shared_ptr避免异常 • 锁保护整个操作 • 避免top+pop分离 线程安全队列 • 生产者-消费者模型 • 条件变量+谓词 • 防止虚假唤醒 • notify_one/notify_all 无锁编程 • CAS原子操作 • compare_exchange_weak • ABA问题 • hazard pointer 核心原则 1. 锁保护的是数据，不是代码 2. 尽量缩小临界区 3. 无锁不等于没有竞争，只是没有阻塞 4. 优先用锁，性能瓶颈时再考虑无锁

10.5 避坑指南与最佳实践

最后，分享几个我在实战中总结的经验：

  • 能用锁就别用无锁。无锁编程的调试难度是指数级的。我见过一个团队花了两周排查一个ABA问题，最后发现加个锁就能解决。
  • 锁的粒度要细。别一把锁锁住整个数据结构。可以试试读写锁（shared_mutex），读多写少时性能提升明显。
  • 注意死锁。如果两个线程各自持有一个锁，又都在等对方的锁，就死锁了。我习惯用std::lock一次性锁住多个互斥量，或者用std::scoped_lock。
  • 测试要覆盖并发场景。单线程跑得欢，多线程就崩，这是并发编程的常态。用ThreadSanitizer这类工具跑一跑，能发现很多隐藏问题。

📌 一句话总结： 线程安全的数据结构，核心就两件事——要么用锁保护好临界区，要么用CAS实现无锁操作。但无论哪种方式，都要把数据一致性放在第一位。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →