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 likesynchronized: the holder can lock it again.tryLock(time, unit): wait at most that long; returnsfalseif the lock wasn't free.tryLock()with no arguments doesn't wait at all.unlock()infinally, always. Unlikesynchronized, nothing releases it automatically; an exception that skipsunlock()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
Conditionis 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
whileloop, re-checking the condition: a thread can wake without the condition being true (a spurious wake-up, or another thread got there first). - The
synchronizedequivalent isobj.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);updateAndGetruns the CAS loop for you.LongAdder: a counter for high contention (many threads writing). It keeps several internal cells and adds them up insum(), 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), useAtomicInteger.
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 inExecutors.submit(Runnable): a task with no result.Callable<T>: a task whosecall()returns aT(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. Forgetshutdown()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
ReentrantLockvssynchronized? Explicit lock withtryLock, timeouts, interruptible waits, fairness and multiple conditions; but you mustunlock()infinally.- What is a fair lock? One that grants the lock to the longest-waiting thread; avoids starvation, costs throughput.
- What is a
Condition? A wait-set tied to aLock:await()releases the lock and waits;signal()/signalAll()wake waiters. Always await in a loop. - When use a
ReadWriteLock? Many concurrent readers, few writers.StampedLockadds optimistic reads (not reentrant). - 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.
AtomicIntegervsLongAdder?AtomicInteger: one value, exact reads, CAS contention under heavy writes.LongAdder: striped cells, much better under high write contention, read viasum().- 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). - Why thread pools? Reuse threads, bound concurrency, queue work, get results via
Future, manage lifecycle. RunnablevsCallable?Callablereturns a value and may throw checked exceptions;Runnabledoes neither.shutdown()vsshutdownNow()?shutdownfinishes queued tasks;shutdownNowinterrupts 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; alwaysunlock()infinally.Condition:await()releases the lock and waits;signal()wakes; await in awhileloop.- Read-write locks let many readers in together;
StampedLockadds optimistic reads. - Atomic variables use compare-and-swap: lock-free and exact;
LongAdderfor busy counters. ExecutorServicereuses a pool of threads;Callable+Futurereturn results; alwaysshutdown().
Next episode: Concurrency 4: concurrent collections (ConcurrentHashMap, BlockingQueue), producer-consumer, Semaphore, CountDownLatch, CyclicBarrier, CompletableFuture and virtual threads.