ブロックなしのスレッドセーフキュー

挑戦する

対話型アプリケーションの開発中、送信または受信ストリームの遅延を回避しながら、あるストリームから別のストリームにデータを転送する必要がありました。 データは1つずつ送信する必要があります。 キューの形で。


あるストリームから別のストリームへの安全なデータ転送に使用される2つの既存のソリューション-相互に排他的なオブジェクト（相互排他オブジェクト）とロックパターンの使用：読み取り/書き込みロックパターンを見つけました。 しかし、これらの解決策は私の問題を解決するのに適していませんでした。 MUTEXオブジェクトは一度に1つのスレッドでしか使用できないため、1つのスレッドがMUTEXオブジェクトを使用する場合、別のスレッドは待機する必要があります。 2番目のオプションには同様の欠点があります-読み取りが進行中の場合、記録スレッドはロックが解除されるまで待機する必要があり、逆も同様です-記録が進行中の場合、読み取りスレッドは記録の終了を待機しています。

既存のソリューションは適合しなかったため、この場合に役立つソリューションを開発する必要がありました。 タスクに基づいて、ソリューションの要件は次のとおりでした。

• 使用されるデータ構造はキューです。
• ソリューションは、1つのストリーム書き込みデータと1つのストリーム読み取りデータをサポートする必要があります。
• このソリューションでは、データの書き込みと読み取りを同時に許可する必要があります。

解決策

この決定は、単方向リンクリストに基づいて構築されたキューに基づいていました。このリストには、別の要素が常に存在していました。 キューが空になることはありませんでした。 キューに要素がないという基準は、キューの先頭と末尾へのポインタが同じ要素を指しているという事実でした。 等しかった：



記録するとき、新しい要素が最初に作成され、その後のみポインタがキューの末尾に転送されます。 末尾へのポインターが最後の瞬間に転送されるという事実により、キューに既にデータがある場合、書き込みと読み取りの競合の可能性が回避されます。



読み取り時には、最初にポインターがキューの先頭に転送され、次にキューの空の要素が削除され、最後にキューからデータが読み取られます。 同時に、読み取られたデータは削除され、「パッケージング」のみが残り、新しい空の要素になります。



その結果、読み取りと書き込みは互いに完全に分離されます。 2つのストリームは、互いに干渉することなく、同時に読み書きできます。 キュー内に少なくとも1つの要素が常に存在するため、競合を回避できます。

実装

キュー要素は、次のようにテンプレートとして実装されました。

template <class E>
class QueueItem
{
public:
E* data;
QueueItem* next;

QueueItem(E* data);
};

template <class E>
QueueItem<E>::QueueItem(E* data)
{
this->data = data;
next = NULL;
}


キューを作成すると、空の要素がすぐに作成されます。

template <class T>
Queue<T>::Queue()
{
QueueItem<T>* stub = new QueueItem<T>(NULL);

head = stub;
tail = stub;
}


空のキューのチェックは、単にキューの先頭と末尾へのポインタを比較することで行われます。

template <class T>
bool Queue<T>::empty()
{
return head == tail;
}


新しい要素を書き込むとき、要素は最初にリストに書き込まれ、次にキューの末尾へのポインタのみが転送されます。

template <class T>
void Queue<T>::enqueue(T* value)
{
QueueItem<T>* item = new QueueItem<T>(value);

item->data = value;
item->next = NULL;

tail->next = item;

tail = item;
}

読書は標準です：

template <class T>
T* Queue<T>::dequeue()
{
if (head == tail)
return NULL; // queue is empty

QueueItem<T>* tmp = head;
head = head->next;
delete tmp;

return head->data;
}


データ転送に使用されるメモリを返す責任はコンシューマスレッドにあることに注意することが重要です。

まとめ

このソリューションは、いくつかの特別な場合、つまり次の場合に適用できるスレッドセーフキュー実装の例です。

• タスクの本質には、キューの使用が含まれます。
• キューへの書き込みと読み取りの遅延を回避する必要があります（たとえば、コンピューターゲームまたは他の対話型プログラム）。
• データを送信するストリームは1つだけで、データを受信するストリームは1つだけです。 この制限は、複数の送信の場合に拡張でき、1つの受信ストリームが各送信ストリームに対して個別のキューを作成します。