Understanding Deadlock, Livelock and Starvation with Code Examples in Java

This Java concurrency tutorial helps you understand the 3 problems that may happen in multi-threaded applications:  deadlock, livelock and starvation. You will be able to identify each kind of problem so you can know to avoid them.

1. Understanding Deadlock

Deadlock describes a situation where two more threads are blocked because of waiting for each other forever. When deadlock occurs, the program hangs forever and the only thing you can do is to kill the program.

Let’s consider the account transaction example in this tutorial. Modify the maximum amount can be transferred from 10 to 200 in the Bank class as follows:

public static final int MAX_AMOUNT = 200;

Look at the Transaction class you see the amount is chosen randomly by this statement:

int amount = (int) (Math.random() * Bank.MAX_AMOUNT);

Now, recompile the Bank and Transaction classes, and then run the TransactionTest program. Guess what will happen?

You will see that the program runs for a few transactions and hangs forever, as shown in the following screenshot:

The program encounters a deadlock and cannot continue. Why can deadlock happen when we increase the maximum amount of money can be transferred among accounts?

Let’s analyze the code to understand why.

In the Bank class you will each account is initialized with an amount of 100. Now the maximum amount can be transferred is 200, so there will be some threads trying to transfer an amount which is greater than the account’s balance, for example:

      Thread 1 tries to transfer 150 from account 1 to account 2

      Thread 2 tries to transfer 170 from account 3 to account 1

Account 1 has only 100 in balance so thread 1 has to wait for other threads to deposit more funds to this account. Similarly, thread 2 also has to wait because account 3 doesn’t have sufficient fund. Other threads may add funds to accounts 1 and 3, but if all threads are trying to transfer an amount greater than the account’s balance, they are waiting for each other forever. Hence deadlock occurs.

That’s why you see the program quickly runs into deadlock after few transactions have been done. It hangs and you have to press Ctrl + C to terminate the program.

You can ask why the previous version of the example runs fine. It’s because the maximum account is smaller (10) than the balance (100), so all accounts have enough fund to transfer.

Another Deadlock Example:

Another common reason for deadlock problem is two or more threads attempt to acquire two locks simultaneously, but in different order. Consider the following class:

/**
 * Business.java
 * This class is used to illustrate a deadlock situtation.
 * @author www.codejava.net
 */
public class Business {

	private Object lock1 = new Object();
	private Object lock2 = new Object();

	public void foo() {
		synchronized (lock1) {
			synchronized (lock2) {
				System.out.println("foo");
			}
		}
	}

	public void bar() {
		synchronized (lock2) {
			synchronized (lock1) {
				System.out.println("bar");
			}
		}
	}
}

As you can see, both the methods foo() and bar() try to acquire two lock objects lock1 and lock2 but in different order.

And consider the following test program:

/**
 * BusinessTest1.java
 * This program tests for deadlock situtation.
 * @author www.codejava.net
 */
public class BusinessTest1 {
	public static void main(String[] args) {
		Business business = new Business();

		Thread t1 = new Thread(new Runnable() {
			public void run() {
				business.foo();
			}
		});

		t1.start();

		Thread t2 = new Thread(new Runnable() {
			public void run() {
				business.bar();
			}
		});

		t2.start();
	}
}

This program creates two threads, one executes the foo() method and another executes the bar() method on a shared instance of the Business class. But deadlock is likely never to occur because one thread can execute and exit a method very quickly so the other thread have chance to acquire the locks.

Let’s modify this test program in order to create 10 threads for executing foo() and other 10 threads for executing bar() as follows:

/**
 * BusinessTest2.java
 * This program tests for deadlock situtation.
 * @author www.codejava.net
 */
public class BusinessTest2 {
	public static void main(String[] args) {
		Business business = new Business();

		for (int i = 0; i < 10; i++) {
			new Thread(new Runnable() {
				public void run() {
					business.foo();
				}
			}).start();
		}

		for (int i = 0; i < 10; i++) {
			new Thread(new Runnable() {
				public void run() {
					business.bar();
				}
			}).start();
		}
	}
}

