Threading & Deadlocks#

flowchart LR
  T1[Thread A<br/>holds L1, wants L2]
  T2[Thread B<br/>holds L2, wants L1]
  L1([Lock 1])
  L2([Lock 2])
  T1 -- holds --> L1
  T2 -- holds --> L2
  T1 -- waits --> L2
  T2 -- waits --> L1

  classDef p fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
  classDef s fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
  class T1,T2 p;
  class L1,L2 s;

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class T1,T2,L1,L2 service;

A deadlock happens when two or more threads form a cycle of "I hold this, I want yours". Prevention is about breaking the four Coffman conditions: mutual exclusion, hold-and-wait, no preemption, circular wait.

Thread states#

stateDiagram-v2
  [*] --> New
  New --> Runnable : start()
  Runnable --> Running : scheduler picks it
  Running --> Runnable : preempt
  Running --> Waiting : wait() / await condition
  Waiting --> Runnable : notify / signal
  Running --> TimedWaiting : sleep / join with timeout
  TimedWaiting --> Runnable : time elapses / signal
  Running --> Blocked : try to take a held lock
  Blocked --> Runnable : lock released
  Running --> [*] : run() returns

Threading models#

Model	Example	Trade-off
1:1 (OS threads)	Java, Linux pthreads	full preemption, ~MB stack each
N:1 (user threads)	early Erlang	no preemption, cheap
M:N (mix)	Go goroutines, Erlang BEAM, Java loom (virtual threads)	cheap fibres mapped to OS threads
Single-threaded + event loop	Node.js, Redis	no shared-mutable concurrency, async I/O

Coffman conditions for deadlock#

All four must hold for a deadlock: 1. Mutual exclusion - a resource is held exclusively. 2. Hold and wait - a thread holds one and asks for another. 3. No preemption - the system can't forcibly take the resource. 4. Circular wait - a cycle of holders.

Break any one to prevent deadlock.

Prevention strategies#

Strategy	How	Cost
Lock ordering	always acquire locks in a global order (e.g. by id)	requires discipline; works in single process
`tryLock` with timeout	back off + retry on contention	may livelock; use jitter
Lock coarsening	one big lock	low concurrency
Lock-free / atomics	no locks, CAS loops	hard to design correctly
Resource leveling / pre-allocation	grab all needed resources up front	wastes capacity
Wait-die / wound-wait (classic DB)	older tx wins / kills younger	aborts increase
Detection + abort	run-time cycle detection, then rollback one	needed for arbitrary tx ordering (DBs do this)

Lock ordering example#

For "transfer money from account A to account B":

void transfer(Account a, Account b, BigDecimal amt) {
  Account first  = a.id < b.id ? a : b;
  Account second = a.id < b.id ? b : a;
  synchronized (first) {
    synchronized (second) {
      a.debit(amt);
      b.credit(amt);
    }
  }
}

Without ordering, two simultaneous transfers in opposite directions deadlock.

Detection at runtime#

Java: jstack shows held & waited-on locks; the JVM prints "Found one Java-level deadlock" when it can.
PostgreSQL: pg_stat_activity + pg_locks; configured deadlock_timeout triggers detection.
OS: tools like valgrind --tool=helgrind, tsan (ThreadSanitizer).

Livelock - threads stay active, keep yielding, never make progress. Common with poorly-tuned tryLock + retry.
Starvation - a low-priority thread is perpetually skipped. Use fair locks (ReentrantLock(true)).
Priority inversion - high-priority waits for low-priority holding the lock. Solved by priority inheritance.

Where this shows up in this site#

Stock exchange - avoids the whole class of problems by going single-threaded per symbol.
Distributed lock service - fencing tokens prevent the network-scale version of "no preemption".
Banking / wallet transfers - lock ordering by account id.
Calendar event RSVP - optimistic concurrency to avoid lock cycles.

Glossary & fundamentals#

Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.

Tag	Concept	What it is	Page
`HLD`	Idempotency & retries	safe re-execution, backoff + jitter	idempotency-retries
`LLD`	Async models	futures / async-await / coroutines / actors	async-models
`LLD`	OOP pillars	encapsulation, abstraction, inheritance, polymorphism	oop-pillars
`LLD`	Behavioural patterns	Strategy, Observer, State, Command, Chain	behavioral-patterns
`LLD`	Concurrency primitives	mutex, semaphore, RW lock, atomic, CAS	concurrency-primitives
`LLD`	Threading & deadlocks	thread states, Coffman, lock ordering	threading-and-deadlocks

Quick reference#

Debugging deadlocks#

Reproduce: stress-test with many threads.
Snapshot stacks (jstack, gdb thread apply all bt, tsan).
Look for cycles in the held-vs-waiting lock graph.
Time-bound tryLock to surface deadlocks fast in tests.

Designing them out#

Hold one lock at a time when possible.
If you must hold multiple, define a global lock-ordering policy.
Prefer message-passing (channels, actors, Kafka) over shared mutable state.
Keep critical sections short; never call out into unknown code while holding a lock.

Lock-free isn't a silver bullet#

Lock-free algorithms have their own hazards: ABA, livelocks, memory-ordering bugs. Use battle-tested data structures (ConcurrentHashMap, java.util.concurrent.atomic, c++ std::atomic, Go channels).

Refs#

Java Concurrency in Practice - chapter 10 (avoiding liveness hazards).
Edsger Dijkstra: original treatment of dining philosophers.
The Linux RT-locking and priority inheritance discussions.
PostgreSQL docs: deadlocks & advisory locks.

FAQ#

What is a deadlock in multithreading?#

A deadlock is when two or more threads each wait for a lock the other holds, so none can make progress. All four Coffman conditions must be true at once.

What are the four Coffman conditions for deadlock?#

Mutual exclusion, hold and wait, no preemption, and circular wait. Breaking any one of them prevents deadlocks from forming.

How do I prevent deadlocks?#

Always acquire locks in a globally consistent order, use try-lock with timeouts, or replace fine-grained locks with a single coarse lock when contention permits.

What is the difference between deadlock and livelock?#

In deadlock no thread progresses. In livelock threads keep changing state in response to each other but never finish, like two people sidestepping in a hallway.

How do databases detect deadlocks?#

Most engines build a wait-for graph and look for cycles. When one is found they abort the cheapest victim, which then retries. Postgres and MySQL both do this.

Concurrency Primitives: mutexes, semaphores, and monitors are the primitives involved in deadlock scenarios
Async Models: async and actor models reduce shared-state concurrency and the risk of deadlocks
Error Handling: detecting and recovering from liveness failures like deadlock and livelock