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

User · Answer

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

User · Answer

Imagine you ve thread A and thread B  They are both synchronised on the same object and inside this block there s a global variable they are both updating   static boolean commonVar   false  Object lock   new Object        void threadAMethod                while commonVar    false            synchornized lock                                   commonVar   true                     void threadBMethod                while commonVar    true            synchornized lock                                   commonVar   false                      So  when thread A enters in the while loop and holds the lock  it does what it has to do and set the commonVar to true  Then thread B comes in  enters in the while loop and since commonVar is true now  it is be able to hold the lock  It does so  executes the synchronised block  and sets commonVar back to false  Now  thread A again gets it s new CPU window  it was about to quit the while loop but thread B has just set it back to false  so the cycle repeats over again  Threads do something  so they re not blocked in the traditional sense  but for pretty much nothing   It maybe also nice to mention that livelock does not necessarily have to appear here  I m assuming that the scheduler favours the other thread once the synchronised block finish executing  Most of the time  I think it s a hard-to-hit expectation and depends on many things happening under the hood

User · Answer

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

User · Answer

Maybe these two examples illustrate you the difference between a deadlock and a livelock     Java-Example for a deadlock   import java util concurrent locks Lock  import java util concurrent locks ReentrantLock   public class DeadlockSample        private static final Lock lock1   new ReentrantLock true       private static final Lock lock2   new ReentrantLock true        public static void main String   args            Thread threadA   new Thread DeadlockSample  doA  Thread A            Thread threadB   new Thread DeadlockSample  doB  Thread B            threadA start            threadB start               public static void doA             System out println Thread currentThread   getName         waits for lock 1            lock1 lock            System out println Thread currentThread   getName         holds lock 1             try               System out println Thread currentThread   getName         waits for lock 2                lock2 lock                System out println Thread currentThread   getName         holds lock 2                 try                   System out println Thread currentThread   getName         critical section of doA                    finally                   lock2 unlock                    System out println Thread currentThread   getName         does not hold lock 2 any longer                            finally               lock1 unlock                System out println Thread currentThread   getName         does not hold lock 1 any longer                         public static void doB             System out println Thread currentThread   getName         waits for lock 2            lock2 lock            System out println Thread currentThread   getName         holds lock 2             try               System out println Thread currentThread   getName         waits for lock 1                lock1 lock                System out println Thread currentThread   getName         holds lock 1                 try                   System out println Thread currentThread   getName         critical section of doB                    finally                   lock1 unlock                    System out println Thread currentThread   getName         does not hold lock 1 any longer                            finally               lock2 unlock                System out println Thread currentThread   getName         does not hold lock 2 any longer                         Sample output   Thread A   waits for lock 1 Thread B   waits for lock 2 Thread A   holds lock 1 Thread B   holds lock 2 Thread B   waits for lock 1 Thread A   waits for lock 2     Java-Example for a livelock    import java util concurrent locks Lock  import java util concurrent locks ReentrantLock   public class LivelockSample        private static final Lock lock1   new ReentrantLock true       private static final Lock lock2   new ReentrantLock true        public static void main String   args            Thread threadA   new Thread LivelockSample  doA   Thread A            Thread threadB   new Thread LivelockSample  doB   Thread B            threadA start            threadB start               public static void doA             try               while   lock1 tryLock                      System out println Thread currentThread   getName         waits for lock 1                    Thread sleep 100                             System out println Thread currentThread   getName         holds lock 1                 try                   while   lock2 tryLock                          System out println Thread currentThread   getName         waits for lock 2                        Thread sleep 100                                     System out println Thread currentThread   getName         holds lock 2                     try                       System out println Thread currentThread   getName         critical section of doA                        finally                       lock2 unlock                        System out println Thread currentThread   getName         does not hold lock 2 any longer                                    finally                   lock1 unlock                    System out println Thread currentThread   getName         does not hold lock 1 any longer                            catch  InterruptedException e                   can be ignored here for this sample                      public static void doB             try               while   lock2 tryLock                      System out println Thread currentThread   getName         waits for lock 2                    Thread sleep 100                             System out println Thread currentThread   getName         holds lock 2                 try                   while   lock1 tryLock                          System out println Thread currentThread   getName         waits for lock 1                        Thread sleep 100                                     System out println Thread currentThread   getName         holds lock 1                     try                       System out println Thread currentThread   getName         critical section of doB                        finally                       lock1 unlock                        System out println Thread currentThread   getName         does not hold lock 1 any longer                                    finally                   lock2 unlock                    System out println Thread currentThread   getName         does not hold lock 2 any longer                            catch  InterruptedException e                   can be ignored here for this sample                      Sample output   Thread B   holds lock 2 Thread A   holds lock 1 Thread A   waits for lock 2 Thread B   waits for lock 1 Thread B   waits for lock 1 Thread A   waits for lock 2 Thread A   waits for lock 2 Thread B   waits for lock 1 Thread B   waits for lock 1 Thread A   waits for lock 2 Thread A   waits for lock 2 Thread B   waits for lock 1       Both examples force the threads to aquire the locks in different orders  While the deadlock waits for the other lock  the livelock does not really wait - it desperately tries to acquire the lock without the chance of getting it  Every try consumes CPU cycles

User · Answer

I just planned to share some knowledge  Deadlocks A set of threads processes is deadlocked  if each thread process in the set is waiting for an event that only another process in the set can cause  The important thing here is another process is also in the same set  that means another process also blocked and no one can proceed  Deadlocks occur when processes are granted exclusive access to resources  These four conditions should be satisfied to have a deadlock   Mutual exclusion condition  Each resource is assigned to 1 process  Hold and wait condition  Process holding resources and at the same time it can ask other resources   No preemption condition  Previously granted resources can not forcibly be taken away   This condition depends on the application Circular wait condition  Must be a circular chain of 2 or more processes and each is waiting for resource held by the next member of the chain    It will happen dynamically  If we found these conditions then we can say there may be occurred a situation like a deadlock  LiveLock Each thread process is repeating the same state again and again but doesn t progress further  Something similar to a deadlock since the process can not enter the critical section  However in a deadlock  processes are wait without doing anything but in livelock  the processes are trying to proceed but processes are repeated to the same state again and again   In a deadlocked computation there is no possible execution sequence which succeeds  but In a livelocked computation  there are successful computations  but there are one or more execution sequences in which no process enters its critical section   Difference from deadlock and livelock When deadlock happens  No execution will happen  but in livelock  some executions will happen but those executions are not enough to enter the critical section

User · Answer

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 acquired the other resource and performed the function requiring both resources  The two processes 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                 lt - get lock 0 while  flag 1                  lt - is lock 1 free         do nothing              lt - 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            lt - do what we need  this will never happen  flag 0    false                lt - 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               lt - get lock 0 while  flag 1                 flag 0    false          lt - instead of sleeping  we do useless work                                needed by the lock mechanism       delay                  lt - wait for a second     flag 0    true           lt - and restart useless work again      critical section           lt - 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

User · Answer

DEADLOCK Deadlock is a condition in which a task waits indefinitely for conditions that can never be satisfied - task claims exclusive control over shared resources - task holds resources while waiting for other resources to be released - tasks cannot be forced to relinguish resources - a circular waiting condition exists  LIVELOCK Livelock conditions can arise when two or more tasks depend on and use the some resource causing a circular dependency condition where those tasks continue running forever  thus blocking all lower priority level tasks from running  these lower priority tasks experience a condition called starvation

[multithreading] What's the difference between deadlock and livelock?

Examples related to multithreading

Examples related to pthreads

Examples related to deadlock

Examples related to livelock