Search⌘ K
Home
Courses
Java Multithreading for Senior Engineering Interviews

Nonblocking Stack

We'll cover the following...

Problem

Design a stack that doesn’t use locks or synchronized and is thread-safe. You may assume that you are provided with an application-level API that mocks the hardware instruction compare-and-swap, to atomically compare and swap values at a memory location.

Solution

This is a slightly advanced question that requires knowledge about atomic classes in Java. You can read the section on Atomics in this course and then come back to this question. Very briefly, a stack is a data structure that implements first-in, last-out semantics for stored items.

Usually, we want to atomically execute steps that require checking a value and then taking action based on the observed value. This is usually expressed as an if-clause. For instance, in the stack problem we would have a variable top that points to the top of the stack. Initially, this variable is null and in a single-threaded environment we would perform the following check when pushing the first element in the stack.

​​if (top == null) {
   top = new StackNode();
   // ... other initialization steps
}

As you can see, the above snippet is a check-then-act scenario - We check if top is already null, if so we initialize it to an object of StackNode. The above code fails in a multi-threaded environment because the check-then-act sequence can’t be performed atomically. The straightforward path to make the code thread-safe is to either use locks or simply mark the methods synchronized. The code for a thread-safe stack using synchronized is presented below for context and before we delve into a solution without locking.

Java
import java.util.concurrent.*;
class Demonstration {
    public static void main( String args[] ) throws Exception {
        SynchronizedStack<Integer> stackOfInts = new SynchronizedStack<>();
        ExecutorService executorService = Executors.newFixedThreadPool(20);
        int numThreads = 2;
        CyclicBarrier barrier = new CyclicBarrier(numThreads);
        Integer testValue = new Integer(51);
        try {
            for (int i = 0; i < numThreads; i++) {
                executorService.submit(new Runnable() {
                    @Override
                    public void run() {
                        for (int i = 0; i < 10000; i++) {
                            stackOfInts.push(testValue);
                        }
                        try {
                            barrier.await();
                        } catch (InterruptedException | BrokenBarrierException ex) {
                            System.out.println("ignoring exception");
                            //ignore both exceptions
                        }
                        for (int i = 0; i < 10000; i++) {
                            stackOfInts.pop();
                        }
                    }
                });
            }
        } finally {
            executorService.shutdown();
            executorService.awaitTermination(1, TimeUnit.HOURS);
        }
    }
}

There are several reasons to avoid locks which we described in detail in the Atomics section. The crux is that locking is a heavyweight synchronization mechanism that incurs significant overhead. In low to moderate contention situations, it may be better to execute critical sections of code speculatively in the ...