Java-Queue-Implementierungen – Welche einsetzen?

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.

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.
• 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:

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.