Java Queue Implementations - Feature ImageJava Queue Implementations - Feature Image
HappyCoders Glasses

Java Queue Implementierungen - Welche einsetzen?

Sven Woltmann
Sven Woltmann
20. April 2022

Dieser 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.

KlasseBasis
Daten-struktur
Thread-
sicher?
Blocking/
Non-blocking
Fairness
Policy
Bounded/
Unbounded
Iterator Type
ConcurrentLinkedQueueVerkettete ListeJa
(optimistisches Locking durch Compare-and-set)
Non-blockingUnboundedWeakly consistent¹
PriorityQueueMin-Heap
(gespeichert in einem Array)
NeinNon-blockingUnboundedFail-fast²
LinkedBlockingQueueVerkettete ListeJa
(pessimistisches Locking mit zwei Locks)
BlockingNicht verfügbarBoundedWeakly consistent¹
ArrayBlockingQueueArrayJa
(pessimistisches Locking mit einem Lock)
Blocking OptionalBoundedWeakly consistent¹
PriorityBlockingQueueMin-Heap
(gespeichert in einem Array)
Ja
(pessimistisches Locking mit einem Lock)
Blocking
(nur dequeue)
Nicht verfügbarUnboundedWeakly consistent¹
DelayQueuePriority QueueJa
(pessimistisches Locking mit einem Lock)
Blocking
(nur dequeue)
Nicht verfügbarUnboundedWeakly consistent¹
SynchronousQueueStack
(impl. mit verketteter Liste)
Ja
(optimistisches Locking durch Compare-and-set)
BlockingOptionalUnboundedDer Iterator ist immer leer.
LinkedTransferQueueVerkettete ListeJa
(optimistisches Locking durch Compare-and-set)
Blocking
(nur transfer und dequeue)
Nicht verfügbarUnboundedWeakly 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.
  • ConcurrentLinkedQueue als threadsichere, nicht blockierende und unbounded Queue.
  • ArrayBlockingQueue als threadsichere, blockierende, bounded Queue, sofern du niedrige bis mittlere Contention zwischen Producer- und Consumer-Threads erwartest.
  • LinkedBlockingQueue als 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:

Entscheidungsbaum Java Queue-Implementierungen
Entscheidungsbaum Java Queue-Implementierungen

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.