Livelock same as race condition?

[John Eipe]

Hi

Could someone explain Livelock? I believe both are same. After much googling found this

The definition provided by the Free On-Line Dictionary Of Computing [1] is
“Anomalous behavior due to unexpected critical dependence on the relative timing of events”.
Probably the best known result of a race condition is deadlock. A less well known problem is that of livelock.

So deadlock and livelock are results of race condition? I think livelock results when people tries to avoid deadlock. I got below a code to emulate deadlock. Please give your suggestions. Also I need a code to understand livelock.

    
//DeadLock example - i got a deadlock the 3rd time i ran this :)

class s9
{
	public static void main(String[] args)
	{
		String p = "+";
		String n = "-";
		Thread t1 = new Thread(new One(p,n));
		Thread t2 = new Thread(new Two(n,p));
		t1.start();
		t2.start();
	}
}

class One implements Runnable
{
	String p;
	String n;
	public One(String p, String n)
	{
		this.p = p;
		this.n = n;
	}
	public void run()
	{
		for(int i=0; i<100; i++)
		{
			synchronized(p)
			{
				synchronized(n)
				{
					System.out.println(p+" "+n);
				}
			}
		}
	}
}

class Two implements Runnable
{
	String p;
	String n;
	public Two(String n, String p)
	{
		this.p = p;
		this.n = n;
	}
	public void run()
	{
		for(int i=0; i<100; i++)
		{
			synchronized(n)
			{
				synchronized(p)
				{
					System.out.println(n+" "+p);
				}
			}
		}
	}
}

[Mohamed Sanaulla]

This is an interesting topic- Livelock. Never heard about it before. Thanks a lot for bringing this up I was trying to google and found a related question here (and also I found this forum thread ).

From what I understood after reading the content on the link shared-
Thread-1- Locks L1
Thread-2- Locks L2
*Thread-1- Finds that Thread-2 is locked on L2 and wants L1
*Thread-2- Finds that Thread-1 is locked on L1 and wants L2

So due to that (*) events- Both of them release their locks and keep waiting. And yeah as you have mentioned- Its to avoid the deadlock.

I would like to hear from others as well.

[John Eipe]

mohamed,

Thanks.
Could you think of any real code? I didn't find any googling.

Maybe someone could try to change my code(above) to a livelock situation!

[Jim Akmer]

@John: Deadlock occurs when 2 threads Block each other indefinitely.
I.e.
Thread A acquires a lockX.
Thread B acquires lockY.
Thread A tries to acquire lockY and blocks.
Thread B tries to acquire lockX (held by ThreadA which is blocked) and blocks.
Thread A and Thread B are blocked for ever and this is a deadlock. This is usually caused by circular dependencies.

In Livelock there is NO BLOCKING of the threads, but there is NO PROGRESS i.e. real work actually done.
I.e.
Thread A acts as a response of action of Thread B
Thread B acts as a response of action of Thread A
The 2 threads are so consumed in responding one to the other so no real processing is able to be performed.
The best analogy for livelock I have read is the following:
2 people (John and Jim) walk in a corridor in opposite directions. At a point they meet face to face blocking each other's way. John goes left to make way but Jim also goes left. Jim goes right to make way but John also goes right. John and Jim keep on moving but they do not actually go where the want to go (just keep making way for each other)

[John Eipe]

I'm trying to modify the above code(deadlock example) to simulate livelock. Are there methods to obtain and release locks on an object. (without using class ReentrantLock)?

[Mohamed Sanaulla]

John Eipe wrote:I'm trying to modify the above code(deadlock example) to simulate livelock. Are there methods to obtain and release locks on an object. (without using class ReentrantLock)?

Ah!! Even I have been trying with the ReentrantLock but sometimes end up with java.lang.IllegalMonitorStateException.

[John Eipe]

I conclude that: only ways to lock - unlock on objects is by using the Lock interface.
Here is example for LiveLock.

 
//LiveLock example - i got a livelock the 4th time i ran
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
class s9a
{
	public static void main(String[] args)
	{
		Lock p = new ReentrantLock();
		Lock n = new ReentrantLock();
		Thread t1 = new Thread(new One(p,n));
		Thread t2 = new Thread(new Two(n,p));
		t1.start();
		t2.start();
	}
}