Run this program several times (4-10 times), you will see that sometimes the program runs fine:

But sometimes it hangs like this:

Why? It’s because deadlock happens. Let me explain how:

- Thread 1 enters foo() method and it acquires lock1. At the same time, thread 2 enters bar() method and it acquires lock2.

- Thread 1 tries to acquire lock2 which is currently held by thread 2, hence thread 1 blocks.

- Thread 2 tries to acquire lock1 which is currently held by thread 1, hence thread 2 blocks.

Both threads block each other forever, deadlock occurs and the program hangs.

So how to avoid deadlock?

Java doesn’t have anything to escape deadlock state when it occurs, so you have to design your program to avoid deadlock situation. Avoid acquiring more than one lock at a time. If not, make sure that you acquire multiple locks in consistent order. In the above example, you can avoid deadlock by synchronize two locks in the same order in both methods:

public void foo() {
	synchronized (lock1) {
		synchronized (lock2) {
			System.out.println("foo");
		}
	}
}

public void bar() {
	synchronized (lock1) {
		synchronized (lock2) {
			System.out.println("bar");
		}
	}
}

Also try to shrink the synchronized blocks as small as possible to avoid unnecessary locking on code that doesn’t need to be synchronized.

2. Understanding Livelock

Livelock describes situation where two threads are busy responding to actions of each other. They keep repeating a particular code so the program is unable to make further progress:

Thread 1 acts as a response to action of thread 2

Thread 2 acts as a response to action of thread 1

Unlike deadlock, threads are not blocked when livelock occurs. They are simply too busy responding to each other to resume work. In other words, the program runs into an infinite loop and cannot proceed further.

A Livelock Example:

Let’s see an example: a criminal kidnaps a hostage and he asks for ransom in order to release the hostage. A police agrees to give the criminal the money he wants once the hostage is released. The criminal releases the hostage only when he gets the money. Both are waiting for each other to act first, hence livelock.

Here’s the code of this example.

Criminal class:

/**
 * Criminal.java
 * This class is used to demonstrate livelock situation
 * @author www.codejava.net
 */
public class Criminal {
	private boolean hostageReleased = false;

	public void releaseHostage(Police police) {
		while (!police.isMoneySent()) {

			System.out.println("Criminal: waiting police to give ransom");

			try {
				Thread.sleep(1000);
			} catch (InterruptedException ex) {
				ex.printStackTrace();
			}
		}

		System.out.println("Criminal: released hostage");

		this.hostageReleased = true;
	}

	public boolean isHostageReleased() {
		return this.hostageReleased;
	}
}

Police class:

/**
 * Police.java
 * This class is used to demonstrate livelock situation
 * @author www.codejava.net
 */
public class Police {
	private boolean moneySent = false;

	public void giveRansom(Criminal criminal) {

		while (!criminal.isHostageReleased()) {

			System.out.println("Police: waiting criminal to release hostage");

			try {
				Thread.sleep(1000);
			} catch (InterruptedException ex) {
				ex.printStackTrace();
			}
		}

		System.out.println("Police: sent money");

		this.moneySent = true;
	}

	public boolean isMoneySent() {
		return this.moneySent;
	}

}

Test class:

/**
 * HostageRescueLivelock.java
 * This class is used to demonstrate livelock situation
 * @author www.codejava.net
 */
public class HostageRescueLivelock {
	static final Police police = new Police();

	static final Criminal criminal = new Criminal();

	public static void main(String[] args) {


		Thread t1 = new Thread(new Runnable() {
			public void run() {
				police.giveRansom(criminal);
			}
		});
		t1.start();

		Thread t2 = new Thread(new Runnable() {
			public void run() {
				criminal.releaseHostage(police);
			}
		});
		t2.start();
	}

}

