SyntaxPilot
Courses/Low-Level Design/Lesson 48
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Low-Level Design · Lesson 48 of 90

Concurrency 3: locks, atomics and executors

java.util.concurrentLockReentrantLocktryLockfairnessReadWriteLockReentrantReadWriteLockStampedLockConditionawait and signalatomic variablesAtomicIntegerAtomicReferencecompare-and-swap

These are the notes for Low-Level Design (LLD) episode 48. synchronized keeps code safe, but it can't give up waiting, can't let many readers in together, makes threads queue even for a simple counter, and we've been creating a new thread for every job. Java's package java.util.concurrent (and its sub-packages locks and atomic) fixes all of that. We invent ReentrantLock and tryLock, fairness, Condition with await/signal, read-write locks and StampedLock, atomic variables (AtomicInteger, AtomicReference, LongAdder) and the compare-and-swap instruction behind them, and thread pools with ExecutorService, Callable, Future and shutdown. Every program was actually run with javac Main.java && java -cp . Main (Java 21). Outputs are real; timings are rounded by the programs, and the order of thread output varies.

1. The real-life idea

In the cafe In java.util.concurrent
The washroom key: busy? come back later tryLock(): a lock you can give up on
The kitchen bell: the waiter waits until it rings Condition: await() ... signal()
"Board still says 5? then write 4" Compare-and-swap (CAS): update only if unchanged
A permanent team of cooks + token slips Thread pool + Future: reused threads, results later

2. The problem: synchronized can't give up

class Printer {                                                   // one shared bill printer
    synchronized void print(String who, int ms) {
        System.out.println(who + " printing...");
        try { Thread.sleep(ms); } catch (InterruptedException e) { }   // a paper jam: 3 seconds
        System.out.println(who + " done");
    }
}
public class Main {
    public static void main(String[] args) throws InterruptedException {
        Printer printer = new Printer();
        Thread jam = new Thread(() -> printer.print("cashier-1", 3000));
        jam.start(); Thread.sleep(100);                           // cashier-1 holds the printer
        long t0 = System.currentTimeMillis();
        printer.print("cashier-2", 10);                           // main = cashier-2: must it wait?
        System.out.println("cashier-2 waited " + (System.currentTimeMillis() - t0) / 100 / 10.0 + " s");
    }
}

Output (real):

cashier-1 printing...
cashier-1 done
cashier-2 printing...
cashier-2 done
cashier-2 waited 2.9 s

A thread waiting for an intrinsic lock stays BLOCKED as long as it takes. No timeout, no giving up, no cancelling.

3. ReentrantLock and tryLock

import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.*;
class Printer {
    private final ReentrantLock lock = new ReentrantLock();       // an explicit lock object
    boolean tryPrint(String who, int ms) throws InterruptedException {
        if (!lock.tryLock(500, TimeUnit.MILLISECONDS)) return false;   // wait at most 0.5 s
        try {
            System.out.println(who + " printing...");
            Thread.sleep(ms);
            System.out.println(who + " done"); return true;
        } finally {
            lock.unlock();                                        // ALWAYS unlock in finally
        }
    }
}
public class Main {
    public static void main(String[] args) throws InterruptedException {
        Printer printer = new Printer();
        Thread jam = new Thread(() -> {
            try { printer.tryPrint("cashier-1", 3000); } catch (InterruptedException e) { }
        });
        jam.start(); Thread.sleep(100);
        long t0 = System.currentTimeMillis();
        boolean ok = printer.tryPrint("cashier-2", 10);
        System.out.println(ok ? "cashier-2 printed" : "printer busy: cashier-2 sends the bill by SMS instead");
        System.out.println("cashier-2 waited " + (System.currentTimeMillis() - t0) / 100 / 10.0 + " s");
    }
}

Output (real):

cashier-1 printing...
printer busy: cashier-2 sends the bill by SMS instead
cashier-2 waited 0.5 s
cashier-1 done
  • ReentrantLock: an explicit lock object (java.util.concurrent.locks). Reentrant like synchronized: the holder can lock it again.
  • tryLock(time, unit): wait at most that long; returns false if the lock wasn't free. tryLock() with no arguments doesn't wait at all.
  • unlock() in finally, always. Unlike synchronized, nothing releases it automatically; an exception that skips unlock() leaves the lock taken forever.
