Skip to content

Deadlock

Category: Hazards · Status: stub · Lessons: chapter 03, When locks go wrong (planned)

One line: Tasks each hold something another of them needs and wait for it, so none of them can ever continue.

Also called: deadly embrace.

How it connects

flowchart LR
  n_deadlock["Deadlock"]
  n_livelock["Livelock"]
  n_liveness_failure["Liveness failure"]
  n_lock_ordering["Lock ordering"]
  n_lock_free["Lock-free"]
  n_mutex["Mutex"]
  n_starvation["Starvation"]
  n_timeout["Timeout"]
  n_transactional_memory["Transactional memory"]
  n_deadlock ---|vs| n_livelock
  n_deadlock ---|vs| n_starvation
  n_deadlock -->|is a| n_liveness_failure
  n_lock_free -->|prevents| n_deadlock
  n_lock_ordering -->|prevents| n_deadlock
  n_mutex -->|can cause| n_deadlock
  n_timeout -->|prevents| n_deadlock
  n_transactional_memory -->|prevents| n_deadlock
  classDef center stroke-width:3px
  class n_deadlock center
  classDef outside stroke-dasharray: 4 3
  class n_livelock,n_liveness_failure,n_lock_ordering,n_lock_free,n_mutex,n_starvation,n_timeout,n_transactional_memory outside

In each language
Rust Not prevented: Mutex::lock ↗ on the thread that already holds the lock may deadlock or panic, and the Book ↗ warns that Mutex<T> comes with the risk of deadlocks
Go The runtime's checkdead in runtime/proc.go ↗ stops the program with all goroutines are asleep - deadlock!; in a testing/synctest ↗ bubble a deadlock makes Test panic
C mtx_lock ↗: locking a non-recursive mutex the thread already holds is undefined behaviour
C++ std::lock ↗ and std::scoped_lock ↗ (C++17) take several mutexes with a deadlock avoidance algorithm; relocking a std::mutex ↗ is undefined and may deadlock
Java JLS §17.1 ↗: not prevented or detected by the language; ThreadMXBean.findDeadlockedThreads ↗ finds deadlocked threads at run time
Python Lock.acquire ↗ takes a timeout, so a thread can give up instead of waiting for ever
Erlang and Elixir gen_server:call/2 ↗ waits at most 5000 ms for a reply unless given infinity
Haskell BlockedIndefinitelyOnMVar ↗: a thread blocked on an MVar that nothing else references gets this exception instead of hanging
The operating system POSIX pthread_mutex_lock ↗: a PTHREAD_MUTEX_ERRORCHECK mutex returns EDEADLK when its owner locks it again; Linux lockdep ↗ checks the kernel's lock order for cycles

Where to read more