Której współbieżnej implementacji kolejki należy używać w języku Java?

134

Z JavaDocs:

  • ConcurrentLinkedQueue jest właściwym wyborem, gdy wiele wątków będzie współużytkować dostęp do wspólnej kolekcji. Ta kolejka nie zezwala na elementy puste.
  • ArrayBlockingQueue to klasyczny „ograniczony bufor”, w którym tablica o stałej wielkości zawiera elementy wstawiane przez producentów i wyodrębniane przez konsumentów. Ta klasa obsługuje opcjonalne zasady uczciwości dotyczące zamawiania oczekujących wątków producenta i konsumenta
  • LinkedBlockingQueue zwykle ma wyższą przepustowość niż kolejki oparte na tablicach, ale mniej przewidywalną wydajność w większości współbieżnych aplikacji.

Mam 2 scenariusze, jeden wymaga kolejki do obsługi wielu producentów (wątków z niej korzystających) z jednym konsumentem, a drugi na odwrót.

Nie rozumiem, której implementacji użyć. Czy ktoś może wyjaśnić, jakie są różnice?

Co to jest „opcjonalna polityka uczciwości” w ArrayBlockingQueue?

David Hofmann
źródło
1
Zapomniałeś również zapytać o PriorityBlockingQueue, co jest przydatne do określenia kolejności przetwarzania wątków.
Igor Ganapolsky

Odpowiedzi:

55

Zasadniczo różnica między nimi polega na charakterystyce wydajności i zachowaniu blokującym.

Najłatwiejszym rozwiązaniem ArrayBlockingQueuejest kolejka o ustalonym rozmiarze. Więc jeśli ustawisz rozmiar na 10 i spróbujesz wstawić jedenasty element, instrukcja insert będzie blokować, dopóki inny wątek nie usunie elementu. Problem z uczciwością polega na tym, co się dzieje, gdy wiele wątków próbuje wstawiać i usuwać w tym samym czasie (innymi słowy w okresie, w którym kolejka została zablokowana). Algorytm uczciwości zapewnia, że ​​pierwszy wątek, który pyta, jest pierwszym wątkiem, który otrzyma. W przeciwnym razie dany wątek może czekać dłużej niż inne wątki, powodując nieprzewidywalne zachowanie (czasami jeden wątek zajmuje tylko kilka sekund, ponieważ inne wątki, które zaczęły się później, były przetwarzane jako pierwsze). Kompromis polega na tym, że zarządzanie uczciwością zajmuje koszty ogólne, spowalniając przepustowość.

Najważniejsza różnica między LinkedBlockingQueuei ConcurrentLinkedQueuepolega na tym, że jeśli zażądasz elementu z a, LinkedBlockingQueuea kolejka jest pusta, Twój wątek będzie czekał, aż coś tam będzie. A ConcurrentLinkedQueuewróci od razu z zachowaniem pustej kolejki.

Który zależy od tego, czy potrzebujesz blokowania. Tam, gdzie masz wielu producentów i jednego konsumenta, wygląda na to. Z drugiej strony, gdy masz wielu konsumentów i tylko jednego producenta, możesz nie potrzebować zachowania blokującego i możesz być szczęśliwy, gdy konsumenci sprawdzą, czy kolejka jest pusta, i przejdą dalej, jeśli tak jest.

Yishai
źródło
68
Odpowiedź jest myląca. Zarówno LinkedBlockingQueue, jak i ConcurrentLinkedQueue mają metodę „poll ()”, która usuwa nagłówek kolejki lub zwraca wartość null (nie blokuje), oraz metodę „offer (E e)”, która wstawia do końca kolejki i nie blokuje. Różnica polega na tym, że tylko LinkedBlockingQueue ma operacje blokujące oprócz operacji nieblokujących - i za ten przywilej płacisz cenę, którą LinkedBlockingQueue faktycznie ma pewne blokowanie. Druga odpowiedź wyjaśnia to.
Naga
124

ConcurrentLinkedQueue oznacza, że ​​żadne blokady nie są przyjmowane (tj. Żadne zsynchronizowane (this) lub wywołania Lock.lock ). Podczas modyfikacji użyje operacji CAS - Compare and Swap, aby sprawdzić, czy węzeł główny / końcowy jest nadal taki sam, jak podczas uruchamiania. Jeśli tak, operacja powiedzie się. Jeśli węzeł głowy / ogona jest inny, obróci się i spróbuje ponownie.

LinkedBlockingQueue podejmie blokadę przed jakąkolwiek modyfikacją. Więc Twoje połączenia z ofertą będą blokowane, dopóki nie zostaną zablokowane. Możesz użyć przeciążenia oferty, które wymaga TimeUnit, aby powiedzieć, że chcesz poczekać tylko X czasu przed porzuceniem dodawania (zwykle dobre w przypadku kolejek typu wiadomości, w których wiadomość jest nieaktualna po upływie X milisekund).

