LinkedBlockingQueue vs ConcurrentLinkedQueue

Question

La mia domanda riguarda questa domanda chiesto prima. In situazioni in cui sto usando una coda per la comunicazione tra i thread del produttore e del consumatore, le persone generalmente raccomanderebbero l'uso di LinkedBlockingQueue o ConcurrentLinkedQueue ?

Quali sono i vantaggi / gli svantaggi dell'utilizzo l'uno rispetto all'altro?

La principale differenza che posso vedere dal punto di vista dell'API è che un LinkedBlockingQueue può essere facoltativamente limitato.

Answer 1

Per un thread produttore / consumatore, non sono sicuro che ConcurrentLinkedQueue sia persino un'opzione ragionevole - non implementa BlockingQueue , che è l'interfaccia fondamentale per code produttore / consumatore IMO. Dovresti chiamare poll () , attendere un po 'se non avessi trovato nulla, e quindi sondare di nuovo ecc ... portando a ritardi quando arriva un nuovo oggetto e inefficienze quando è vuoto (a causa del risveglio inutile dal sonno).

Dai documenti per BlockingQueue:

  Le implementazioni

?? BlockingQueue sono progettate per essere utilizzate principalmente per le code produttore-consumatore

So che non rigorosamente dice che dovrebbero essere usate solo code di blocco per le code produttore-consumatore, ma anche così ...

Answer 2

Questa domanda merita una risposta migliore.

Il ConcurrentLinkedQueue di Java si basa sul famoso algoritmo di Maged M. Michael e Michael L . Scott per code senza blocco senza blocco.

" non bloccante " come termine qui per una risorsa contesa (la nostra coda) significa che indipendentemente da ciò che fa lo scheduler della piattaforma, come interrompere un thread o se il thread in questione è semplicemente troppo lento, altri thread contendenti per la stessa risorsa saranno ancora in grado di progresso. Se ad esempio è coinvolto un blocco, il thread che tiene il blocco potrebbe essere interrotto e tutti i thread in attesa di quel blocco verrebbero bloccati. I blocchi intrinseci (la parola chiave sincronizzata ) in Java possono anche comportare una grave penalità per le prestazioni, come quando blocco distorto è coinvolto e si ha contesa, o dopo che la VM ha deciso di" gonfiare " il blocco dopo un periodo di tolleranza di spin e il blocco dei thread contendenti ... ecco perché in molti contesti (scenari di contesa medio / bassa), fare confronti e insiemi su riferimenti atomici può essere molto più efficiente e questo è esattamente ciò che molti non stanno bloccando le strutture di dati.

Il ConcurrentLinkedQueue di Java non è solo non bloccante, ma ha la straordinaria proprietà che il produttore non contesta il consumatore. In uno scenario a singolo produttore / singolo consumatore (SPSC), ciò significa che non ci sarà alcuna contesa di cui parlare. In uno scenario a produttore multiplo / singolo consumatore, il consumatore non contenderà i produttori. Questa coda è contesa quando più produttori provano a offer () , ma questa è concorrenza per definizione. È fondamentalmente uno scopo generico ed efficiente coda non bloccante.

Per quanto non sia un BlockingQueue , beh, bloccare un thread in attesa di una coda è un modo stranamente terribile di progettare sistemi concorrenti. Non farlo. Se non riesci a capire come utilizzare un ConcurrentLinkedQueue in uno scenario consumatore / produttore, passa alle astrazioni di livello superiore, come un buon framework per attori.

Answer 3

LinkedBlockingQueue blocca il consumatore o il produttore quando la coda è vuota o piena e il rispettivo thread consumatore / produttore viene messo in sospensione. Ma questa funzione di blocco ha un costo: ogni operazione put o take è contesa tra produttori o consumatori (se molti), quindi in scenari con molti produttori / consumatori l'operazione potrebbe essere più lenta.

ConcurrentLinkedQueue non utilizza i blocchi, ma CAS , nelle sue operazioni put / take che riducono potenzialmente la contesa con molti thread di produttori e consumatori. Ma essendo un " aspetta gratis " la struttura dei dati, ConcurrentLinkedQueue non si bloccherà se vuota, il che significa che il consumatore dovrà gestire i take () restituendo i valori null di " occupato ad aspettare " ;, ad esempio, con il thread consumer che consuma CPU.

Quindi quale è "migliore" dipende dal numero di thread dei consumatori, dal tasso che consumano / producono, ecc. Per ogni scenario è necessario un benchmark.

Un caso particolare in cui ConcurrentLinkedQueue è chiaramente migliore è quando i produttori producono e finiscono il loro lavoro inserendo il lavoro nella coda e solo dopo i consumatori iniziano consumare, sapendo che saranno fatti quando la coda è vuota. (qui non c'è concorrenza tra produttore-consumatore ma solo tra produttore-produttore e consumatore-consumatore)

Answer 4

Un'altra soluzione (che non si adatta bene) è i canali di appuntamento: java.util.concurrent SynchronousQueue

Answer 5

Se la coda non è espandibile e contiene solo un thread produttore / consumatore. È possibile utilizzare la coda senza blocco (non è necessario bloccare l'accesso ai dati).