8

次の特性を持つ C でのリング バッファーの実装 (または疑似コード) を探しています。

  • 複数のプロデューサー、単一のコンシューマー パターン (MPSC)
  • 空のコンシューマー ブロック
  • プロデューサーは完全にブロックします
  • ロックフリー (高い競合が予想される)

これまでのところ、SPSC バッファー (プロデューサーごとに 1 つ) のみを使用して作業してきましたが、すべての入力バッファーで新しいデータをチェックするために、コンシューマーが連続して回転するのを避けたいと思います (おそらく、私のいくつかのマーシャリング スレッドを取り除くために)。システム）。

Intel マシン上の Linux 向けに開発しています。

4

2 に答える 2

4

liblfds、ロックフリー MPMC リングバッファを参照してください。ロックフリーのポイントはブロックを回避することなので、ロックフリーのデータ構造はこれを行う傾向がありません。これを処理するNULL必要があります。空で読み取ろNULLうとするとデータ構造が返されますが、完全に書き込むと要件が一致しません。ここでは、最も古い要素を破棄し、それを書き込み用に提供します。

ただし、その動作を取得するには、わずかな変更しか必要ありません。

しかし、より良い解決策があるかもしれません。リングバッファのトリッキーな部分は、いっぱいになったときに最も古い要素を取得して再利用することです。これは必要ありません。SPSC メモリ バリアのみの循環バッファを使用して、アトミック操作を使用して書き換えることができると思います。これは、MPMC リングバッファー(キューとスタックの組み合わせ)よりもはるかにパフォーマンスが高くなります。liblfds

于 2012-09-07T07:39:47.343 に答える
3

私はあなたが探しているものを持っていると思います。プロデューサ/コンシューマをブロックするロックフリーのリングバッファ実装です。アトミック プリミティブへのアクセスのみが必要です。この例では、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++;
   }
}
于 2012-09-05T05:47:27.013 に答える