Thread safe enqueue and dequeue method in Queue

Question

As an exercise, I have implemented a linked queue whose enqueue and dequeue methods are synchronized. There is a Producer thread which keeps inserting elements into the queue as long as there are less than 10 items in it. When the queue is full, the thread waits. The second thread Consumer keep removing elements from queue as long as it is not empty. I would like to get a review of this code - is there any flaw? How could I improve it?

MyLinkedQueue.java

public class MyLinkedQueue<T> implements Iterable<T> {
 private Node first, last;
 private int size = 0;
 private static final int MAX_QUEUE_SIZE = 10;
 public Iterator<T> iterator() { return new QueueIterator(); }
 private class Node {
 T item;
 Node next;
 }
 public boolean isEmpty() { return first == null; }
 public boolean isFull() { return MAX_QUEUE_SIZE == size(); }
 public synchronized void enqueue(T item) throws InterruptedException {
 while (isFull()) {
 wait();
 }
 Node oldLast = last;
 last = new Node();
 last.item = item;
 last.next = null;
 if (isEmpty()) {
 first = last;
 } else {
 oldLast.next = last;
 }
 notifyAll();
 size++;
 }
 public synchronized T dequeue() throws InterruptedException {
 while (0 == size()) {
 wait();
 }
 T item = first.item;
 first = first.next;
 if (isEmpty()) { last = null; }
 size--;
 notifyAll();
 return item;
 }
 public synchronized int size() { return size; }
 private class QueueIterator implements Iterator<T> {
 private Node current = first;
 public boolean hasNext() { return current != null; }
 public void remove() {}
 public T next() {
 T item = current.item;
 current = current.next;
 return item;
 }
 }
}

Producer.java

public class Producer implements Runnable {
 private static final int DELAY = 1000;
 private MyLinkedQueue queue;
 private int count;
 public Producer(MyLinkedQueue queue, int count) {
 this.queue = queue;
 this.count = count;
 }
 public void run() {
 try {
 for (int i = 0; i < count; ++i) {
 queue.enqueue(new Date().toString());
 Thread.sleep(DELAY);
 }
 } catch(InterruptedException e) {
 }
 }
}

Consumer.java

public class Consumer implements Runnable {
 private static final int DELAY = 1000;
 private MyLinkedQueue queue;
 private int count;
 public Consumer(MyLinkedQueue queue, int count) {
 this.queue = queue;
 this.count = count;
 }
 public void run() {
 try {
 for (int i = 0; i < count; ++i) {
 queue.dequeue();
 Thread.sleep(DELAY);
 }
 } catch(InterruptedException e) {
 }
 }
}

QueueThreadrunner.java

public class QueueThreadrunner {
 public static void main(String[] args) {
 MyLinkedQueue queue = new MyLinkedQueue();
 final int THREADS = 10;
 final int REPETITIONS = 50;
 for (int i = 1; i <= THREADS; ++i) {
 Producer pr = new Producer(queue, REPETITIONS);
 Consumer cr = new Consumer(queue, REPETITIONS);
 Thread dt = new Thread(pr);
 Thread wt = new Thread(cr);
 dt.start();
 wt.start();
 }
 }
}

• rolfl: public boolean isEmpty() { return first == null; } needs to be synchronized otherwise it could have a stale version of first.

Answer 1

It is apparent that you have put some thought in to this implementation, and apart from the not-synchronized isEmpty() method, it all looks functional.

I have some minor nit-picks though, and please bear in mind that these are just my opinion...

I prefer to have the notifyAll method to be the last thing in a synchronized block, where possible... You have:

....
 }
 notifyAll();
 size++;
}

I would always put the notifyAll() after the size++. This does not make a functional difference to the program, but it makes the logic more apparent (that size++ will happen before any other thread can read the size value):

....
 }
 size++;
 notifyAll();
}

As I say, this does not affect the logic of the code, but it does affect the readability.

A second nit-pick I have is that you 'leak' logic from your synchronized blocks. What I mean by this, is that you should try to avoid any method calls from inside the block. When you call other methods from a block it becomes much easier to introduce synchronization bugs and deadlocks. Additionally, the methods you call are also synchronized, so you introduce a readability/complexity (and perhaps even a slight performance) issue by having nested synchronization calls.

EDIT: I would add another nit-pick here which is you do not use 'final' enough. 'final' is a good hint to the optimizer in Java and it allows it to make smarter choices when inlining and otherwise rearranging/compiling your code

Finally, I would choose just one mechanism to manage the empty/full condition of the queue. Currently you have a few: isEmpty depends on first == null; isFull() depends on size == MAX_QUEUE_SIZE; in your enqueue(...) you test for isFull() and isEmpty(); and in your dequeue() you test for 0 == size() and isEmpty(). I would reduce all of these to tests on size only. That way there is only one condition that you need to mentally track when you read the code.

So, if it were me, I would replace your code as follows:

public synchronized boolean isEmpty() { return size == 0; } // replace first == null
public synchronized boolean isFull() { return size == MAX_QUEUE_SIZE; } // replace size()
public synchronized void enqueue(final T item) throws InterruptedException { // add final
 while (size == MAX_QUEUE_SIZE) { // replace isFull() call.
 wait();
 }
 final Node oldLast = last; // add final
 last = new Node();
 last.item = item;
 last.next = null;
 if (size == 0) { // remove isEmpty()
 first = last;
 } else {
 oldLast.next = last;
 }
 size++; // move before notifyAll()
 notifyAll();
} 
public synchronized T dequeue() throws InterruptedException {
 while (size == 0) { // remove size() call.
 wait();
 }
 final T item = first.item; // add final
 first = first.next;
 size--; // move size-- up a bit to make the logic below more transparent
 if (size == 0) { // remove isEmpty() call
 last = null;
 }
 notifyAll();
 return item;
}

Finally, if it really was me, I would recommend that you consider ReentrantLocks and Conditions to manage the queue.... There's a good example (almost identical to this exact problem) of how to do it in the JavaDoc.