LinkedBlockingQueue vs ConcurrentLinkedQueue

112

Moje pytanie dotyczy tego pytania zadanego wcześniej. W sytuacjach, w których używam kolejki do komunikacji między wątkami producenta i konsumenta, czy ludzie ogólnie zalecają używanie LinkedBlockingQueuelub ConcurrentLinkedQueue?

Jakie są zalety / wady używania jednego nad drugim?

Główną różnicą, którą widzę z perspektywy API, jest to, że LinkedBlockingQueuemoże być opcjonalnie ograniczony.

Adamskiego
źródło

Odpowiedzi:

110

W przypadku wątku producenta / konsumenta nie jestem pewien, czy ConcurrentLinkedQueuejest to nawet rozsądna opcja - nie implementuje BlockingQueue, co jest podstawowym interfejsem dla kolejki producentów / konsumentów IMO. Będziesz musiał zadzwonić poll(), trochę poczekać, jeśli nic nie znalazłeś, a następnie ponownie sondować itp., Co prowadzi do opóźnień, gdy pojawia się nowy przedmiot i nieefektywności, gdy jest pusty (z powodu niepotrzebnego budzenia się ze snu) .

Z dokumentacji BlockingQueue:

BlockingQueue implementacje są przeznaczone przede wszystkim dla kolejek producent-konsument

Wiem, że nie jest to ściśle określone , że tylko kolejki blokujące powinny być używane w kolejkach producent-konsument, ale mimo to ...

Jon Skeet
źródło
4
Dzięki Jon - nie zauważyłem tego. Więc gdzie / dlaczego miałbyś używać ConcurrentLinkedQueue?
Adamski
27
Gdy potrzebujesz uzyskać dostęp do kolejki z wielu wątków, ale nie musisz na to „czekać”.
Jon Skeet
2
A ConcurrentLinkedQueuejest również przydatne, jeśli Twój wątek sprawdza wiele kolejek. Na przykład na serwerze z wieloma dzierżawcami. Zakładając, że z powodów izolacji nie używasz zamiast tego pojedynczej kolejki blokowania i dyskryminatora dzierżawy.
LateralFractal
Twój przypadek jest prawdziwy tylko wtedy, gdy używamy ograniczonej kolejki, w nieograniczonej kolejce take()i put()tylko zużywa dodatkowe zasoby (pośrednie synchronizacji) niż ConcurrentLinkedQueue . chociaż tak jest w przypadku stosowania kolejek ograniczonych w scenariuszach producent-konsument
amarnath harish
@Adamski IMO, ConcurrentLinkedQueue to po prostu lista linków do użytku w środowisku wielowątkowym. Najlepszą analogią do tego byłoby ConcurrentHashMap i HashMap.
Nishit
69

To pytanie zasługuje na lepszą odpowiedź.

Java ConcurrentLinkedQueuejest oparta na słynnym algorytmie Mageda M. Michaela i Michaela L. Scotta, który zapewnia brak blokowania bez blokowania kolejek .

„Nieblokujący” jako termin określający rywalizujący zasób (nasza kolejka) oznacza, że ​​niezależnie od tego, co robi program planujący platformy, np. Przerywa wątek, lub jeśli dany wątek jest po prostu zbyt wolny, inne wątki rywalizują o ten sam zasób nadal będzie mógł się rozwijać. Jeśli na przykład występuje blokada, wątek utrzymujący blokadę może zostać przerwany, a wszystkie wątki oczekujące na tę blokadę zostaną zablokowane. Wewnętrzne blokady ( synchronizedsłowo kluczowe) w Javie mogą również wiązać się z poważnymi spadkami wydajności - na przykład w przypadku blokowania stronniczegojest zaangażowany i masz rywalizację lub po tym, jak maszyna wirtualna zdecyduje się „nadmuchać” blokadę po okresie karencji obrotu i zablokować rywalizujące wątki ... dlatego w wielu kontekstach (scenariusze niskiej / średniej rywalizacji) wykonując porównania i -sets na atomowych referencjach może być znacznie bardziej wydajne i właśnie to robi wiele nieblokujących struktur danych.

