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

| コメント(0) | トラックバック(0) このエントリーを含むはてなブックマーク

先日、プリミティブスレッドを使わない並列処理に向けてという記事を書いた。

今回は、その中で出ていたキューについて、その中でもマルチスレッド対応のキューについて書いてみたい。

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

定義

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

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

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

 

20091206_queue1.png

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

実装方法

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

配列

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

20091206_queue2.png 

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

リスト

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

 

20091206_queue3.png

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

マルチスレッド対応Queue

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

 

20091206_queue4.png

この時の挙動として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」時の挙動も気を付ける必要がある。また、この時にブロックするという案は非常に良いと考えられる。

トラックバック(0)

トラックバックURL: http://www.m-tea.info/mt-tb.cgi/34

コメントする

あわせて読みたいブログパーツ

このブログ記事について

このページは、k1ha410が2009年12月 6日 23:58に書いたブログ記事です。

ひとつ前のブログ記事は「プリミティブスレッドを使わない並列処理に向けて」です。

次のブログ記事は「記事作成ツールの更新」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。