0
\$\begingroup\$

I wrote it this just for learning. Is there holes at this code?

public interface ConcurrentStack<T> {
    //blocking
    void put(T t) throws InterruptedException;

    //blocking
    T poll() throws InterruptedException;

    //non-blocking put
    boolean offer(T t);

    //non-blocking get
    T take();
}

class ConcurrentStackImpl<T> implements ConcurrentStack<T> {
    private volatile AtomicBoolean locked = new AtomicBoolean(false);
    private List<T> internalList = new ArrayList<T>();
    private final int maxSize; // this final mandatory? I am afraid about visibility

    public ConcurrentStackImpl(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException();
        }
        this.maxSize = maxSize;
    }

    @Override //blocking
    public void put(T t) throws InterruptedException {
        while (!locked.compareAndSet(false, true)) ;//busy waiting
        internalList.add(t);
        locked.set(false);
    }

    @Override // non-blocking
    public T poll() throws InterruptedException {
        while (!locked.compareAndSet(false, true)) ;//busy waiting
        T value = internalList.get(internalList.size() - 1);
        locked.set(false);
        return value;
    }

    @Override
    public boolean offer(T t) {
        if (locked.compareAndSet(false, true)) {

            if (internalList.size() >= maxSize) {
                return false;
            }
            boolean addResult = internalList.add(t);
            locked.set(false);
            return addResult;
        }
        return false;
    }

    @Override
    public T take() {
        if (locked.compareAndSet(false, true)) {
            T t = internalList.get(internalList.size() - 1);
            locked.set(false);
            return t;
        }
        return null;
    }

}
\$\endgroup\$
3
\$\begingroup\$

I see that you made improvements to your code since here.

Synchronizing

You decided to use internal locking what is technically ok. The way you did it is a variant that I never used. I prefer to use following pattern:

Define an object local Lock-Object:

Object lock = new Object();

And synchronize with the synchronized-block construct:

public void anyMethod() {
    synchronized (this.lock) {
        // do stuff in monitor here
    }
}

Even if your approach is comparable to this you should go with less statements as you are always have aquire the lock with locked.compareAndSet(false, true) and release the lock with locked.set(false). You have no compiler and language support for this locking mechanism. You can easily forget to release the lock or you may find yourself in situations that will compromise your locking like: If your list is empty and you call the poll-method, it aquires the lock, failing afterwards with an ArrayIndexOutOfBoundsException that causes the lock never to be released. That is also true for the take-method().

Missing maxSize constraint (?)

I do not know if there should be any other assertion in the put-method. But there you do not check for maxSize.

Handle empty list

Your take()-method and your poll-method are vulnerable if the internalList is empty. They both fail with an ArrayIndexOutOfBoundsException. Either you return null or what I think is the better way to check for emptyness and throw an "EmptyStackException". This is the standard behaviour from the Java Stack implementation:

java.util.Stack<Object> stack = new java.util.Stack<>();
stack.pop(); // throws EmptyStackException

Avoiding the ArrayIndexOutOfBoundsException has semantical reasons. This Exception is published from different abstraction layer. So using an EmptyStackException is an interpretation of the underlying state of the internalList from the stack'S point of view.

You may say that you catch the ArrayOutOfBoundsException and map it to the EmptyStackException which would be the correct semantic. But you should avoid it to be thrown as throwing exceptions is very expensive.

Busy waiting

Currently you use a while-loop to wait for new elements if no element is present.

Busy waiting should be replaced by a non cpu killing concept. I doubt that in your case busy waiting or equivalent functionality should be done as mentioned in the comments there is a possibility never to recover from it. Providing a timeout mechanism would be an approach. Your busy waiting solution could easily extended to evaluate a given timout but it keeps very cpu expensive.

On the other side a non cpu killing way is complicated. The only chance to do so is to instantiate a Timeout-thread sleeping n seconds, before put the current thread to wait and notify it if the timout is reached with a timout marker. You have to consider that a notification should also be made when new elements become available. Furthermore your timeout thread has to be killed. You have to decide what to do if a timeout happens (returning null oor throwing an exception). Equivalent Java classes return null.

A personal note: In productive environments I would not implement such a timeout mechanism by myself if there is a chance to use existing well tested solutions. For the sake of education this is something where you certainly learn a lot but it also can be very frustrating as this goal is miles away in contrast to centimeters to the implementation so far. But I encourage you at least to go some meters to experience the burden you put on your shoulders.

\$\endgroup\$
  • 5
    \$\begingroup\$ I beg to differ: "while (!locked.compareAndSet(false, true)) ;//busy waiting" is not comparable to synchronized(this.lock). The synchronized will use object monitors and an internal notification system of the JVM effectively releasing the thread, whereas the busy loop will hog 100% CPU. Even worse, on a single processor system, the busy loop may never yield to another thread and therefore block the system infinitely. \$\endgroup\$ – mtj Feb 7 '17 at 7:15
1
\$\begingroup\$

Why a blocking solution? I think a non-blocking solution could be nicer. Here's some old code I've made in the past. Hope it can help too for anyone wishing for a non-blocking solution:

public class ConcurrentStack<T> {
    private final AtomicReference<StackNode<T>> head = new AtomicReference<>();

    // /////////////////////////////////
    public void put(final T item) {
        final StackNode<T> newHead = new StackNode<>(item);
        while (true) {
            newHead.next = head.get();
            if (head.compareAndSet(newHead.next, newHead))
                return;
        }
    }

    /**
     * gets the first element and removes it from the data structure . will return null if empty
     */
    public T get() {
        StackNode<T> temp;
        while (true) {
            temp = head.get();
            if (temp == null)
                return null;
            if (head.compareAndSet(temp, temp.next))
                return temp.item;
        }
    }

    /**
     * returns the last item that was inserted into the bin , without removing it
     */
    public T peek() {
        final StackNode<T> temp = head.get();
        if (temp == null)
            return null;
        return temp.item;
    }

    public boolean isEmpty() {
        return head.get() == null;
    }

    public void clear() {
        head.set(null);
    }

    /**
     * warning:might not give actual result when other threads adding/removing elements!
     */
    public int size() {
        StackNode<T> temp = head.get();
        if (temp == null || temp.item == null)
            return 0;
        int result = 1;
        while ((temp = temp.next) != null)
            if (temp.item != null)
                ++result;
        return result;
    }

    // /////////////////////////////////
    // ////////////
    // StackNode //
    // ////////////
    private static class StackNode<SS> {
        StackNode<SS> next = null;
        SS item;

        public StackNode(final SS newItem) {
            item = newItem;
        }
    }
}
\$\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.