livelock and starvation

Two people meet head-on in a narrow hallway. Each politely steps to one side — but both pick the same side, then both switch to the other, then back again, forever mirroring each other and never passing. They are not frozen like a deadlock; they are very busy, just making no progress. That is a livelock: threads keep changing state in response to each other, actively running, yet none of them ever completes its task.

Livelock typically arises from naive deadlock-avoidance: a thread that grabs one lock, fails to get the second, releases the first and retries — if two threads do this in perfect sync, they endlessly grab-fail-release-grab-fail-release without either winning. The fix is to break the symmetry, usually with a randomised backoff (wait a random short while before retrying) so the threads stop marching in step. Starvation is a related but distinct misery: a particular thread is perpetually denied a resource it needs, not because of a cycle, but because others keep getting chosen ahead of it. A low-priority thread under a strict-priority scheduler may starve while higher-priority threads keep running; a writer may starve under a reader-preferring reader-writer lock while readers keep arriving. The cure for starvation is fairness — a scheduling or locking policy that guarantees every waiter eventually gets its turn (for example a FIFO queue of waiters).

These three failure modes form a family worth distinguishing precisely. Deadlock: threads stuck forever, doing nothing (no progress, no activity). Livelock: threads active forever, but achieving nothing (no progress, lots of activity). Starvation: the system as a whole progresses, but one unlucky thread is left out indefinitely. Naming which one you have matters because the cures differ: deadlock wants lock ordering, livelock wants randomised backoff, starvation wants a fairness guarantee.