Implementazioni di Java Queue, quale?

Da Javadoc:

  • Un ConcurrentLinkedQueue è una scelta appropriata quando molti thread condivideranno l’accesso a una raccolta comune. Questa coda non consente elementi null.
  • ArrayBlockingQueue è un classico “buffer limitato”, in cui un array di dimensioni fisse contiene elementi inseriti dai produttori ed estratti dai consumatori. Questa class supporta una politica di equità opzionale per ordinare i filati dei produttori e dei consumatori in attesa
  • In genere, LinkedBlockingQueue ha un throughput più elevato rispetto alle code basate su array, ma prestazioni meno prevedibili nella maggior parte delle applicazioni concorrenti.

Ho 2 scenari, uno richiede la coda per supportare molti produttori (thread che lo usano) con un consumatore e l’altro è il contrario.

Non sto capendo se dovrei usare ConcurrentLikedQueue o gli altri (l’array o le implementazioni di linkList). Considerando che tutte queste implementazioni dovrebbero essere concomitanti? Voglio dire, qualcuno può spiegarmi qual è la differenza tra ConcurrentLikedQueue e LinkedBlockingQueue ?

Inoltre, qual è la cosa di politica di equità opzionale in ArrayBlockingQueue favore?

Fondamentalmente la differenza tra loro sono le caratteristiche di performance e il comportamento di blocco.

Prendendo per primo il più semplice, ArrayBlockingQueue è una coda di dimensioni fisse. Quindi, se si imposta la dimensione su 10 e si tenta di inserire un undicesimo elemento, l’istruzione di inserimento bloccherà fino a quando un altro thread non rimuoverà un elemento. Il problema dell’equità è cosa succede se più thread tentano di inserire e rimuovere contemporaneamente (in altre parole durante il periodo in cui la coda è stata bloccata). Un algoritmo di correttezza garantisce che il primo thread che chiede sia il primo thread che ottiene. In caso contrario, un dato thread potrebbe attendere più a lungo degli altri thread, causando un comportamento imprevedibile (a volte un thread richiederà solo alcuni secondi perché gli altri thread avviati successivamente vengono elaborati per primi). Il compromesso è che prende il sopravvento per gestire l’equità, rallentando il rendimento.

La differenza più importante tra LinkedBlockingQueue e ConcurrentLinkedQueue è che se si richiede un elemento da un object LinkedBlockingQueue e la coda è vuota, il thread attenderà finché non ci sarà qualcosa lì. A ConcurrentLinkedQueue tornerà subito con il comportamento di una coda vuota.

Quale dipende se hai bisogno del blocco. Dove hai molti produttori e un solo consumatore, sembra che sia così. D’altra parte, dove si hanno molti consumatori e un solo produttore, potrebbe non essere necessario il comportamento di blocco, e potrebbe essere felice di avere solo i consumatori che controllano se la coda è vuota e se si muove.

ConcurrentLinkedQueue significa che non vengono eseguiti blocchi (ovvero non sincronizzati (questo) o chiamate Lock.lock ). Utilizzerà un’operazione CAS – Confronta e scambia durante le modifiche per vedere se il nodo testa / coda è ancora lo stesso di quando è iniziato. Se è così, l’operazione ha successo. Se il nodo testa / coda è diverso, girerà intorno e riproverà.

LinkedBlockingQueue prenderà un blocco prima di qualsiasi modifica. Quindi le tue chiamate di offerta si bloccerebbero fino a quando non ottengono il blocco. È ansible utilizzare l’overload dell’offerta che richiede un TimeUnit per dire che si è disposti ad attendere X quantità di tempo prima di abbandonare l’add (solitamente buono per le code del tipo di messaggio in cui il messaggio è scaduto dopo il numero X di millisecondi).

Equità significa che l’implementazione di Blocco manterrà i fili ordinati. Significato se il thread A entra e quindi il thread B entra, il thread A otterrà il blocco per primo. Senza equità, è davvero indefinito ciò che accade. Molto probabilmente sarà il prossimo thread che verrà programmato.

Per quanto riguarda quale usare, dipende. Tendo ad usare ConcurrentLinkedQueue perché il tempo necessario ai miei produttori per ottenere il lavoro da mettere in coda è vario. Non ho molti produttori che producono nello stesso momento. Ma il lato del consumatore è più complicato perché il sondaggio non entrerà in un piacevole stato di sonno. Devi gestirlo da solo.

Il titolo della tua domanda menziona le code di blocco. Tuttavia, ConcurrentLinkedQueue non è una coda di blocco.

I BlockingQueue sono ArrayBlockingQueue , DelayQueue , LinkedBlockingDeque , LinkedBlockingQueue , PriorityBlockingQueue e SynchronousQueue .

Alcuni di questi sono chiaramente non adatti al tuo scopo ( DelayQueue , PriorityBlockingQueue e SynchronousQueue ). LinkedBlockingQueue e LinkedBlockingDeque sono identici, tranne che il secondo è una coda a doppio LinkedBlockingDeque (implementa l’interfaccia di Deque).

Dato che ArrayBlockingQueue è utile solo se vuoi limitare il numero di elementi, rimango a LinkedBlockingQueue .

ArrayBlockingQueue ha un minore ingombro di memoria, può riutilizzare il nodo di elementi, non come LinkedBlockingQueue che deve creare un object LinkedBlockingQueue $ Node per ogni nuovo inserimento.

  1. SynchronousQueue (Tratto da un’altra domanda )

SynchronousQueue è più un handoff, mentre LinkedBlockingQueue consente solo un singolo elemento. La differenza è che la chiamata put () a un SynchronousQueue non ritorna finché non c’è una corrispondente chiamata take (), ma con un LinkedBlockingQueue di dimensione 1, la chiamata put () (a una coda vuota) verrà restituita immediatamente. È essenzialmente l’implementazione di BlockingQueue per quando non si desidera realmente una coda (non si desidera mantenere alcun dato in sospeso).

2. LinkedBlockingQueue (Implementazione LinkedList ma non esattamente Implementazione JDK di LinkedList Utilizza il nodo di class interno statico per mantenere collegamenti tra gli elementi)

Costruttore per 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 ) } 

Classe nodo utilizzata per il mantenimento dei collegamenti

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

3. ArrayBlockingQueue (implementazione dell’array)

Costruttore per 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 La più grande differenza tra ArrayBlockingQueue e LinkedBlockingQueue è chiara dal costruttore con la matrice di dati sottostante Array e altri linkedList .

ArrayBlockingQueue utilizza un algoritmo a doppia condizione a blocco singolo e LinkedBlockingQueue è una variante dell'algoritmo "two lock queue" e presenta 2 condizioni di lock 2 (takeLock, putLock)

ConcurrentLinkedQueue è lock-free, LinkedBlockingQueue no. Ogni volta che invochi LinkedBlockingQueue.put () o LinkedBlockingQueue.take (), devi prima acquisire il blocco. In altre parole, LinkedBlockingQueue ha una scarsa concorrenza. Se ti interessa la prestazione, prova ConcurrentLinkedQueue + LockSupport.