Java ConcurrentLinkedQueuejest nie tylko nieblokująca, ale ma niesamowitą właściwość polegającą na tym, że producent nie walczy z konsumentem. W scenariuszu z jednym producentem / pojedynczym konsumentem (SPSC) oznacza to naprawdę, że nie będzie o czym mówić. W scenariuszu z wieloma producentami / jednym konsumentem konsument nie będzie walczył z producentami. W tej kolejce występuje rywalizacja, gdy wielu producentów próbuje offer(), ale z definicji jest to współbieżność. Jest to w zasadzie wydajna kolejka bez blokowania ogólnego przeznaczenia.

A jeśli chodzi o to, że nie jest to BlockingQueue, no cóż, blokowanie wątku w celu oczekiwania w kolejce, to niesamowicie okropny sposób projektowania systemów współbieżnych. Nie. Jeśli nie możesz dowiedzieć się, jak użyć ConcurrentLinkedQueuescenariusza konsumenta / producenta, po prostu przełącz się na abstrakcje wyższego poziomu, takie jak dobre ramy dla aktorów.

Alexandru Nedelcu
źródło
8
W swoim ostatnim akapicie, dlaczego twierdzisz, że czekanie w kolejce to straszny sposób projektowania współbieżnych systemów? Jeśli mamy grupę wątków z 10 wątkami zjadającymi zadania z kolejki zadań, co jest złego w blokowaniu, gdy kolejka zadań ma mniej niż 10 zadań?
Pacerier,
11
@AlexandruNedelcu Nie można wydać rozległego stwierdzenia, takiego jak „szalenie okropne”, w którym bardzo często te same frameworki aktorów, o których mówisz, używają puli wątków, które same są przez ciebie BlockingQueue . Jeśli potrzebujesz wysoce reaktywnego systemu i wiesz, jak radzić sobie z przeciwciśnieniem (czymś, co łagodzi kolejki blokujące), to nieblokowanie jest zdecydowanie lepsze. Ale ... często blokowanie IO i blokowanie kolejek może nie działać bez blokowania, szczególnie jeśli masz długo działające zadania, które są ograniczone IO i nie można ich podzielić i pokonać.
Adam Gent
1
@AdamGent - Framework aktorów ma implementację skrzynek pocztowych w oparciu o blokowanie kolejek, ale moim zdaniem jest to błąd, ponieważ blokowanie nie działa poza granicami asynchronicznymi, a zatem działa tylko w wersjach demonstracyjnych. Dla mnie było to źródłem frustracji, ponieważ na przykład koncepcja radzenia sobie z przepełnieniem polega na blokowaniu, zamiast porzucać wiadomości, aż do wersji 2.4, która jeszcze nie jest dostępna. To powiedziawszy, nie wierzę, że istnieją przypadki użycia, w których kolejki blokujące mogą być lepsze. Łączysz również dwie rzeczy, których nie należy łączyć. Nie mówiłem o blokowaniu I / O.
Alexandru Nedelcu
1
@AlexandruNedelcu Chociaż generalnie zgadzam się z tobą w sprawie przeciwciśnienia, nie widziałem jeszcze systemu „bez zamków” od góry do dołu. Gdzieś w stosie technologii, czy to Node.js, Erlang, Golang, używa jakiejś strategii czekania, niezależnie od tego, czy jest to kolejka blokująca (blokady), czy CAS obracający blokowanie, a w niektórych przypadkach tradycyjna strategia blokowania jest szybsza. Bardzo trudno jest nie mieć blokad ze względu na spójność, a jest to szczególnie ważne w przypadku blokowania io i harmonogramów, które są ~ producentem / konsumentem. ForkJoinPool działa z krótkimi zadaniami i nadal ma wirujące blokady CAS.
Adam Gent
1
@AlexandruNedelcu Wydaje mi się, że jeśli możesz mi pokazać, jak możesz użyć ConcurrentLinkedQueue (która nie jest ograniczona, stąd mój słaby argument przeciwprężny) dla wzorca Producent / Konsument, który jest wzorcem potrzebnym do planowania i łączenia wątków Myślę, że poddam się i przyznam, że BlockingQueue nigdy nie powinno być używane (i nie możesz oszukiwać i delegować na coś innego zajmującego się planowaniem, tj. Akka, ponieważ to z kolei zrobi blokowanie / czekanie, ponieważ jest producentem / konsumentem).
Adam Gent
33

