ConcurrentLinkedQueue $ nodo rimane in mucchio, dopo remove ()

Question

Ho una scrittura applicazione multithread e la lettura di un ConcurrentLinkedQueue, che è concettualmente utilizzato per eseguire le voci di un elenco / tavolo. All'inizio ho usato una ConcurrentHashMap per questo, che ha funzionato bene. Un nuovo requisito richiesto il monitoraggio delle voci di ordine è arrivato, in modo che potrebbe essere rimosso nel più antico primo ordine, a seconda di alcune condizioni. ConcurrentLinkedQueue sembrava essere una buona scelta, e funzionalmente funziona bene.

Una quantità configurabile di voci si svolgono in memoria, e quando una nuova voce viene offerto quando viene raggiunto il limite, la coda viene ricercato nel più antico-primo ordine per uno che può essere rimosso. Certe voci non devono essere rimossi dal sistema e attendere interazione client.

Quello che sembra accadere è che ho una voce nella parte anteriore della coda che si è verificato, ad esempio 100K voci fa. La coda sembra avere il numero limitato di voci configurate (dimensione () == 100), ma quando profiling, ho scoperto che ci sono stati gli oggetti di 100K ConcurrentLinkedQueue $ Nodo in memoria. Questo sembra essere in base alla progettazione, un semplice sguardo alla fonte per ConcurrentLinkedQueue, un remove rimuove solo il riferimento all'oggetto viene memorizzato, ma lascia la lista collegata al suo posto per l'iterazione.

Infine la mia domanda: Esiste un "migliore" modo pigro per gestire una collezione di questa natura? Amo la velocità della ConcurrentLinkedQueue, ho appena posso permettermi la perdita illimitata che sembra essere possibile in questo caso. In caso contrario, sembra che avrei dovuto creare una seconda struttura per monitorare l'ordine e posso avere gli stessi problemi, più una preoccupazione di sincronizzazione.

Answer 1

Che cosa realmente sta accadendo qui è il metodo remove prepara un filetto di polling a null il riferimento collegato.

Il ConcurrentLinkedQueue è un'implementazione coda non adatti filo bloccante. Tuttavia, quando si tenta di eseguire il polling un nodo dalla coda si tratta di un processo a due funzioni. Per prima cosa il valore NULL allora nullo il riferimento. Un'operazione CAS è una singola funzione atomica che non avrebbe offerto la risoluzione immidiate per un sondaggio.

Cosa succede quando si sondaggio è che il primo thread che riesce otterrà il valore del nodo e nulla che apprezzi di fuori, quel filo sarà quindi provare a null il riferimento. E 'possibile un altro thread sarà quindi entrare e cercare di polling dalla coda. Per garantire questa coda contiene una proprietà non bloccante (cioè guasto di un filo non porterà al fallimento di un altro thread) che nuovo thread incomming vedrà se il valore è nullo, se è nulla che thread nullo il riferimento e provare di nuovo per il polling ().

Quindi, quello che si vede accadendo qui è il filo di rimozione viene semplicemente preparando ogni nuovo thread di polling a null il riferimento. Cercando di ottenere una funzione non bloccante rimuovi penserei è quasi impossibile, perché ciò richiederebbe tre funzioni atomici. Il nulla del valore del riferimento nullo a detto nodo, e infine il nuovo riferimento da tale nodi genitore al suo successore.

Per rispondere alla tua ultima domanda. Non v'è unforutnalty modo migliore per implementare rimuovere e mantenere lo stato non bloccante della coda. Questo è, almeno a questo punto. Una volta processori iniziano a che esce con involucro 2 e 3 modo quindi che è possibile.

Answer 2

principali semantica della coda è aggiungere / sondaggio. Se si utilizza poll () sul ConcurrentLinkedQueue , verrà pulita come dovrebbe. Sulla base della sua descrizione, poll () dovrebbe darvi la rimozione voce meno recente. Perché non usarlo al posto di rimuovere ()

Answer 3

Guardando il codice sorgente per 1.6.0_29, sembra che iteratore di CLQ è stata modificata per provare a rimuovere i nodi con elementi nulli. 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

In effetti quando provo il seguente ottengo un OOME con la vecchia versione, ma non con quella 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);
}