Livelock and Deadlock In Java

The following article talks about the livelock and deadlock states in java, how they occur and what can be done to avoid them.

Livelock

Livelock in Java is a recursive condition where two or more threads keep repeating a particular piece of code.

Livelock occurs when one thread keeps responding to the other thread and the other thread is also doing the same.

To break it down, we can summarize it with the following points:

  • A thread is acting in response to the action of another thread and the other thread is also acting in response to the prior thread then livelock may occur.
  • Livelock threads are unable to progress any further.
  • The threads are not blocked; they are simply busy responding to each other.

Livelock is also known as a special case of resource starvation

Let us understand the concept by relating it with a real world situation. Consider two cars on opposite sides of a narrow bridge. Only one car is able to pass the bridge at a time. Drivers of both cars are very polite and are waiting for the other to pass through the bridge first. They both respond to each other by honking and letting them know that they want the other to pass first. However, both do not cross the bridge and keep honking at each other. This kind of situation is similar to livelock.




Now lets try out this real case scenario with some coding:

Class for first car waiting to pass the bridge:

public class Car1 {
    private boolean honking = true;
    public void passBridge(Car2 car2) {
        while (car2.hasPassedBridge()) {
            System.out.println("Car1 waiting to pass the bridge");
 
            try {
                Thread.sleep(1000);
            } catch (InterruptedException ex) {
                ex.printStackTrace();
            }
        }
 
        System.out.println("Passed bridge");
 
        this.honking= false;
    }
 
    public boolean hasPassedBridge() {
        return this.honking;
    }
}

 

Class for second car waiting to pass the bridge:

public class Car2 {
    private boolean honking = true;
 
    public void passBridge(Car1 car1) {
 
        while (car1.hasPassedBridge()) {
 
            System.out.println("Car 2 is waiting to pass the bridge!");
 
            try {
                Thread.sleep(1000);
            } catch (InterruptedException ex) {
                ex.printStackTrace();
            }
        }
 
        System.out.println("Car 2 has passed the bridge!");
 
        this.honking = false;
    }
 
    public boolean hasPassedBridge() {
        return this.honking;
    }
 }

 

Main test class:

public class BridgeCheck {
   static final Car2 car2 = new Car2();
   static final Car1 car1 = new Car1();
   public static void main(String[] args) {
        Thread t1 = new Thread(new Runnable() {
            public void run() {
                car2.passBridge(car1);
            }
        });
        t1.start();
 
        Thread t2 = new Thread(new Runnable() {
            public void run() {
                car1.passBridge(car2);
            }
        });
        t2.start();
    }
}

 

Output:

This results in a non-terminating loop.

 

Deadlock

Deadlock is a bit different than livelock. Deadlock is a state in which each member is waiting for some other member to release a lock.

There maybe situations when a thread is waiting for an object lock, that is acquired by another thread and second thread is waiting for an object lock that is acquired by first thread. Since, both threads are waiting for each other to release the lock, the condition is called deadlock.

Figure: Deadlock State

 

Let us look at a scenario where deadlock has occurred:

public class DeadlockExample{
 
private static String A = "Something A";
private static String B = "Something B";
 
    public void someFunction(){
        synchronized(A){//may deadlock here
            synchronized(B){
                // function does some work here
            }
        }
    }
 
    public void someOtherFunction(){
        synchronized(B){//may deadlock here
            synchronized(A){
                // the function does something here
            }   
        }
    }
}

Consider two threads T1 and T2, T1 acquires A and waits on B to complete its function. However, T2 acquires B and waits on A to complete its own function. Here T1 and T2 are waiting on resources that are being locked by other thread. Hence, this is a deadlock scenario.

 

Avoiding Deadlocks all together:

  • First suggestion would be to avoid using multi-threads all together but that may not be practical in many situations. So this solution is not very wise.
  • Analyze and make sure there are no locks while resources are accessed beforehand.
  • In our coding example above, to avoid a deadlock, simply manage the order by which the resources are accessed (The order by which A and B is accessed).
  • Avoid holding several locks at once and in case you have to then always acquire the locks in the same order.
  • Avoid executing foreign code while holding a lock.
  • Try to use interruptable locks so that even when a deadlock is faced, the locks can be interrupted and the process can be carried out without any problem.

 

Leave a Reply

avatar