What's the difference between deadlock and livelock?

Question

Can somebody please explain with examples (of code) what is the difference between deadlock and livelock?

Answer 1

Taken from http://en.wikipedia.org/wiki/Deadlock:

In concurrent computing, a deadlock is a state in which each member of a group of actions, is waiting for some other member to release a lock

A livelock is similar to a deadlock, except that the states of the processes involved in the livelock constantly change with regard to one another, none progressing. Livelock is a special case of resource starvation; the general definition only states that a specific process is not progressing.

A real-world example of livelock occurs when two people meet in a narrow corridor, and each tries to be polite by moving aside to let the other pass, but they end up swaying from side to side without making any progress because they both repeatedly move the same way at the same time.

Livelock is a risk with some algorithms that detect and recover from deadlock. If more than one process takes action, the deadlock detection algorithm can be repeatedly triggered. This can be avoided by ensuring that only one process (chosen randomly or by priority) takes action.

Answer 2

Livelock

A thread often acts in response to the action of another thread. If the other thread's action is also a response to the action of another thread, then livelock may result.

As with deadlock, livelocked threads are unable to make further progress. However, the threads are not blocked — they are simply too busy responding to each other to resume work. 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, Alphonse moves to his right, while Gaston moves to his left. They're still blocking each other, and so on...

The main difference between livelock and deadlock is that threads are not going to be blocked, instead they will try to respond to each other continuously.

In this image, both circles (threads or processes) will try to give space to the other by moving left and right. But they can't move any further.