ConcurrentLinkedQueue $ El nodo permanece en el montón después de eliminar()

Question

Tengo una aplicación multiproceso que escribe y lee un ConcurrentLinkedQueue, que se usa conceptualmente para respaldar entradas en una lista/tabla. Originalmente usé un ConcurrentHashMap para esto, que funcionó bien. Se requería un nuevo requisito para rastrear las entradas de la orden, por lo que se podían eliminar en la primera orden más antigua, dependiendo de algunas condiciones. ConcurrentLinkedQueue parecía ser una buena opción, y funcionalmente funciona bien.

Se almacena una cantidad configurable de entradas en la memoria, y cuando se ofrece una nueva entrada cuando se alcanza el límite, la cola se busca en la primera orden más antigua para una que se puede eliminar. Ciertas entradas no deben ser eliminadas por el sistema y esperar la interacción del cliente.

Lo que parece estar sucediendo es que tengo una entrada en la parte delantera de la cola, digamos 100K entradas. Parece que la cola tiene un número limitado de entradas configuradas (tamaño() == 100), pero cuando hice el perfil, encontré que había ~ 100K objetos ConcurrentLinkedQueue $ Node en la memoria. Esto parece ser por diseño, simplemente echando un vistazo a la fuente de ConcurrentLinkedQueue, una eliminación simplemente elimina la referencia al objeto que se está almacenando, pero deja la lista enlazada en su lugar para la iteración.

Finalmente mi pregunta: ¿Existe una forma "mejor" de holgazanería para manejar una colección de esta naturaleza? Me encanta la velocidad de ConcurrentLinkedQueue, simplemente no puedo permitirme la filtración ilimitada que parece ser posible en este caso. Si no, parece que tendría que crear una segunda estructura para seguir el orden y puede tener los mismos problemas, además de una preocupación de sincronización.

Answer 1

Lo que realmente sucede aquí es que el método remove prepara un hilo de sondeo para anular la referencia enlazada.

ConcurrentLinkedQueue es una implementación de cola segura que no bloquea el bloqueo. Sin embargo, cuando intenta sondear un nodo desde la cola, se trata de un proceso de dos funciones. Primero anulas el valor y luego anulas la referencia. Una operación CAS es una única función atómica que no ofrecería una resolución inmediata para una encuesta.

Lo que ocurre cuando la encuesta es que el primer hilo que tiene éxito obtendrá el valor del nodo y anulará ese valor, ese hilo intentará anular la referencia. Es posible que otro hilo entre y trate de sondear desde la cola. Para garantizar que esta cola tenga una propiedad que no sea de bloqueo (que es la falla de un hilo no dará lugar a la falla de otro hilo), el nuevo hilo entrante verá si el valor es nulo, si es nulo ese hilo anulará la referencia y lo intentará de nuevo para sondear().

Entonces, lo que ve que sucede aquí es que el hilo de eliminación simplemente está preparando cualquier hilo de sondeo nuevo para anular la referencia. Tratando de lograr una función de eliminación sin bloqueo, creo que es casi imposible porque eso requeriría tres funciones atómicas. El valor nulo del valor nulo que hace referencia a dicho nodo y, por último, la nueva referencia de ese nodo padre a su sucesor.

Para responder a su última pregunta. No hay ninguna forma mejor de implementar eliminar y mantener el estado de no bloqueo de la cola. Eso es al menos en este punto. Una vez que los procesadores comienzan a salir con carcasa de 2 y 3 vías, es posible.

Answer 2

La semántica principal de la cola es add/poll. Si usa encuesta() en el ConcurrentLinkedQueue, se limpiará como debería. Según su descripción, encuesta() debería darle la eliminación de la entrada más antigua. ¿Por qué no usarlo en lugar de eliminar()?

Answer 3

En cuanto al código fuente de 1.6.0_29, parece que el iterador de CLQ fue modificado para tratar de eliminar nodos con elementos 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 el versión anterior pero no con la nueva:

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