コンシューマのみをブロックする単一のプロデューサ/コンシューマ循環バッファ

Question

コンシューマのみがブロックされる単一のプロデューサと単一のコンシューマでバッファを実装したいと考えています。ここで重要な点は、キューがいっぱいになるとプロデューサが更新を削除できることです。

私は待ち時間のない実装の変換を検討しましたが、一見して、消費者に通知を失うことなく新しいデータが到着したことを通知する簡単な方法はないようです。

Object ar[SIZE]; 
int head = 0, tail = 0; 
sem_t semItems; // initialized to 0 

void enqueue(Object o) { 
    int val; 
    sem_getvalue(&semItems, &val); 
    if (val < SIZE - 1) { 
     ar[head] = o; 
     head = (head + 1) % SIZE; 
     sem_post(&semItems); 
    } 
    else { 
     // dropped 
    } 
} 
Object dequeue(void) { 
    sem_wait(&semItems); 
    Object o = ar[tail]; 
    tail = (tail + 1) % SIZE; 
    return o; 
} 

は、このコードのいずれかの安全性の問題があります。だから私は（いくつかのエラー処理の詳細については、明確にするために省略）カウンティングセマフォを使用して、以下の非常に単純なアプローチに定住しましたか？私は普及した文献のどこにでもそのような実装を見ないことに驚いた。もう1つの疑問は、 sem_post()がブロックするかどうかです（linuxでは futex_wake()を呼び出します）。簡単なソリューションももちろん歓迎します。

編集：リーダーとライターの間にスペースを残して編集したコードです（Mayurkの回答を参照）。

Answer 1

この実装では1つの問題があります。次のシーケンスを考えてみましょう。

1. バッファーはいっぱいですが、コンシューマーはまだ開始されていないものとします。したがって（head = 0、tail = 0、sem_val = SIZE）。
2. dequeue（）はコンシューマスレッドから呼び出されます。 sem_wait（）は成功します。だからそのインスタンス（head = 0、tail = 0、sem_val = SIZE-1）。消費者はar [0]の読み込みを開始します。
3. スレッドスイッチがあります。 enqueue（）はプロデューサスレッドから呼び出されます。 sem_getvalue（）はSIZE-1を返します。だから、プロデューサーはar [0]に書きます。

基本的には、読み書き操作のためのmutex保護が必要だと思います。しかし、mutexを追加するとスレッドがブロックされる可能性があります。だから私はあなたがこのロジックから期待される行動を取るかどうかはわかりません。