class One implements Runnable
{
	Lock p;
	Lock n;
	public One(Lock p, Lock n)
	{
		this.p = p;
		this.n = n;
	}
	public void run()
	{
		for(int i=0; i<100; i++)
		{
			synchronized(p)
			{
				while(Thread.holdsLock(n))
				{
					try {
					p.unlock();
					wait(10);
					p.lock();
					}catch(InterruptedException e){}
				}
				synchronized(n)
				{
					System.out.println("p--n");
				}
			}
		}
	}
}

class Two implements Runnable
{
	Lock p;
	Lock n;
	public Two(Lock n, Lock p)
	{
		this.p = p;
		this.n = n;
	}
	public void run()
	{
		for(int i=0; i<100; i++)
		{
			synchronized(n)
			{
				while(Thread.holdsLock(p))
				{
					try{
					n.lock();
					wait(10);
					n.unlock();
					}catch(InterruptedException e){}
				}
				synchronized(p)
				{
					System.out.println("n--p");
				}
			}
		}
	}
}

[Jim Akmer]

A livelock. Both threads run i.e. none is blocked but no real work is done.

class s9
  {
      public static void main(String[] args)
      {
          Lock p = new ReentrantLock();
          Lock n = new ReentrantLock();
          Thread t1 = new Thread(new One(p,n));
          Thread t2 = new Thread(new Two(n,p));
          t1.start();
          t2.start();
      }
  }

  class One implements Runnable
  {
      Lock p;
      Lock n;
      public One(Lock p, Lock n)
      {
          this.p = p;
          this.n = n;
      }
      public void run()
      {
          for(int i=0; i<100; i++)
          {
            p.lock();
            try {
                System.out.println("Locked p");
                while (!n.tryLock()) {
                    System.out.println("n is locked. Try to get n");
                }
                System.out.println("Locked n");
                n.unlock();
            } finally {
                p.unlock();
            }

          }
      }
  }

  class Two implements Runnable
  {
      Lock p;
      Lock n;
      public Two(Lock n, Lock p)
      {
          this.p = p;
          this.n = n;
      }
      public void run()
      {
          for(int i=0; i<100; i++)
          {
            n.lock();
            try {
                System.out.println("Locked n");
                while(!p.tryLock())
                {
                    System.out.println("p is locked. Try to get p");
                }
                System.out.println("Locked p");
                p.unlock();


            } finally {
                n.unlock();
            }
          }
      }
  }  

[Mohamed Sanaulla]

John Eipe wrote:I conclude that: only ways to lock - unlock on objects is by using the Lock interface.
Here is example for LiveLock.

Thanks a lot for sharing the example. I was thinking of writing a blog post about Livelock. Can I use your example for the same?

[John Eipe]

Sure go ahead! But wait for other ranchers response. I could be wrong!

[John Eipe]

Jim,

Then the Livelock code I posted is a deadlock only, right?
If we use wait()/join()/sleep() what happens is blocking and when blocking comes into picture it's deadlock.

Your code is the right example. Thanks.

[Henry Wong]

John Eipe wrote:Then the Livelock code I posted is a deadlock only, right?
If we use wait()/join()/sleep() what happens is blocking and when blocking comes into picture it's deadlock.

Your code is the right example. Thanks.

Actually, Jim's code is the one that is a deadlock. It is just a deadlock, except that the second lock, for both threads are spinning. Think of Jim's example as a deadlock condition that eats up tons of processor time. There is no attempt to get out of the deadlock condition.

John, in your example, it does attempt to get out of the deadlock condition, and may actually succeed. Don't know if it consistutes as a livelock condition, but at least it is not a definitely deadlock.


Now... having said that, I really don't like the concept of "livelock" at all. IMHO, it is just a race condition that causes no real work to be done -- and this no real work done can either be caused by lock starvation or cpu starvation or some other resource issue. Why do we need a term to describe this condition, when the term is vague? The cause isn't clear. No real work getting done doesn't explain why.

Henry

[Jim Akmer]

