LinkedBlockingQueue vs ConcurrentLinkedQueue

112

Meine Frage bezieht sich auf diese zuvor gestellte Frage. In Situationen, in denen ich eine Warteschlange für die Kommunikation zwischen Produzenten- und Konsumententhreads verwende, würden die Leute generell empfehlen, LinkedBlockingQueueoder zu verwenden ConcurrentLinkedQueue?

Was sind die Vor- und Nachteile einer Verwendung übereinander?

Der Hauptunterschied, den ich aus API-Sicht sehen kann, besteht darin, dass a LinkedBlockingQueueoptional begrenzt werden kann.

java multithreading data-structures concurrency queue Adamski
quelle

Antworten:

110

Für einen Produzenten / Konsumenten-Thread bin ich mir nicht sicher, ob dies ConcurrentLinkedQueueüberhaupt eine vernünftige Option ist - es wird nicht implementiert BlockingQueue, was die grundlegende Schnittstelle für Produzenten / Konsumenten-Warteschlangen IMO ist. Sie müssten anrufen poll(), etwas warten, wenn Sie nichts gefunden haben, und dann erneut abfragen usw. ... was zu Verzögerungen beim Eintreffen eines neuen Elements und zu Ineffizienzen beim Leeren führt (aufgrund unnötigen Aufwachens aus dem Schlaf) .

Aus den Dokumenten für BlockingQueue:

BlockingQueue Implementierungen sind so konzipiert, dass sie hauptsächlich für Produzenten-Konsumenten-Warteschlangen verwendet werden

Ich weiß, es heißt nicht unbedingt , dass nur Blockierungswarteschlangen für Produzenten-Konsumenten-Warteschlangen verwendet werden sollten, aber trotzdem ...

Jon Skeet
quelle
4
Danke Jon - das hatte ich nicht bemerkt. Wo / warum würden Sie ConcurrentLinkedQueue verwenden?
Adamski
27
Wenn Sie von vielen Threads aus auf die Warteschlange zugreifen müssen, aber nicht darauf warten müssen.
Jon Skeet
2
A ConcurrentLinkedQueueist auch nützlich, wenn Ihr Thread mehrere Warteschlangen überprüft. Zum Beispiel in einem Server mit mehreren Mandanten. Angenommen, Sie verwenden aus Isolationsgründen nicht eine einzige Blockierungswarteschlange und keinen Mandantendiskriminator.
LateralFractal
Ihr Fall gilt nur, wenn wir eine begrenzte Warteschlange in einer unbegrenzten Warteschlange verwenden take()und put()lediglich zusätzliche Ressourcen (Synchronisationsinterms) verbrauchen als ConcurrentLinkedQueue . obwohl es der Fall ist, begrenzte Warteschlangen für Produzenten-Konsumenten-Szenarien zu verwenden
Amarnath Harish
@Adamski IMO, ConcurrentLinkedQueue ist nur eine verknüpfte Liste, die in einer Umgebung mit mehreren Threads verwendet werden kann. Die beste Analogie hierfür wäre ConcurrentHashMap und HashMap.
Nishit
69

Diese Frage verdient eine bessere Antwort.

Java ConcurrentLinkedQueuebasiert auf dem berühmten Algorithmus von Maged M. Michael und Michael L. Scott für nicht blockierende Warteschlangen ohne Sperren .

"Nicht blockierend" als Begriff für eine konkurrierende Ressource (unsere Warteschlange) bedeutet, dass unabhängig davon, was der Scheduler der Plattform tut, wie das Unterbrechen eines Threads oder wenn der betreffende Thread einfach zu langsam ist, andere Threads um dieselbe Ressource konkurrieren wird noch in der Lage sein, Fortschritte zu machen. Wenn es sich beispielsweise um eine Sperre handelt, kann der Thread, der die Sperre hält, unterbrochen werden, und alle Threads, die auf diese Sperre warten, werden blockiert. Intrinsische Sperren (das synchronizedSchlüsselwort) in Java können auch mit erheblichen Leistungseinbußen verbunden sein - wie beim voreingenommenen Sperrenist beteiligt und Sie haben Konflikte, oder nachdem die VM beschlossen hat, die Sperre nach einer Spin-Grace-Periode zu "aufblasen" und konkurrierende Threads zu blockieren ... weshalb in vielen Kontexten (Szenarien mit geringen / mittleren Konflikten) Vergleiche und -Sätze für atomare Referenzen können viel effizienter sein, und genau das tun viele nicht blockierende Datenstrukturen.

