4
\$\begingroup\$

Implement a multi-threaded stack, with freedom to use existing implementations of stack. On top of being thread-safe, it must block (not busy-wait) a pushing thread when stack is full and a popping thread when stack is empty. It must signal the threads out of sleep when stack has space again or elements to pop. Fairness is optional in this question.

How can I implement such a stack in Java? I came up with below implementation. Is this the correct way to solve above problem?

public class MyStack<E> {
  private final Stack<E> stack;
  private int max = 16;
  private final ReentrantLock lock = new ReentrantLock(true);
  private final Condition notEmpty = lock.newCondition();
  private final Condition notFull = lock.newCondition();

  public MyStack(int size) {
    this.stack = new Stack<>();
    this.max = size;
  }

  public void push(E e) {
    lock.lock();
    try {
      while (stack.size() == max) {
        notFull.await();
      }
      stack.push(e);
      notEmpty.signalAll();
    } catch (InterruptedException e1) {
      e1.printStackTrace();
    } finally {
      lock.unlock();
    }
  }

  public E pop() {
    lock.lock();
    try {
      while (stack.size() == 0) {
        notEmpty.await();
      }
      E item = stack.pop();
      notFull.signalAll();
      return item;
    } catch (InterruptedException e) {
      e.printStackTrace();
    } finally {
      lock.unlock();
    }
  }
}
\$\endgroup\$
  • \$\begingroup\$ Is your Stack a java.util.Stack? Isn't java.util.Stack already thread-safe? \$\endgroup\$ – 200_success Jun 13 at 7:35
  • \$\begingroup\$ Yes it is thread safe but I need to do some extra things on top of that as mentioned in my problem statement. \$\endgroup\$ – user5447339 Jun 13 at 7:38
  • \$\begingroup\$ @200_success It's thread-safe, but not blocking. \$\endgroup\$ – dfhwze Jul 13 at 16:36
1
\$\begingroup\$

Looks good to me on a cursory glance. It's pretty much the exact same code as in java.util.concurrent.locks.Condition JavaDoc.

The only definitive problem I see is the catching and logging of InterruptedException. The code acts towards the caller as if the operation succeeded while nothing was done.

Not providing a way to set the maximum wait time will be a limitation in a library intended for generic use.

Stylistically, private int max should be final to emphasize that it must not be changed after initialization (as changing it when threads are waiting would cause serious problems).

Another thing, which may be a matter of taste, is the stack.size() == max comparison. I always like to use >= where a size is compared to a maximum limit (with a comment, of course). This gives an extra safeguard against infinite loops in the case where a programming error causes the collection to exceed maximum size.

\$\endgroup\$
1
\$\begingroup\$

Guard Arguments

  • put does not check for e == null. Are null values allowed? If not, add an argument guard if (e == null) throw new NullPointerException();.

Naming Conventions

  • Call your class BlockingStack to conform to Java naming guidelines concerning concurrent collections.
  • max should be called capacity. A collection's capacity is its maximum size. As suggested in another answer, make it final. Also, since you set it in the constructor, there is no reason for the magic number 16. It will always be overriden.
  • The constructor takes a parameter size which you store to max. There is no reason to use different names. Both should be called capacity anyway.

Threading

  • You silently catch InterruptedException. This is bad design. Exceptions should propagate up the call stack for callers to handle.
  • Also, on exception, notify other threads waiting on the condition before throwing the exception up the call stack.
  • Prefer lockInterruptibly() over lock(). Discussed here
  • The specification dictates fairness is optional. Let the consumer of the class specify a boolean fair in the constructor.

Refactored Code

public class BlockingStack<E> {

  private final Stack<E> stack;
  private final int capacity;
  private final ReentrantLock lock;
  private final Condition notEmpty;
  private final Condition notFull;

  public BlockingStack(int capacity) {
    this(capacity, false);
  }

  public BlockingStack(int capacity, boolean fair) {
    if (capacity <= 0)
      throw new IllegalArgumentException();
    this.capacity = capacity;
    stack = new Stack<>();
    lock = new ReentrantLock(fair);
    notEmpty = lock.newCondition();
    notFull = lock.newCondition();
  }

  public void push(E e) throws InterruptedException {
    if (e == null)
      throw new NullPointerException();
    lock.lockInterruptibly();
    try {
      while (stack.size() == capacity) {
        notFull.await();
      }
      stack.push(e);
      notEmpty.signalAll();
    } catch (InterruptedException error) {
      notFull.signal();
      throw error;
    } finally {
      lock.unlock();
    }
  }

  public E pop() throws InterruptedException {
    lock.lockInterruptibly();
    try {
      while (stack.size() == 0) {
        notEmpty.await();
      }
      E item = stack.pop();
      notFull.signalAll();
      return item;
    } catch (InterruptedException error) {
      notEmpty.signal();
      throw error;
    } finally {
      lock.unlock();
    }
  }
}
\$\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.