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

Question

我在C中寻找具有以下特征的环形缓冲区实现(或伪代码):

• 多生产者单一消费模式(MPSC)
• 消费者阻止空
• 生产者完全阻止
• 无锁(我期望高争用)

到目前为止,我一直只使用SPSC缓冲区 - 每个生产者一个 - 但我想避免消费者不断旋转以检查所有输入缓冲区的新数据(也许是为了摆脱我的一些编组线程)系统).

我在Intel机器上开发Linux.

Answer 1

我想我有你正在寻找的东西。它是一个无锁环形缓冲区实现，会阻止生产者/消费者。您只需要访问原子原语 - 在本例中我将使用 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++;
   }
}