wake-up-neo.com

Welche gleichzeitige Queue-Implementierung sollte ich in Java verwenden?

Aus den JavaDocs:

  • Ein ConcurrentLinkedQueue ist eine geeignete Wahl, wenn viele Threads den Zugriff auf eine gemeinsame Sammlung teilen. Diese Warteschlange erlaubt keine Null-Elemente.
  • ArrayBlockingQueue ist ein klassischer "Bounded Buffer", in dem ein Array fester Größe Elemente enthält, die von Produzenten eingefügt und von Konsumenten extrahiert wurden. Diese Klasse unterstützt eine optionale Fairness-Richtlinie zum Bestellen wartender Produzenten- und Konsumententhreads
  • LinkedBlockingQueue hat normalerweise einen höheren Durchsatz als Array-basierte Warteschlangen, ist jedoch in den meisten gleichzeitigen Anwendungen weniger vorhersehbar.

Ich habe 2 Szenarien, eines erfordert, dass die Warteschlange viele Produzenten (Threads, die es verwenden) mit einem Konsumenten unterstützt und das andere umgekehrt.

Ich verstehe nicht, welche Implementierung ich verwenden soll. Kann jemand die Unterschiede erklären?

Was ist die optionale Fairness-Richtlinie in ArrayBlockingQueue?

122
David Hofmann

Grundsätzlich unterscheiden sie sich durch Leistungsmerkmale und Sperrverhalten.

Bei ArrayBlockingQueue handelt es sich um eine Warteschlange mit fester Größe. Wenn Sie also die Größe auf 10 festlegen und versuchen, ein 11. Element einzufügen, wird die insert-Anweisung blockiert, bis ein anderer Thread ein Element entfernt. Das Fairness-Problem tritt auf, wenn mehrere Threads gleichzeitig versuchen, Threads einzufügen und zu entfernen (mit anderen Worten während des Zeitraums, in dem die Warteschlange blockiert war). Ein Fairness-Algorithmus stellt sicher, dass der erste Thread, der fragt, der erste Thread ist, der abgerufen wird. Andernfalls wartet ein bestimmter Thread möglicherweise länger als andere Threads, was zu unvorhersehbarem Verhalten führt (manchmal dauert ein Thread nur einige Sekunden, da andere Threads, die später gestartet wurden, zuerst verarbeitet wurden). Der Kompromiss besteht darin, dass die Verwaltung der Fairness einen Mehraufwand erfordert und der Durchsatz verlangsamt wird.

Der wichtigste Unterschied zwischen LinkedBlockingQueue und ConcurrentLinkedQueue besteht darin, dass, wenn Sie ein Element von einem LinkedBlockingQueue anfordern und die Warteschlange leer ist, Ihr Thread wartet, bis sich dort etwas befindet. Ein ConcurrentLinkedQueue kehrt sofort mit dem Verhalten einer leeren Warteschlange zurück.

Welches hängt davon ab, ob Sie die Sperre benötigen. Wo es viele Produzenten und einen Konsumenten gibt, klingt es so. Auf der anderen Seite, wenn Sie viele Verbraucher und nur einen Erzeuger haben, benötigen Sie möglicherweise nicht das Sperrverhalten und können sich freuen, wenn nur die Verbraucher prüfen, ob die Warteschlange leer ist, und wenn dies der Fall ist, fortfahren.

47
Yishai

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.

109
Justin Rudd

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.

8
Powerlord

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.

4
Deng
  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).

  1. 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)

1
Vipin

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.

0
user319609