ConcurrentLinkedQueue $ Node rimane in heap dopo remove()

Question

Ho un'app multithreading che scrive e legge un ConcurrentLinkedQueue, che è concettualmente utilizzato per eseguire il backing delle voci in un elenco/tabella. Originariamente ho usato una ConcurrentHashMap per questo, che ha funzionato bene. È arrivato un nuovo requisito necessario per tenere traccia delle voci degli ordini, in modo che potessero essere rimossi nel primo ordine meno recente, a seconda di alcune condizioni. ConcurrentLinkedQueue sembrava essere una buona scelta e funzionalmente funzionava bene.

Una quantità configurabile di voci viene mantenuta in memoria e quando viene offerta una nuova voce quando viene raggiunto il limite, la coda viene cercata nel primo ordine più vecchio per uno che può essere rimosso. Alcune voci non devono essere rimosse dal sistema e attendere l'interazione del client.

Quello che sembra accadere è che ho una voce nella parte anteriore della coda che si è verificata, ad esempio 100K voci fa. La coda sembra avere il numero limitato di voci configurate (size() == 100), ma durante la profilazione, ho trovato che c'erano ~ 100K oggetti ConcurrentLinkedQueue $ Node in memoria. Questo sembra essere di progettazione, basta dare un'occhiata all'origine per ConcurrentLinkedQueue, una rimozione rimuove semplicemente il riferimento all'oggetto che viene memorizzato, ma lascia l'elenco collegato in posizione per l'iterazione.

Infine la mia domanda: esiste un modo "migliore" pigro per gestire una raccolta di questa natura? Adoro la velocità di ConcurrentLinkedQueue, non posso permettermi la perdita illimitata che sembra essere possibile in questo caso. In caso contrario, sembra che dovrei creare una seconda struttura per tenere traccia dell'ordine e potrebbe avere gli stessi problemi, oltre a un problema di sincronizzazione.

Answer 1

Ciò che effettivamente accade qui è che il metodo remove prepara un thread di polling per annullare il riferimento collegato.

ConcurrentLinkedQueue è un'implementazione di coda non bloccabile. Tuttavia, quando si tenta di eseguire il polling di un nodo dalla coda, si tratta di un processo a due funzioni. Prima si annulla il valore, quindi si annulla il riferimento. Un'operazione CAS è una singola funzione atomica che non offre una risoluzione immediata per un sondaggio.

Cosa succede quando si esegue il polling è che il primo thread che riesce otterrà il valore del nodo e annullerà tale valore, quindi il thread tenterà di annullare il riferimento. È possibile che entri un altro thread e provi a eseguire il polling dalla coda. Per garantire che questa coda abbia una proprietà non bloccante (cioè un errore di un thread non porti all'errore di un altro thread), quel nuovo thread in entrata vedrà se il valore è null, se è null quel thread annullerà il riferimento e tenterà di nuovo al sondaggio().

Quindi quello che vedete succedere qui è che il thread di rimozione sta semplicemente preparando qualsiasi nuovo thread di polling per azzerare il riferimento. Cercando di ottenere una funzione di rimozione non bloccante, penserei che sia quasi impossibile perché ciò richiederebbe tre funzioni atomiche. Il nullo del valore il riferimento nullo a detto nodo e infine il nuovo riferimento da quel nodo padre al suo successore.

Per rispondere alla tua ultima domanda. Non c'è ingiustamente modo migliore per implementare rimuovere e mantenere lo stato non bloccante della coda. Questo è almeno a questo punto. Una volta che i processori hanno iniziato a uscire con case a 2 e 3 vie, allora è possibile.

Answer 2

La semantica principale della coda è add/poll. Se si utilizza il sondaggio () su ConcurrentLinkedQueue, verrà pulito come dovrebbe. In base alla descrizione, il sondaggio () dovrebbe fornire la rimozione della voce meno recente. Perché non usarlo invece di remove()?

Answer 3

Osservando il codice sorgente per 1.6.0_29, sembra che l'iteratore di CLQ sia stato modificato per provare a rimuovere nodi con elementi null. Invece di:

p = p.getNext(); 

Il codice è ora:

Node<E> next = succ(p); 
if (pred != null && next != null) 
    pred.casNext(p, next); 
p = next; 

Questo è stato aggiunto come parte del fix per il bug: http://bugs.sun.com/view_bug.do?bug_id=6785442

Infatti quando provo il seguente ottengo un OOME con la vecchia versione ma non con la nuova:

Queue<Integer> queue = new ConcurrentLinkedQueue<Integer>(); 
for (int i=0; i<10000; i++) 
{ 
    for (int j=0; j<100000; j++) 
    { 
     queue.add(j); 
    } 
    boolean start = true; 
    for (Iterator<Integer> iter = queue.iterator(); iter.hasNext();) 
    { 
     iter.next(); 
     if (!start) 
      iter.remove(); 
     start = false; 
    } 
    System.out.println(i); 
}