Java ConcurrentLinkedQueueist nicht nur nicht blockierend, sondern hat auch die großartige Eigenschaft, dass der Produzent nicht mit dem Verbraucher konkurriert. In einem Einzelproduzenten / Einzelkonsumentenszenario (SPSC) bedeutet dies wirklich, dass es keinen nennenswerten Streit geben wird. In einem Szenario mit mehreren Herstellern / einzelnen Verbrauchern wird der Verbraucher nicht mit den Herstellern konkurrieren. Diese Warteschlange hat Konflikte, wenn mehrere Produzenten dies versuchen offer(), aber das ist per Definition Parallelität. Es ist im Grunde eine allgemeine und effiziente nicht blockierende Warteschlange.

Das BlockingQueueBlockieren eines Threads, um in einer Warteschlange zu warten, ist eine schrecklich schreckliche Art, gleichzeitige Systeme zu entwerfen. Tu es nicht. Wenn Sie nicht herausfinden können, wie ein ConcurrentLinkedQueuein einem Consumer / Producer-Szenario verwendet wird, wechseln Sie einfach zu übergeordneten Abstraktionen, wie z. B. einem guten Schauspieler-Framework.

Alexandru Nedelcu
quelle
8
Warum sagen Sie laut Ihrem letzten Absatz, dass das Warten in einer Warteschlange eine schreckliche Möglichkeit ist, gleichzeitige Systeme zu entwerfen? Wenn wir eine Threadgruppe mit 10 Threads haben, die Aufgaben aus einer Taskwarteschlange essen, was ist falsch daran zu blockieren, wenn die Taskwarteschlange weniger als 10 Aufgaben enthält?
Pacerier
11
@AlexandruNedelcu Sie können keine pauschale Aussage wie "freakishly schrecklich" machen, bei der sehr oft die von Ihnen angegebenen Schauspieler-Frameworks Threadpools verwenden, die Sie selbst BlockingQueue verwenden . Wenn Sie ein hochreaktives System benötigen und wissen, wie Sie mit Gegendruck umgehen (etwas, das blockierende Warteschlangen mildert), ist das Nicht-Blockieren eindeutig überlegen. Aber ... oft kann das Blockieren von E / A und das Blockieren von Warteschlangen eine Nichtblockierung bewirken, insbesondere wenn Sie lange laufende Aufgaben haben, die an E / A gebunden sind und nicht geteilt und erobert werden können.
Adam Gent
1
@AdamGent - Die Actor-Frameworks haben zwar die Implementierung von Postfächern basierend auf blockierenden Warteschlangen, aber das ist meiner Meinung nach ein Fehler, da das Blockieren nicht über asynchrone Grenzen funktioniert und daher nur in Demos funktioniert. Für mich war dies eine Quelle der Frustration, da beispielsweise Akkas Idee, mit Überlauf umzugehen, darin besteht, Nachrichten zu blockieren, anstatt sie zu löschen, bis Version 2.4, die noch nicht veröffentlicht wurde. Trotzdem glaube ich nicht, dass es Anwendungsfälle gibt, für die blockierende Warteschlangen überlegen sein können. Sie verschmelzen auch zwei Dinge, die nicht zusammengeführt werden sollten. Ich habe nicht darüber gesprochen, E / A zu blockieren.
Alexandru Nedelcu
1
@AlexandruNedelcu, obwohl ich Ihnen in Bezug auf den Gegendruck im Allgemeinen zustimme, habe ich noch kein "sperrfreies" System von oben nach unten gesehen. Irgendwo in einem Technologie-Stack, ob Node.js, Erlang, Golang, wird eine Art Wartestrategie verwendet, unabhängig davon, ob es sich um eine Blockierungswarteschlange (Sperren) handelt oder ob CAS die Blockierung dreht, und in einigen Fällen ist eine herkömmliche Sperrstrategie schneller. Es ist sehr schwierig, aufgrund der Konsistenz keine Sperren zu haben, und dies ist besonders wichtig beim Blockieren von Io und Schedulern, die ~ Produzent / Verbraucher sind. ForkJoinPool arbeitet mit kurz laufenden Aufgaben und verfügt weiterhin über CAS-Drehsperren.
Adam Gent
1
@AlexandruNedelcu Ich denke, wenn Sie mir zeigen können, wie Sie eine ConcurrentLinkedQueue (die nicht an mein schwaches Gegendruckargument gebunden ist) für das Producer / Consumer-Muster verwenden können, das für Scheduler und Threadpooling benötigt wird, denke ich, dass ich nachgeben und das zugeben werde BlockingQueue's sollten niemals verwendet werden (und Sie können nicht betrügen und an etwas anderes delegieren, das die Planung durchführt, dh akka, da dies wiederum das Blockieren / Warten übernimmt, da es ein Produzent / Konsument ist).
Adam Gent
33

