Java Concurrency: Classic Problems

Five classic problems cover most of what interviews ask. Producer-consumer is a bounded buffer where producers block when it’s full and consumers block when it’s empty. In real code that’s a BlockingQueue. Dining philosophers is a deadlock through circular wait, fixed by taking forks in a global order. Readers-writers is about letting readers share while writers get exclusive access, without starving the writers. Sleeping barber is a bounded waiting room where customers leave if it’s full, which maps neatly onto offer() and take(). Odd/even printing is two threads taking strict turns on one shared condition.

Part of the Java Concurrency Roadmap. Uses Thread communication, Locks and Concurrent collections.

Producer-consumer

#

By hand, with wait/notifyAll:

class BoundedBuffer<T> {
    private final Queue<T> items = new ArrayDeque<>();
    private final int capacity;
    BoundedBuffer(int capacity) { this.capacity = capacity; }

    synchronized void put(T item) throws InterruptedException {
        while (items.size() == capacity) wait();
        items.add(item);
        notifyAll();            // producers and consumers share one wait set
    }

    synchronized T take() throws InterruptedException {
        while (items.isEmpty()) wait();
        T item = items.remove();
        notifyAll();
        return item;
    }
}

In real code:

BlockingQueue<Order> queue = new ArrayBlockingQueue<>(100);
queue.put(order);              // producer
Order o = queue.take();        // consumer

To stop consumers, put a poison pill (a sentinel object) on the queue for each consumer, or interrupt them.

Dining philosophers

#

Five philosophers sit at a round table with five forks. Each one picks up the left fork, then the right. If all five pick up their left fork at once, each waits for a right fork held by a neighbour, and that’s a deadlock.

int first  = Math.min(left, right);   // lower-numbered fork first
int second = Math.max(left, right);
forks[first].lock();
try {
    forks[second].lock();
    try { eat(); } finally { forks[second].unlock(); }
} finally { forks[first].unlock(); }

Taking forks in a global order breaks the circular wait. Two other fixes work too: a Semaphore(4) that lets at most four philosophers reach for forks at once, or tryLock with a random backoff.

Readers-writers

#

Many readers can read together, while a writer needs everyone else out. ReentrantReadWriteLock solves exactly this. The design question is who gets priority: readers first can starve writers, and writers first can starve readers. new ReentrantReadWriteLock(true) makes it fair. Details in Locks.

Sleeping barber

#

One barber, N waiting chairs. The barber sleeps when nobody’s waiting, and a customer who finds every chair taken leaves.

BlockingQueue<Customer> chairs = new ArrayBlockingQueue<>(N);

// customer
if (!chairs.offer(me)) leave();         // full: don't wait, just go

// barber
while (true) cut(chairs.take());        // take() is the sleep

The non-blocking offer models “leave if full”, and the blocking take models “sleep until a customer arrives”.

Printing odd/even with two threads

#

class OddEven {
    private int n = 1;
    private final int max;
    OddEven(int max) { this.max = max; }

    synchronized void run(int parity) throws InterruptedException {   // 1 = odd, 0 = even
        while (true) {
            while (n <= max && n % 2 != parity) wait();
            if (n > max) { notifyAll(); return; }
            System.out.println(Thread.currentThread().getName() + ": " + n++);
            notifyAll();
        }
    }
}
// new Thread(() -> p.run(1), "odd") and new Thread(() -> p.run(0), "even"), with InterruptedException handled

The shared condition is “whose turn is it” (n % 2). The n > max checks let both threads exit cleanly instead of one waiting forever. Another approach uses two Semaphores, odd(1) and even(0): each thread acquires its own semaphore and releases the other’s after it prints.