Deadlock, Livelock, and Starvation in Java

1. Introduction

In this article, we'll discuss the three most familiar problems associated with the liveness of a program in multi-thread environments: livelock, deadlock, and starvation.

2. Liveness and Thread Problems

Liveness refers to the capacity of a program to keep running without stopping. Liveness problems make the application unresponsive or stuck at some point.

Threads can perform tasks execution independently of each other and usually requires coordination. That coordination indicates that tasks submitted to threads should be executed synchronously and in order. Here are some examples of coordination between threads in Java:

• Block a part of the code to be executed by a single thread at a time using the Lock API or the synchronized keyword.
• Make threads wait for each other to execute subsequent tasks using the CyclicBarrier class.
• Keep memory consistency of data using atomic variables, for example, the AtomicInteger class.
• Use concurrent collections to avoid synchronization and concurrent modification problems.

Even handling coordination between threads with the mentioned APIs, some issues that affect liveness might still happen at runtime. The three most common liveness issues are deadlock, livelock, and starvation. Those problems are usually unpredictable and hard to debug.

3. What is a Deadlock

Deadlock happens when two or more threads are blocked by each other. One thread is waiting for the second thread to release a task. At the same time, the second thread is waiting for the first thread to release that same task. The situation where two threads are perpetually waiting for each other is called deadlock.

3.1. Example of a Deadlock in Java

Presume two users interacting with a system to save and print files. We can generate a new thread for every arriving user to make it faster using. Let's illustrate the described scenario using the image below:

The User 1 prints a file and then wants to save that file using the Saver service blocked by User 2. At the same time, the User 2 saves a file and then wants to print that file using Printer blocked by User 1

That condition, known as deadlock, shows that both services are blocked by each other. That situation keeps both services blocked, which causes both threads to hang indefinitely, and the program to stop responding.

Let's exercise the situation described with a Java code example. First, let's define the Printer and Saver services:

1public class PrinterService {
2}

1public class SaverService {
2}

Secondly, let's create a class to represent the User:

 1public class User {
 2  public void printAndSave(PrinterService printer, SaverService saver) {
 3    synchronized(printer) {  
 4      System.out.println("File Printed");
 5      synchronized(saver) {
 6        System.out.println("File Saved");
 7      }
 8    }
 9  }
10
11  public void saveAndPrint(PrinterService printer, SaverService saver) {
12    synchronized(saver) {
13      System.out.println("File Saved");
14      synchronized(printer) {
15        System.out.println("File Printed");
16      }
17    }
18  }
19}

The User can execute two actions, _printAndSave_and saveAndPrint. The _printAndSave_method locks the PrinterService using the sychrnonized block, then try to acquire the lock for the SaverService. The saveAndPrint method does the opposite: it first obtains the lock for SaverService, then try to lock PrinterService.

Finally, let's define the main method in a separate class to create and execute a thread for each user:

 1public class DeadLockExample {
 2  public static void main(String[] args) {
 3      User user1 = new User();
 4      User user2 = new User();
 5      PrinterService printer = new PrinterService();
 6      SaverService saver = new SaverService();
 7
 8      ExecutorService service = null;
 9      try {
10        service = Executors.newScheduledThreadPool(2);
11        service.submit(() -> user1.printAndSave(printer, saver));
12        service.submit(() -> user2.saveAndPrint(printer, saver)); 
13      } finally {
14        if (service != null) service.shutdown();
15    }
16  }
17}

First, we define user1 and user2 users along with the printer and saver services. Then, we create an instance of ExecutorService that stores two threads. After that, we submit one thread for user1's printAndSave and another for user2's saveAndPrint simultaneously. The finally block closes the ExecutorService after its execution finishes.

Running the main method, we should get the following output:

1File Saved
2File Printed

The user1 could save the file but could not print it. On the other hand, the user2 could print the file but couldn't save it. The program hangs indefinitely because the user1 and user2 variables are deadlocked by each other.

3.2. How to Avoid a Deadlock

One common strategy to avoid deadlocks is to create order between tasks execution. For instance, we can avoid the deadlock situation described above if the application states that each user in our program must always save the file before printing it. Thus, if user1 acquires the lock first, the user2 should wait for the entire user1's execution after trying to acquire any lock.

Another strategy is to set a timed attempt to acquire a lock. Timed lock attempts use a timeout window to let the program's threads obtain a particular lock. If one thread exceeds that timeout, that thread will execute a different set of tasks or wait. Timed lock attempts can be implemented in java using the tryLock method from the Lock interface.

4. What is a Livelock

Like a deadlock, livelocks occur when two or more threads are virtually blocked forever. The difference is that they are not waiting for each to complete, like in a deadlock. In a livelock, the threads involved are trying to acquire a set of locks, can't complete it, and restart part of the process.

Imagine the same deadlock scenario described earlier. The user1 locks the printer service, and user2 locks the saver service. The user1 wants to save a file after printing, whereas user2 wants to print a file after saving it.

One way to avoid the deadlock situation is by releasing their locks so that they can complete their tasks. If both users keep releasing their locks to acquire another, trying to avoid a deadlock, they might stay blocked forever.

While user1 release its lock to acquire another, user2 repeats that same process. If user1 and user2 threads continue doing that forever, then we have a livelock. A livelock is typically a result of two threads trying to resolve a deadlock

4.1. How to Avoid Livelocks

Livelocks are very difficult to spot in real applications because, in this kind of situation, threads seem to be responding correctly, but in fact, they are in an infinite loop-like state. There's no easy and deterministic way to detect and avoid livelocks.

5. What is Thread Starvation

Starvation occurs when one thread is denied access to a shared resource or synchronized block indefinitely. Using the same example, it is like user1 is saving many files in a row and thus blocking that piece of code in the synchronized block so that user2 never gets a chance to use the SaverService. The user2 thread continues to run without getting any resources and waits indefinitely while user1 saves all the files.

5.1. Example of Thread Stavartion in Java

Suppose that one user takes about 10 seconds to save a file. Let's exercise thread starvation by creating the method saveFile in the User class:

 1public void saveFile(SaverService saver, String user)  {
 2    synchronized (saver) {
 3      try {
 4        System.out.println("File Saved for user " + user);
 5        Thread.sleep(10000);
 6      } catch (InterruptedException ex) {
 7
 8      }
 9  }
10}

The saveFile method locks the SaverService and takes 10 seconds (Thread.sleep(10000) method call) to save a file.

Running the main method defined previously, we should get the following output immediately:

1File Saved for user user1

But the program didn't finish yet, because user2 also needs to save a file. After 10 seconds, the program outputs:

1File Saved for user user1
2File Saved for user user2
3
4Process finished with exit code 0

In that example, user1 took 10 seconds to release the lock. If user1 keeps accepting new files to save before user2 acquires the lock, then user_2 might wait forever for user1 to release it. That describes the typical thread starvation scenario.

5.2. How to Avoid Thread Starvation

To avoid starvations, we can implement a fairness policy for threads to acquire locks. Fairness is the idea that each thread should allow other threads to access a resource using predefined rules, like how many times one thread acquired a lock or how much time a thread is holding it. In Java, we can use the ReetrantLock(boolean fair) constructor implementation of the Lock Interface to implement an out-of-the-box fairness strategy.

6. Conclusion

In this post, we've seen how deadlock, livelock, and starvation affect the application's liveness, along with strategies to avoid those three problems.