Tuesday, February 28, 2017

Linux: Difference between livelocks and deadlocks

Everyone knows what a deadlock [2] is!

Wait for graph as described on wikipedia
Defn Deadlock:
Two or more entities vying to get two or more locks in out of order. This leads to each entity waiting for the other entity to release the lock. Since no one releases their held lock the system is stuck and there is no easy recovery.

What is a livelock then?


Livelock is a case which is similar to a deadlock. In this case two or more entities are competing for a set of resources. However, they are not blocked or "holding" the locks forever. They keep releasing hoping the other entity will get done and release "all the required" resources to them. However, both the entities waiting on the resources just keep doing this.

A nice analogy for a live lock is described here [1]:
"This is comparable to two people attempting to pass each other in a corridor: Alphonse moves to his left to let Gaston pass, while Gaston moves to his right to let Alphonse pass. Seeing that they are still blocking each other, Alphone moves to his right, while Gaston moves to his left. They're still blocking each other, so..."

How do we fix a livelock condition? The solution to livelocks is same as that for deadlocks, get the resources in the same order at all the entities vying to get control of the resources.

References
[1] Live locks on the Linux kernel mailing list, https://lkml.org/lkml/2007/3/6/189
[2] Make Linux Deadlocks, http://www.makelinux.net/books/lkd2/ch08lev1sec3