Concurrent Queue with enqueue and dequeue using Stack as underlying data structure

Question

This is a mix of data structure and multi threading concept based question. (This is only for understanding and learning purpose) The language for the solution : Java

A Queue with FIFO behavior needs to be implemented by having underlying data structure as Stack. Enqueue and Dequeue need to be parallel and need not block each other, i.e. enqueue thread must not wait for dequeue thread.

During my search (java based solutions) I could only find the blocking version of this problem where enqueue and dequeue are blocking for each other.

Below is my attempt for this, please correct me if I am wrong or in case I missed something.

1. Two Stacks : addStack and removeStack with individual Lock Objects addLock and removeLock
2. Enqueue operation : enqueue inside synchronized block on addLock, once item added, invoke notifyAll on addLock
3. Dequeue operation : If removeStack is empty then addStack is checked if it is empty , if not then all the elements from addStack are popped and pushed to removeStack
4. pop the element from removeStack and return

Below is the java code :

import java.util.Stack;

/**
 * Queue Implementation with Stack as underlying data-structure and with
 * parallel (almost) enqueue and dequeue
 * 
 * @author krishna_k
 *
 */
public class Queue {

    private Stack<Integer> addStack = new Stack<>();
    private Stack<Integer> removeStack = new Stack<>();
    private final Object addLock = new Object();
    private final Object removeLock = new Object();

    public void enqueue(int item) {
        synchronized (addLock) {
            addStack.push(item);
            addLock.notifyAll();
        }
    }

    public int dequeue(){
        int value = 0;
        synchronized (removeLock) {
            if (removeStack.isEmpty()) {
                try {
                    synchronized (addLock) {
                        while (addStack.isEmpty()) {
                            addLock.wait();
                        }
                        while (!addStack.isEmpty()) {
                            removeStack.push(addStack.pop());
                        }
                    }
                }catch(InterruptedException e) {
                    //code to log the exception e
                }
            }
            value = removeStack.pop();
        }
        return value;
    }
}

Answer 1

Let's start by talking about the requirements.

Implement a thread-safe queue with an underlying stack. This is pretty basic, and has many ways to implement. However, the catch here is Enqueue and Dequeue need to be parallel. This is actually problematic, because as long as a lock is used, blocking will occur. So one can either not use locks, or try to limit their affects.

Your Implementation

Let's talk about your implementation. The first clear thing is that you are using locks, which means blocking is likely.

You have 2 locks, a good thought to try and separate the methods. You also have 2 stacks, each corresponding to a lock. Again, good thought, a single lock must be responsible for all the usage of a specific data source.

The usage of the Stack class however, is a problem. Not only is Stack a outdated collection class, you must also be aware that it extends Vector and each method in it is synchronized. Luckily, as we will see, most of this doesn't have much functionality impact, but rather more of a performance issue. I would recommend using a Dequeue instead.

Another clear part is that it is an int only implementation. In reality, implementing it generically isn't that different or complicated, since an underlying data structure that supports generics is used.

Enqueue

Your enqueue is quite basic. Take the addition lock, add an element, notify about this addition, and release the lock.

The notifying part, tells us that there is waiting somewhere. I'm assuming this is a blocking queue then. This is both not defined in the requirements, and will cause blocking between the threads. Although, the use of notifyAll may cause a problem.

Otherwise, this is quite straightforward. However, it is already obvious that for the dequeue to work, addStack must be accessed, and thus addLock must be touched. This already tells us that blocking will occur.

Dequeue

Now comes the complicated part.

You start by entering a synchronized block of removeLock, this is quite expected, given how the stacks require usage of the locks.

You then check if the removeStack is empty or not. If it isn't you simply pop and return that value. This might seem like a basic example of a dequeue implementation, but that is not true. Because values are not added directly into removeStack, so it being empty means nothing about the actual queue.

Now, if removeStack is empty... then comes the problematic part. The moment addLock is used, we know blocking between the two method will occur.

If addStack is empty, you wait on addLock until it is notified. This is a blocking queue operation. Which again, is not specified as needed. A non-blocking queue operation would be simply to throw some exception indicating that no value is available. Let's return to the use of notifyAll. If multiple dequeue calls are done, all of them will reach the wait, since the locks are not actually taken while waiting. When enqueue is called and notifyAll is done, only one element was added, however all the waiting threads will wake up, and compete on getting the lone element. Perhaps it is best to just use notify.

if addStack is not empty, you copy the values from it to removeStack, and then pop from it and return a value. This still causes blocking between enqueue and dequeue. Luckily, if enqueue runs longer, the blocking will be decreased, since the values will already be in removeStack.

Catching of InterruptedException here is not really a good idea. When you have a blocking method (method that waits), throwing an InterruptedException is important, since this exception is thrown when the thread is interrupted and the user likely wants to stop the operations running.

Summary

Although it has some good logic behind it, in reality this implementation both doesn't accomplish the full requirements, and adds some complications. However, because stack is LIFO, the complexity in dequeue cannot be avoided. Luckily, this blocking is actually pretty short. So it might be even negligible enough to not care about it.

If enqueue is used more than dequeue, the blocking in dequeue will be longer for the first call, but because removeStack stores stuff, subsequent runs may be faster. If dequeue is used more than enqueue, dequeue will simply be blocked most of the time, because it is waiting.

Unfortunately using stack is not a good option for implementing a queue, because the 2 are completely reversed. There are more ways to implement, however they will all be blocking. So this really depends on how each method is used in relation to the other (frequency of calls, amount of read/write threads).

Snapshot on addStack

An example for another implementation is to use a single stack, and limit the holding of the lock by taking a snapshot of it:

private Stack<Integer> stack = new Stack<>();

public int dequeue() {
    Stack<Integer> reverse = new Stack<>();
    Stack<Integer> copy;
    synchronized(lock) {
        copy = new Stack<>(stack);
    }

    while (!copy.isEmpty()) {
        reverse.push(copy.pop());
    }

    if (reverse.isEmpty()) {
        throw new NoSuchElementException(); 
    }

    return reverse.pop();
}

Of course, if stack has a lot of elements, the synchronized block may take some time. However it is just a complexity of o(n).

Not using a stack

Of course not using a stack is always an option. There are many other data structures which can be used to implement a queue. However, the real problem is Enqueue and Dequeue need to be parallel.

There are 2 ways to safely deal with data in a concurrent environment:

• Locks
• Atomic operations

Locks, inherently can cause blocking. However, atomic operations, do not. So a true non-blocking implementation lays in using atomic operation.

Lock-free queue

The concept of a lock-free queue is to implement a queue, which is safe for use in concurrent environments, without using locks, which only leaves us with atomic operations for use.

This is actually well known, but difficult to implement. Depending on the amount of read/write threads, the difficulty can increase.

When working with a single writer thread, and a single reader thread it is actually quite simple.