Welche gleichzeitige Queue-Implementierung sollte ich in Java verwenden?

ConcurrentLinkedQueue bedeutet, dass keine Sperren verwendet werden (d. H. Keine synchronisierten (this) oder Lock.lock Aufrufe). Während der Änderungen wird eine CAS - Compare and Swap - Operation verwendet, um festzustellen, ob der Kopf-/Endknoten noch derselbe ist wie zu Beginn. Wenn ja, ist der Vorgang erfolgreich. Wenn der Kopf-/Schwanzknoten unterschiedlich ist, dreht er sich und versucht es erneut.

LinkedBlockingQueue wird vor jeder Änderung eine Sperre setzen. So würden Ihre Angebotsanrufe blockieren, bis sie das Schloss erhalten. Sie können die Angebotsüberladung, die eine TimeUnit benötigt, verwenden, um anzugeben, dass Sie nur X Mal warten möchten, bevor Sie das Hinzufügen beenden (in der Regel gut für Warteschlangen mit Nachrichtentyp, bei denen die Nachricht nach X Millisekunden veraltet ist).

Fairness bedeutet, dass die Lock-Implementierung die Reihenfolge der Threads beibehält. Das heißt, wenn Thread A und dann Thread B eintreten, wird Thread A zuerst gesperrt. Ohne Fairness ist es undefiniert, was wirklich passiert. Es wird höchstwahrscheinlich der nächste Thread sein, der geplant wird.

Welche man verwenden soll, hängt davon ab. Ich benutze normalerweise ConcurrentLinkedQueue , da meine Produzenten sehr unterschiedliche Zeit benötigen, um Arbeit in die Warteschlange zu stellen. Ich habe nicht viele Produzenten, die genau im selben Moment produzieren. Die Verbraucherseite ist jedoch komplizierter, da die Umfrage nicht in einen Zustand mit gutem Schlaf geht. Damit musst du selbst umgehen.

In Ihrem Fragentitel werden blockierende Warteschlangen erwähnt. ConcurrentLinkedQueue ist jedoch keine blockierende Warteschlange.

Die BlockingQueue s sind ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, PriorityBlockingQueue und SynchronousQueue.

Einige davon sind eindeutig nicht für Ihren Zweck geeignet (DelayQueue, PriorityBlockingQueue und SynchronousQueue). LinkedBlockingQueue und LinkedBlockingDeque sind identisch, mit der Ausnahme, dass es sich bei letzterer um eine doppelte Warteschlange handelt (sie implementiert die Deque-Schnittstelle).

Da ArrayBlockingQueue nur nützlich ist, wenn Sie die Anzahl der Elemente begrenzen möchten, würde ich mich an LinkedBlockingQueue halten.

ArrayBlockingQueue hat einen geringeren Speicherbedarf und kann Elementknoten wiederverwenden, nicht wie LinkedBlockingQueue, die für jede neue Einfügung ein LinkedBlockingQueue $ Node-Objekt erstellen müssen.

1. SynchronousQueue (Aus einem anderen Frage )

SynchronousQueue ist eher eine Übergabe, während LinkedBlockingQueue nur ein einzelnes Element zulässt. Der Unterschied besteht darin, dass der put() -Aufruf an ein SynchronousQueue erst dann zurückgegeben wird, wenn ein entsprechender take() -Aufruf vorliegt, jedoch mit einem LinkedBlockingQueue der Größe 1 wird der put() -Aufruf (an eine leere Warteschlange) sofort zurückgegeben. Dies ist im Wesentlichen die BlockingQueue -Implementierung für den Fall, dass Sie keine Warteschlange benötigen (Sie möchten keine ausstehenden Daten verwalten).

2. LinkedBlockingQueue (LinkedList Implementierung, aber nicht exakt JDK-Implementierung von LinkedList Verwendet die statische innere Klasse Node zur Verwaltung von Verknüpfungen zwischen Elementen)

Konstruktor für LinkedBlockingQueue

public LinkedBlockingQueue(int capacity) 
{
        if (capacity < = 0) throw new IllegalArgumentException();
        this.capacity = capacity;
        last = head = new Node< E >(null);   // Maintains a underlying linkedlist. ( Use when size is not known )
}

Knotenklasse Wird zum Verwalten von Links verwendet

static class Node<E> {
    E item;
    Node<E> next;
    Node(E x) { item = x; }
}

3 . ArrayBlockingQueue (Array-Implementierung)

Konstruktor für ArrayBlockingQueue

public ArrayBlockingQueue(int capacity, boolean fair) 
{
            if (capacity < = 0)
                throw new IllegalArgumentException();
            this.items = new Object[capacity]; // Maintains a underlying array
            lock = new ReentrantLock(fair);
            notEmpty = lock.newCondition();
            notFull =  lock.newCondition();
}

IMHO Der größte Unterschied zwischen ArrayBlockingQueue und LinkedBlockingQueue ist aus dem Konstruktor ersichtlich, dem eine zugrunde liegende Datenstruktur Array und andere linkedList zugrunde liegen.

ArrayBlockingQueue verwendet Single-Lock-Double-Condition-Algorithmus und LinkedBlockingQueue ist eine Variante des "Two Lock Queue" -Algorithmus und hat 2 Sperren 2 Bedingungen (takeLock, putLock)

ConcurrentLinkedQueue ist nicht gesperrt, LinkedBlockingQueue nicht. Jedes Mal, wenn Sie LinkedBlockingQueue.put () oder LinkedBlockingQueue.take () aufrufen, müssen Sie zuerst die Sperre erwerben. Mit anderen Worten, LinkedBlockingQueue weist eine schlechte Parallelität auf. Wenn Sie Leistung interessieren, versuchen Sie ConcurrentLinkedQueue + LockSupport.