Deadlock, Livelock & Starvation
The four conditions for deadlock and how to break each one, lock ordering as the practical answer, wait-for graphs and their cycles, livelock where everyone is busy and nothing advances, starvation, fairness and priority inversion.
Thread A holds the lock on account 7 and waits for account 12; thread B holds account 12 and waits for account 7. Neither thread is broken, neither lock is broken, and neither will ever run again. The bug is not in either thread — it is the cycle between them.
Q · Two threads are alive, each holding a lock it acquired correctly, and neither will ever make progress again — how do I find the cycle that did it?
Mutual exclusion, hold-and-wait, no preemption, circular wait. All four must hold simultaneously for a deadlock to exist — which makes the list useful for exactly one thing: choosing which one you are going to break, and paying that specific price.
Q · A deadlock needs four things to be true at once — which one is cheapest for me to make false in this particular system?
Five techniques, ordered by leverage rather than by cleverness: use fewer locks, impose an order, never hold a lock across a blocking call, acquire with a timeout, and let a higher-level primitive own the coordination. The first three cost nothing at runtime; the last two buy safety with an error path.
Q · Given a system that could deadlock, which fix gives the most safety for the least ongoing cost?
The practical answer to deadlock, and it fits in one sentence: whenever two accounts must be locked, lock the lower id first. The cycle is not detected or escaped — it becomes impossible to construct, in every schedule, for free.
Q · How do I make circular wait unconstructable rather than merely unlikely?
Both threads are running. Both are executing useful-looking code. Neither has completed anything in four minutes. Livelock is deadlock with a busy CPU graph — and because everything is "working", it is the liveness failure your dashboards are least likely to catch.
Q · Both threads are runnable and neither is blocked, so why has nothing finished?
The system is making progress. Throughput is at target, no thread is deadlocked, and one particular task has been waiting eleven minutes. Starvation is the failure where the aggregate is healthy and a specific participant never wins.
Q · The system is progressing and one task never gets to run — what keeps taking its turn?
A fair lock hands the resource to whoever waited longest. It bounds the worst case, and it is usually slower — often much slower — than the unfair lock it replaced. That trade is the lesson: fairness is bought with throughput, and you should know the price before you pay it.
Q · Should this lock hand the resource to the longest waiter, and what does that decision cost me?
A high-priority task waits on a lock held by a low-priority task, and a medium-priority task — which needs neither the lock nor anything else — preempts the holder and keeps it off the CPU. The highest-priority work in the system is now blocked behind the priority it outranks.
Q · Why is my highest-priority task waiting on work that a medium-priority task keeps interrupting?