手写并发件：SPSC 无锁环 / 有界阻塞队列 / 单写多读快照

并发手写题考察三点：每个共享变量由哪个线程写、每次读写搭配的内存序是否配对、边界（满/空/关闭）如何表达。 原语与理论基础见 并发编程、无锁编程、 内存序。

一、题面与澄清

常见问法：

• A：实现线程安全的环形缓冲区 / 有界队列（可能追加：改为 SPSC 无锁、慢消费者背压）；
• B：实现 SPSCQueue：单生产者单消费者，要求无锁、零分配；
• C：实现一个 key-value 存储，要求单写多读且读端能看到一致快照。

动手前需澄清：

1. 生产者与消费者各有几个（SPSC 可完全无锁；MPMC 复杂度显著更高）；
2. 队满时拒收还是覆盖最旧；
3. 是否需要 close() / 停机语义（缺少时消费者会永久阻塞在条件变量上）；
4. 延迟优先还是吞吐优先（决定自旋、批量、alignas、是否使用 futex）。

二、接口与约束

• 接口：BoundedQueue(capacity)、push(T)、pop()、close()、size()
• 不变量：0 <= size() <= capacity()；队列内部状态的所有访问都在互斥量保护下
• 关闭语义：closed_ 为 true 后 push 必定失败，pop 在排空后返回空
• 复杂度：push / pop 均摊 O(1)；等待为阻塞式，无忙等
• 错误通道：push -> bool（false 表示已关闭）；pop -> optional<T>（空表示已关闭且排空）
• 所有权：push 传值（元素入队）；pop 返回值（元素出队）
• 线程安全：任意线程可 push / pop；析构前须保证无其他线程仍在使用该对象

三、精简版：有界阻塞队列（先交这个）

实现范围：完整实现阻塞式 push / pop 与 close / size；底层用 std::deque。 未实现超时等待（wait_for）、emplace、批量操作与无界模式。

template <class T>
class BoundedQueue {
 public:
  explicit BoundedQueue(std::size_t cap) : cap_(cap) {}

  bool push(T x) {
    std::unique_lock<std::mutex> lk(m_);
    not_full_.wait(lk, [&] { return q_.size() < cap_ || closed_; });   // 谓词循环，防虚假唤醒
    if (closed_) return false;
    q_.push_back(std::move(x));
    lk.unlock();                                    // 先解锁再 notify
    not_empty_.notify_one();
    return true;
  }
  std::optional<T> pop() {
    std::unique_lock<std::mutex> lk(m_);
    not_empty_.wait(lk, [&] { return !q_.empty() || closed_; });
    if (q_.empty()) return std::nullopt;            // 已关闭且排空，供消费者退出
    T x = std::move(q_.front());
    q_.pop_front();
    lk.unlock();
    not_full_.notify_one();
    return x;
  }
  void close() {
    { std::lock_guard<std::mutex> g(m_); closed_ = true; }
    not_empty_.notify_all();                        // 两类等待者都需唤醒
    not_full_.notify_all();
  }
  std::size_t size() const {
    std::lock_guard<std::mutex> g(m_);
    return q_.size();
  }

 private:
  mutable std::mutex m_;
  std::condition_variable not_full_, not_empty_;
  std::deque<T> q_;
  std::size_t cap_;
  bool closed_ = false;
};

技术选型

• 条件变量配 unique_lock 与谓词循环
  • 存在虚假唤醒，且通知可能被其他等待者先消费；wait(lk, pred) 等价于「循环判断谓词」的写法。
• notify 在解锁后调用
  • 若持锁通知，被唤醒的线程会立即又阻塞在互斥量上，产生额外上下文切换。
• 显式的 close() 停机语义
  • 缺少时消费者会永久阻塞；关闭时对两类等待者都 notify_all（否则同侧等待线程不被唤醒）。
• 底层用 std::deque 而非 vector
  • 需要头部 O(1) 弹出；vector 的 pop_front 是 O(n) 搬移。

小问答

