What's the difference between deadlock and livelock?
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 theprocesses involved in the livelockconstantly change with regard to oneanother, none progressing. Livelock isa special case of resource starvation;the general definition only statesthat a specific process is notprogressing.
A real-world example oflivelock occurs when two people meetin a narrow corridor, and each triesto be polite by moving aside to letthe other pass, but they end upswaying from side to side withoutmaking any progress because they bothrepeatedly move the same way at thesame time.
Livelock is a risk withsome algorithms that detect andrecover from deadlock. If more thanone process takes action, the deadlockdetection algorithm can be repeatedlytriggered. This can be avoided byensuring that only one process (chosenrandomly or by priority) takes action.
A thread often acts in response to the action of another thread. Ifthe other thread's action is also a response to the action of anotherthread, 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.
All the content and examples here are from
Operating Systems: Internals and Design Principles
William Stallings
8º Edition
Deadlock: A situation in which two or more processes are unable to proceed because each is waiting for one the others to do something.
For example, consider two processes, P1 and P2, and two resources, R1 and R2. Suppose that each process needs access to both resources to perform part of its function. Then it is possible to have the following situation: the OS assigns R1 to P2, and R2 to P1. Each process is waiting for one of the two resources. Neither will release the resource that it already owns until it has acquiredthe other resource and performed the function requiring both resources. The twoprocesses are deadlocked
Livelock: A situation in which two or more processes continuously change their states in response to changes in the other process(es) without doing any useful work:
Starvation: A situation in which a runnable process is overlooked indefinitely by the scheduler; although it is able to proceed, it is never chosen.
Suppose that three processes (P1, P2, P3) each require periodic access to resource R. Consider the situation in which P1 is in possession of the resource, and both P2 and P3 are delayed, waiting for that resource. When P1 exits its critical section, either P2 or P3 should be allowed access to R. Assume that the OS grants access to P3 and that P1 again requires access before P3 completes its critical section. If the OS grants access to P1 after P3 has finished, and subsequently alternately grants access to P1 and P3, then P2 may indefinitely be denied access to the resource, even though there is no deadlock situation.
APPENDIX A - TOPICS IN CONCURRENCY
Deadlock Example
If both processes set their flags to true before either has executed the while statement, then each will think that the other has entered its critical section, causing deadlock.
/* PROCESS 0 */flag[0] = true; // <- get lock 0while (flag[1]) // <- is lock 1 free? /* do nothing */; // <- no? so I wait 1 second, for example // and test again. // on more sophisticated setups we can ask // to be woken when lock 1 is freed/* critical section*/; // <- do what we need (this will never happen)flag[0] = false; // <- releasing our lock /* PROCESS 1 */flag[1] = true;while (flag[0]) /* do nothing */;/* critical section*/;flag[1] = false;Livelock Example
/* PROCESS 0 */flag[0] = true; // <- get lock 0while (flag[1]){ flag[0] = false; // <- instead of sleeping, we do useless work // needed by the lock mechanism /*delay */; // <- wait for a second flag[0] = true; // <- and restart useless work again.}/*critical section*/; // <- do what we need (this will never happen)flag[0] = false; /* PROCESS 1 */flag[1] = true;while (flag[0]) { flag[1] = false; /*delay */; flag[1] = true;}/* critical section*/;flag[1] = false;[...] consider the following sequence of events:
- P0 sets flag[0] to true.
- P1 sets flag[1] to true.
- P0 checks flag[1].
- P1 checks flag[0].
- P0 sets flag[0] to false.
- P1 sets flag[1] to false.
- P0 sets flag[0] to true.
- P1 sets flag[1] to true.
This sequence could be extended indefinitely, and neither process could enter its critical section. Strictly speaking, this is not deadlock, because any alteration in the relative speed of the two processes will break this cycle and allow one to enter the critical section. This condition is referred to as livelock. Recall that deadlock occurs when a set of processes wishes to enter their critical sections but no process can succeed. With livelock, there are possible sequences of executions that succeed, but it is also possible to describe one or more execution sequences in which no process ever enters its critical section.
Not content from the book anymore.
And what about spinlocks?
Spinlock is a technique to avoid the cost of the OS lock mechanism. Typically you would do:
try{ lock = beginLock(); doSomething();}finally{ endLock();}A problem start to appear when beginLock() costs much more than doSomething(). In very exagerated terms, imagine what happens when the beginLock costs 1 second, but doSomething cost just 1 millisecond.
In this case if you waited 1 millisecond, you would avoid being hindered for 1 second.
Why the beginLock would cost so much? If the lock is free is does not cost a lot (see https://stackoverflow.com/a/49712993/5397116), but if the lock is not free the OS will "freeze" your thread, setup a mechanism to wake you when the lock is freed, and then wake you again in the future.
All of this is much more expensive than some loops checking the lock. That is why sometimes is better to do a "spinlock".
For example:
void beginSpinLock(lock){ if(lock) loopFor(1 milliseconds); else { lock = true; return; } if(lock) loopFor(2 milliseconds); else { lock = true; return; } // important is that the part above never // cause the thread to sleep. // It is "burning" the time slice of this thread. // Hopefully for good. // some implementations fallback to OS lock mechanism // after a few tries if(lock) return beginLock(lock); else { lock = true; return; }}If your implementation is not careful, you can fall on livelock, spending all CPU on the lock mechanism.
Also see:
https://preshing.com/20120226/roll-your-own-lightweight-mutex/
Is my spin lock implementation correct and optimal?
Summary:
Deadlock: situation where nobody progress, doing nothing (sleeping, waiting etc..). CPU usage will be low;
Livelock: situation where nobody progress, but CPU is spent on the lock mechanism and not on your calculation;
Starvation: situation where one procress never gets the chance to run; by pure bad luck or by some of its property (low priority, for example);
Spinlock: technique of avoiding the cost waiting the lock to be freed.