Blocking and non-blocking queue

Question

I came up with the following for a blocking and non-blocking queue implementation. Please suggest any changes/improvements/gotchas.

Blocking queue:

public class BlockingQueue<T> {
 List<T> buffer;
 private static final int MAX_QUEUE_SIZE = 100;
 public BlockingQueue() {
 buffer = new ArrayList<T>();
 }
 public void enqueue(T value) throws InterruptedException {
 synchronized(buffer) {
 while(buffer.size() >= MAX_QUEUE_SIZE) {
 buffer.wait();
 }
 buffer.add(value);
 buffer.notifyAll();
 }
 }
 public T dequeue() throws InterruptedException {
 synchronized(buffer) {
 while(buffer.size() < 1) {
 buffer.wait();
 }
 T value = buffer.remove(0);
 buffer.notifyAll();
 return value;
 }
 }
}

Non-blocking queue:

public class NonBlockingQueue<T> {
 List<T> buffer;
 private static final int MAX_QUEUE_SIZE = 100;
 private AtomicBoolean mutex = new AtomicBoolean(false);
 public NonBlockingQueue() {
 buffer = new ArrayList<T>();
 }
 public void enqueue(T value) throws InterruptedException {
 while(true) {
 while(!mutex.compareAndSet(false, true)) {
 Thread.sleep(100);
 }
 if(buffer.size() < MAX_QUEUE_SIZE) {
 buffer.add(value);
 mutex.set(false);
 return;
 } else {
 mutex.set(false);
 }
 }
 }
 public T dequeue() throws InterruptedException {
 T value = null;
 while(true) {
 while(!mutex.compareAndSet(false, true)) {
 Thread.sleep(100);
 }
 if(buffer.size() > 0) {
 value = buffer.remove(0);
 mutex.set(false);
 return value;
 } else {
 mutex.set(false);
 }
 } 
 }
}

I think by non-blocking it means that the thread should not be blocked, so I used the sleep method. Please let me know if it has any issues.

• markspace: THread.sleep(100) is a terrible idea, and it also blocks. So "no." C.f.: ibm.com/developerworks/library/j-jtp04186
• user12331: @jtp04186. If I remove the Thread.sleep(100), that will make it non blocking right.
• Peter Lawrey: @user12331 either operation could block forever. They should try once and return failure if non blocking.

Answer 1

You asked for critique ....

1. Why are you trying to use an AtomicBoolean as a mutex? Use a primitive lock, or a Lock if you need more sophisticated behavior.

2. (Almost) any time you use sleep in an algorithm, you are doing it the wrong way. In this case, the "wrong way" is a direct consequence of point 1. above.

3. If you want good performance in a situation where you have multiple producers and consumers, you should avoid doing a notifyAll. For instance if there are N consumers waiting, and a producer adds a queue entry, then all N consumers will be woken up. Ideally, only one consumer should be woken.

• user12331: If I use Lock, won't it making it blocking?
• Stephen C: Not if you call tryLock.

Answer 2

Because you will be doing a lot of adding at the end and (in particular) removing from the beginning, I would use a LinkedList rather than an ArrayList.

I'm also not sure what makes your NonBlockingQueue non-blocking. It's sleeping, which is just as well.