LinkedBlockingQueueblokuje konsumenta lub producenta, gdy kolejka jest pusta lub pełna, a odpowiedni wątek konsumenta / producenta jest uśpiony. Ale ta funkcja blokowania wiąże się z kosztami: każda operacja typu put lub take jest blokowana między producentami lub konsumentami (jeśli jest ich wielu), więc w scenariuszach z wieloma producentami / konsumentami operacja może być wolniejsza.

ConcurrentLinkedQueuenie używa blokad, ale CAS w swoich operacjach typu put / take potencjalnie redukuje rywalizację z wieloma wątkami producentów i konsumentów. Ale bycie „wolne” czekać strukturę danych, ConcurrentLinkedQueuenie będzie blokować gdy pusty, co oznacza, że konsument będzie musiał uporać się z take()powracającym nullwartości przez „zajęty oczekiwania”, na przykład, z gwintem konsument pochłania CPU.

Zatem, który z nich jest „lepszy”, zależy od liczby wątków konsumenckich, tempa ich konsumpcji / produkcji itp. Dla każdego scenariusza potrzebny jest punkt odniesienia.

Jeden szczególny przypadek użycia, w którym ConcurrentLinkedQueuejest wyraźnie lepiej, to sytuacja, gdy producenci najpierw coś wytwarzają i kończą pracę, umieszczając pracę w kolejce i dopiero po tym, jak konsumenci zaczną konsumować, wiedząc, że zrobią to, gdy kolejka będzie pusta. (tutaj nie ma współbieżności między producentem-konsumentem, ale tylko między producentem-producentem a konsumentem-konsumentem)

dcernahoschi
źródło
tu jedna wątpliwość. Jak wspomniałeś, konsument czeka, kiedy kolejka jest pusta… jak długo czeka. Kto powiadomi go, aby nie czekał?
Brinal
@brindal Jedynym sposobem, aby czekać, o czym wiem, jest zapętlenie. Co jest znaczącym problemem, któremu nie poświęcono wiele uwagi w odpowiedziach tutaj. Samo wykonanie pętli czekającej na dane zajmuje dużo czasu procesora. Dowiesz się, kiedy Twoi fani zaczną się rozwijać Jedynym rozwiązaniem jest uśpienie w pętli. Jest to więc problem w systemie z niespójnym przepływem danych. Być może źle zrozumiałem odpowiedź AlexandruNedelcu, ale sam system operacyjny jest systemem współbieżnym, który byłby niezwykle nieefektywny, gdyby był pełen nieblokujących pętli zdarzeń.
orodbhen
w porządku, ale jeśli unbounded blockingqueuezostanie użyte, byłoby lepsze niż równoległe oparte na CASConcurrentLinkedQueue
amarnath harish
@orodbhen Uśpienie również nie wyeliminowałoby marnotrawstwa. System operacyjny musi wykonać dużo pracy, aby wyprowadzić wątek ze snu, zaplanować i uruchomić go. Jeśli wiadomości nie są jeszcze dostępne, praca wykonana przez system operacyjny idzie na marne. Poleciłbym lepiej użyć BlockingQueue, ponieważ został zaprojektowany specjalnie dla problemu producent-konsument.
Nishit
właściwie, jestem bardzo zainteresowany częścią „wskaźnik konsumpcji / produkcji”, więc która z nich jest lepsza, jeśli stawka rośnie?
workplaylifecycle
0

Innym rozwiązaniem (które nie skaluje się dobrze) są kanały rendezvous: java.util.concurrent SynchronousQueue

Ovidiu Lupas
źródło
0

Jeśli kolejka nie jest rozwijalna i zawiera tylko jeden wątek producenta / konsumenta. Możesz korzystać z kolejki bez blokady (nie musisz blokować dostępu do danych).

Rahul
źródło