Deadlock vs Livelock vs Starvation

Same symptom, three different diseases

You have now spent four guides on deadlock: the four necessary conditions, the resource-allocation graph, the banker's algorithm, and detection with recovery. But deadlock is only one of three ways a process can get stuck forever, and from the outside they look almost identical. A user reports that the program "hangs" — it does not crash, it does not print an error, it just sits there doing nothing useful. Underneath that one symptom hide three completely different illnesses, and prescribing the wrong cure can make things worse. This final guide in the rung is the diagnostic chart that tells them apart.

Here is the one-sentence version of each. A deadlock is a set of processes all blocked, each waiting on a resource held by another in the set — nobody is running, and nothing inside the group can ever change. Livelock is the opposite of blocked: the processes are busy, constantly running and reacting to each other, yet they make no progress, like two people sidestepping in a corridor forever. Starvation is when a process is ready and able to run but the system keeps choosing someone else, so it waits indefinitely while the rest of the system hums along fine. Notice the giveaway difference: in deadlock and livelock a whole group is stuck together; in starvation it is usually one unlucky process while everybody else thrives.

Livelock: busy, polite, and going nowhere

Picture two people meeting head-on in a narrow hallway. You step left to let the other pass; they step the same way; you both step back; you both step the same way again. You are moving constantly, you are being courteous, and yet you never get past each other. That is livelock: states keep changing, work keeps happening, but no useful progress is ever made. The cruel part is that everyone is doing exactly what they were told — "if you are blocking someone, get out of the way" — and that very rule is what traps them.

Livelock often appears precisely when programmers try to AVOID deadlock with a too-clever trick. A common one is "polite backoff": if I cannot get all the locks I need, I release the ones I am holding and retry, so I never sit holding-and-waiting. That breaks one of the four conditions — good instinct. But if two processes back off and retry in perfect lockstep, each releasing and re-grabbing at the same instant, they collide on every single attempt and never both succeed. They are not blocked, so a deadlock detector sees nothing wrong; they are simply spinning forever.

loop forever:
    if can grab BOTH locks:  proceed     <- never both at once
    else:
        release any held lock
        wait a moment
        retry            <- both retry in lockstep -> collide again

The classic fix is to break the symmetry so the two sides stop mirroring each other. Add a small RANDOM delay before each retry — now the chance they keep colliding shrinks fast with every round (this is the same idea as the randomised backoff used in networks). Even better, impose a global lock ordering so locks are always acquired in the same fixed order; then the holding-and-waiting that would force a backoff cannot form in the first place, and you avoid both the deadlock AND the livelock that the naive backoff was trying to dodge.

Starvation: always ready, never chosen

Starvation is different in kind. The starved process is not blocked on a resource cycle and it is not spinning uselessly — it is sitting in the ready queue, perfectly able to run, but the scheduler keeps picking other processes ahead of it forever. You met this idea back in the scheduling rung as scheduling starvation: with strict priority handling, a steady stream of high-priority work means a low-priority process may never reach the front of the line. The system is making progress the whole time — it just never makes progress for THIS process.

Starvation also lurks inside synchronization itself. In the classic readers-writers setup, if you let readers in whenever any reader is already reading, a continuous trickle of readers can keep the lock perpetually busy and a waiting writer never gets a turn — that exact bug even has a name, writer starvation. Notice what is shared across all these cases: the resource keeps being granted, just never to the unlucky party. Unlike deadlock, the system is NOT stuck; unlike livelock, no one is wasting cycles flailing. It is purely a fairness failure in whoever does the choosing.

Because starvation is a fairness problem, the cure is a fairness mechanism rather than a lock trick. The standard tool is aging: the longer a process waits without being chosen, the more its effective priority is quietly raised, so eventually it climbs to the top no matter how busy the high-priority crowd stays. A round-robin turn-taking scheme, where every ready process gets a guaranteed slice within a bounded number of turns, is another way to promise that nobody waits forever. The general guarantee you are reaching for has a name from the concurrency rung — bounded waiting: a hard cap on how many times others may go ahead of you before it is finally your turn.

A worked comparison: the dining philosophers, three ways

The famous dining philosophers problem — five thinkers around a table, one fork between each pair, each needs both neighbouring forks to eat — is the perfect specimen because all three diseases can grow in it depending on how you code the rules. Watching the same five philosophers fall into each trap makes the differences impossible to confuse.

1. DEADLOCK: every philosopher picks up their LEFT fork first, then reaches for the right. If all five grab left at the same moment, each holds one fork and waits on the right fork their neighbour is holding. That is a perfect circular wait — all four necessary conditions are present, nobody runs, CPU near zero. They will sit there forever.
2. LIVELOCK: to dodge that deadlock, you tell each philosopher "if you cannot get the second fork soon, put the first one down and try again." If all five act in unison — grab left, fail on right, put left down, pause, repeat — they cycle forever, hands moving constantly, never eating. Busy, polite, zero progress: a livelock.
3. STARVATION: now add a rule that whenever two philosophers compete for a fork, the younger one always wins. One particularly old philosopher, hemmed in by hungry youngsters, may be ready and reaching every time yet lose every contest — the others eat in turns while this one never does. The table as a whole is making progress; just not for them. That is starvation.

Telling them apart, and why it matters

The reason the distinction is not just vocabulary is that each disease needs a different cure, and the cure for one can be the cause of another — you saw that exactly when the release-and-retry meant to dodge deadlock created a livelock. For a deadlock, you must break one of the four conditions (prevention, avoidance, or detection-and-recovery from the earlier guides). For a livelock, you inject asymmetry — randomness or a fixed ordering — so the actors stop mirroring each other. For starvation, you add fairness — aging or bounded turn-taking — so the chooser cannot ignore anyone forever. Matching the cure to the disease is the whole skill.

One honest caveat ties the rung together. Just as most real systems take the ostrich approach to deadlock rather than running the banker's algorithm, livelock and starvation are also usually handled by pragmatic patches — a dash of randomness here, an aging counter there — not by a grand theory that proves they can never happen. And remember the deeper subtlety from the synchronization rung: none of these guarantees hold unless EVERY thread plays by the same rules. One process that grabs locks out of order, or one scheduler path that forgets to age a waiter, is enough to reopen the trap. These are properties of the whole system's discipline, not of any single clever line of code.