Java Queue Implementierungen – Welche einsetzen?
20. April 2022Dieser Artikel gibt einen Überblick über alle im JDK verfügbaren Queue-Implementierungen mitsamt ihrer Eigenschaften sowie eine Entscheidungshilfe, für welche Einsatzzwecke welche Implementierung am besten geeignet ist.
Der Klassenname in der folgenden Tabelle ist jeweils mit demjenigen Artikel der Tutorial-Serie verlinkt, in dem die jeweilige Queue-Implementierung mit all ihren Eigenschaften im Detail erklärt wird.
Eine Erklärung der Begriffe blocking, non-blocking, fairness policy, bounded und unbounded findest du im Artikel über das BlockingQueue-Interface.
| Klasse | Basis Daten-struktur | Thread- sicher? | Blocking/ Non-blocking | Fairness Policy | Bounded/ Unbounded | Iterator Type |
|---|---|---|---|---|---|---|
| ConcurrentLinkedQueue | Verkettete Liste | Ja (optimistisches Locking durch Compare-and-set) | Non-blocking | — | Unbounded | Weakly consistent¹ |
| PriorityQueue | Min-Heap (gespeichert in einem Array) | Nein | Non-blocking | — | Unbounded | Fail-fast² |
| LinkedBlockingQueue | Verkettete Liste | Ja (pessimistisches Locking mit zwei Locks) | Blocking | Nicht verfügbar | Bounded | Weakly consistent¹ |
| ArrayBlockingQueue | Array | Ja (pessimistisches Locking mit einem Lock) | Blocking | Optional | Bounded | Weakly consistent¹ |
| PriorityBlockingQueue | Min-Heap (gespeichert in einem Array) | Ja (pessimistisches Locking mit einem Lock) | Blocking (nur dequeue) | Nicht verfügbar | Unbounded | Weakly consistent¹ |
| DelayQueue | Priority Queue | Ja (pessimistisches Locking mit einem Lock) | Blocking (nur dequeue) | Nicht verfügbar | Unbounded | Weakly consistent¹ |
| SynchronousQueue | Stack (impl. mit verketteter Liste) | Ja (optimistisches Locking durch Compare-and-set) | Blocking | Optional | Unbounded | Der Iterator ist immer leer. |
| LinkedTransferQueue | Verkettete Liste | Ja (optimistisches Locking durch Compare-and-set) | Blocking (nur transfer und dequeue) | Nicht verfügbar | Unbounded | Weakly consistent¹ |
¹ Weakly consistent: Alle Elemente, die zum Zeitpunkt der Erzeugung des Interators in der Queue liegen, werden vom Iterator genau einmal durchlaufen. Änderungen, die danach erfolgen, können – müssen aber nicht – durch den Iterator berücksichtigt werden.
² Fail-fast: Der Iterator wirft eine ConcurrentModificationException, wenn während der Iteration Elemente in die Queue eingefügt oder aus dieser entnommen werden.
Wann solltest du welche Queue-Implementierung einsetzen?
Anhand der Eigenschaften der Queue-Implementierungen, die in den jeweiligen Artikeln beschrieben und in der Tabelle oben zusammengefasst sind, kannst du die richtige Queue für jeden Einsatzzweck finden.
Für den tagtäglichen Gebrauch der allgemeinen Queue-Implementierungen mache ich folgende Empfehlungen:
- ArrayDeque für single-threaded Anwendungen.
ConcurrentLinkedQueueals threadsichere, nicht blockierende und unbounded Queue.ArrayBlockingQueueals threadsichere, blockierende, bounded Queue, sofern du niedrige bis mittlere Contention zwischen Producer- und Consumer-Threads erwartest.LinkedBlockingQueueals threadsichere, blockierende, bounded Queue, wenn du hohe Contention zwischen Producer- und Consumer-Threads erwartest (am besten testen, welche Implementierung für deinen Use Case performanter ist).
Hier das ganze noch einmal als Entscheidungsbaum:
Optimierte MPMC-, MPSC-, SPMC- und SPSC-Queues
Alle vom JDK angebotenen threadsicheren Queue-Implementierungen können bedenkenlos in multi-producer-multi-consumer-Umgebungen eingesetzt werden. Das bedeutet, dass ein oder mehrere schreibende Threads sowie ein oder mehrere lesende Threads nebenläufig auf die JDK-Queues zugreifen können.
Mit speziellen Mechanismen ist es möglich Queues so zu optimieren, dass der Overhead für das Gewährleisten der Threadsicherheit minimiert wird, wenn es eine Beschränkung auf einen lesenden und/oder einen schreibenden Thread gibt.
Dementsprechend unterscheidet man folgende vier Fälle:
- Multi-producer-multi-consumer (MPMC)
- Multi-producer-single-consumer (MPSC)
- Single-producer-multi-consumer (SPMC)
- Single-producer-single-consumer (SPSC)
Die Open-Source-Bibliothek JCTools bietet für alle vier Fälle hoch-optimierte Queue-Implementierungen.
Zusammenfassung und Ausblick
Dieser Artikel hat einen Überblick über alle in Java verfügbaren Queue-Implementierungen gegeben sowie eine Entscheidungshilfe, in welchen Fällen welche Queue einzusetzen ist.
In den nächsten Teilen dieser Serie zeige ich dir, wie du Queues selbst implementieren kannst, beginnend mit der Implementierung mit einem Stack.
Wenn du noch Fragen hast, stelle sie gerne über die Kommentar-Funktion. Möchtest du über neue Tutorials und Artikel informiert werden? Dann klicke hier, um dich für den HappyCoders.eu-Newsletter anzumelden.