synchronized ReentrantLock
Release Automatic You call unlock() (in finally)
Give up if busy No tryLock(), tryLock(timeout)
Cancel while waiting No lockInterruptibly()
Fairness option No new ReentrantLock(true)
Several wait-sets One (wait/notify) Many Conditions
Advice Default choice When you need one of these features

Fairness: by default a released lock can go to any waiting thread, even one that just arrived (faster, but a thread may keep losing). A fair lock (new ReentrantLock(true)) gives it to the thread that has waited longest, like a queue, at some cost in speed.

4. Condition: await and signal

import java.util.concurrent.locks.*;
class Counter {                                                   // the kitchen pass: one dish slot
    private final ReentrantLock lock = new ReentrantLock();    private String dish = null;
    private final Condition dishReady = lock.newCondition();      // a waiting room on this lock
    void serve(String d) {                                        // the cook
        lock.lock();
        try { dish = d; System.out.println("cook: " + d + " is ready"); dishReady.signal(); }  // wake one
        finally { lock.unlock(); }
    }
    String pickUp() throws InterruptedException {                 // the waiter
        lock.lock();
        try {
            while (dish == null) { System.out.println("waiter: waiting..."); dishReady.await(); }  // frees lock
            String d = dish; dish = null; return d;
        } finally { lock.unlock(); }
    }
}
public class Main {
    public static void main(String[] args) throws InterruptedException {
        Counter pass = new Counter();
        Thread waiter = new Thread(() -> {
            try { System.out.println("waiter: took " + pass.pickUp() + " to table 4"); }
            catch (InterruptedException e) { }
        });
        waiter.start(); Thread.sleep(500);                        // the cook needs half a second
        pass.serve("Masala Dosa"); waiter.join();
    }
}

Output (real):

waiter: waiting...
cook: Masala Dosa is ready
waiter: took Masala Dosa to table 4
  • A Condition is a waiting room attached to a lock: lock.newCondition().
  • await() must be called holding the lock; it releases the lock and sleeps until signalled, then re-takes the lock before returning.
  • signal() wakes one waiting thread; signalAll() wakes all.
  • Always wait in a while loop, re-checking the condition: a thread can wake without the condition being true (a spurious wake-up, or another thread got there first).
  • The synchronized equivalent is obj.wait() / obj.notify() / notifyAll().

5. Read-write locks

A ReentrantReadWriteLock has a read lock many threads can hold at once, and a write lock only one thread can hold, with no readers.

import java.util.*;
import java.util.concurrent.locks.*;
class Menu {
    private final Map<String, Integer> prices = new HashMap<>(Map.of("Thali", 250, "Chai", 20));
    private final ReentrantReadWriteLock rw = new ReentrantReadWriteLock();
    int price(String item) {                                      // many readers at once
        rw.readLock().lock();
        try { pause(200); return prices.get(item); } finally { rw.readLock().unlock(); }
    }
    void setPrice(String item, int p) {                           // one writer, nobody reading
        rw.writeLock().lock();
        try { prices.put(item, p); } finally { rw.writeLock().unlock(); }
    }
    static void pause(int ms) { try { Thread.sleep(ms); } catch (InterruptedException e) { } }
}
public class Main {
    public static void main(String[] args) throws InterruptedException {
        Menu menu = new Menu();
        List<Thread> readers = new ArrayList<>();
        long t0 = System.currentTimeMillis();
        for (int i = 0; i < 5; i++) readers.add(new Thread(() -> menu.price("Thali")));
        readers.forEach(Thread::start);
        for (Thread t : readers) t.join();
        System.out.println("5 readers took about " + (System.currentTimeMillis() - t0) / 100 * 100 + " ms");
        menu.setPrice("Thali", 260);
        System.out.println("new price: " + menu.price("Thali"));
    }
}

Output (real):

5 readers took about 200 ms
new price: 260

The same program with readers taking the write lock:

5 readers took about 1000 ms
new price: 260

Use it when reads are many and writes are few.

StampedLock and optimistic reads