Uczciwość oznacza, że ​​implementacja Lock zachowa kolejność wątków. Oznacza to, że jeśli Wątek A wejdzie, a następnie Wątek B, Wątek A otrzyma najpierw blokadę. Bez uczciwości nie jest zdefiniowane, co się naprawdę dzieje. Najprawdopodobniej będzie to następny wątek, który zostanie zaplanowany.

To zależy od tego, którego użyć. Zwykle używam ConcurrentLinkedQueue, ponieważ czas potrzebny moim producentom na umieszczenie pracy w kolejce jest zróżnicowany. Nie mam wielu producentów produkujących dokładnie w tym samym momencie. Ale strona konsumencka jest bardziej skomplikowana, ponieważ ankieta nie przejdzie w przyjemny stan snu. Musisz sobie z tym poradzić.

Justin Rudd
źródło
1
A w jakich warunkach ArrayBlockingQueue jest lepsza niż LinkedBlockingQueue?
kolobok
@akapelko ArrayBlockingQueue pozwala na bardziej szczegółowe porządkowanie.
IgorGanapolsky
2
Co to znaczy - „obróci się i spróbuje ponownie”. ?
Lester
9

W tytule Twojego pytania jest mowa o kolejkach blokujących. Jednak nieConcurrentLinkedQueue jest to kolejka blokująca.

Do BlockingQueues są ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, PriorityBlockingQueue, i SynchronousQueue.

Niektóre z nich z pewnością nie nadają się do celu ( DelayQueue, PriorityBlockingQueue, i SynchronousQueue). LinkedBlockingQueuei LinkedBlockingDequesą identyczne, z tą różnicą, że ta ostatnia jest kolejką dwustronną (implementuje interfejs Deque).

Ponieważ ArrayBlockingQueuejest to przydatne tylko wtedy, gdy chcesz ograniczyć liczbę elementów, trzymałbym się LinkedBlockingQueue.

Powerlord
źródło
Usunąłem słowo blokujące z tytułu, dzięki. Pozwól, że zobaczę, czy to rozumiem, to, co powiedziałeś, oznacza, że ​​LinkedBlockingQueue może być używany w wielu konsumentach / scenariuszach tworzących na tym samym obiekcie?
David Hofmann
1
Myślałem, że ArrayBlockingQueue pozwala na bardziej precyzyjne porządkowanie wątków? Stąd jego zaleta.
Igor Ganapolsky
4

ArrayBlockingQueue ma mniejszy ślad pamięci, może ponownie wykorzystać węzeł elementu, a nie jak LinkedBlockingQueue, który musi tworzyć obiekt LinkedBlockingQueue $ Node dla każdego nowego wstawienia.

Deng
źródło
1
Słuszna uwaga! wolę ArrayBlockingQueue bardziej niż LinkedBlockingQueue
biliony
2
Niekoniecznie jest to prawdą - jeśli kolejka jest bliska opróżnienia przez ArrayBlockingQueuedługi czas, ale musi być w stanie się rozrosnąć, będzie miała znacznie gorszy ślad pamięci - nadal ma dużą tablicę przydzieloną w pamięci przez cały czas LinkedBlockingQueuebędzie miał znikomy ślad pamięci, gdy w pobliżu pusty.
Krease
1
  1. SynchronousQueue(Zaczerpnięte z innego pytania )

SynchronousQueueto raczej przekazanie, podczas gdy LinkedBlockingQueuetylko zezwala na pojedynczy element. Różnica polega na tym, że put()wywołanie a SynchronousQueuenie powróci, dopóki nie pojawi się odpowiednie take()wywołanie, ale przy LinkedBlockingQueuerozmiarze 1 put()wywołanie (do pustej kolejki) powróci natychmiast. Zasadniczo jest to BlockingQueueimplementacja, gdy naprawdę nie chcesz kolejki (nie chcesz utrzymywać żadnych oczekujących danych).

  1. LinkedBlockingQueue( LinkedListImplementacja, ale nie dokładnie JDK Implementacja tego LinkedListużywa statycznej klasy wewnętrznej Node do utrzymywania połączeń między elementami)

Konstruktor dla 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 )
}

Klasa węzła używana do utrzymywania łączy

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

3. ArrayBlockingQueue (implementacja tablicy)

Konstruktor dla 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 Największa różnica między ArrayBlockingQueuei LinkedBlockingQueuejest oczywista z konstruktora, jeden ma podstawową strukturę danych Array i inny linkedList .

ArrayBlockingQueueużywa algorytmu pojedynczej blokady i podwójnego warunku i LinkedBlockingQueuejest wariantem algorytmu "kolejki dwóch blokad" i ma 2 blokady 2 warunki (takeLock, putLock)

Vipin
źródło
0

ConcurrentLinkedQueue nie zawiera blokad, a LinkedBlockingQueue nie. Za każdym razem, gdy wywołujesz LinkedBlockingQueue.put () lub LinkedBlockingQueue.take (), musisz najpierw uzyskać blokadę. Innymi słowy, LinkedBlockingQueue ma słabą współbieżność. Jeśli zależy Ci na wydajności, wypróbuj ConcurrentLinkedQueue + LockSupport.

user319609
źródło