Run this program and you will see that it runs into a loop which never terminates:

So how to avoid livelock? There’s no general guideline, you have to design your program to avoid livelock situation.

3. Understanding Starvation

Starvation describes a situation where a greedy thread holds a resource for a long time so other threads are blocked forever. The blocked threads are waiting to acquire the resource but they never get a chance. Thus they starve to death.

Starvation can occur due to the following reasons:

- Threads are blocked infinitely because a thread takes long time to execute some synchronized code (e.g. heavy I/O operations or infinite loop).

- A thread doesn’t get CPU’s time for execution because it has low priority as compared to other threads which have higher priority.

- Threads are waiting on a resource forever but they remain waiting forever because other threads are constantly notified instead of the hungry ones.

When a starvation situation occurs, the program is still running but doesn’t run to completion because some threads are not executed.

A Starvation Example:

Let’s see an example. Suppose we have a Worker class like this:

import java.io.*;

/**
 * Worker.java
 * This class is used to demonstrate starvation situation.
 * @author www.codejava.net
 */
public class Worker {

	public synchronized void work() {
		String name = Thread.currentThread().getName();
		String fileName = name + ".txt";

		try (
			BufferedWriter writer = new BufferedWriter(new FileWriter(fileName));
		) {
			writer.write("Thread " + name + " wrote this mesasge");
		} catch (IOException ex) {
			ex.printStackTrace();
		}

		while (true) {
			System.out.println(name + " is working");
		}
	}
}

This class has a synchronized method work() that creates a text file <thread-name>.txt and writes a message to it. Then it repeatedly prints a message:

<thread-name> is working

And the following program creates 10 threads that call the work() method on a shared instance of the Worker class:

/**
 * StarvationExample.java
 * This class is used to demonstrate starvation situation.
 * @author www.codejava.net
 */
public class StarvationExample {

	public static void main(String[] args) {
		Worker worker = new Worker();

		for (int i = 0; i < 10; i++) {
			new Thread(new Runnable() {
				public void run() {
					worker.work();
				}
			}).start();
		}
	}
}

Compile and run this program and you will see that there’s only one thread gets executed:

According to the code logic, each thread should create a text file with the name of <thread-name>.txt but you see only one gets created, e.g. thread-1.txt. That means other threads are unable to execute the work() method.

Why does this happen? It’s because the while loop runs forever so that the first executed thread never release the lock, causing other threads to wait forever.

A solution to solve this starvation problem is to make the current thread waits for a specified amount of time so other threads have chance to acquire the lock on the Worker object:

while (true) {
	System.out.println(name + " is working");

	try {
		wait(1000);
	} catch (InterruptedException ex) {
		ex.printStackTrace();
	}

}

Recompile and run this program again and you will see that all threads get executed, proven by 10 text files created and in the output:

In general, you should design your program to avoid starvation situation.

4. Conclusion

So far I have helped you identify the 3 problems which can happen in multi-threading Java programs: deadlock, livelock and starvation.  Livelock and starvation are less common than deadlock but they still can occur. To summarize, the following points help you understand the key differences of these problems:

- Deadlock:  All threads are blocked, the program hangs forever.

- Livelock: No threads blocked but they run into infinite loops. The program is still running but unable to make further progress.

- Starvation: Only one thread is running, and other threads are waiting forever.

You should be aware of these problems which can occur with multiple threads and synchronization, and design your programs to avoid them.

Other Java Concurrency Tutorials:

• How to use Threads in Java (create, start, pause, interrupt and join)
• Understanding Java Fork-Join Framework with Examples
• Java Synchronization Tutorial
• Understand Thread Pool and Executors
• Understanding Atomic Variables in Java

About the Author:

Nam Ha Minh is certified Java programmer (SCJP and SCWCD). He began programming with Java back in the days of Java 1.4 and has been passionate about it ever since. You can connect with him on Facebook and watch his Java videos on YouTube.