StampedLock adds an optimistic read: read with no lock, then validate that no write happened; only if one did, read again under a real read lock. Note: StampedLock is not reentrant.

import java.util.concurrent.locks.StampedLock;
class Board {                                                     // the price board: read very often
    private final StampedLock sl = new StampedLock();
    private int thali = 250, chai = 20;
    int total() {
        long stamp = sl.tryOptimisticRead();                      // no lock: just a version number
        int t = thali, c = chai;
        if (!sl.validate(stamp)) {                                // a write happened meanwhile?
            stamp = sl.readLock();                                // then read again, properly locked
            try { t = thali; c = chai; } finally { sl.unlockRead(stamp); }
        }
        return t + c;
    }
    void setPrices(int t, int c) {
        long stamp = sl.writeLock();
        try { thali = t; chai = c; } finally { sl.unlockWrite(stamp); }
    }
}
public class Main {
    public static void main(String[] args) {
        Board b = new Board();
        System.out.println("thali + chai = " + b.total());
        b.setPrices(260, 25);
        System.out.println("thali + chai = " + b.total());
    }
}

Output (real):

thali + chai = 270
thali + chai = 285

6. Atomic variables

import java.util.concurrent.atomic.*;
class OrderCounter {
    private final AtomicInteger count = new AtomicInteger();      // no lock, no synchronized
    void add() { count.incrementAndGet(); }                       // one atomic step
    int get() { return count.get(); }
}
public class Main {
    public static void main(String[] args) throws InterruptedException {
        OrderCounter counter = new OrderCounter();
        Runnable cashier = () -> { for (int i = 0; i < 10_000_000; i++) counter.add(); };
        Thread a = new Thread(cashier), b = new Thread(cashier);
        a.start(); b.start(); a.join(); b.join();
        System.out.println("orders = " + counter.get() + " (expected 20000000)");
        AtomicInteger stock = new AtomicInteger(1);               // the last thali, again
        Runnable sell = () -> {
            int left = stock.getAndUpdate(s -> s > 0 ? s - 1 : s);   // check-and-act in ONE atomic step
            System.out.println(Thread.currentThread().getName() + (left > 0 ? ": SOLD" : ": sold out"));
        };
        Thread c1 = new Thread(sell, "cashier-1"), c2 = new Thread(sell, "cashier-2");
        c1.start(); c2.start(); c1.join(); c2.join();
        System.out.println("thalis left = " + stock.get());
    }
}

Output (real; which cashier wins varies):

orders = 20000000 (expected 20000000)
cashier-2: SOLD
cashier-1: sold out
thalis left = 0
  • Atomic variables (java.util.concurrent.atomic): AtomicInteger, AtomicLong, AtomicBoolean, AtomicReference<T>...
  • incrementAndGet(), addAndGet(n), getAndUpdate(fn), updateAndGet(fn), compareAndSet(expected, new): each is one atomic step, with no lock.
  • getAndUpdate(s -> s > 0 ? s - 1 : s) makes the last-thali check-then-act atomic.

7. Compare-and-swap (CAS)

compareAndSet(expected, newValue): "if the variable still holds expected, set newValue; otherwise change nothing and return false." Processors do it as one instruction, so nobody gets in between. Atomic updates are CAS loops: read, compute, CAS; if it failed, someone changed the value, so read again and retry. No thread ever blocks: that's lock-free.

import java.util.concurrent.atomic.*;
public class Main {
    public static void main(String[] args) {
        AtomicInteger stock = new AtomicInteger(5);
        int seen = stock.get();                                   // I read 5...
        stock.set(4);                                             // ...meanwhile another cashier sells one
        boolean ok = stock.compareAndSet(seen, seen - 1);         // "if it is STILL 5, make it 4"
        System.out.println("CAS(5 -> 4) succeeded? " + ok + ", stock = " + stock.get());
        seen = stock.get();                                       // read again: 4
        ok = stock.compareAndSet(seen, seen - 1);                 // "if it is still 4, make it 3"
        System.out.println("CAS(4 -> 3) succeeded? " + ok + ", stock = " + stock.get());
        AtomicReference<String> special = new AtomicReference<>("Chai");   // any object, atomically
        special.updateAndGet(s -> s + " + Samosa");               // CAS in a loop, retried for you
        System.out.println("special = " + special.get());
        LongAdder visits = new LongAdder();                       // for very busy counters
        for (int i = 0; i < 1000; i++) visits.increment();
        System.out.println("visits = " + visits.sum());
    }
}