• 这个版本差在哪？ 无 wait_for 超时、无 emplace 与批量操作；容量固定，close() 是唯一的停机通道。
• 与 std::queue 的差别？ 多了互斥量、条件变量与关闭语义（std::queue 非线程安全，也没有背压）。
• 与 SPSC 无锁环的差别？ 任意线程可收发但每次操作都要走锁；延迟敏感的单生产单消费热点路径应换无锁版。
• 和 tbb::concurrent_bounded_queue 之类比？ 无取消/中止、无容量动态调整、无并发迭代。

四、完整版：SPSC 无锁环

实现范围：固定容量、单生产者单消费者、无锁、零分配；仅实现 push / pop / empty。 未实现批量收发、size()、水位通知、超时与 MPMC 支持。

template <class T, std::size_t N>              // N 必须是 2 的幂
class SpscRing {
 public:
  bool push(const T& x) {                              // 只有生产者写 tail_
    const std::size_t t = tail_.load(std::memory_order_relaxed);
    const std::size_t h = head_.load(std::memory_order_acquire);   // 读取消费者进度
    if (t - h == N) return false;                      // 满；无符号回绕天然正确
    buf_[t & (N - 1)] = x;                             // 先写数据
    tail_.store(t + 1, std::memory_order_release);     // 再发布：release 保证数据先于下标可见
    return true;
  }
  std::optional<T> pop() {                             // 只有消费者写 head_
    const std::size_t h = head_.load(std::memory_order_relaxed);
    const std::size_t t = tail_.load(std::memory_order_acquire);   // 与上述 release 配对
    if (h == t) return std::nullopt;                   // 空
    T x = buf_[h & (N - 1)];
    head_.store(h + 1, std::memory_order_release);
    return x;
  }
  bool empty() const {
    return head_.load(std::memory_order_acquire) == tail_.load(std::memory_order_acquire);
  }

 private:
  alignas(64) std::atomic<std::size_t> head_{0};       // 各占一条 cache line，避免伪共享
  alignas(64) std::atomic<std::size_t> tail_{0};
  alignas(64) T buf_[N];
};

技术选型

• 不用 CAS，只做 release/acquire 配对
  • 单生产者只写 tail_、单消费者只写 head_，每个下标只有一个写者，因此无需比较交换。
  • 读对端下标用 acquire、写自己下标用 release，即构成完整的同步关系。
• 自身下标使用 relaxed
  • 该下标只被本线程写入，不承担同步他人数据的职责；需要顺序的是「数据 ↔ 对端可见的下标」。
• 容量取 2 的幂，配合 & (N - 1)
  • 下标计算退化为位与；判空判满用无符号减法 t - h == N，回绕天然正确。
• alignas(64) 隔离 head_ / tail_ / 缓冲
  • 若 head_ 与 tail_ 落在同一 cache line，两核会互相使对方的行失效（伪共享），实测吞吐相差数倍。

小问答

• 这个版本差在哪？ 单生产单消费、固定容量；push 失败只表示「满」，没有阻塞语义，背压需上层处理。
• 与 mutex 队列的差别？ 每个下标只有一个写者，因此无需 CAS 与系统调用；代价是不能多生产者、也不能阻塞等待。
• 与 boost::lockfree::spsc_queue 的差别？ 接口更少（无批量 consume_all），缓存行填充只做了 alignas(64)，未压缩下标类型。
• 内存序要点？ 数据与自身下标用 relaxed；对端下标 acquire 读、自己下标 release 写，二者配对。

五、配套：单写多读（发布不可变快照）

实现范围：极简版，只提供 load / publish 两个操作（原子 shared_ptr）。 不含写端序列化（写者自行「拷贝-修改-发布」），也不含 epoch / hazard pointer 回收。

template <class Snapshot>
class PublishedSnapshot {
 public:
  using Ptr = std::shared_ptr<const Snapshot>;

  Ptr load() const { return cur_.load(std::memory_order_acquire); }   // 读端无锁
  void publish(Ptr next) { cur_.store(std::move(next), std::memory_order_release); }

