SyntaxPilot
Courses/Low-Level Design/Lesson 50
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 50 of 90

Concurrency 5: deadlocks and concurrency patterns in LLD

deadlockCoffman conditionslock orderinglock timeoutlivelockstarvationthread dumpsoptimistic lockingversioningpessimistic lockingrow-level locking analogyidempotencyworker pool patternread-write lock pattern

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

  1. Prefer immutability. final fields, no setters, records, List.copyOf. What can't change can't race.
  2. Encapsulate state. Fields private; never return your internal collection (return a copy or an unmodifiable view).
  3. One lock per piece of state, used on every access, reads and writes. Document which lock guards which field.
  4. Make check-then-act atomic: putIfAbsent, merge, compute, compareAndSet, or one synchronized method.
  5. 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.
  6. Reuse the library: concurrent collections, atomics, executors, latches, instead of hand-written wait/notify.
  7. Never hold two locks if you can avoid it; if you must, use one global order.
  8. 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

  1. 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).
  2. How do you prevent deadlocks? Global lock order; tryLock with timeout and back-off; take fewer locks (immutable data, atomics, concurrent collections); never call alien code while holding a lock.
  3. How do you find a deadlock in production? Thread dumps (jstack, jcmd Thread.print), look for Found one Java-level deadlock or threads BLOCKED on each other across several dumps; ThreadMXBean.findDeadlockedThreads() for monitoring.
  4. Deadlock vs livelock vs starvation? Nobody moves / everybody moves but nothing completes / some move, one never gets a turn.
  5. Optimistic vs pessimistic locking? Check a version at save and retry vs lock the row before reading; choose by how often conflicts happen.
  6. 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.
  7. 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.
  8. 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.