Introduction

In this article we will discuss a common problem; "Deadlock in Java" and also discuss the necessary conditions, deadlock handling, an example that shows a deadlock and describe some points of how to overcome a deadlock.

What is deadlock?

Deadlock means a lock that has no key. Deadlock is a condition where two or more threads are blocked forever, waiting for each other to release the resource (for execution) but never get the proper resource to execute. The following figure illustrates the problem.

fig2.jpg

In this figure we have two threads (thread 1 and thread 2). Thread1 is for a printing operation and thread2 is for I/O operations. Now thread1 (the printing operation) needs the keyboard to get the command for printing some data or an image and thread2 (I/O operations) needs a printer to show the output. So, in this example  the problem exists that both needs a resource that the other needs to execute properly, but they can never reconcile the problem so the result is called a deadlock. A deadlock is a condition in which a process waits for a resource they can never get.

Deadlock requirements

The following conditions are required for a deadlock:

  1. Mutual Exclusion
  2. Hold and Wait
  3. No Preemption
  4. Circular wait

Mutual exclusion

In this condition a minimum of one resource is a non-shareable type; a resource that only one process can use at a time.

Hold and Wait

In this, a process is already holding a resource and then demands another resource that is already used by another process.

No Preemption

When one process is allocated to hold the resource until the work is not finished. So no re-allocation is allowed.

Circular wait

A process must wait for a resource held by another process that is in turn waiting for another process to release that resource. In general, there is a set of waiting processes, Pr = {Pr1, Pr2.. PrN}, such that Pr1 is waiting for a resource held by Pr2, Pr2 is waiting for a resource held by Pr3 and so on until PrN is waiting for a resource held by Pr1.

Deadlock Handling

  • Ignoring deadlock
  • Detection
  • Prevention
       1. Removing the mutual exclusion condition
       2. The hold and wait or resource holding conditions may be removed
       3. Remove no preemption condition
       4. Remove circular wait condition.
  • Avoidance
  • Livelock

Example

To proper understand the deadlock condition we must see an example of what happens in a deadlock. In this example we create a class DeadlockEx, that contains a runnable interface and use another thread pokedBack( ) for the deadlock condition to occur.

When pokedBack starts running, meaning the deadlock starts running, then both the other threads stop working since they tried to invoke pokedBack. Hence both are blocked and will never exit because
each thread is waiting for the other to exit poke (i.e both threads goes into a deadlock state).

public class DeadlockEx
 
{
    static class Group
     
{
      private final String name;
     
public Group(String name)
        {
          this.name = name;
        }
      public String getName()
        {
          return this.name;
        }
      public synchronized void poke(Group poked)
        {
          System.out.format("%s: %s" + " poked me !%n", this.name, poked.getName());
          poked.pokedBack(this);
        }
      public synchronized void pockedBack(Group poked)
       
{
          System.out.format("%s: %s" + " pocked me !%n", this.name, poked.getName());
        }
    }
  public static void main(String[] args)
 
  {
      final Group john =new Group("John");
      final Group sam =new Group("Sam");
      new Thread(new Runnable()
        {
          public void run()
         
  {
           
  john.poke(sam);
         
  }
      }).start();
      new Thread(new Runnable()
 
      {
          public void run()
     
      {
              sam.poke(john);
            }
        }).start();
    }  
}

Output

fig-1.jpg

Note: We are making a deadlocked program, so we need to press "CTRL+C" to close (end) the program.

How to overcome a deadlock

  • If you provide the method in a proper order then the problem will be resolved.
  • Usually, the simplest and most efficient way to avoid deadlock is to ensure that resources are always acquired in some well-defined order.
  • Make synchronization's scope to as small as possible.
  • Maintain a proper documentation about the order, and other locking strategy if used.
  • Avoid multiple object locking
  • Use a consistent lock order, by which if multiple locks need to be acquired then they will be acquired in a particular predefined order.