2

これはConcurrentLinkedQueueのドキュメントの説明です:

リンクされたノードに基づく無制限のスレッド セーフ キュー。このキューは要素を FIFO (先入れ先出し) で順序付けます。
...
この実装は、効率的な「ウェイトフリー」アルゴリズムを採用しています

無制限 で 待機なしにすることは可能ですか?
私は、待機の自由があらゆる操作の限界を保証すると確信しています。

4

2 に答える 2

8

私は、待機の自由があらゆる操作の限界を確実にすることをかなり確信しています。

操作にかかる時間（または命令の数など）の制限。

そのJavaDocでは、「無制限」はおそらくキューに含まれる可能性のある要素の数を指します。

たとえば、LinkedBlockingDequeのJavaDocは次のように記述します。

リンクされたノードに基づくオプションで制限されたブロッキング両端キュー。

オプションの容量制限コンストラクター引数は、過度の拡張を防ぐ方法として機能します。指定されていない場合、容量はInteger.MAX_VALUEに等しくなります。リンクされたノードは、両端キューが容量を超えない限り、挿入のたびに動的に作成されます。

于 2012-04-12T21:19:59.290 に答える
2

待機の自由とは、説明したように、有限数のステップ内で操作が完了することを意味するだけです

すべての操作が、操作が完了する前にアルゴリズムが実行するステップ数に制限がある場合、アルゴリズムはウェイトフリーです

この定義は には適用されませんConcurrentLinkedQueue。キューをポーリング (または書き込み) するとき、各スレッドは無限に失敗する可能性があります。この事実だけでも、キューが完全に待機状態ではないことがわかります。著者は、The Art of Multiprocessor Programming の Herlihy のウェイトフリーの定義を使用していないと思います。

詳細については、CLQ はここで説明されている Michael & Scott アルゴリズムを使用します。

編集: M および S キューに指定したリンクが API にもあることに気付きました。どちらでもいいはずです。

于 2012-04-12T21:09:19.780 に答える