@Henry Wong: I disagree with you.
1) When a thread holds a lock forever, other threads that will attempt to grab the lock, will block forever. All threads are blocked and this is the concept of deadlock
2) Livelock is a form of liveness failure where a thread, although is not blocked, is impossible to make any actual progress because it keeps retrying an operation that can only fail.

Assuming you agree with the above definitions, in the post, threads t1 and t2 are not blocked and keep re-trying on an operation that can only fail. Hence the behavior is consistent with the definition of livelock. It is obviously not a deadlock since no thread is blocked

Starvation is also a form of liveness failure. But at this case the thread is infinitely being denied access to resources needed to make progress in its work. Livelock is a special case of starvation

[Stephan van Hulst]

I agree with your definitions Jim, but I also agree with Henry about the fact that the concept of Livelock is vague, and arguably pointless.

With a small change to the definition of Deadlock, all these situations could fall under it.

For instance, we could say that Deadlock is what happens when a program fails to make any progress because of the existence of multiple running threads that hold resources needed by other threads, be these resources processor time, I/O resources, or object locks.

[Jim Akmer]

With a small change to the definition of Deadlock, all these situations could fall under it.

@Stephan van Hulst: Both deadlock and livelock are dead-end situations if that is what you mean. But there is a conceptual difference. The liveness characteristic. In deadlock threads are blocked. In livelock they are not blocked and are "working".
Deadlocks are always caused by programming errors (cyclic graph dependencies etc) while this is not the case for livelocks. For example in a livelock the code may be correct but there could be some timing collisions that cause livelock (or user "tampering" priorities causing starvation). E.g. 2 pc's try to send a packet in ethernet. Packets collide. With some unlucky timing this could end up in a livelock. By retrying after random delays, livelock is avoided (ethernet protocol includes backoff to avoid livelock) i.e. constant collisions. But network stack code is considered correct

[Henry Wong]

Stephan van Hulst wrote:
With a small change to the definition of Deadlock, all these situations could fall under it.

For instance, we could say that Deadlock is what happens when a program fails to make any progress because of the existence of multiple running threads that hold resources needed by other threads, be these resources processor time, I/O resources, or object locks.

Actually, here is how I define deadlock, and here is why it has to be so....


When many threads are trying to acquire or set many resources, be it synchronization locks, file locks, database locks, or even setting a state in a state machine, a deadlock is when there is a circular dependency when the threads are trying to set those resources, and hence, can't be resolved.

Why should the definition be so broad? The symptoms of deadlock, regardless of the resource, are the basically the same. The techniques in preventing the deadlock are the same. The techniques in detecting (although not the tools) are the same.

In fact, if you use certain techniques, such as lock ordering to prevent deadlocks, but only take into account synchronization locks, it won't work. You need lock ordering across all state changes that has dependencies. If you think about it, there is little difference between a thread owning a lock, and a owner state in a state machine pointing to the thread data -- in fact, that is how a lock is implemented.

Henry

[Henry Wong]

Jim Akmer wrote:
2) Livelock is a form of liveness failure where a thread, although is not blocked, is impossible to make any actual progress because it keeps retrying an operation that can only fail.

So, a live lock is a deadlock, but it isn't block? Is there really much of a difference between a thread spinning to wait for the lock, via trylock(), and the JVM putting putting the lock in a blocked state? Besides eating up processor cycles, they are both wait for resources -- except one is a block wait, while the other is a spin wait.

I don't see the point of making the distinction. In both cases, the techniques / designs to prevent the deadlock are the same. The techniques to recover from that condition are the same. etc.


Note: I know that a livelock isn't just a spinning wait deadlock -- I am just saying that the example provided is a spinning wait deadlock.

Henry

[John Eipe]

Note: I know that a livelock isn't just a spinning wait deadlock -- I am just saying that the example provided is a spinning wait deadlock.

Henry,

You seem to contradict. From your explanations it seems that livelock is indeed a spinning wait deadlock.
If it's different, could you post a example for livelock that will help me understand better. Thanks.

[Henry Wong]

John Eipe wrote:
You seem to contradict. From your explanations it seems that livelock is indeed a spinning wait deadlock.
If it's different, could you post a example for livelock that will help me understand better. Thanks.

