Livelocks

Livelock is a type of concurrency problem in which two or more processes continuously change their state in response to each other, but no process makes progress toward its goal. In a livelock, the processes remain active and runnable, yet their actions keep canceling each other out, preventing forward progress. This differs from deadlock, where processes are blocked and unable to proceed; in a livelock the processes are not blocked, only ineffective.

Livelocks commonly arise when local decisions are made to avoid contention. For example, two threads each hold one resource and need the other to proceed. To avoid deadlock, both may release or back off and then retry in a way that depends on the other’s behavior. If both keep backing off and retrying in lockstep, they never acquire both resources simultaneously, leading to perpetual mutual adaptation without progress.

Consequences of livelock include repeated work without completion, wasted CPU cycles, and reduced system throughput. It can be harder to detect than deadlock because the processes appear active.

Prevention and mitigation strategies include using strict resource acquisition ordering to prevent circular wait, implementing timeouts and aborting/restarting after a failed attempt, and employing randomized or exponential backoff to desynchronize retries. Fine-grained locking with try-lock semantics and bounded retries can also reduce livelock risk. In distributed systems, designing algorithms that guarantee progress or using transactional approaches can help avoid livelock scenarios.

See also: deadlock, starvation, concurrency.