Two failures that are not deadlock
In a deadlock threads are blocked and idle. Livelock and starvation are different: threads keep running, yet useful work stalls.
Livelock
In a livelock, threads actively change state in response to each other but make no progress. The classic picture is two people in a hallway who keep stepping the same direction to let the other pass. Each is polite, each keeps moving, and neither gets through.
- Often caused by retry and back off logic that is too symmetric.
- Fix it by adding randomized back off so the symmetry breaks.
Starvation
In starvation, a thread is perpetually denied a resource because others keep winning the contest. A low priority thread may never run if higher priority threads are always ready, or an unfair lock may keep handing the same waiter to the back of the line.
- Use fair scheduling or fair locks that grant access in arrival order.
- Avoid unbounded priority gaps.
Key idea
Livelock is busy non progress from symmetric reactions; starvation is permanent denial from unfair contention. Randomness cures the first, fairness cures the second.