Skip to content

Lock ordering

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

One line: Always taking locks in one agreed order, so that no cycle of tasks waiting on each other — and so no deadlock — can form.

Also called: lock hierarchy.

How it connects

flowchart LR
  n_deadlock["Deadlock"]
  n_lock_ordering["Lock ordering"]
  n_lock_ordering -->|prevents| n_deadlock
  classDef center stroke-width:3px
  class n_lock_ordering center
  classDef outside stroke-dasharray: 4 3
  class n_deadlock outside

In each language
C++ std::lock ↗ takes several mutexes with a deadlock avoidance algorithm instead of a fixed order
Java JLS §17.1 ↗ tells programs holding locks on multiple objects to use conventional deadlock-avoidance techniques
The operating system Linux lockdep ↗ records which lock is taken while holding which, and reports orders that could form a cycle
Elsewhere Valgrind's Helgrind ↗ monitors the order threads acquire locks in to find potential deadlocks; ThreadSanitizer ↗ reports lock-order inversions (detect_deadlocks)

Where to read more