在C中寻找合适的环形缓冲区实现

Question

我正在寻找一个具有以下特性的C中的环形缓冲区实现（或伪代码）：

• 多生产者-单一消费者模式
• 空时的使用者区块
• 生产者完全阻止
• 无锁定（我预计竞争激烈）

到目前为止，我只使用SPSC缓冲区（每个生产者一个），但我想避免消费者在其所有输入缓冲区上检查新数据的持续旋转（也许可以在我的系统中消除一些封送线程）。

我在英特尔机器上为Linux开发。

Answer 1

请参阅liblfds，一个无锁的MPMC环形缓冲区。它根本不会阻塞—无锁数据结构不倾向于这样做，因为无锁的目的是避免阻塞当数据结构返回NULL—如果您尝试在空状态下读取，但在满状态下写入时不符合您的要求，则返回NULL；在这里，它将丢弃最古老的元素，并为您的写作提供这些元素。

然而，只需要一点小小的修改就可以获得这种行为。

但可能还有更好的解决方案。环形缓冲区的棘手部分是在满时获取最旧的前一个元素并重新使用它。你不需要这个。我认为您可以使用SPSC内存屏障专用的循环缓冲区，并使用原子操作对其进行重写。这将比liblfds中的MPMC环形缓冲区（它是队列和堆栈的组合）性能更高。

Answer 2

我想我有你想要的东西。它是一个无锁的环形缓冲区实现，用于阻止生产者/消费者。您只需要访问原子基元——在本例中，我将使用gcc的sync函数。

它有一个已知的错误——如果缓冲区溢出超过100%，就不能保证队列保持FIFO（它最终仍会处理所有这些）。

这个实现依赖于作为原子操作读取/写入缓冲区元素（对于指针来说，这几乎是有保证的）

struct ringBuffer
{
   void** buffer;
   uint64_t writePosition;
   size_t size;
   sem_t* semaphore;
}
//create the ring buffer
struct ringBuffer* buf = calloc(1, sizeof(struct ringBuffer));
buf->buffer = calloc(bufferSize, sizeof(void*));
buf->size = bufferSize;
buf->semaphore = malloc(sizeof(sem_t));
sem_init(buf->semaphore, 0, 0);
//producer
void addToBuffer(void* newValue, struct ringBuffer* buf)
{
   uint64_t writepos = __sync_fetch_and_add(&buf->writePosition, 1) % buf->size;
   //spin lock until buffer space available
   while(!__sync_bool_compare_and_swap(&(buf->buffer[writePosition]), NULL, newValue));
   sem_post(buf->semaphore);
}    
//consumer
void processBuffer(struct ringBuffer* buf)
{
   uint64_t readPos = 0;
   while(1)
   {
       sem_wait(buf->semaphore);
       //process buf->buffer[readPos % buf->size]
       buf->buffer[readPos % buf->size] = NULL;
       readPos++;
   }
}