Output (real):

CAS(5 -> 4) succeeded? false, stock = 4
CAS(4 -> 3) succeeded? true, stock = 3
special = Chai + Samosa
visits = 1000
  • AtomicReference<T>: atomic updates of any object reference (best with immutable objects); updateAndGet runs the CAS loop for you.
  • LongAdder: a counter for high contention (many threads writing). It keeps several internal cells and adds them up in sum(), so threads rarely fight over one value. Best for counters written a lot and read rarely (page views, metrics). For a value you read-check-update (like stock), use AtomicInteger.

8. Thread pools: ExecutorService

A new thread per task costs memory (each thread has its own stack) and operating-system bookkeeping, has no upper limit, and gives no result back. A thread pool keeps a fixed team of threads; tasks wait in a queue and free threads pick them up.

import java.util.*;
import java.util.concurrent.*;
public class Main {
    public static void main(String[] args) throws Exception {
        ExecutorService pool = Executors.newFixedThreadPool(2);   // 2 cooks, hired once
        for (int order = 1; order <= 6; order++) {
            int n = order;
            pool.submit(() -> {                                   // a Runnable task: no result
                sleep(300);
                System.out.println("order " + n + " cooked by " + Thread.currentThread().getName());
            });
        }
        Callable<Integer> billTask = () -> { sleep(300); return 250 + 20; };   // a task WITH a result
        Future<Integer> bill = pool.submit(billTask);             // a receipt for a result to come
        System.out.println("bill submitted, done yet? " + bill.isDone());
        System.out.println("bill total = " + bill.get());         // get() waits for the result
        pool.shutdown();                                          // no new tasks; finish queued ones
        System.out.println("finished in time? " + pool.awaitTermination(5, TimeUnit.SECONDS));
    }
    static void sleep(int ms) { try { Thread.sleep(ms); } catch (InterruptedException e) { } }
}

Output (real; the order of the order lines varies):

bill submitted, done yet? false
order 2 cooked by pool-1-thread-2
order 1 cooked by pool-1-thread-1
order 4 cooked by pool-1-thread-2
order 3 cooked by pool-1-thread-1
order 5 cooked by pool-1-thread-2
order 6 cooked by pool-1-thread-1
bill total = 270
finished in time? true
  • ExecutorService: runs submitted tasks on a pool of threads. Created with factory methods in Executors.
  • submit(Runnable): a task with no result. Callable<T>: a task whose call() returns a T (and may throw).
  • Future<T>: a handle to a result that isn't ready yet: isDone(), get() (waits), get(timeout, unit), cancel(true).
  • shutdown(): accept no new tasks, finish queued ones, then the threads end. awaitTermination(t, unit) waits for that. shutdownNow() also interrupts running tasks. Forget shutdown() and the program never ends (pool threads keep waiting for work).
newFixedThreadPool(n) newCachedThreadPool()
Threads Exactly n, reused Created as needed, idle ones reused, removed after a while unused
Extra tasks Wait in a queue Get a new thread
Good for Steady CPU work (n ≈ number of cores) Many short tasks
Risk Queue can grow No upper limit on threads

Runtime.getRuntime().availableProcessors() tells you the number of cores.

Common mistakes

Mistake What you see Why Fix
lock() without finally { unlock(); } No error: other threads wait forever An exception skipped unlock() lock(); try { ... } finally { unlock(); }
lock() inside the try IllegalMonitorStateException from unlock() if lock() failed Unlocking a lock you don't hold Call lock() just before try
if (!ready) cond.await(); Acts on a false condition Spurious/early wake-up while (!ready) cond.await();
await()/signal() without holding the lock java.lang.IllegalMonitorStateException Must own the lock Lock first
A lock for a simple counter Slow under load Threads queue AtomicInteger / LongAdder
Executor never shut down Program never ends Pool threads keep waiting shutdown() + awaitTermination()
future.get() right after submit in a loop No speed-up Waiting for each task before submitting the next Submit all first, then get()
Cached pool for a flood of tasks Thousands of threads No upper limit Fixed pool (bounded)

