Go和C语言的32 位的无锁、并发、通用队列的源码

22-05-16 banq

在考虑并发队列设计时，我想到了一个通用的、无锁的队列，它适合于32位整数。这个队列是 "通用 "的，因为一个单一的实现支持任何任意类型的元素，尽管它是用C语言实现的。它是无锁的，因为它保证了全系统的进度。它一次最多可以存储32,767个元素--对于必须始终保持约束的消息队列来说，这已经足够了。

我将首先介绍一个单消费者、单生产者的队列，然后以一定的代价将支持扩展到多个消费者。

队列只有32位，怎么能存储这么多元素？它只处理一个循环缓冲区的索引。调用者负责分配和操作队列的存储，在单一消费者的情况下，这不需要任何花哨的东西。同步是由队列管理的。

像一个典型的圆形缓冲区，它有一个头部索引和一个尾部索引。头部是下一个要推送的元素，而尾部是下一个要弹出的元素。队列存储必须有两个幂的长度，但容量比长度少一个。如果头和尾相等，那么队列就是空的。这就 "浪费 "了一个元素，这就是为什么容量比存储的长度少一个。因此，这种设计已经有了一些明显的限制，但我相信这种队列的主要用例--用于CPU绑定的作业队列--对这些限制没有问题。

由于这是一个并发的队列，值得注意的是存储元素的 "所有权"。消费者拥有从尾部到头部的元素，但不包括头部。生产者拥有其他一切。推送和弹出都涉及一个 "提交 "步骤，将一个元素的所有权转移到另一个线程。没有元素被同时访问，这使得任何一个调用者的事情都很容易。

单消费者队列和多消费者队列都支持：
  • 原子：C11、GNU、MSC
  • 线程：pthreads，win32
  • 编译器：GCC、Clang、MSC
  • 主机：Linux、Windows、BSD


源码：queue.c
C 和 Go 之间共享的并发队列：queue.go