These are the notes for Low-Level Design (LLD) episode 50, the last of the concurrency block. We have locks, atomics, pools and concurrent collections; now we look at what goes wrong when they are combined, and at the designs that prevent it. We invent deadlock and the four Coffman conditions, lock ordering and lock timeouts, livelock and starvation, thread dumps, optimistic locking with versioning vs pessimistic locking (the row-level locking idea), idempotency, the worker pool and read-write lock patterns, thread-per-request vs event loop, and a checklist for designing thread-safe classes. Every program was actually run with javac Main.java && java -cp . Main (Java 21). Outputs are real; the order of some lines varies from run to run.
1. The real-life idea: the narrow lane
| On the road | In code |
|---|---|
| Two cars enter a one-car lane from both ends; each waits for the other to reverse | Deadlock: each thread holds something the other needs; nobody moves, forever |
| Both reverse, both come back at the same moment, again and again | Livelock: threads keep reacting to each other; busy, but no progress |
| A shy driver who is always overtaken never gets through | Starvation: the system moves, but one thread never gets its turn |
| A rule: northbound cars always go first | Lock ordering: a fixed order makes the circle of waiting impossible |
2. The problem: a deadlock
One tawa and one ladle; a dosa needs both. Cook 1 takes the tawa then the ladle; cook 2 takes the ladle then the tawa.
import java.lang.management.*;
public class Main {
static final Object tawa = new Object(), ladle = new Object(); // two shared utensils
static void cook(String who, Object first, Object second) {
synchronized (first) {
System.out.println(who + " took the " + (first == tawa ? "tawa" : "ladle"));
sleep(100);
synchronized (second) { System.out.println(who + " made a dosa"); }
}
}
public static void main(String[] args) throws InterruptedException {
Thread c1 = new Thread(() -> cook("cook-1", tawa, ladle), "cook-1"); // tawa first
Thread c2 = new Thread(() -> cook("cook-2", ladle, tawa), "cook-2"); // ladle first
c1.start(); c2.start(); c1.join(1000); // wait 1 s
System.out.println("cook-1: " + c1.getState() + ", cook-2: " + c2.getState());
ThreadMXBean jvm = ManagementFactory.getThreadMXBean(); // like a thread dump
for (ThreadInfo t : jvm.getThreadInfo(jvm.findDeadlockedThreads()))
System.out.println(t.getThreadName() + " waits for " + t.getLockOwnerName());
System.exit(0); // else: forever
}
static void sleep(int ms) { try { Thread.sleep(ms); } catch (InterruptedException e) { } }
}
Output (real):
cook-1 took the tawa
cook-2 took the ladle
cook-1: BLOCKED, cook-2: BLOCKED
cook-1 waits for cook-2
cook-2 waits for cook-1
A deadlock is a set of threads where each one waits for a resource (here a lock) held by another one in the set, so none of them can ever continue. There is no exception and no error message: the program simply freezes. BLOCKED is the Thread.State of a thread waiting to enter a synchronized block. ThreadMXBean.findDeadlockedThreads() asks the JVM to find such cycles (it returns null when there are none). Without System.exit(0) this program would never end.
3. The four Coffman conditions
A deadlock can happen only if all four hold at the same time. They are named after Edward G. Coffman Jr., first author (with Michael Elphick and Arie Shoshani) of the 1971 paper "System Deadlocks" in ACM Computing Surveys.
| # | Condition | Meaning | In our kitchen | How to break it |
|---|---|---|---|---|
| 1 | Mutual exclusion | A resource can be used by only one thread at a time | One cook per tawa | Use shareable or lock-free things (immutable data, atomics) |
| 2 | Hold and wait | A thread holds one resource while waiting for another | Holding the tawa, waiting for the ladle | Take all locks at once, or give up what you hold if you can't get the rest (tryLock + back off) |
| 3 | No preemption | Nobody can force a thread to give up what it holds | Nobody can snatch the tawa | Timeouts (tryLock(time)), interruptible waits (lockInterruptibly) |
| 4 | Circular wait | A waits for B, B waits for A (a cycle) | Cook 1 → cook 2 → cook 1 | One global lock order |
Break any one and deadlock becomes impossible. In practice: break #4 with lock ordering, or #2/#3 with timeouts.
4. Fix 1: lock ordering
public class Main {
record Utensil(int id, String name) { } // every lock gets a rank
static final Utensil tawa = new Utensil(1, "tawa"), ladle = new Utensil(2, "ladle");
static void cook(String who, Utensil x, Utensil y) {
Utensil first = x.id() < y.id() ? x : y; // ALWAYS lower id first
Utensil second = x.id() < y.id() ? y : x;
synchronized (first) {
System.out.println(who + " took the " + first.name());
sleep(100);
synchronized (second) { System.out.println(who + " made a dosa"); }
}
}
public static void main(String[] args) throws InterruptedException {
Thread c1 = new Thread(() -> cook("cook-1", tawa, ladle));
Thread c2 = new Thread(() -> cook("cook-2", ladle, tawa)); // asks in the other order
c1.start(); c2.start(); c1.join(); c2.join();
System.out.println("kitchen still running: no deadlock");
}
static void sleep(int ms) { try { Thread.sleep(ms); } catch (InterruptedException e) { } }
}
Output (real):
cook-1 took the tawa
cook-1 made a dosa
cook-2 took the tawa
cook-2 made a dosa
kitchen still running: no deadlock
Lock ordering: give every lock a rank (an id, an account number) and always acquire locks in increasing rank, whatever order the caller asked in. Everyone climbs the same ladder in the same direction, so a cycle can't form. The classic interview case is a bank transfer: always lock the account with the smaller number first (practice 1).
If objects have no natural id, System.identityHashCode(obj) can rank them, with a tie-breaker lock for the rare equal hashes.
5. Fix 2: lock timeouts, and the livelock trap
Use tryLock (from episode 48): get the second lock now (or within a time limit) or give up, release the first, pause, retry. That breaks hold and wait.
import java.util.concurrent.locks.*;
public class Main {
static final Lock tawa = new ReentrantLock(), ladle = new ReentrantLock();
static void cook(String who, Lock first, Lock second) {
for (int attempt = 1; attempt <= 4; attempt++) {
first.lock();
try {
sleep(100);
if (second.tryLock()) { // don't wait: busy? give up
try { System.out.println(who + " made a dosa"); return; }
finally { second.unlock(); }
}
System.out.println(who + " backs off (try " + attempt + ")");
sleep(100);
} finally { first.unlock(); } // put the utensil down
sleep(100); // same pause every time
}
System.out.println(who + " gave up: busy all the time, no progress");
}
public static void main(String[] args) throws InterruptedException {
Thread c1 = new Thread(() -> cook("cook-1", tawa, ladle));
Thread c2 = new Thread(() -> cook("cook-2", ladle, tawa));
c1.start(); c2.start(); c1.join(); c2.join();
}
static void sleep(int ms) { try { Thread.sleep(ms); } catch (InterruptedException e) { } }
}
Output (real):
cook-2 backs off (try 1)
cook-1 backs off (try 1)
cook-2 backs off (try 2)
cook-1 backs off (try 2)
cook-1 backs off (try 3)
cook-2 backs off (try 3)
cook-1 backs off (try 4)
cook-2 backs off (try 4)
cook-1 gave up: busy all the time, no progress
cook-2 gave up: busy all the time, no progress
No thread was ever blocked for long, yet nothing got done: a livelock, threads repeatedly changing state in response to each other without progress (like two people in a corridor stepping to the same side again and again). It happened because both cooks paused for exactly the same time and stayed in step.
Fix: break the symmetry. Make the pauses different; real systems use a random pause, called jitter (often growing after each failure: exponential back-off with jitter).
import java.util.concurrent.locks.*;
public class Main {
static final Lock tawa = new ReentrantLock(), ladle = new ReentrantLock();
static void cook(String who, Lock first, Lock second) {
for (int attempt = 1; attempt <= 4; attempt++) {
first.lock();
try {
sleep(100);
if (second.tryLock()) { // don't wait: busy? give up
try { System.out.println(who + " made a dosa"); return; }
finally { second.unlock(); }
}
System.out.println(who + " backs off (try " + attempt + ")");
sleep(100);
} finally { first.unlock(); } // put the utensil down
sleep(who.equals("cook-1") ? 100 : 350); // DIFFERENT pauses
}
System.out.println(who + " gave up: busy all the time, no progress");
}
public static void main(String[] args) throws InterruptedException {
Thread c1 = new Thread(() -> cook("cook-1", tawa, ladle));
Thread c2 = new Thread(() -> cook("cook-2", ladle, tawa));
c1.start(); c2.start(); c1.join(); c2.join();
}
static void sleep(int ms) { try { Thread.sleep(ms); } catch (InterruptedException e) { } }
}
Output (real):
cook-1 backs off (try 1)
cook-2 backs off (try 1)
cook-1 made a dosa
cook-2 made a dosa
Lock timeout = waiting for a lock only up to a limit (tryLock(50, TimeUnit.MILLISECONDS)), then doing something else: retry, report "busy", or fail the request. It turns a permanent freeze into a visible, handleable failure. Careful: only unlock() a lock you actually got (see Common mistakes).
6. Starvation
Starvation: some threads make progress but one thread waits indefinitely, like a shy customer at a crowded counter.
| Cause | Fix |
|---|---|
| Unfair lock: a released lock may go to any thread, even a newcomer | new ReentrantLock(true) (fair: longest waiter first), or FIFO queues of work |
| A greedy thread holds a lock for a long time | Keep the critical section (the code that runs while holding a lock) short |
| Thread priorities | Don't rely on priorities for correctness |
| Readers keep a read-write lock busy so the writer never gets in | Fair ReentrantReadWriteLock(true) |
7. Reading a thread dump
A thread dump is a snapshot of every thread in a running JVM: its name, state (RUNNABLE, BLOCKED, WAITING, TIMED_WAITING), its stack of method calls, and the locks it holds and wants. Take one with jstack <pid> (the JDK tool; jps lists Java process ids), jcmd <pid> Thread.print, or kill -3 <pid> on Linux/macOS (printed to the program's output). For our two cooks, jstack printed (real output, Java 21.0.12):
Found one Java-level deadlock:
=============================
"cook-1":
waiting to lock monitor 0x00007fea20040d30 (object 0x00000000a8718f70, a java.lang.Object),
which is held by "cook-2"
"cook-2":
waiting to lock monitor 0x00007fea2c0015b0 (object 0x00000000a8718f60, a java.lang.Object),
which is held by "cook-1"
Java stack information for the threads listed above:
===================================================
"cook-1":
at Main.lambda$main$0(Main.java:4)
- waiting to lock <0x00000000a8718f70> (a java.lang.Object)
- locked <0x00000000a8718f60> (a java.lang.Object)
at Main$$Lambda/0x00007fea4c000a08.run(Unknown Source)
at java.lang.Thread.runWith(java.base@21.0.12.1/Thread.java:1596)
at java.lang.Thread.run(java.base@21.0.12.1/Thread.java:1583)
"cook-2":
at Main.lambda$main$1(Main.java:5)
- waiting to lock <0x00000000a8718f60> (a java.lang.Object)
- locked <0x00000000a8718f70> (a java.lang.Object)
at Main$$Lambda/0x00007fea4c000c28.run(Unknown Source)
at java.lang.Thread.runWith(java.base@21.0.12.1/Thread.java:1596)
at java.lang.Thread.run(java.base@21.0.12.1/Thread.java:1583)
Found 1 deadlock.
How to use it on a frozen server: take 2-3 dumps a few seconds apart. Threads BLOCKED in the same place in every dump, each "waiting to lock" something "held by" the other, are your deadlock, with exact file and line numbers. Many threads RUNNABLE in the same loop suggests a livelock or busy-wait.
8. The problem: a lost update
One thali left, stored as a row with a stock and a version number. Two waiters each read the row, talk to the customer, then save. Nothing is locked, just like two separate web requests hitting a database.
public class Main {
record Row(int stock, int version) { } // one row in the "database"
static volatile Row thali = new Row(1, 1); // 1 thali left
static void sell(String waiter) {
Row seen = thali; // 1. read the row
sleep(100); // 2. talk to the customer...
if (seen.stock() > 0) {
thali = new Row(seen.stock() - 1, seen.version() + 1); // 3. save: blind write
System.out.println(waiter + ": SOLD");
} else System.out.println(waiter + ": sold out");
}
public static void main(String[] args) throws InterruptedException {
Thread a = new Thread(() -> sell("waiter-1")), b = new Thread(() -> sell("waiter-2"));
a.start(); b.start(); a.join(); b.join();
System.out.println("stock now " + thali.stock() + ", but how many did we sell?");
}
static void sleep(int ms) { try { Thread.sleep(ms); } catch (InterruptedException e) { } }
}
Output (real):
waiter-1: SOLD
waiter-2: SOLD
stock now 0, but how many did we sell?
Both read stock 1; the second save overwrote the first (a blind write: saving without checking what changed since you read). Two customers were promised one thali: a lost update.
9. Optimistic locking with versioning
Optimistic locking: assume conflicts are rare, lock nothing while working, and detect a conflict when saving. Versioning: every row carries a version number that goes up by one on every save. A save succeeds only if the version is still the one you read.
import java.util.concurrent.atomic.*;
public class Main {
record Row(int stock, int version) { }
static final AtomicReference<Row> thali = new AtomicReference<>(new Row(1, 1));
static void sell(String waiter) {
while (true) {
Row seen = thali.get(); // read row + its version
sleep(100);
if (seen.stock() == 0) { System.out.println(waiter + ": sold out"); return; }
Row next = new Row(seen.stock() - 1, seen.version() + 1);
if (thali.compareAndSet(seen, next)) { // save ONLY if unchanged
System.out.println(waiter + ": SOLD, v" + seen.version() + " -> v" + next.version());
return;
}
System.out.println(waiter + ": conflict! version changed, read again");
}
}
public static void main(String[] args) throws InterruptedException {
Thread a = new Thread(() -> sell("waiter-1")), b = new Thread(() -> sell("waiter-2"));
a.start(); b.start(); a.join(); b.join();
System.out.println("stock now " + thali.get().stock() + ", sold exactly once");
}
static void sleep(int ms) { try { Thread.sleep(ms); } catch (InterruptedException e) { } }
}
Output (real; the two first lines can swap):
waiter-2: conflict! version changed, read again
waiter-1: SOLD, v1 -> v2
waiter-2: sold out
stock now 0, sold exactly once
compareAndSet(seen, next) plays the database. In SQL the same idea is:
UPDATE menu_item SET stock = stock - 1, version = version + 1
WHERE id = 4 AND version = 1; -- 0 rows changed = someone saved first: re-read and retry
10. Pessimistic locking and row-level locks
Pessimistic locking: assume conflicts are likely, so lock first, then read and change, while others wait. A row-level lock locks only the one row you are changing, not the whole table: like a waiter reserving only table 4 instead of closing the whole restaurant. In SQL: SELECT ... FOR UPDATE inside a transaction. In Java, one lock per row id:
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.*;
public class Main {
static final Map<Integer, Integer> stock = new ConcurrentHashMap<>(Map.of(4, 1, 5, 1)); // item id -> stock
static final Map<Integer, Lock> rowLocks = new ConcurrentHashMap<>(); // one lock per row
static void sell(String waiter, int item) {
Lock row = rowLocks.computeIfAbsent(item, id -> new ReentrantLock());
row.lock(); // lock THIS row before reading
try {
int seen = stock.get(item);
sleep(100); // others wanting row 4 wait here
if (seen > 0) { stock.put(item, seen - 1); System.out.println(waiter + ": SOLD item " + item); }
else System.out.println(waiter + ": item " + item + " sold out");
} finally { row.unlock(); }
}
public static void main(String[] args) throws InterruptedException {
long t0 = System.currentTimeMillis();
Thread a = new Thread(() -> sell("waiter-1", 4)), b = new Thread(() -> sell("waiter-2", 4));
Thread c = new Thread(() -> sell("waiter-3", 5)); // a different row: not blocked
a.start(); b.start(); c.start(); a.join(); b.join(); c.join();
System.out.println("stock " + stock + ", took about " + (System.currentTimeMillis() - t0) / 100 * 100 + " ms");
}
static void sleep(int ms) { try { Thread.sleep(ms); } catch (InterruptedException e) { } }
}
Output (real):
waiter-2: SOLD item 4
waiter-3: SOLD item 5
waiter-1: item 4 sold out
stock {4=0, 5=0}, took about 200 ms
The two waiters on row 4 took turns (2 × 100 ms); waiter 3 on row 5 was never blocked.
| Optimistic | Pessimistic | |
|---|---|---|
| Lock while working | No | Yes, from read to save |
| On conflict | Detect at save, re-read, retry | Others simply wait |
| Best when | Conflicts are rare (editing your own profile, admin edits) | Conflicts are common (the last concert seat, flash sales) |
| Risks | Many retries under heavy contention | Waiting, and deadlocks if rows are locked in different orders |
11. The problem: charged twice
The payment goes through, but the reply is lost on the network, so the app retries.
class PaymentService {
private int charged = 0;
synchronized void pay(String orderId, int amount) {
charged += amount;
System.out.println("charged Rs " + amount + " for " + orderId);
}
synchronized int total() { return charged; }
}
public class Main {
public static void main(String[] args) {
PaymentService payments = new PaymentService();
payments.pay("order-42", 250); // the reply gets lost on the way...
payments.pay("order-42", 250); // ...so the app RETRIES
System.out.println("customer paid Rs " + payments.total() + " for one thali");
}
}
Output (real):
charged Rs 250 for order-42
charged Rs 250 for order-42
customer paid Rs 500 for one thali
12. Idempotency
An operation is idempotent if doing it twice has the same effect as doing it once: pressing the lift button again doesn't call a second lift; PUT price = 260 twice leaves 260; but "add Rs 250" twice is not idempotent. Idempotency is that property. The usual design: the client creates a unique idempotency key per logical request (an order id, a UUID) and sends the same key on every retry; the server remembers the keys it has processed and ignores repeats (or returns the first result again).
import java.util.*;
import java.util.concurrent.*;
class PaymentService {
private final Set<String> done = ConcurrentHashMap.newKeySet(); // keys already handled
private int charged = 0;
synchronized String pay(String idempotencyKey, int amount) {
if (!done.add(idempotencyKey)) return "duplicate " + idempotencyKey + ": ignored";
charged += amount;
return "charged Rs " + amount + " for " + idempotencyKey;
}
synchronized int total() { return charged; }
}
public class Main {
public static void main(String[] args) throws InterruptedException {
PaymentService payments = new PaymentService();
Runnable tap = () -> System.out.println(payments.pay("order-42", 250));
Thread first = new Thread(tap), retry = new Thread(tap), again = new Thread(tap);
first.start(); retry.start(); again.start(); // 3 copies of one request
first.join(); retry.join(); again.join();
System.out.println("customer paid Rs " + payments.total() + " for one thali");
}
}
Output (real):
charged Rs 250 for order-42
duplicate order-42: ignored
duplicate order-42: ignored
customer paid Rs 250 for one thali
Set.add returns false if the key is already present, and ConcurrentHashMap.newKeySet() makes that check-and-insert atomic, so three simultaneous copies charge once. Real systems store the keys in a database with a unique constraint and an expiry time. Message consumers need the same thing, because messaging systems often deliver a message at least once, i.e. sometimes twice.
13. Concurrency patterns
| Pattern | Idea | Where we built it |
|---|---|---|
| Worker pool | A fixed number of reused worker threads take tasks from a shared queue | ExecutorService (ep 48), producer-consumer kitchen (ep 49) |
| Producer-consumer | Producers put work in a (bounded) queue, consumers take it | BlockingQueue (ep 49) |
| Read-write lock | Many readers together, or one writer alone | ReentrantReadWriteLock menu (ep 48) |
| Thread confinement | Data used by only one thread needs no locks | Local variables, ThreadLocal (ep 47) |
| Immutable objects | Objects that never change can be shared freely | records, List.copyOf |
| Optimistic concurrency | Work without locks, check a version on save | Section 9 |
Thread-per-request vs event loop
| Thread-per-request | Event loop | |
|---|---|---|
| Idea | Each incoming request gets its own thread, which simply waits for the database or network | One (or a few) threads run a loop that picks up events ("data arrived", "timer fired") and never blocks; slow work is started and a callback (a function to call later) runs when it completes |
| Code | Straight-line and easy to read and debug | Split into callbacks/promises; harder to follow |
| Cost | One thread per waiting request: platform threads are expensive | Very few threads for many connections |
| Example | Classic blocking Java servers; Java with virtual threads (cheap threads, same simple code) | JavaScript: per MDN, "JavaScript has a runtime model based on an event loop" |
14. Designing thread-safe classes: the checklist
- Prefer immutability.
finalfields, no setters, records,List.copyOf. What can't change can't race. - Encapsulate state. Fields
private; never return your internal collection (return a copy or an unmodifiable view). - One lock per piece of state, used on every access, reads and writes. Document which lock guards which field.
- Make check-then-act atomic:
putIfAbsent,merge,compute,compareAndSet, or onesynchronizedmethod. - Keep critical sections short. Never call slow code (network, disk) or unknown code (listeners, callbacks passed in) while holding a lock: that is how hidden lock orders and deadlocks appear. Copy what you need, unlock, then call.
- Reuse the library: concurrent collections, atomics, executors, latches, instead of hand-written
wait/notify. - Never hold two locks if you can avoid it; if you must, use one global order.
- Document the thread-safety ("thread-safe", "not thread-safe, confine to one thread", "immutable").
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
/** Thread-safe: any thread may call any method at any time. */ final class TableBooking {
record Booking(int table, String guest) { } // immutable: safe to share
private final Map<Integer, Booking> byTable = new ConcurrentHashMap<>();
boolean book(int table, String guest) { // check-and-act in ONE call
return byTable.putIfAbsent(table, new Booking(table, guest)) == null;
}
boolean cancel(int table, String guest) { // only the owner may cancel
return byTable.remove(table, new Booking(table, guest));
}
Map<Integer, Booking> snapshot() { return Map.copyOf(byTable); } // a copy
}
public class Main {
public static void main(String[] args) throws InterruptedException {
TableBooking cafe = new TableBooking();
AtomicInteger wins = new AtomicInteger();
try (ExecutorService pool = Executors.newVirtualThreadPerTaskExecutor()) {
for (int i = 1; i <= 100; i++) {
String guest = "guest-" + i;
pool.submit(() -> { if (cafe.book(4, guest)) wins.incrementAndGet(); });
}
} // close() waits
System.out.println("100 guests tried table 4, winners: " + wins.get());
System.out.println("cancel by a stranger: " + cafe.cancel(4, "guest-0"));
System.out.println(cafe.snapshot().size() + " booking(s)");
}
}
Output (real):
100 guests tried table 4, winners: 1
cancel by a stranger: false
1 booking(s)
remove(key, value) removes only if the current value equals the given one; Booking is a record, so equals compares table and guest. The class holds no lock across calls, so it can't take part in a deadlock.
Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
| Two locks taken in different orders | No error: the program freezes; jstack says Found one Java-level deadlock |
Circular wait | One global lock order |
| Same fixed back-off for every thread | No error: livelock, "busy" but no progress | Threads stay in step | Random back-off (jitter) |
unlock() in finally after a failed tryLock() |
java.lang.IllegalMonitorStateException |
Unlocking a lock you don't hold | if (lock.tryLock()) { try { ... } finally { lock.unlock(); } } |
| Read, change, blind save | No error: lost update (sold twice) | Second save overwrites the first | Version check (optimistic) or row lock (pessimistic) |
| Retrying a non-idempotent call | No error: charged twice | No duplicate detection | Idempotency key |
| Calling slow or unknown code inside a lock | No error: everyone waits, or a deadlock | Long critical section, hidden lock order | Copy data, unlock, then call |
| Locking rows in random order in pessimistic locking | Database deadlock errors | Circular wait between transactions | Lock rows in a fixed order (by id) |
| Unfair lock under heavy load | No error: some requests wait very long | Starvation | Fair lock / FIFO queue, short critical sections |
Mini project: a thread-safe parking lot
Fixed number of spots (a Semaphore), an idempotent park() (the same car gets the same ticket and doesn't take a second spot), and no locks held across calls.
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
/** Thread-safe parking lot: fixed spots, idempotent park(), no locks held across calls. */
final class ParkingLot {
private final Semaphore freeSpots;
private final ConcurrentMap<String, Integer> ticketByCar = new ConcurrentHashMap<>();
private final AtomicInteger nextTicket = new AtomicInteger(1);
ParkingLot(int spots) { freeSpots = new Semaphore(spots); }
Optional<Integer> park(String car) { // idempotent: same car, same ticket
Integer already = ticketByCar.get(car);
if (already != null) return Optional.of(already);
if (!freeSpots.tryAcquire()) return Optional.empty(); // full: don't wait
boolean[] mine = {false};
Integer ticket = ticketByCar.computeIfAbsent(car, c -> { mine[0] = true; return nextTicket.getAndIncrement(); });
if (!mine[0]) freeSpots.release(); // a twin request won the race: give the spot back
return Optional.of(ticket);
}
boolean leave(String car) {
if (ticketByCar.remove(car) == null) return false;
freeSpots.release(); return true;
}
int free() { return freeSpots.availablePermits(); }
}
public class Main {
public static void main(String[] args) throws InterruptedException {
ParkingLot lot = new ParkingLot(3);
System.out.println("MH12-0 ticket " + lot.park("MH12-0").get() + ", retry ticket " + lot.park("MH12-0").get()
+ ", free " + lot.free()); // a retry doesn't take a 2nd spot
AtomicInteger parked = new AtomicInteger(), turnedAway = new AtomicInteger();
try (ExecutorService gate = Executors.newVirtualThreadPerTaskExecutor()) {
for (int i = 1; i <= 10; i++) {
String car = "MH12-" + i;
gate.submit(() -> { if (lot.park(car).isPresent()) parked.incrementAndGet(); else turnedAway.incrementAndGet(); });
}
}
System.out.println("parked " + parked + ", turned away " + turnedAway + ", free " + lot.free());
}
}
Output (real):
MH12-0 ticket 1, retry ticket 1, free 2
parked 2, turned away 8, free 0
If two copies of the same car's request race, both may take a permit, but computeIfAbsent lets only one insert a ticket; the loser gives its permit back.
Practice
1. Two threads transfer money between the same two accounts in opposite directions, 100,000 times each. Make it deadlock-free.
Answer
public class Main {
static class Account {
final int number; int balance;
Account(int number, int balance) { this.number = number; this.balance = balance; }
}
static void transfer(Account from, Account to, int amount) {
Account first = from.number < to.number ? from : to; // smaller account number first
Account second = first == from ? to : from;
synchronized (first) {
synchronized (second) {
from.balance -= amount; to.balance += amount;
}
}
}
public static void main(String[] args) throws InterruptedException {
Account asha = new Account(101, 1000), ravi = new Account(202, 1000);
Thread t1 = new Thread(() -> { for (int i = 0; i < 100_000; i++) transfer(asha, ravi, 1); });
Thread t2 = new Thread(() -> { for (int i = 0; i < 100_000; i++) transfer(ravi, asha, 1); });
t1.start(); t2.start(); t1.join(); t2.join();
System.out.println("asha " + asha.balance + ", ravi " + ravi.balance + ", total " + (asha.balance + ravi.balance));
}
}
Output (real):
asha 1000, ravi 1000, total 2000
Without the ordering (synchronized (from) { synchronized (to) { ... } }) the two threads deadlock within moments.
2. Add a version to a seat so that only one of 5 fans can book seat A1, without any lock.
Answer
import java.util.*;
import java.util.concurrent.*;
public class Main {
record Seat(String id, String holder, int version) { }
static final ConcurrentMap<String, Seat> seats = new ConcurrentHashMap<>(Map.of("A1", new Seat("A1", null, 1)));
static boolean book(String seatId, String who) {
while (true) {
Seat seen = seats.get(seatId);
if (seen.holder() != null) return false; // already taken
Seat next = new Seat(seatId, who, seen.version() + 1);
if (seats.replace(seatId, seen, next)) return true; // only if still the same version
}
}
public static void main(String[] args) throws InterruptedException {
List<Thread> fans = new ArrayList<>();
for (int i = 1; i <= 5; i++) { String who = "fan-" + i; fans.add(new Thread(() -> { if (book("A1", who)) System.out.println(who + " got A1"); })); }
fans.forEach(Thread::start);
for (Thread t : fans) t.join();
System.out.println(seats.get("A1"));
}
}
Output (real; which fan wins varies):
fan-1 got A1
Seat[id=A1, holder=fan-1, version=2]
ConcurrentMap.replace(key, oldValue, newValue) is the "save only if unchanged" step.
3. Make a refund API idempotent, so that a retry returns the same answer and refunds nothing extra.
Answer
import java.util.concurrent.*;
public class Main {
static final ConcurrentMap<String, String> results = new ConcurrentHashMap<>(); // key -> first result
static int refunded = 0;
static synchronized int addRefund(int amount) { refunded += amount; return refunded; }
static String refund(String idempotencyKey, int amount) {
return results.computeIfAbsent(idempotencyKey, k -> { // runs at most once per key
addRefund(amount);
return "refunded Rs " + amount + " (" + k + ")";
}); // a retry gets the SAME answer
}
public static void main(String[] args) {
System.out.println(refund("refund-42", 250));
System.out.println(refund("refund-42", 250)); // retry
System.out.println(refund("refund-43", 60));
System.out.println("total refunded Rs " + refunded);
}
}
Output (real):
refunded Rs 250 (refund-42)
refunded Rs 250 (refund-42)
refunded Rs 60 (refund-43)
total refunded Rs 310
4. Which Coffman condition does each fix break? (a) lock ordering (b) tryLock with timeout and back-off (c) replacing a lock with an AtomicInteger.
Answer
(a) circular wait; (b) hold and wait (and, in effect, no preemption: you give up your own lock); (c) mutual exclusion (no lock to hold).
5. A profile page is edited by its owner a few times a month; a flash sale has 10,000 buyers for 100 phones. Optimistic or pessimistic?
Answer
Profile: optimistic (conflicts are rare, no waiting). Flash sale: pessimistic or an atomic decrement (UPDATE ... SET stock = stock - 1 WHERE id = ? AND stock > 0), because optimistic retries would pile up.
Quick quiz
// thread 1: lock(A) then lock(B)
// thread 2: lock(B) then lock(A)
Which change makes deadlock impossible? (a) Make both locks fair (b) Make both threads lock A, then B (c) Add Thread.sleep between the locks (d) Use volatile fields
Answer
(b). One lock order removes the circular wait. Fairness, sleeping or volatile don't break any of the four conditions; a sleep only makes the deadlock more likely.
Interview questions
- What is a deadlock? Give the four necessary conditions. Threads each waiting for a resource another holds; mutual exclusion, hold and wait, no preemption, circular wait (Coffman, 1971).
- How do you prevent deadlocks? Global lock order;
tryLockwith timeout and back-off; take fewer locks (immutable data, atomics, concurrent collections); never call alien code while holding a lock. - How do you find a deadlock in production? Thread dumps (
jstack,jcmd Thread.print), look forFound one Java-level deadlockor threadsBLOCKEDon each other across several dumps;ThreadMXBean.findDeadlockedThreads()for monitoring. - Deadlock vs livelock vs starvation? Nobody moves / everybody moves but nothing completes / some move, one never gets a turn.
- Optimistic vs pessimistic locking? Check a version at save and retry vs lock the row before reading; choose by how often conflicts happen.
- What is idempotency and how do you implement it for payments? Same effect once or many times; a client-generated idempotency key stored with a unique constraint, repeats return the original result.
- Thread-per-request vs event loop? Simple blocking code with one thread per request vs few non-blocking threads with callbacks; virtual threads give thread-per-request style at low cost.
- How do you design a thread-safe class? Immutability, encapsulation, one lock per state, atomic compound actions, short critical sections, library tools, documented thread-safety.
Glossary
| Term | Meaning, with an example |
|---|---|
| Deadlock | Threads each waiting for a resource another holds, so none can continue: cook 1 has the tawa and wants the ladle, cook 2 the reverse |
| Coffman conditions | The four conditions that must all hold for a deadlock (Coffman, Elphick, Shoshani, 1971) |
| Mutual exclusion | A resource usable by only one thread at a time: one cook per tawa |
| Hold and wait | Holding one resource while waiting for another |
| No preemption | A held resource can't be taken away; only its holder releases it |
| Circular wait | A cycle of threads each waiting for the next: A → B → A |
BLOCKED |
Thread state: waiting to enter a synchronized block held by another thread |
| Lock ordering | Always acquiring locks in one global order (by id) to make circular wait impossible |
| Lock timeout | Waiting for a lock only up to a limit: tryLock(50, MILLISECONDS) |
| Back-off | Releasing what you hold and pausing before retrying |
| Jitter | A random amount added to a pause so threads don't stay in step |
| Livelock | Threads keep changing state in response to each other but make no progress |
| Starvation | One thread never gets its turn while others progress |
| Fair lock | A lock that goes to the longest-waiting thread: new ReentrantLock(true) |
| Critical section | The code that runs while holding a lock |
| Thread dump | A snapshot of all threads: names, states, stacks, locks held and wanted |
jstack |
JDK tool that prints a thread dump of a running JVM: jstack <pid> |
ThreadMXBean |
Java management API to inspect threads, e.g. findDeadlockedThreads() |
| Lost update | A save that silently overwrites another thread's save |
| Blind write | Saving without checking whether the data changed since you read it |
| Optimistic locking | Lock nothing while working; at save, check the data is unchanged, else retry |
| Versioning | A version number on each row, increased on every save, used by optimistic locking |
| Pessimistic locking | Lock the data before reading it; others wait until you finish |
| Row-level lock | A lock on one row only, not the whole table: reserve table 4, not the restaurant |
SELECT ... FOR UPDATE |
SQL that reads rows and locks them until the transaction ends |
| Idempotent | Doing it twice has the same effect as once: pressing the lift button again |
| Idempotency key | A unique id sent with a request and its retries so the server can ignore repeats |
| At-least-once delivery | A messaging guarantee where a message may arrive more than once |
| Worker pool | A fixed set of reused threads taking tasks from a shared queue |
| Read-write lock pattern | Many readers together or one writer alone |
| Thread confinement | Keeping data inside one thread so it needs no locking |
| Thread-per-request | Server model: each request gets its own thread |
| Event loop | Server model: a few threads loop over events and never block; callbacks finish the work |
| Callback | A function you hand over to be called later, when something completes |
| Thread-safe class | A class that stays correct under any number of threads calling it at once |
| Alien method | Code you don't control (a listener, an overridable method) called from your class |
Summary
- A deadlock needs all four Coffman conditions; break one: lock ordering (circular wait) or timeouts with back-off (hold and wait).
- Identical back-off can cause livelock: add jitter. Unfair locks and long critical sections cause starvation.
- Thread dumps (
jstack) show who holds and who waits for which lock. - Optimistic locking checks a version at save; pessimistic locking locks the row first (row-level locks keep other rows free).
- Idempotency keys make retries safe.
- Patterns: worker pool, producer-consumer, read-write lock; servers are thread-per-request (now cheap with virtual threads) or event loops.
- A thread-safe class: immutable where possible, private state, atomic compound actions, short critical sections, documented.
Next episode: Clean code: meaningful names, small functions, command-query separation and the code smells that warn you a design is going wrong.