Search⌘ K
AI Features
Home
Courses
Java Multithreading for Senior Engineering Interviews

Nonblocking Stack

Explore how to implement a thread-safe nonblocking stack in Java without using locks or synchronized methods. Understand the use of compare-and-swap techniques with simulated and AtomicReference classes to atomically update stack states in multithreaded environments. This lesson helps you grasp advanced concurrency concepts crucial for senior engineering interviews.

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 ...