LinkedBlockingQueue vs ConcurrentLinkedQueue

Question

Meine Frage bezieht sich href="https://stackoverflow.com/questions/1426342/need-a-queue-that-can-support-multiple-readers/1426375#1426375"> diese Frage fragte früher. In Situationen, in denen ich eine Warteschlange für die Kommunikation zwischen Produzenten und Konsumenten-Threads bin mit würden empfehlen, die Menschen im Allgemeinen mit LinkedBlockingQueue oder ConcurrentLinkedQueue?

Was sind die Vorteile / Nachteile des einen über den anderen verwenden?

Der Hauptunterschied I aus einer API Perspektive sehen kann, ist, dass ein LinkedBlockingQueue kann optional begrenzt werden.

Answer 1

Für einen Erzeuger / Verbraucher-Thread, ich bin nicht sicher, dass ConcurrentLinkedQueue ist auch eine vernünftige Option - es ist nicht BlockingQueue nicht implementiert, die für die Erzeuger / Verbraucher-Warteschlangen IMO die grundlegende Schnittstelle ist. Sie müßten poll() nennen, noch ein bisschen warten, wenn man nichts gefunden hatte, und dann wieder abfragen, etc ... zu Verzögerungen führen, wenn ein neues Element kommt, und Ineffizienzen, wenn es leer ist (wegen unnötig von sleeps Aufwachen ).

Von der Dokumentation für Blocking:

  

BlockingQueue Implementierungen sind in erster Linie für Erzeuger-Verbraucher-Warteschlangen verwendet werden

Ich weiß es nicht streng sagen, dass nur blockiert Warteschlangen für Erzeuger-Verbraucher-Warteschlangen verwendet werden soll, aber auch so ...

Answer 2

Diese Frage verdient eine bessere Antwort.

Java ConcurrentLinkedQueue auf dem bekannten Algorithmus von Maged M. Michael und Michael L. Scott nicht blockierende Sperre frei Warteschlangen.

„Non-blocking“ als Begriff hier für eine behauptete Ressource (unsere Warteschlange) bedeutet, dass unabhängig davon, was die Plattform Scheduler tut, wie ein roten Faden unterbrochen wird, oder wenn der Faden in Frage einfach zu langsam ist, andere Threads streit für die gleiche Ressource in der Lage, noch Fortschritte. Wenn eine Sperre zum Beispiel beteiligt ist, kann der Thread die Sperre halten konnte unterbrochen und alle Fäden für die Sperre warten würden blockiert werden. Intrinsic Schlösser (das synchronized Schlüsselwort) in Java können auch mit einer schweren Strafe für die Leistung kommen - wie bei voreingenommen Sperr beteiligt ist, und Sie tun Streit haben oder nach entscheidet die VM auf ‚‘ die Sperre nach einem Dreher Karenzzeit und Block streitenden Fäden ... aufblasen weshalb in vielen Kontexten (Szenarien geringer ist / Medium Streit), tut Vergleichs- und setzt auf Atom Referenzen kann viel effizienter, und das ist genau das, was viele nicht-blockierende Datenstrukturen tun.

sein

Java ConcurrentLinkedQueue ist nicht nur nicht-blockierend, aber es hat die großartige Eigenschaft, dass der Hersteller nicht mit dem Verbraucher nicht behaupten. In einem einzigen Hersteller / Einzel Verbraucher Szenario (SPSC) bedeutet dies wirklich, dass es keine Konkurrenz sein zu sprechen. In einem mehr Herstellern / Einzel Verbraucher Szenario wird der Verbraucher nicht mit den Produzenten kämpfen. Diese Warteschlange tut Behauptung haben, wenn mehrere Hersteller offer() versuchen, aber das ist Gleichzeitigkeit per Definition. Es ist im Grunde ein Mehrzweck- und effiziente non-blocking-Warteschlange.

Was es kein BlockingQueue zu sein, nun ja, einen Thread blockiert wartet auf einer Warteschlange eine freakishly schreckliche Art und Weise ist parallel arbeitenden Systeme zu entwerfen. Nicht. Wenn Sie nicht herausfinden können, wie man eine ConcurrentLinkedQueue in einem Verbraucher / Produzenten Szenario verwenden, dann wechseln Sie einfach auf höhere Ebene Abstraktionen, wie ein guter Schauspieler Rahmen.

Answer 3

LinkedBlockingQueue Blöcke der Verbraucher oder der Hersteller, wenn die Warteschlange leer oder voll ist und der jeweilige Verbraucher / Produzent Thread eingeschläfert. Aber diese Blocking-Funktion kommt mit einem Preis. Jeder oder nehmen Sie setzen Bedienungssperre zwischen den Erzeugern und Verbrauchern (wenn viele) geltend gemacht, so in Szenarien mit vielen Produzenten / Konsumenten die Operation könnte langsamer sein

ConcurrentLinkedQueue nicht mit Schlössern, aber CAS auf seiner put / nehmen Operationen möglicherweise Streit mit vielen Produzenten und Konsumenten-Threads zu reduzieren. ein „wait frei“ Datenstruktur aber sein, ConcurrentLinkedQueue wird nicht blockieren, wenn sie leer, was bedeutet, dass der Verbraucher mit dem take() Rückkehr null Werte von „busy waiting“ befassen müssen wird, zum Beispiel mit dem Verbraucher-Thread CPU auffressen.

So die man „besser“ ist, hängt von der Anzahl der Verbraucher-Threads, auf die Rate sie / Produkte konsumieren usw. Ein Benchmark für jedes Szenario benötigt wird.

Ein besonderer Anwendungsfall, wo die ConcurrentLinkedQueue deutlich besser ist, wenn die Produzenten zunächst etwas produzieren und ihre Arbeit zu beenden, indem die Arbeit in der Warteschlange platzieren und erst nach die Verbraucher zu konsumieren beginnen, wohl wissend, dass sie getan werden, wenn die Warteschlange leer ist. (Hier ist keine Parallelität zwischen Erzeuger-Verbraucher aber nur zwischen Produzent-Erzeuger und Verbraucher-consumer)

Answer 4

Eine andere Lösung (das nicht gut skalierbar) ist Rendezvous Kanäle: java.util.concurrent SynchronousQueue

Answer 5

Wenn die Warteschlange nicht erweiterbar ist, und enthält nur einen Erzeuger / Verbraucher-Thread. Sie können lockless Warteschlange verwenden (Sie müssen nicht den Datenzugriff sperren).