wake-up-neo.net

LinkedBlockingQueue vs ConcurrentLinkedQueue

Meine Frage bezieht sich auf diese Frage früher gestellt. In Situationen, in denen ich eine Warteschlange für die Kommunikation zwischen Produzenten- und Konsumententhreads verwende, empfehlen die Leute im Allgemeinen die Verwendung von LinkedBlockingQueue oder ConcurrentLinkedQueue?

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

Der Hauptunterschied, den ich aus API-Sicht sehe, besteht darin, dass ein LinkedBlockingQueue optional begrenzt werden kann.

101
Adamski

Für einen Producer/Consumer-Thread bin ich mir nicht sicher, ob ConcurrentLinkedQueue überhaupt eine vernünftige Option ist - er implementiert BlockingQueue nicht, die grundlegende Schnittstelle für IMO-Warteschlangen für Producer/Consumer. Sie müssten poll() aufrufen, ein wenig warten, wenn Sie nichts gefunden haben, und dann erneut abfragen usw. ... was zu Verzögerungen beim Eingang eines neuen Elements und Ineffizienzen führt, wenn es leer ist (fällig) unnötigerweise aus dem Schlaf aufzuwachen).

In den Dokumenten für BlockingQueue:

BlockingQueue -Implementierungen sind in erster Linie für Produzenten-Konsumenten-Warteschlangen vorgesehen

Ich weiß es nicht streng sagen, dass nur blockierende Warteschlangen für Produzenten-Konsumenten-Warteschlangen verwendet werden sollten, aber trotzdem ...

99
Jon Skeet

Diese Frage verdient eine bessere Antwort.

Javas ConcurrentLinkedQueue basiert auf dem berühmten Algorithmus von Maged M. Michael und Michael L. Scott für nicht blockierende, schlossfreie Warteschlangen.

"Nicht blockieren" als Begriff für eine konkurrierende Ressource (unsere Warteschlange) bedeutet hier, dass andere Threads, die um dieselbe Ressource konkurrieren, unabhängig davon, was der Scheduler der Plattform tut, wie das Unterbrechen eines Threads oder wenn der betreffende Thread einfach zu langsam ist wird immer noch in der Lage sein, Fortschritte zu machen. Wenn es sich zum Beispiel um eine Sperre handelt, könnte der Thread, der die Sperre hält, unterbrochen werden, und alle Threads, die auf diese Sperre warten, würden blockiert. Intrinsische Sperren (das Schlüsselwort synchronized) in Java) können ebenfalls mit einer erheblichen Beeinträchtigung der Leistung einhergehen - beispielsweise, wenn voreingenommene Sperrung beteiligt ist und Sie dies tun Konflikt, oder nach dem VM entscheidet sich, die Sperre nach einer Kulanzperiode aufzublähen und konkurrierende Threads zu blockieren ... weshalb in vielen Kontexten (Szenarien mit niedrigem/mittlerem Konflikt) zu tun Compare-and-Sets auf atomaren Referenzen können viel effizienter sein, und genau das tun viele nicht blockierende Datenstrukturen.

Javas ConcurrentLinkedQueue ist nicht nur nicht blockierend, sondern hat auch die großartige Eigenschaft, dass der Produzent nicht mit dem Konsumenten konkurriert. In einem Single Producer/Single Consumer-Szenario (SPSC) bedeutet dies, dass es keine nennenswerten Konflikte gibt. In einem Szenario mit mehreren Produzenten/einzelnen Konsumenten wird der Konsument nicht mit den Produzenten streiten. Diese Warteschlange hat Konflikte, wenn mehrere Produzenten versuchen, offer(), aber das ist per Definition Parallelität. Grundsätzlich handelt es sich um eine universelle und effiziente nicht blockierende Warteschlange.

Da es sich nicht um ein BlockingQueue handelt, ist das Blockieren eines Threads, um auf eine Warteschlange zu warten, eine furchtbar schreckliche Methode zum Entwerfen gleichzeitiger Systeme. Nicht. Wenn Sie nicht herausfinden können, wie ein ConcurrentLinkedQueue in einem Konsumenten-/Produzenten-Szenario verwendet wird, wechseln Sie einfach zu übergeordneten Abstraktionen, wie einem guten Akteur-Framework.

62

LinkedBlockingQueue blockiert den Verbraucher oder den Erzeuger, wenn die Warteschlange leer oder voll ist und der jeweilige Verbraucher/Erzeuger-Thread in den Ruhezustand versetzt wird. Diese Blockierungsfunktion ist jedoch mit Kosten verbunden: Jede Put- oder Take-Operation ist eine Sperre, die zwischen den Herstellern oder Verbrauchern (wenn es viele gibt) besteht. In Szenarien mit vielen Herstellern/Verbrauchern kann die Operation daher langsamer sein.

ConcurrentLinkedQueue verwendet keine Sperren, aber CAS , um bei Put/Take-Vorgängen potenziell Konflikte mit vielen Produzenten- und Konsumententhreads zu vermeiden. Da es sich jedoch um eine "wartefreie" Datenstruktur handelt, wird ConcurrentLinkedQueue nicht blockiert, wenn sie leer ist. Dies bedeutet, dass der Verbraucher sich mit der take() -Rückgabe von null -Werten durch "busy" befassen muss Warten ", zum Beispiel, wenn der Consumer-Thread die CPU auffrisst.

Welche Variante "besser" ist, hängt von der Anzahl der Konsumententhreads, der Rate, die sie verbrauchen/produzieren usw. ab. Für jedes Szenario ist ein Benchmark erforderlich.

Ein spezieller Anwendungsfall, bei dem die ConcurrentLinkedQueue eindeutig besser ist, ist, wenn Produzenten zuerst etwas produzieren und ihre Arbeit beenden, indem sie die Arbeit in die Warteschlange stellen und erst nach Der Verbraucher beginnt zu konsumieren, da er weiß, dass er fertig ist, wenn die Warteschlange leer ist. (Hier gibt es keine Parallelität zwischen Produzent-Konsument, sondern nur zwischen Produzent-Produzent und Konsument-Konsument)

25
dcernahoschi

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

1
Ovidiu Lupas

Wenn Ihre Warteschlange nicht erweiterbar ist und nur einen Producer/Consumer-Thread enthält. Sie können die Warteschlange ohne Sperre verwenden (Sie müssen den Datenzugriff nicht sperren).

0
Rahul