1
\$\begingroup\$

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.

\$\endgroup\$

migrated from stackoverflow.com Oct 3 '16 at 6:42

This question came from our site for professional and enthusiast programmers.

  • 3
    \$\begingroup\$ THread.sleep(100) is a terrible idea, and it also blocks. So "no." C.f.: ibm.com/developerworks/library/j-jtp04186 \$\endgroup\$ – markspace Oct 3 '16 at 5:32
  • \$\begingroup\$ @jtp04186. If I remove the Thread.sleep(100), that will make it non blocking right. \$\endgroup\$ – user12331 Oct 3 '16 at 6:21
  • \$\begingroup\$ @user12331 either operation could block forever. They should try once and return failure if non blocking. \$\endgroup\$ – Peter Lawrey Oct 3 '16 at 7:56
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ If I use Lock, won't it making it blocking? \$\endgroup\$ – user12331 Oct 3 '16 at 6:20
  • \$\begingroup\$ Not if you call tryLock. \$\endgroup\$ – Stephen C Oct 3 '16 at 6:33
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.