ConcurrentLinkedQueue $ nodo permanece en el montón después remove ()

Question

Tengo una escritura de aplicaciones multiproceso y leyendo un ConcurrentLinkedQueue, que se utiliza conceptualmente a las entradas traseras en una lista / tabla. He utilizado originalmente un ConcurrentHashMap para esto, que funcionaba bien. Un nuevo requisito necesario el seguimiento de las entradas de pedidos entraron, para que pudieran ser eliminados en antiguos primero orden, dependiendo de algunas condiciones. ConcurrentLinkedQueue parecía ser una opción buena, y funcionalmente funciona bien.

Una cantidad configurable de entradas se mantiene en la memoria, y cuando una nueva entrada se ofrece cuando se alcanza el límite, la cola se busca en más antigua-primer orden para uno que se puede quitar. Ciertas entradas no deben ser retiradas por el sistema y espera para interacción con el cliente.

Lo que parece estar sucediendo es que tengo una entrada en la parte delantera de la cola que se produjo, hace decir 100K entradas. La cola parece tener el número limitado de entradas configuradas (size () == 100), pero al perfilar, me encontré con que había objetos ~ 100K ConcurrentLinkedQueue $ nodo en la memoria. Esto parece ser por diseño, simplemente echando un vistazo a la fuente para ConcurrentLinkedQueue, un quitar simplemente elimina la referencia al objeto que está siendo almacenada, pero deja la lista enlazada en su lugar para la iteración.

Finalmente mi pregunta: ¿Hay una "mejor" forma perezosa para manejar una colección de esta naturaleza? Me encanta la velocidad de la ConcurrentLinkedQueue, yo sólo puedo pagar la fuga sin límites que parece ser posible en este caso. Si no es así, parece que tendría que crear una segunda estructura para realizar un seguimiento de orden y puede tener los mismos problemas, además de una preocupación de sincronización.

Answer 1

Lo que en realidad está sucediendo aquí es el método remove prepara un hilo de votación a cabo nula la referencia vinculada.

El ConcurrentLinkedQueue es un hilo de bloqueo de seguridad no aplicación de cola. Sin embargo, cuando se intenta sondear un nodo de la cola es un proceso de dos funciones. En primer lugar, el valor nulo, entonces la referencia nula. Una operación CAS es una sola función atómica que no ofrecería resolución immidiate de una votación.

¿Qué pasa cuando una encuesta es que el primer hilo que tiene éxito obtendrá el valor del nodo y nula de que el valor cabo, ese hilo y luego tratará de anular la referencia. Es posible que otro hilo a continuación, entrar y tratar de sondear de la cola. Para asegurar esta cola contiene una propiedad de no bloqueo (es decir, incumplimiento de un hilo no conducirá al fracaso de otro hilo) que el nuevo hilo incomming será ver si el valor es nulo, si es nula de que el hilo se anular la referencia y prueba de nuevo para poll ().

Así que lo que vemos que sucede aquí es el hilo quita es simplemente la preparación de cualquier nuevo hilo de votación para anular la referencia. Tratando de conseguir una función de bloqueo no quite yo creo que es casi imposible, ya que requeriría tres funciones atómicas. La nula del valor de la nula referencia a dicho nodo, y, finalmente, la nueva referencia de que los nodos matriz a su sucesor.

Para responder a su última pregunta. Hay unforutnalty hay mejor manera de poner en práctica de eliminación y mantener el estado de no bloqueo de la cola. Eso es al menos en este punto. Una vez que los procesadores comiencen desconchaba a cabo con 2 y 3 manera carcasa entonces que es posible.

Answer 2

principales semántica de la cola se agrega / sondeo. Si utiliza poll () en el ConcurrentLinkedQueue , que se limpiará como debería. Sobre la base de su descripción, poll () debe darle la eliminación de entrada más antigua. ¿Por qué no usarlo en lugar de remove ()

Answer 3

Si examina el código fuente para 1.6.0_29, parece que el iterador de CLQ fue modificado para intentar quitar nodos con los objetos nulos. En lugar de:

p = p.getNext();

El código es ahora:

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

Esto se añadió como parte de la solución para el bug: http: //bugs.sun .com / view_bug.do? bug_id = 6785442

De hecho cuando intento el siguiente recibo un OOME con la antigua versión, pero no con el nuevo:

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);
}