Actually, no. In my very first post in this topic, I specifically said that the example was *not* an example of a livelock, but of a deadlock.


In my last post, I merely agreed under the ground rules that it was a live lock, in order to come to the conclusion that the distinction is pointless, which I guess is where the confusion comes in... The definition of live lock is vague, and hence, somewhat pointless If the definition of live lock was a spinning wait deadlock, then while the definition would not be vague, the distinction would be completely pointless.

Henry

[John Eipe]

Oh.. got it. Thanks Henry.

[Jim Akmer]

When many threads are trying to acquire or set many resources, be it synchronization locks, file locks, database locks, or even setting a state in a state machine, a deadlock is when there is a circular dependency when the threads are trying to set those resources, and hence, can't be resolved.

I have already given an example of livelock that has nothing to do with this i.e. packet collision in ethernet. Network protocols have build in mechanism to avoid this livelock

The techniques in preventing the deadlock are the same. The techniques in detecting (although not the tools) are the same.

As mentioned in livelock (unlike deadlock which there are these techiques you refer) the solution is something outside of the programming structure of code. Random time intervals for example.

So, a live lock is a deadlock, but it isn't block?

No it is not a deadlock. It is a dead-end.A livelock is a failure and a form of starvation. Unless you think starvation and deadlock are same concepts

Is there really much of a difference between a thread spinning to wait for the lock, via trylock(), and the JVM putting putting the lock in a blocked state?

Yes, the state is blocked in one case, and the thread is running in the other. The example of keep trying to acquire the lock is a trivial one. It could be a different operation that the thread could keep retrying and always fails. From the user's perspective in deadlock, it is visible. Nothing works. From the user's perspective, in livelock, it takes time to "see" there is a problem because the system is "working"

I don't see the point of making the distinction. In both cases, the techniques / designs to prevent the deadlock are the same. The techniques to recover from that condition are the same. etc.

You have a point that it is splitting hair, if you view it in the highest level of abstraction as failures. But as mentioned the solution for these failures is not common.

I specifically said that the example was *not* an example of a livelock, but of a deadlock. ....If the definition of live lock was a spinning wait deadlock, then while the definition would not be vague, the distinction would be completely pointless.

Spinning wait deadlock? The example is trivial, but there is no deadlock. Both threads keep retrying an operation that can only fail. No thread is blocked. It is like the common example, of the 2 guys in the corridor that both make way for each other but in the same direction

[Henry Wong]

Jim Akmer wrote:I have already given an example of livelock that has nothing to do with this i.e. packet collision in ethernet. Network protocols have build in mechanism to avoid this livelock

And I actually *loved* the example.

This example is a case of a form of a partial resource starvation, an attempt to solve that resource starvation, that if not done right, aggravates the issue to a complete resource starvation. IOWs, the code that supposed to fixed the issues aggravates the issues.


I highlighted the previous point for a reason, and ...

Jim Akmer wrote:Spinning wait deadlock? The example is trivial, but there is no deadlock. Both threads keep retrying an operation that can only fail. No thread is blocked. It is like the common example, of the 2 guys in the corridor that both make way for each other but in the same direction

This is where we disagree. There is a deadlock -- there is no chance that it will recover. And the algorithm makes no attempt to solve the problem. And all the techniques that can detect and solve the problem can be applied here. And yes, it will look different, but that is just a matter of using different tools -- hardly a case of making a separate distinction.

In the case of "2 guys in the corridor", they are attempting to solve the problem. This is more like both guys trying to move forward and expecting the other to move out of the way -- not two guys moving in the same direction. It's a deadlock condition, it just can't be detected by the JVM tools that can only detect synchronization deadlocks. Heck, many of those tools can't even detect deadlocks that use the concurrent Lock class.


And I agree, the example is simple -- maybe too simple, because it is clearly a deadlock. If it is something else, I don't see it.

Henry

[Henry Wong]

Henry Wong wrote:

Jim Akmer wrote:I have already given an example of livelock that has nothing to do with this i.e. packet collision in ethernet. Network protocols have build in mechanism to avoid this livelock

