マルチスレッド対応のキュー

 ここでは、Queueの基本的確認とそのマルチスレッド対応について検討し、Enqueue/Dequeue時のブロックについて記載する。

定義

Wikipedia の キュー (コンピュータ) によると以下のような特徴を持つデータ構造だという事が分かる

• FIFO
  先入れ先だし(最初に入れたアイテムが最初に取出される
• キューにアイテムを入れる操作を enqueue
• キューからアイテムを取り出す操作を dequeue

これを図にすると以下のようになるかと思う

場合によっては、キューのサイズも重要な情報となるかもしれないが、ここではオプショナルとする。

実装方法

キューの実装方法として、配列やリスト等を用いた方法が考えられる

配列

配列の要素番号順にアイテムを入れていく方式である。以下のような実現になるかと考えられる。

first , last のポジション情報が重要になり、FIFOを実現することとなる。

リスト

先頭と末尾を覚えておき、Enqueueでは、末尾に、Dequeue では先頭から取得する。

この時も、first,lastのポジション情報が重要となりFIFOを実現する。

マルチスレッド対応Queue

キューのマルチスレッド対応を検討する時、複数から利用されるであろう共有リソース（主にfirst,last)をどのように排他するか？という点のみに注目しがちである。しかし上記のみでは不十分であり、Enqueue時にキューが一杯であるや Dequeue 時に空っぽの時について考慮が必要である。

この時の挙動として2案上げておく

案1 Full,Empty の情報を返却

この方法は、Enqueue,Dequeue が FULL または EMPTY の情報を即時に返却する方法である。この方法は、利用者が戻り値を見て、自分で情報を元に判断する必要がある。

案2 Full,Empty 時にブロック

この方法は、Enqueue,Dequeueがブロックする方法である。 Equeue時には、1つ以上の空きが出来るまでAPIが復帰してこず、Dequeue時には1つ以上到着するまでは戻ってこない方法である。

案1と案2の比較

利用者観点でみると、余計な事を考えなくてすむ案2を押したいであろう。しかし場合によっては、高度なセマフォやMutexや条件変数を用いたロックではなく、並列性の特性を活かしスピンロックをしたいので、Full,Emptyの情報が欲しいと主張するかもしれない。

しかし、この案1,案2では、利用者観点の比較であり、スピンロックの要件であれば、スピンロック方式の案2のキューを作ればよいのである。ただ、案1の情報を返却するは、他との結合でどうしても必要という場合もあり、一概に案1は不要とは言い切れない。 (この点は別に記載したい)

おわりに

これらを踏まえると、マルチスレッド対応のキューは、単なる排他だけではなく「FULL」「EMPTY」時の挙動も気を付ける必要がある。また、この時にブロックするという案は非常に良いと考えられる。