Part 2 · 2 chapters · ~12 min

Deadlock, Livelock and Starvation

Deadlock from opposite lock orders, lock ordering, timeouts and detection, livelock and randomised backoff, starvation and fairness, priority inversion (and the Mars Pathfinder story), and finding deadlocks in thread dumps and database logs.

4

Deadlock and its prevention

code
// lock both accounts in a global order, whatever the transfer direction
const [first, second] = from < to ? [from, to] : [to, from];
await db.query('SELECT 1 FROM accounts WHERE id = ANY($1) ORDER BY id FOR UPDATE', [[first, second]]);
A DEADLOCK, AND THE ORDER THAT PREVENTS IT
two transfers in opposite directions
transfer A → Blocks A, wants Btransfer B → Alocks B, wants Alock Alock Bfix: lock in id orderboth lock A first, then B
swipe the figure sideways, or tap expand for full screen
1/4
two transfers
Transfer 1 moves money from A to B and locks A first; transfer 2 moves from B to A and locks B first.
opposite directions, opposite lock ordereach holds one lock
5

Livelock, starvation and priority inversion

hazardwhat happensfix
livelockthreads keep reacting to each other (both back off, both retry at the same moment) and never progressrandomised backoff (jitter)
starvationa thread never gets the lock or the CPU because others keep winningfair locks or queues, aging priorities
priority inversiona high-priority task waits for a lock held by a low-priority task that a medium-priority task keeps preemptingpriority inheritance (the fix applied remotely to Mars Pathfinder in 1997)