Skip to content

Threading & Deadlocks — Detailed#

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