gleichzeitige Warteschlange - allgemeine Frage (Beschreibung und Verwendung)

Question

Ich habe etwas Mühe, die Idee einer gleichzeitigen Warteschlange zu begreifen. Ich verstehe, eine Warteschlange ist ein FIFO oder First first serve, Datenstruktur.

Wenn wir nun den Nebenläufigkeitsteil hinzufügen, den ich als Thread-Sicherheit interpretiere (bitte lassen Sie mich wissen, wenn das falsch ist), werden die Dinge etwas unscharf. Unter Nebenläufigkeit verstehen wir die Art und Weise, in der verschiedene Threads der Warteschlange hinzugefügt oder aus der Warteschlange gelöscht (ein Element gewartet) werden können. Ist die Parallelität ein Gefühl der Ordnung für diese Operationen?

Ich würde eine allgemeine Beschreibung der Funktionalität einer gleichzeitigen Warteschlange sehr schätzen. Ein ähnlicher Beitrag here ist nicht so allgemein wie ich gehofft hatte.

Gibt es auch so etwas wie eine Warteschlange mit gleichzeitiger Priorität? Was wäre seine Verwendung?

Vielen Dank im Voraus, für kurze Erklärungen oder hilfreiche Links zu diesem Thema.

Answer 1

Sie sollten mit der Schnittstellendefinition BlockingQueue beginnen, da dies der Eckpfeiler für die Verwendung von Warteschlangen für die Kommunikation zwischen Threads ist und Dienstprogrammmethoden enthält, die Producer- und Consumer-Threads blockierend oder nicht blockierend auf die Warteschlange zugreifen können. Dies, zusammen mit dem thread-sicheren Zugriff, ist mein Verständnis dessen, was eine "gleichzeitige Warteschlange" ausmacht (obwohl ich noch nie von dieser Phrase gehört habe - BlockingQueue existiert lediglich in dem java.util.concurrent Paket).

Um den zweiten Teil Ihrer Frage zu beantworten, ist die Implementierung der Prioritätswarteschlange PriorityBlockingQueue. Dies kann nützlich sein, wenn Ihre Producer-Threads Aufgaben mit unterschiedlichen Prioritäten erzeugen (zB Anfragen von "normalen Benutzern" und "Power-Usern") und Sie die Reihenfolge, in der Aufgaben von Ihren Consumer-Threads verarbeitet werden, steuern möchten. . Eine mögliche zu vermeidende Gefahr ist das Verhungern von Tasks mit niedriger Priorität, die aufgrund des konstanten Zustroms von Tasks mit höherer Priorität niemals aus der Warteschlange entfernt werden.

Answer 2

Ich verstehe durch "Nebenläufigkeit", dass die Warteschlange Thread-sicher ist. Dies bedeutet nicht, dass es effizient sein wird. Allerdings würde ich mir vorstellen, dass die Java-Warteschlange eine lockfreie Implementierung verwendet, was bedeutet, dass es wenig oder gar keine Penatly gibt, wenn zwei Threads gleichzeitig einen Push oder Pop versuchen. In der Regel verwenden sie das atomare Locking auf Assembler-Ebene, das dafür sorgt, dass das gleiche Objekt nicht zweimal geöffnet werden kann.

Ich schrieb einmal eine lock-freie FIFO-Warteschlange (in Delphi), die sehr gut funktionierte. Viel effizienter als eine vorherige Version, die kritische Abschnitte verwendet. Die CS-Version stoppte vor allem mit vielen Threads, die versuchten, auf die Warteschlange zuzugreifen. Die Lock-Free-Version hatte jedoch keine Engpässe, die viele Threads, die darauf zugreifen, stark einschränkten.

Answer 3

Nur verlassen Sie hier eine link to the java.util.concurrent package, die ich denke, enthält sehr wichtige Informationen über einige Fragen hier angesprochen.

See: Concurrent Sammlungen und Memory Consistency Properties

Answer 4

Die Vorstellung, dass ein Blocking wenig Overhead bietet, ist ein bisschen vermissen führt. Das Erlangen einer Sperre ruft einen ziemlich hohen Aufwand hervor. Alleine mit der Kontextumschaltung sprechen wir tausende Anweisungen. Nicht nur das, sondern der Fortschritt eines Threads wirkt sich direkt auf einen anderen Thread aus. Nun, es ist nicht so schlimm wie es vor Jahren war, aber im Vergleich zu nicht blockieren, ist es erheblich.

Blocking die Nutzung Schlösser für gegenseitigen Ausschluss

ArrayBlockingQueue, LinkedBlockingQueue, PriorityBlockingQUeue: sind drei Sperr der Warteschlange während

ConcurrentLinkedQueue, Java 1.7 LinkedTransferQueue: Verwendet das Michael und Scott, nicht blockierende Warteschlange-Algorithmus.

Bei moderaten bis niedrigen Konflikten (was eher ein realistisches Szenario ist) führen die blockierungsfreien Warteschlangen blockierende Warteschlangen aus.

Und zu Steve Kommentar über das Fehlen von Engpässen zu notieren. Unter starken Konflikten kann ein nicht blockierender Algorithmus bei den konstanten Cas-Versuchen einen Flaschenhals bilden, während beim Blockieren die Threads suspendiert werden. Wir sehen dann, dass eine BlockingQueue bei starker Konkurrenz leicht eine nicht blockierende Warteschlange ausfüllt, aber diese Art von Konkurrenz ist keineswegs eine Norm.