Deadlock and Livelock - Java Training School

Deadlock

Deadlock in java is a situation where two threads are holding two different locks on two different objects and waiting for each other to release their respective locks so that they can acquire it without releasing their own locks. Now, this situation results in a forever waiting. Such a situation is known as deadlock. Let’s understand it from the below diagram.

In the above diagram, Thread1 has a lock on object1, and Thread2 has a lock on object2. Now, Thread1 wants another lock on object2 while keeping its lock on object1, whereas Thread2 wants lock on object1 while keeping its lock on object2. This results in a deadlock.

A real world example can be understood by a scene in a Bollywood movie Andaj Apna Apna. In that scene, Amir and Salman both wants to enter a bus at the same time but they get stuck on the bus entry door. None of them is ready to leave their position but want to enter the bus and thus bocking each other. None of them could make a progress resulting in a deadlock.

Those who haven’t watched Andaj Apna Apna, they can understand this situation when two lovebirds want to end their telephone call but nobody actually wants to do it. One person is saying to the other – you end the call. Another person is saying – you end the call. Thus deadlock.

Deadlock example

package may_core_java_project;

public class DeadlockExample {
	
	public static void main(String[] args) {
		
		String obj1 = "abc";
		String obj2 = "xyz";

		Thread t1 = new Thread("Thread-1") {
			public void run() {
				synchronized (obj1) {
					System.out.println(Thread.currentThread().getName() + " has acquired lock on obj1");
					try {
						Thread.sleep(1000);
					} catch (Exception e) {
						e.printStackTrace();
					}
					System.out.println(Thread.currentThread().getName() + " waiting for lock on obj2");
					synchronized (obj2) {
						System.out.println(Thread.currentThread().getName() + " has acquired lock on obj2");
						System.out.println(Thread.currentThread().getName() + " task complete");
					}
				}
			}
		};
		
		Thread t2 = new Thread("Thread-2") {
			public void run() {
				synchronized (obj2) {
					System.out.println(Thread.currentThread().getName() + " has acquired lock on obj2");
					try {
						Thread.sleep(1000);
					} catch (Exception e) {
						e.printStackTrace();
					}
					System.out.println(Thread.currentThread().getName() + " waiting for lock on obj1");
					synchronized (obj1) {
						System.out.println(Thread.currentThread().getName() + " has acquired lock on obj1");
						System.out.println(Thread.currentThread().getName() + " task complete");
					}
				}
			}
		};
		
		t1.start();
		t2.start();
	}
}

Output:

In the above example, the program will keep on running due to deadlock.

Fixing the DeadLock

To fix this deadlock situation, we need to change the order for thread t2 in which lock is acquired on obj1 and obj2 as shown below

package may_core_java_project;

public class DeadlockExample {
	
	public static void main(String[] args) {
		
		String obj1 = "abc";
		String obj2 = "xyz";

		Thread t1 = new Thread("Thread-1") {
			public void run() {
				synchronized (obj1) {
					System.out.println(Thread.currentThread().getName() + " has acquired lock on obj1");
					try {
						Thread.sleep(1000);
					} catch (Exception e) {
						e.printStackTrace();
					}
					System.out.println(Thread.currentThread().getName() + " waiting for lock on obj2");
					synchronized (obj2) {
						System.out.println(Thread.currentThread().getName() + " has acquired lock on obj2");
						System.out.println(Thread.currentThread().getName() + " task complete");
					}
				}
			}
		};
		
		Thread t2 = new Thread("Thread-2") {
			public void run() {
				synchronized (obj1) {
					System.out.println(Thread.currentThread().getName() + " has acquired lock on obj1");
					try {
						Thread.sleep(1000);
					} catch (Exception e) {
						e.printStackTrace();
					}
					System.out.println(Thread.currentThread().getName() + " waiting for lock on obj2");
					synchronized (obj2) {
						System.out.println(Thread.currentThread().getName() + " has acquired lock on obj2");
						System.out.println(Thread.currentThread().getName() + " task complete");
					}
				}
			}
		};
		
		t1.start();
		t2.start();
	}
}

Output :

Livelock

Livelock is similar to deadlock, except that fact that the states of threads change constantly with respect to each other in a non progressive manner.

Usually, Livelock happens when there are some actions taken to solve a deadlock problem, and they cause this never ending corrective action which doesn’t allow the system making progress.

A real world example is when two people come in front of each other on the way. In order to pass each other, one person moves to his right. At the same time, another person moves in the same side. Then both of them move to the other side thus again blocking each other way. So, this way they change their position constantly but still blocking each others way.

Livelock Java Example

In the below example, there are two travellers Arjun and Shakar who try to enter a bus at the same time. But they feel they are blocking each other’s way, so they move aside and make way for the other in the same way – pahle aap, pahle aap. They keep on doing it and get into a livelock

Bus.java

package com.sks;

public class Bus {
	
	public String personEnteringTheBus;
	
}

Traveller.java

package com.sks;

public class Traveller {

	private String name;
	// Initial state of the traveller is blocked
	private boolean isBlocked = true;
	private Bus bus;

	public synchronized void moveInsideTheBus(Traveller fellowTvlr) throws InterruptedException {
		// If the traveller feels blocked, he will make way for his fellow traveller
		if (isBlocked) {
			makeWayForFellowTraveller(fellowTvlr);
		}
		// If he is not blocked, his name would be the person to enter the bus
		else {
			bus.personEnteringTheBus = this.name;
			System.out.println(this.name + " moved inside.");
		}
	}

	private void makeWayForFellowTraveller(Traveller fellowTvlr) throws InterruptedException {
		while (isBlocked) {
			bus.personEnteringTheBus = fellowTvlr.name;
			System.out
					.println(Thread.currentThread().getName() + ":" + this.name + " making way for " + fellowTvlr.name);

			if (bus.personEnteringTheBus.equals(this.name)) {
				isBlocked = false;
				break;
			}
			wait(1000);
		}
	}

	public Traveller(String name, Bus bus) {
		super();
		this.name = name;
		this.bus = bus;
	}

	public boolean isBlocked() {
		return isBlocked;
	}

	public void setBlocked(boolean isBlocked) {
		this.isBlocked = isBlocked;
	}	
}

LivelockExample.java

package com.sks;

public class LivelockExample {

	public static void main(String[] args) {

		Bus bus = new Bus();

		final Traveller tvlr1 = new Traveller("Arjun", bus);
		final Traveller tvlr2 = new Traveller("Shankar", bus);

		Thread t1 = new Thread(new Runnable() {
			public void run() {
				try {
					tvlr1.moveInsideTheBus(tvlr2);
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
			}
		});

		Thread t2 = new Thread(new Runnable() {
			public void run() {
				try {
					tvlr2.moveInsideTheBus(tvlr1);
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
			}
		});

		t1.start();
		t2.start();
	}
}

The output keeps on going until we stop the application. That means even though it is continuously giving the output, it has got stuck in a live lock situation.

That’s enough. Let’s not get into a deadlock ourselves but enjoy a cup of tea