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

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?

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.

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

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.

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.

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

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

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.