DEV Community

loading...

Deadlock in Java: A tale of two cooks

Naveen
Software Engineer, Learner by experiments, Finds a kick out of solving problems, Blogger, Chess player, CallOfDuty Player, Loves biking
Updated on ・3 min read

Deadlock is a scenario where, at a minimum, two threads block each other holding resources that each other require to complete. Resources are stateful and these resources are shared between the threads. When these conditions, there is a probability of deadlock. Key phrases to note here are "shared stateful resources" and "multiple threads".

I am feeling pretty hungry now. Keeping aside the definition of deadlock, let us have some food. Chef Tom and Chef Jerry had been kitchen for a while now to prepare two different dishes for me. I will be right back in a minute after checking with my Chefs.
(... after a while)
It appears that the effect of thinking about "Deadlock" has its influence in the kitchen. Neither Chef Tom nor Chef Jerry had completed their dishes. They were waiting for ingredients common between them to use. In other words, the set of ingredients were to be shared by the cooks in the kitchen. Also, these ingredients have a state of their own.

Presented below is a coded representation of the deadlock that occurred in the kitchen. Entities involved here are Ingredient, ChefTom, ChefJerry. To simplify, the set of ingredients is limited to just two - "salt" and "pepper". These ingredients are to be shared between the chefs.

Class implementation for "Ingredient".

class Ingredient {
  private String name;
  Ingredient(String ingredientName) { name = ingredientName;}
  @Override public String toString() {
    return this.name;
  }
}
Enter fullscreen mode Exit fullscreen mode

Class implementation for Chef Tom. Notice the order application of ingredient. Tom applies salt, pepper and salt again.

class CookTom implements Runnable {

  ...
  @Override
  public void run() {
    Ingredient salt = store.get("salt");
    Ingredient pepper = store.get("pepper");
    synchronized(salt) {
      ...
      synchronized(pepper){...}
      ...
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

Class implementation for Chef Jerry. Notice the order application of ingredient. Tom applies pepper, salt and pepper again.

class CookJerry implements Runnable {

  @Override
  public void run() {
    ...
    synchronized(pepper) {
      ...
      synchronized(salt){...}
      ...
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

Though it appears perfectly valid order adding ingredients, there is a probability of running into deadlock. How? Resources are shared. So, Tom holds on to Salt but needs Pepper. Tom does not yield or give away salt immediately after adding salt the first time. Likewise, Jerry does not give away pepper immediately after using it. This results in a deadlock.

Here is the complete code.

import static java.lang.System.out;

import java.util.HashMap;
import java.util.Map;

class DeadLock {
  public static void main(String [] args) {
    log("Demo: Deadlock");
    Ingredient salt = new Ingredient("salt");
    Ingredient pepper = new Ingredient("pepper");
    Map<String, Ingredient> store = new HashMap<String, Ingredient>();
    store.put(salt.toString(), salt);
    store.put(pepper.toString(), pepper);
    CookTom tom = new CookTom(store);
    CookJerry jerry = new CookJerry(store);
    Thread dish1 = new Thread(tom);
    Thread dish2 = new Thread(jerry);
    dish1.start();
    dish2.start();
  }

  static void log(String message) {
    out.printf("%s \n", new Object[]{message});
  }
  static void waitForAWhile(){
    try {
      Thread.sleep(1000 * 3);
    } catch (InterruptedException e) {}
  }
}
class Ingredient {
  private String name;
  Ingredient(String ingredientName) { name = ingredientName;}
  @Override public String toString() {
    return this.name;
  }
}

class CookTom implements Runnable {

  private final Map<String, Ingredient> store;
  CookTom(Map<String, Ingredient> ingredientStore) { store = ingredientStore;}

  @Override
  public void run() {
    Ingredient salt = store.get("salt");
    Ingredient pepper = store.get("pepper");
    synchronized(salt) {
      DeadLock.log(this.toString() + " [has] adds " + salt);
      DeadLock.waitForAWhile();
      DeadLock.log(this.toString() + " [needs] " + pepper);
      synchronized(pepper){
        DeadLock.log(this.toString() + "[has] adds" + pepper);
      }
      DeadLock.log(this.toString() + " [has] adds " + salt);
    }
  }

  @Override
  public String toString() {
    return "Cook Tom  ";
  }
}

class CookJerry implements Runnable {

  private final Map<String, Ingredient> store;
  CookJerry(Map<String, Ingredient> ingredientStore) { store = ingredientStore;}

  @Override
  public void run() {
    Ingredient salt = store.get("salt");
    Ingredient pepper = store.get("pepper");
    synchronized(pepper) {
      DeadLock.log(this.toString() + " [has] adds " + pepper);
      DeadLock.log(this.toString() + " [needs] " + salt);
      synchronized(salt){
        DeadLock.log(this.toString() + "[has] adds" + salt);
      }
      DeadLock.log(this.toString() + " [has] adds " + pepper);      
    }
  }
  @Override
  public String toString() {
    return "Cook Jerry";
  }
}
Enter fullscreen mode Exit fullscreen mode

JVM 8 threaddumps detects the deadlock as well. In a linux machine, find the process id running the above java code and use jstask to threaddump. Snippet of threaddump reporting deadlock is given below.



> jstack $pid
...
Java stack information for the threads listed above:
===================================================
"Thread-1":
  at dev.mercury.CookJerry.run(Deadlock.java:78)
  - waiting to lock <0x00000007199b0d00> (a dev.mercury.Ingredient)
  - locked <0x00000007199b0d40> (a dev.mercury.Ingredient)
  at java.lang.Thread.run(Thread.java:748)
"Thread-0":
  at dev.mercury.CookTom.run(Deadlock.java:54)
  - waiting to lock <0x00000007199b0d40> (a dev.mercury.Ingredient)
  - locked <0x00000007199b0d00> (a dev.mercury.Ingredient)
  at java.lang.Thread.run(Thread.java:748)

Found 1 deadlock.

`
Enter fullscreen mode Exit fullscreen mode

Discussion (0)