Javaでの並行キューのガイド - 開発者ドキュメント

1. 概要

このチュートリアルでは、Javaでの並行キューの主な実装のいくつかを説明します。キューの一般的な概要については、Javaキューインターフェイスガイドの記事を参照してください。

2. キュー

マルチスレッドアプリケーションでは、キューは複数の同時プロデューサー-コンシューマーシナリオを処理する必要があります。並行キューを正しく選択することは、アルゴリズムで優れたパフォーマンスを実現するために重要になる可能性があります。

まず、ブロッキングキューと非ブロッキングキューの重要な違いをいくつか見ていきます。次に、いくつかの実装とベストプラクティスを見ていきます。

2. ブロッキングキューと非ブロッキングキュー

BlockingQueue は、シンプルなスレッドセーフメカニズムを提供します。このキューでは、スレッドはキューが使用可能になるまで待機する必要があります。プロデューサーは要素を追加する前に使用可能な容量を待機し、コンシューマーはキューが空になるまで待機します。このような場合、非ブロッキングキューは例外をスローするか、nullやfalseなどの特別な値を返します。

このブロッキングメカニズムを実現するために、 BlockingQueue インターフェイスは、通常のQueue関数に加えてputとtakeの2つの関数を公開します。これらの関数は、標準のキューのaddおよびremoveと同等です。

3. 並行キューの実装

3.1. ArrayBlockingQueue

その名前が示すように、このキューは内部で配列を使用します。結果として、それは制限付きキューであり、固定サイズを持っていることを意味します。

単純なワークキューは、ユースケースの例です。このシナリオは、多くの場合、生産者と消費者の比率が低く、時間のかかるタスクを複数のワーカーに分割します。このキューは無期限に拡張できないため、メモリが問題になる場合は、サイズ制限が安全しきい値として機能します。

メモリについて言えば、キューがアレイを事前に割り当てることに注意することが重要です。これによりスループットが向上する可能性がありますが、は必要以上のメモリを消費する可能性があります。たとえば、大容量のキューは長期間空のままになる場合があります。

また、 ArrayBlockingQueue は、put操作とtake操作の両方に単一のロックを使用します。これにより、パフォーマンスが低下する代わりに、エントリが上書きされることはありません。

3.2. LinkedBlockingQueue

LinkedBlockingQueue は、 LinkedInList バリアントを使用します。ここで、各キュー項目は新しいノードです。これにより、キューは原則として無制限になりますが、Integer.MAX_VALUEのハード制限があります。

一方、コンストラクター LinkedInBlockingQueue（intcapacity）を使用してキューサイズを設定できます。

このキューは、putおよびtake操作に個別のロックを使用します。結果として、両方の操作を並行して実行し、スループットを向上させることができます。

LinkedBlockingQueue は制限付きまたは制限なしのいずれかである可能性があるため、なぜこれにArrayBlockingQueueを使用するのでしょうか。 LinkedBlockingQueueは、アイテムがキューに追加またはキューから削除されるたびに、ノードの割り当てと割り当て解除を行う必要があります。このため、キューが急速に拡大し、縮小する場合は、ArrayBlockingQueueの方が適しています。

LinkedBlockingQueueのパフォーマンスは予測できないと言われています。つまり、適切なデータ構造を使用できるように、シナリオのプロファイルを常に作成する必要があります。

3.3. PriorityBlockingQueue

PriorityBlockingQueue は、特定の順序でアイテムを消費する必要がある場合のソリューションです。これを実現するために、PriorityBlockingQueueは配列ベースのバイナリヒープを使用します。

内部的には単一のロックメカニズムを使用しますが、take操作はput操作と同時に発生する可能性があります。単純なスピンロックを使用すると、これが可能になります。

典型的なユースケースは、異なる優先順位のタスクを消費することです。 優先度の高いタスクの代わりに優先度の低いタスクを使用したくありません。

3.4. DelayQueue

DelayQueue は、消費者が期限切れのアイテムしか受け取れない場合に使用します。興味深いことに、内部で PriorityQueue を使用して、有効期限ごとにアイテムを注文します。

これは汎用キューではないため、ArrayBlockingQueueまたはLinkedBlockingQueueほど多くのシナリオをカバーしていません。たとえば、このキューを使用して、NodeJSにあるものと同様の単純なイベントループを実装できます。非同期タスクは、期限切れになったときに後で処理できるようにキューに入れます。

3.5. LinkedTransferQueue

LinkedTransferQueue は、transferメソッドを導入します。他のキューは通常、アイテムを生成または消費するときにブロックしますが、 LinkedTransferQueue を使用すると、プロデューサーはアイテムの消費を待つことができます。

LinkedTransferQueue は、キューに入れた特定のアイテムが誰かによって取得されたことを保証する必要がある場合に使用します。また、このキューを使用して単純なバックプレッシャアルゴリズムを実装できます。実際、消費するまでプロデューサーをブロックすることにより、コンシューマーは生成されたメッセージのフローを駆動できます。

3.6. SynchronousQueue

通常、キューには多くのアイテムが含まれますが、SynchronousQueueには常に最大で1つのアイテムが含まれます。つまり、SynchronousQueueを2つのスレッド間でデータを交換する簡単な方法と見なす必要があります。

共有状態にアクセスする必要がある2つのスレッドがある場合、これらをCountDownLatchまたは他の同期メカニズムと同期することがよくあります。 SynchronousQueue を使用することで、このスレッドの手動同期を回避できます。

3.7. ConcurrentLinkedQueue

ConcurrentLinkedQueue は、このガイドの唯一の非ブロッキングキューです。その結果、 addとpollがスレッドセーフであり、すぐに戻ることが保証される「待機なし」アルゴリズムを提供します。このキューは、ロックの代わりに CAS（Compare-And-Swap）を使用します。

内部的には、MagedMによるSimple、Fast、and Practical Non-Blocking and Blocking Concurrent QueueAlgorithmsのアルゴリズムに基づいています。マイケルとマイケルL。スコット。

これは、最新のリアクティブシステムの完璧な候補であり、ブロッキングデータ構造の使用が禁止されていることがよくあります。

一方、コンシューマーがループで待機することになった場合は、より適切な代替手段としてブロッキングキューを選択する必要があります。