c - 在 C 中寻找正确的环形缓冲区实现

Question

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

• 多生产者单消费者模式（MPSC）
• 消费者阻塞空
• 生产者完全封锁
• 无锁（我期待高争用）

到目前为止，我一直只使用 SPSC 缓冲区 - 每个生产者一个 - 但我想避免消费者连续旋转以检查其所有输入缓冲区中的新数据（并且可能摆脱我的一些编组线程系统）。

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

Answer 1

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

但是，只需稍作修改即可获得该行为。

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

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++;
   }
}