LinkedBlockingQueue vs ConcurrentLinkedQueue

1. Introduzione

LinkedBlockingQueue e ConcurrentLinkedQueue sono le due code simultanee utilizzate più di frequente in Java . Sebbene entrambe le code siano spesso utilizzate come una struttura di dati simultanea, ci sono caratteristiche sottili e differenze comportamentali tra di loro.

In questo breve tutorial, discuteremo di entrambe queste code e spiegheremo le loro somiglianze e differenze.

2. LinkedBlockingQueue

Il LinkedBlockingQueue è opzionalmente delimitata attuazione coda di blocco, il che significa che la dimensione della coda può essere specificato se necessario.

Creiamo una LinkedBlockingQueue che può contenere fino a 100 elementi:

BlockingQueue boundedQueue = new LinkedBlockingQueue(100);

Possiamo anche creare una LinkedBlockingQueue illimitata semplicemente non specificando la dimensione:

BlockingQueue unboundedQueue = new LinkedBlockingQueue();

Una coda senza limiti implica che la dimensione della coda non viene specificata durante la creazione. Pertanto, la coda può crescere dinamicamente man mano che gli elementi vengono aggiunti. Tuttavia, se non è rimasta memoria, la coda genera un'eccezione java.lang.OutOfMemoryError.

Possiamo anche creare una LinkedBlockingQueue da una raccolta esistente:

Collection listOfNumbers = Arrays.asList(1,2,3,4,5); BlockingQueue queue = new LinkedBlockingQueue(listOfNumbers);

La classe LinkedBlockingQueue implementa l' interfaccia BlockingQueue , che le fornisce la natura di blocco .

Una coda di blocco indica che la coda blocca il thread di accesso se è piena (quando la coda è limitata) o diventa vuota. Se la coda è piena, l'aggiunta di un nuovo elemento bloccherà il thread di accesso a meno che non vi sia spazio disponibile per il nuovo elemento. Allo stesso modo, se la coda è vuota, l'accesso a un elemento blocca il thread chiamante:

ExecutorService executorService = Executors.newFixedThreadPool(1); LinkedBlockingQueue queue = new LinkedBlockingQueue(); executorService.submit(() -> { try { queue.take(); } catch (InterruptedException e) { // exception handling } });

Nello snippet di codice sopra, stiamo accedendo a una coda vuota. Pertanto, il metodo take blocca il thread chiamante.

La funzione di blocco di LinkedBlockingQueue è associata a un certo costo. Questo costo è dovuto al fatto che ogni operazione put o take viene contesa tra i thread del produttore o del consumatore. Pertanto, in scenari con molti produttori e consumatori, mettere e intraprendere azioni potrebbe essere più lento.

3. ConcurrentLinkedQueue

Un ConcurrentLinkedQueue è una coda senza limiti, thread-safe e non bloccante.

Creiamo un ConcurrentLinkedQueue vuoto :

ConcurrentLinkedQueue queue = new ConcurrentLinkedQueue();

Possiamo creare un ConcurrentLinkedQueue anche da una raccolta esistente:

Collection listOfNumbers = Arrays.asList(1,2,3,4,5); ConcurrentLinkedQueue queue = new ConcurrentLinkedQueue(listOfNumbers);

A differenza di un LinkedBlockingQueue, un ConcurrentLinkedQueue è una coda non bloccante . Pertanto, non blocca un thread una volta che la coda è vuota. Invece, restituisce null . Poiché è illimitato, lancerà un'eccezione java.lang.OutOfMemoryError se non c'è memoria aggiuntiva per aggiungere nuovi elementi.

Oltre ad essere non bloccante, un ConcurrentLinkedQueue ha funzionalità aggiuntive.

In qualsiasi scenario produttore-consumatore, i consumatori non si accontenteranno dei produttori; tuttavia, più produttori si contenderanno l'un l'altro:

int element = 1; ExecutorService executorService = Executors.newFixedThreadPool(2); ConcurrentLinkedQueue queue = new ConcurrentLinkedQueue(); Runnable offerTask = () -> queue.offer(element); Callable pollTask = () -> { while (queue.peek() != null) { return queue.poll().intValue(); } return null; }; executorService.submit(offerTask); Future returnedElement = executorService.submit(pollTask); assertThat(returnedElement.get().intValue(), is(equalTo(element))); 

La prima attività, offerTask , aggiunge un elemento alla coda e la seconda attività, pollTask, recupera un elemento dalla coda. L'attività di polling controlla inoltre prima la coda per un elemento poiché ConcurrentLinkedQueue non blocca e può restituire un valore null .

4. Somiglianze

Sia LinkedBlockingQueue che ConcurrentLinkedQueue sono implementazioni di code e condividono alcune caratteristiche comuni. Discutiamo le somiglianze di queste due code:

  1. Entrambi implementano l' interfaccia della coda
  2. Entrambi usano nodi collegati per memorizzare i loro elementi
  3. Entrambi sono adatti per scenari di accesso simultaneo

5. Differenze

Sebbene entrambe queste code abbiano alcune somiglianze, ci sono anche differenze sostanziali nelle caratteristiche:

Caratteristica LinkedBlockingQueue ConcurrentLinkedQueue
Bloccare la natura È una coda di blocco e implementa l' interfaccia BlockingQueue È una coda non bloccante e non implementa l' interfaccia BlockingQueue
Dimensione coda È una coda facoltativamente delimitata, il che significa che ci sono disposizioni per definire la dimensione della coda durante la creazione È una coda illimitata e non è possibile specificare la dimensione della coda durante la creazione
Bloccare la natura È una coda basata sul blocco È una coda priva di blocchi
Algoritmo Implementa il suo blocco in base all'algoritmo di coda a due blocchi Si basa sull'algoritmo di Michael & Scott per code non bloccanti e prive di blocchi
Implementazione Nel meccanismo dell'algoritmo della coda a due blocchi , LinkedBlockingQueue utilizza due blocchi diversi: putLock e takeLock . Le operazioni put / take utilizzano il primo tipo di blocco e le operazioni take / poll utilizzano l'altro tipo di blocco Utilizza CAS (Compare-And-Swap ) per le sue operazioni
Comportamento bloccante È una coda di blocco. Quindi, blocca i thread di accesso quando la coda è vuota Non blocca il thread di accesso quando la coda è vuota e restituisce null

6. Conclusione

In questo articolo abbiamo appreso di LinkedBlockingQueue e ConcurrentLinkedQueue.

Innanzitutto, abbiamo discusso individualmente queste due implementazioni della coda e alcune delle loro caratteristiche. Quindi, abbiamo visto le somiglianze tra queste due implementazioni di coda. Infine, abbiamo esplorato le differenze tra queste due implementazioni di coda.

Come sempre, il codice sorgente degli esempi è disponibile su GitHub.