 private:
  std::atomic<std::shared_ptr<const Snapshot>> cur_{std::make_shared<const Snapshot>()};  // C++20
};

技术选型

• 用「不可变快照 + 原子指针」而非原地加锁
  • 写线程执行「拷贝-修改-发布」，读端只做一次 load 即可拿到自洽快照，无需加锁。
  • 旧快照由引用计数兜底，最后一个读者离开时自动回收；该模式是容器与哈希表手写题的并发版本。
• 不使用 seqlock
  • seqlock 的读者会非原子地读取被写者修改的负载，在 C++ 内存模型下构成数据竞争（UB）。
  • 若确需该形态，应改为原子读或依赖编译器屏障，成本与风险都更高。
• 需要更低回收延迟时改用 epoch / hazard pointer
  • shared_ptr 的计数会把旧快照的内存至少留到最后一个读者的临界区结束。

小问答

• 这个版本差在哪？ 只有 load / publish；写端如何构造快照、何时回收旧版本都由调用方决定。
• 与 std::atomic<std::shared_ptr> 的关系？ 本版就是它的最小封装，语义一致（本页封装便于加自定义回收策略）。
• 与读写锁的差别？ 读端零同步（一次原子 load），写端付一次快照拷贝；适合读多写少且快照较小。
• 与 seqlock 的差别？ seqlock 读端无引用计数开销，但非原子读负载在 C++ 内存模型下是数据竞争。

六、高频问答

Q1. 内存序如何选择？

仅自增计数用 relaxed；发布数据用 release；消费数据用 acquire；无法判断时用 seq_cst（最易推理，代价最高）。

Q2. condvar 为什么必须用谓词循环？

存在虚假唤醒，且通知可能被其他等待者先消费；wait(lk, pred) 等价于循环判断谓词。

Q3. notify 是否需要在持锁时调用？

通常在解锁后调用，否则被唤醒的线程可能立即又阻塞在锁上。

Q4. 无锁一定比互斥锁快吗？

不一定。临界区短、竞争低时互斥锁往往更快（少量 futex 调用）； 无锁在高竞争且延迟敏感时才有优势，且调试与内存回收成本更高。

Q5. ABA 问题出现在哪里？

仅出现在 CAS 循环中（值被改回原状导致误判），用版本号或 tagged pointer 解决。 SPSC 环不涉及 CAS，因而没有 ABA 问题。

Q6. 伪共享如何测量？

对比相邻计数器与 alignas(64) 版本的吞吐（通常相差数倍），并用 perf stat 观察 cache miss。

Q7. 并发代码如何验证？

ThreadSanitizer 检测数据竞争，配合压力测试与不变量断言 （如消费顺序严格递增、size <= capacity）。

Q8. 消费者过慢如何处理（背压）？

有界队列天然形成背压（push 阻塞）；无锁环则显式返回 false，由上层决定丢弃、降采样或阻塞重试。

Q9. 自身下标使用 relaxed 是否会漏看对端更新？

不会。对端的更新以 release 写入、本线程以 acquire 读取对端的下标； 自身下标只被本线程写入，因而 relaxed 足够。这是 SPSC 的经典论证。

七、常见错误

错误	后果
condvar 用 if 而非谓词 wait	虚假唤醒后带着无效状态继续执行
缺少 close() / 停机语义	消费者永久阻塞
关闭时用 notify_one	其他等待线程不被唤醒
自身下标写用 seq_cst，或数据与下标之间缺少 release/acquire 配对	前者过度，后者导致读到不完整数据
容量非 2 的幂却使用 & (N-1)	下标计算错误
缺少 alignas(64)	伪共享，吞吐下降
写线程原地修改旧快照	读端观察到撕裂状态
无压力测试与 TSan 验证即认定无锁实现正确	隐藏数据竞争

本页三段实现已实测：SPSC 环（50 万条顺序校验）、有界队列（2 生产者 / 3 消费者 / 4 万条）、 快照发布（写者 5000 次更新 + 3 个读者校验自洽），在 ASan/UBSan 与 TSan 下均无报告。