And I actually *loved* the example.

This example is a case of a form of a partial resource starvation, an attempt to solve that resource starvation, that if not done right, aggravates the issue to a complete resource starvation. IOWs, the code that supposed to fixed the issues aggravates the issues.

While I loved this example, it also proves how vague the definition of livelock is. Even in this example, there are specific terms that describes the problem -- when I run into this, when talking to a client, I use specific terms that describes the problem... such as "nak storms", "crybaby receivers", etc... I have never ever used "livelock" in such discussions.

Henry

[Jim Akmer]

This example is a case of a form of a partial resource starvation

I have already stated in my post that livelock is a special form of starvation

IOWs, the code that supposed to fixed the issues aggravates the issues.

What code are you talking about? For this example the livelock is solved via exponential backoff and random waits. There is no problem with the code or logic. Transmitter1 senses the network concurrently with Transmitter2. They both sense network free. Both transmit packet and packets collide. If they transmit again or waiting for the same interval livelock occurs and there is the problem.

And the algorithm makes no attempt to solve the problem

Algorithms do not attempt to get out of liveness failures. I thought you said tools exist for this.....

In the case of "2 guys in the corridor", they are attempting to solve the problem. This is more like both guys trying to move forward and expecting the other to move out of the way

They do not attempt to solve anything. They move randomly and happen to move in the same direction

And I agree, the example is simple -- maybe too simple, because it is clearly a deadlock. If it is something else, I don't see it.

You have not said whether you agree or not with my earlier definitions. Because the post is consistent with them.
In any case if the code was modified as follows is it more clear to you?

    class s9  
    {  
        public static void main(String[] args)  
        {  
            Lock p = new ReentrantLock();  
            Lock n = new ReentrantLock();  
            Thread t1 = new Thread(new One(p,n),300);  
            Thread t2 = new Thread(new Two(n,p),300);  
            t1.start();  
           t2.start();  
        }  
    }  
     
    class One implements Runnable  
    {  
        Lock p;  
        Lock n;  
		int timeout;
        public One(Lock p, Lock n,int timeout)  
        {  
            this.p = p;  
            this.n = n;  
			this.timeout = timeout;
        }  
        public void run()  
        {  
            for(int i=0; i<100; i++)  
            {  
               p.lock();  
              try {  
                   System.out.println("Locked p");  
                   while (!n.tryLock()) {  
                       System.out.println("n is locked Try to get n");  
					   synchronized(this)
					   {
					      try{
							wait(timeout);
							}
							catch(InterruptedException e){}
					   }
                   }  
                   System.out.println("Locked n");  
                   n.unlock();  
               } finally {  
                   p.unlock();  
               }  
     
             }  
         }  
     }  
     
     class Two implements Runnable  
     {  
        Lock p;  
        Lock n;  
        public Two(Lock n, Lock p,int timeout)  
        {  
            this.p = p;  
            this.n = n;  
			this.timeout = timeout;
        }  
        public void run()  
        {  
            for(int i=0; i<100; i++)  
            {  
				n.lock();  
	            try {  
                 System.out.println("Locked n");  
                   while(!p.tryLock())  
                   {  
                       System.out.println("p is locked Try to get p");  
					   synchronized(this)
					   {
					      try{
							wait(timeout);
							}
							catch(InterruptedException e){}
					   }
                   }  
                   System.out.println("Locked p");  
                   p.unlock();  
     
     
               } finally {  
                   n.unlock();  
               }  
             }  
         }  
     }    

how vague the definition of livelock is

Why vague? Unless you think that deadlock definition, which opposite, is also vague

when talking to a client, I use specific terms that describes the problem... such as "nak storms", "crybaby receivers", etc... I have never ever used "livelock" in such discussions.

Why? Have you used deadlock, starvation or race condition to a client? Unless he was also an engineer

[Henry Wong]

At this point, I think it is best to just agree to disagree -- as this debate seems to be going in circles. Or maybe into a live lock.

Henry

[Jim Akmer]

At this point, I think it is best to just agree to disagree -- as this debate seems to be going in circles. Or maybe into a live lock.

See! Now you saw livelock!