C++ 实现 SPSC 与 MPSC:从所有权交接到内存序
SPSC 是单生产者、单消费者;MPSC 是多生产者、单消费者。它们描述的是线程访问约束,不代表一定无锁,也不决定队列必须用数组还是链表。 实现并发队列,关键不是把下标换成 atomic,而是回答三个问题:谁能写这块内存?写完怎样交给别人?什么时候可以复用或释放? 本文实现两个存储 std::uint64_t 的 C++17 队列:有界 SPSC 环形队列,以及基于原子交换的无界 MPSC 链式队列。固定元素类型是为了把注意力放在同步协议上,而不是泛型对象的构造、异常和析构。两者都要求构造完成后再交给工作线程,析构前停止并等待所有访问者退出。 一、SPSC:把共享队列拆成两块单写者状态 环形队列维护两个下标:write_index 指向下一个可写槽位,read_index 指向下一个可读槽位。只有生产者修改前者,只有消费者修改后者;另一方只读取。 这种单写者约束消除了“两个线程抢同一个写下标”的问题,因此更新下标不需要 CAS,也不需要 fetch_add。但下标仍然被跨线程读写,需要是原子变量。 使用 Slots 个物理槽位,始终留一个空位: 状态 判定 空 read_index == write_index 满 next(write_index) == read_index 实际容量 Slots - 1 例如物理槽位为 8 个,当前读下标是 2、写下标是 5: slot: 0 1 2 3 4 5 6 7 contents: . . A B C . . . ^ ^ read_index write_index readable: [2, 5) next push: slot 5 next pop: slot 2 留空位不是同步手段,只是用最简单的编码区分空和满。真正的同步发生在下标发布时。 ...