Mini project: a kitchen that returns bills

Five orders, a 2-thread kitchen, one thali in stock (atomic), a LongAdder of served orders, and a Future per bill.

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
public class Main {
    record Order(int id, String item, int price) { }
    public static void main(String[] args) throws Exception {
        List<Order> orders = List.of(new Order(1, "Thali", 250), new Order(2, "Chai", 20),
                new Order(3, "Dosa", 120), new Order(4, "Thali", 250), new Order(5, "Lassi", 60));
        AtomicInteger thalisLeft = new AtomicInteger(1);          // only one thali in the kitchen
        LongAdder served = new LongAdder();
        ExecutorService kitchen = Executors.newFixedThreadPool(2);
        List<Future<Integer>> bills = new ArrayList<>();
        for (Order o : orders) bills.add(kitchen.submit(() -> {   // Callable<Integer>: returns the bill
            if (o.item().equals("Thali") && thalisLeft.getAndUpdate(s -> s > 0 ? s - 1 : s) == 0)
                return 0;                                         // sold out: no charge
            Thread.sleep(100); served.increment();
            return o.price();
        }));
        int revenue = 0;
        for (Future<Integer> f : bills) revenue += f.get();
        kitchen.shutdown();
        kitchen.awaitTermination(5, TimeUnit.SECONDS);
        System.out.println("served " + served.sum() + " orders, revenue Rs " + revenue);
    }
}

Output (real):

served 4 orders, revenue Rs 450

Two thali orders, one thali: one is served, the other is "sold out" (no charge). Revenue = 250 + 20 + 120 + 60 = 450.

Practice

1. Write sellOne() with your own compare-and-swap loop, and run it from two threads.

Answer
import java.util.concurrent.atomic.AtomicInteger;
public class Main {
    static final AtomicInteger stock = new AtomicInteger(3);
    static boolean sellOne() {                                    // a hand-written CAS loop
        while (true) {
            int seen = stock.get();
            if (seen == 0) return false;                          // sold out
            if (stock.compareAndSet(seen, seen - 1)) return true; // nobody changed it: done
        }                                                         // someone did: retry
    }
    public static void main(String[] args) throws InterruptedException {
        Runnable cashier = () -> { for (int i = 0; i < 5; i++) if (sellOne()) System.out.println(Thread.currentThread().getName() + " sold one"); };
        Thread a = new Thread(cashier, "cashier-1"), b = new Thread(cashier, "cashier-2");
        a.start(); b.start(); a.join(); b.join();
        System.out.println("stock = " + stock.get());
    }
}

Output (real; who sells which varies, but always exactly 3 sales and stock 0):

cashier-2 sold one
cashier-2 sold one
cashier-1 sold one
stock = 0

2. Compute three bills in a pool and add up their Futures.

Answer
import java.util.*;
import java.util.concurrent.*;
public class Main {
    public static void main(String[] args) throws Exception {
        ExecutorService pool = Executors.newFixedThreadPool(3);
        List<Callable<Integer>> bills = List.of(() -> 250 + 20, () -> 120 + 60, () -> 250);
        int total = 0;
        for (Future<Integer> f : pool.invokeAll(bills)) total += f.get();   // run all, wait for all
        pool.shutdown();
        System.out.println("today's total = " + total);
    }
}

Output (real):

today's total = 700

invokeAll submits every task and waits until all are done.

3. When would you choose a fair lock?

Answer

When threads must be served in arrival order and starvation is unacceptable (e.g. requests that must not wait indefinitely), and the extra cost is acceptable.

4. AtomicInteger or LongAdder for "how many people visited the menu page today"?

Answer

LongAdder: many threads write, the total is read rarely, and no decision depends on the exact current value.

Quick quiz

AtomicInteger stock = new AtomicInteger(3);
boolean a = stock.compareAndSet(3, 2);
boolean b = stock.compareAndSet(3, 1);
System.out.println(a + " " + b + " " + stock.get());

What is printed? (a) true true 1 (b) true false 2 (c) false true 1 (d) true false 1

