Livelock in Operating Systems
We spend a lot of time talking about deadlocks, where processes completely freeze and stop executing. But there is a closely related, equally frustrating problem where processes keep executing, yet still fail to get any work done.
This is called a livelock.
What is Livelock?
A livelock is a situation where two or more processes continuously change their states in response to changes in the other processes. Unlike a deadlock, the processes are not blocked or sleeping. They are awake, actively running, and constantly doing things.
The problem is that their actions perfectly counter each other, trapping them in an endless loop of state changes that never results in any actual progress.
How Livelock Occurs
Livelocks almost always occur as an unintended side effect of algorithms designed to PREVENT deadlocks. When a system detects a potential conflict, it tells the involved processes to back off, drop their resources, and try again.
If the retry mechanism is completely deterministic (meaning it behaves exactly the same way every time), the processes might back off simultaneously, wait the exact same amount of time, and try again simultaneously—resulting in another collision. They get trapped in an endless cycle of colliding, backing off, and retrying.
Example of Livelock
The most intuitive example of a livelock happens in real life all the time.
In an operating system context, a classic example involves network communication:
1. Two network nodes try to send a packet on a shared line at the same time.
2. A collision occurs.
3. Both nodes detect the collision and execute a recovery algorithm: "Wait 10 milliseconds, then resend."
4. Both nodes wait exactly 10ms.
5. Both nodes resend exactly at the same time.
6. Another collision occurs. The cycle repeats forever.How do we fix this? By introducing randomness. If the recovery algorithm says "Wait a RANDOM amount of time between 1ms and 20ms," one node will almost certainly retry before the other, breaking the synchronized loop.
Effects of Livelock
Livelocks can actually be worse for system health than deadlocks because of how they interact with the CPU.
- CPU Waste: A deadlocked process goes to sleep. It consumes zero CPU cycles. A livelocked process is actively running, burning through CPU cycles just to change its state back and forth. This starves other healthy processes of CPU time.
- No Progress: Just like a deadlock, the tasks assigned to the livelocked processes are never completed.
- Hard to Detect: Because the processes are still changing state and using the CPU, traditional deadlock detection algorithms (like cycle detection in graphs) will completely miss them. To the OS, they look like processes doing normal, heavy work.
Deadlock vs Livelock
| Feature | Deadlock | Livelock |
|---|---|---|
| Process State | Blocked / Sleeping | Active / Running |
| State Changes | None. Everything is frozen. | Constant. Processes continuously change state. |
| CPU Utilization | Zero (processes are asleep). | High (processes are spinning in a loop). |
| Root Cause | Holding resources while waiting for others. | Poorly designed collision avoidance/retry logic. |
| Real-World Analogy | Two cars stuck at a 4-way stop, neither willing to move. | Two people stepping side-to-side in a hallway. |
Summary
Livelock is the active cousin of deadlock. Instead of freezing up, processes trapped in a livelock burn energy running in circles.
It is a harsh reminder that simply forcing processes to "back off and try again" when they encounter a conflict is not enough. Without randomness or a central coordinator, deterministic retry loops will just recreate the exact same conflict over and over.
Sort the Concepts
Classify the following scenarios as either a Deadlock or a Livelock.