LinkedBlockingQueueblockiert den Konsumenten oder Produzenten, wenn die Warteschlange leer oder voll ist und der jeweilige Konsumenten- / Produzenten-Thread in den Ruhezustand versetzt wird. Diese Blockierungsfunktion ist jedoch mit Kosten verbunden: Jede Put- oder Take-Operation ist eine Sperre zwischen den Herstellern oder Verbrauchern (wenn viele), sodass in Szenarien mit vielen Herstellern / Verbrauchern die Operation möglicherweise langsamer ist.

ConcurrentLinkedQueueverwendet keine Sperren, sondern CAS für seine Put / Take-Operationen, wodurch möglicherweise die Konkurrenz mit vielen Produzenten- und Konsumententhreads verringert wird. Da es sich jedoch um eine "wartefreie" Datenstruktur handelt, ConcurrentLinkedQueuewird sie nicht blockiert, wenn sie leer ist. Dies bedeutet, dass der Verbraucher die take()zurückgegebenen nullWerte durch "beschäftigtes Warten" verarbeiten muss, z. B. wenn der Verbraucher-Thread die CPU auffrisst.

Welches also "besser" ist, hängt von der Anzahl der Consumer-Threads, der Rate, die sie verbrauchen / produzieren usw. ab. Für jedes Szenario wird ein Benchmark benötigt.

Ein besonderer Anwendungsfall, bei dem das ConcurrentLinkedQueueeindeutig besser ist, ist, wenn Produzenten zuerst etwas produzieren und ihre Arbeit beenden, indem sie die Arbeit in die Warteschlange stellen, und erst , wenn die Verbraucher anfangen zu konsumieren, in dem Wissen, dass sie erledigt werden, wenn die Warteschlange leer ist. (Hier besteht keine Parallelität zwischen Produzent-Konsument, sondern nur zwischen Produzent-Produzent und Konsument-Konsument)

dcernahoschi
quelle
ein Zweifel hier. Wie Sie bereits erwähnt haben, wartet der Verbraucher, wenn die Warteschlange leer ist. Wie lange wartet er? Wer wird es benachrichtigen, nicht zu warten?
Brinal
@brindal Der einzige Weg zu warten, den ich kenne, ist in einer Schleife. Dies ist ein bedeutendes Problem, dem in den Antworten hier nicht viel Aufmerksamkeit geschenkt wurde. Das Ausführen einer Schleife, die auf Daten wartet, verbraucht viel Prozessorzeit. Sie werden es wissen, wenn Ihre Fans anfangen, sich zu drehen. Das einzige Mittel ist, einen Schlaf in die Schleife zu setzen. Es ist also ein Problem in einem System mit inkonsistentem Datenfluss. Vielleicht verstehe ich die Antwort von AlexandruNedelcu falsch, aber ein Betriebssystem selbst ist ein gleichzeitiges System, das äußerst ineffizient wäre, wenn es voller nicht blockierender Ereignisschleifen wäre.
Orodbhen
Okay, aber wenn unbounded blockingqueuees verwendet wird, wäre es besser als CAS- basiertes ConcurrentConcurrentLinkedQueue
Amarnath Harish
@orodbhen Einen Schlaf würde auch keine Verschwendung beseitigen. Das Betriebssystem muss viel Arbeit leisten, um einen Thread aus dem Ruhezustand zu bringen und zu planen und auszuführen. Wenn noch keine Nachrichten verfügbar sind, geht die von Ihrem Betriebssystem geleistete Arbeit verloren. Ich würde empfehlen, BlockingQueue besser zu verwenden, da es speziell für Hersteller-Verbraucher-Probleme entwickelt wurde.
Nishit
Eigentlich interessiere ich mich sehr für den Teil "Verbrauchs- / Produktionsrate". Welcher ist also besser, wenn die Rate hoch ist?
Workplaylifecycle
0

Eine andere Lösung (die sich nicht gut skalieren lässt) sind Rendezvous-Kanäle: java.util.concurrent SynchronousQueue

Ovidiu Lupas
quelle
0

Wenn Ihre Warteschlange nicht erweiterbar ist und nur einen Produzenten- / Konsumententhread enthält. Sie können eine sperrenlose Warteschlange verwenden (Sie müssen den Datenzugriff nicht sperren).

Rahul
quelle