Answer

(b) true false 2. The first CAS sees 3 and sets 2; the second expects 3, finds 2, fails and changes nothing.

Interview questions

  1. ReentrantLock vs synchronized? Explicit lock with tryLock, timeouts, interruptible waits, fairness and multiple conditions; but you must unlock() in finally.
  2. What is a fair lock? One that grants the lock to the longest-waiting thread; avoids starvation, costs throughput.
  3. What is a Condition? A wait-set tied to a Lock: await() releases the lock and waits; signal()/signalAll() wake waiters. Always await in a loop.
  4. When use a ReadWriteLock? Many concurrent readers, few writers. StampedLock adds optimistic reads (not reentrant).
  5. What is CAS? An atomic hardware instruction: set a new value only if the current value equals an expected value. Basis of lock-free algorithms and atomic classes.
  6. AtomicInteger vs LongAdder? AtomicInteger: one value, exact reads, CAS contention under heavy writes. LongAdder: striped cells, much better under high write contention, read via sum().
  7. What is the ABA problem? A CAS sees A, the value changes to B and back to A, and the CAS wrongly succeeds; fixed with version stamps (AtomicStampedReference).
  8. Why thread pools? Reuse threads, bound concurrency, queue work, get results via Future, manage lifecycle.
  9. Runnable vs Callable? Callable returns a value and may throw checked exceptions; Runnable does neither.
  10. shutdown() vs shutdownNow()? shutdown finishes queued tasks; shutdownNow interrupts running tasks and returns the queued ones.

Glossary

Term Meaning, with an example
java.util.concurrent Java's package of concurrency tools: locks, atomics, executors, concurrent collections
Lock Interface for explicit locks: lock(), unlock(), tryLock()
ReentrantLock The standard Lock; the holding thread can lock it again
tryLock Take the lock only if free (optionally waiting up to a timeout); returns true/false
Fairness Whether a lock goes to the longest-waiting thread: new ReentrantLock(true)
lockInterruptibly() Wait for a lock in a way another thread can cancel with interrupt()
ReadWriteLock Interface for a read lock (shared) + write lock (exclusive)
ReentrantReadWriteLock The standard ReadWriteLock
StampedLock A lock with optimistic reads validated by a stamp; not reentrant
Condition A waiting room on a lock: lock.newCondition()
await / signal Release the lock and wait / wake one waiting thread
Spurious wake-up A thread waking from await without being signalled; why we loop
Atomic variable A variable updated in one indivisible step without locks: AtomicInteger
AtomicInteger Atomic int: incrementAndGet(), compareAndSet()
AtomicReference Atomic reference to any object: updateAndGet(fn)
Compare-and-swap (CAS) "If still expected, set new", as one hardware instruction
Lock-free No thread ever waits for a lock; failed CAS just retries
LongAdder A counter spread over cells for many writers; total via sum()
Contention Many threads competing for the same lock or variable
ExecutorService Runs tasks on a pool of threads; submit, invokeAll, shutdown
Thread pool A fixed or growing set of reused threads that take tasks from a queue
Fixed thread pool Exactly n threads: Executors.newFixedThreadPool(n)
Cached thread pool Creates threads as needed, reuses idle ones: Executors.newCachedThreadPool()
Callable<T> A task that returns a T: () -> 250 + 20
Future<T> A handle to a result that will come later: get(), isDone()
shutdown() Stop accepting tasks; finish queued ones; let pool threads end
awaitTermination Wait (with a timeout) for a shut-down pool to finish

Summary

  • ReentrantLock: tryLock (with timeout), lockInterruptibly, fairness; always unlock() in finally.
  • Condition: await() releases the lock and waits; signal() wakes; await in a while loop.
  • Read-write locks let many readers in together; StampedLock adds optimistic reads.
  • Atomic variables use compare-and-swap: lock-free and exact; LongAdder for busy counters.
  • ExecutorService reuses a pool of threads; Callable + Future return results; always shutdown().

Next episode: Concurrency 4: concurrent collections (ConcurrentHashMap, BlockingQueue), producer-consumer, Semaphore, CountDownLatch, CyclicBarrier, CompletableFuture and virtual threads.