Synchronization of a Queue

Question

I've been reading up on Doug Lea's 'Concurrency Programming in Java' book. As you may know, Doug originally wrote the Java Concurrency API. However, something has caused me some confusion and I was hoping to gain a few my opinions on this little conundrum!

Take the following code from Doug Lea's queuing example...

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

This a quite a nice Queue. It uses two monitors so a Producer and a Consumer can access the Queue at the same time. Nice! However, the synchronization on 'last' and 'head' is confusing me here. The book states this is needed for for the situation whereby Queue is currently or about to have 0 entries. Ok, fair enough and this kind of makes sense.

However, then I looked at the Java Concurrency LinkedBlockingQueue. The original version of the Queue don't synchronize on head or tail (I also wanted to post another link to the modern version which also suffers from the same problem but I couldn't do so because I'm a newbie). I wonder why not? Am I missing something here? Is there some part of the idiosyncratic nature of the Java Memory Model I'm missing? I would have thought for visibility purposes that this synchronization is needed? I'd appreciate some expert opinions!

Answer 1

The subtlety here is that synchronized(null) would throw a NullPointerException,so neither head nor last is allowed to become null. They are both initialized to the value of the same dummy node that is never returned or removed from either list.

put() and poll() are synchronized on two different locks. The methods would need to synchronize on the same lock to be thread-safe with respect to one another if they could modify the same value from different threads. The only situation in which this is a problem is when head == last (i.e. they are the same object, referenced through different member variables). This is why the code synchronizes on head and last - most of the time these will be fast, uncontented locks, but occasionally head and last will be the same instance and one of the threads will have to block the other.

The only time that visibility is an issue is when the queue is nearly empty, the rest of the time put() and poll() work on different ends of the queue and don't interfere with each other.

Answer 2

In the version you put up a link for as well as the version in the latest JRE the item inside the Node class is volatile which enforces reads and writes to be visible to all other threads, here is a more in depth explaination http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html#volatile