Sincronización de una cola

Question

He estado leyendo en el libro "Concurrency Programming in Java" de Doug Lea. Como sabrá, Doug escribió originalmente la API Java Concurrency. Sin embargo, algo me ha causado cierta confusión y esperaba obtener algunas opiniones sobre este pequeño enigma.

Tome el siguiente código de ejemplo cola de Doug Lea ...

class LinkedQueue { 
    protected Node head = new Node(null); 
    protected Node last = head; 

    protected final Object pollLock = new Object(); 
    protected final Object putLock = new Object(); 

    public void put(Object x) { 
    Node node = new Node(x); 
    synchronized (putLock) {  // insert at end of list 
     synchronized (last) { 
     last.next = node;  // extend list 
     last = node; 
     } 
    } 
    } 

    public Object poll() {   // returns null if empty 
    synchronized (pollLock) { 
     synchronized (head) { 
     Object x = null; 
     Node first = head.next; // get to first real node 
     if (first != null) { 
      x = first.object; 
      first.object = null; // forget old object 
      head = first;   // first becomes new head 
     } 
     return x; 
     } 
    } 
    } 

    static class Node {   // local node class for queue 
    Object object; 
    Node next = null; 

    Node(Object x) { object = x; } 
    } 
} 

Este bastantes un buen cola. Utiliza dos monitores para que un Productor y un Consumidor puedan acceder a la cola al mismo tiempo. ¡Bonito! Sin embargo, la sincronización en 'último' y 'cabeza' me confunde aquí. El libro indica que esto es necesario para la situación en la que Queue está actualmente o a punto de tener 0 entradas. Ok, es justo y este tipo de tiene sentido.

Sin embargo, luego miré Java Concurrency LinkedBlockingQueue. La versión original de la cola no se sincroniza en la cabeza o la cola (también quería publicar otro enlace a la versión moderna que también sufre el mismo problema, pero no pude hacerlo porque soy novato). Me pregunto por qué no? ¿Me estoy perdiendo de algo? ¿Hay alguna parte de la naturaleza idiosincrásica del Modelo de memoria de Java que me falta? ¿Habría pensado con fines de visibilidad que esta sincronización es necesaria? ¡Agradecería algunas opiniones de expertos!

Answer 1

En la versión que coloca un enlace así como la versión en el JRE más reciente, el elemento dentro de la clase Node es volátil y obliga a las lecturas y escrituras a ser visibles para todos los demás hilos. Aquí hay una explicación más detallada http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html#volatile

Answer 2

La sutileza aquí es que synchronized (null) arrojaría una NullPointerException, por lo que ni head ni last pueden convertirse en null. Ambos se inicializan con el valor del mismo nodo ficticio que nunca se devuelve o elimina de ninguna de las listas.

put() y poll() están sincronizados en dos bloqueos diferentes. Los métodos tendrían que sincronizarse en el mismo bloqueo para que sean seguros para hilos entre sí si pudieran modificar el mismo valor desde diferentes subprocesos. La única situación en la que esto es un problema es cuando head == last (es decir, son el mismo objeto, al que se hace referencia a través de diferentes variables de miembro). Esta es la razón por la cual el código se sincroniza en la cabecera y el último; la mayoría de las veces serán bloqueos rápidos, no intencionados, pero ocasionalmente cabecera y última será la misma instancia y uno de los hilos tendrá que bloquear al otro.

La única vez que la visibilidad es un problema es cuando la cola está casi vacía, el resto del tiempo put() y poll() trabajan en diferentes extremos de la cola y no interfieren entre sí.