What is Deadlock?

Deadlock is a programming condition which is found in a multi-threaded environment.
Probability of occurrence of deadlock is the most when more than one thread try to access the same set of resources or work on same objects at the same time.
A couple of scenarios where deadlock would surely occur are detailed below.
Sample programs showing both these scenarios to create deadlock are also given.

Scenario 1 :
One thread gains access to a resource or object and other thread(s) keep on waiting for that resource or object.
Till the time the thread does not release the resource, all the threads are stuck.

Now if the thread holding the resource hangs up or dies, the application goes into a deadlock state since all the threads are waiting for the resource to be released which is engaged for ever.

This scenario occurs due to application failure and not due to programmatic errors.
Though a program is given below which covers this scenario but this program is not always guaranteed to create deadlock.

Scenario 2 :
Two Threads(T1 and T2, say) are accessing 2 resources(RES1 and RES2, say) but in reverse order.
Imagine the below sequence of events
1. T1 first accesses RES1 and then tries to access RES2.
2. T2 first accesses RES2 and then tries to access RES1.
3. T1 accesses RES1 meanwhile T2 accesses RES2.
Refer below image

Now, when T1 tries to access RES2, it cannot since it is used by T2.
And, when T2 tries to access RES1, it is blocked since it is being used by T1.
This scenario can be produced programmatically and will be shown ahead.

Programs
Below are shown two variants of programs which can produce deadlock. Both programs create two threads which produce deadlock.

Variant One :
This program creates two threads with both the threads acting on the same piece of code which acts as the task to be performed by the threads.
The code which is to be executed by the threads is written inside the run() method of Worker class extending java.lang.Thread.
Both the threads work on same Worker class object.
The code inside run contains two nested synchronized blocks which lock on different objects.
Till the time the thread which starts execution of a synchronized block does not complete it, other thread cannot enter the synchronized block.
This is evident from the program output given below.

public class Deadlock { 
  public static void main(String[] args) { 
    // initialize task performed by thread 
    Worker obj = new Worker(); 
    // create first thread 
    Thread t1 = new Thread(obj); 
    // create second thread 
    Thread t2 = new Thread(obj); 
    t1.start(); 
    t2.start(); 
  } 
} 

/** 
* Class which represents a task performed by a thread
 * */ 
class Worker implements Runnable { 
  // objects on which the threads will synchronize 
  String lockObjectOne = "object one"; 
  String lockObjectTwo = "object two"; 
  
  public void run() { 
    // synchronizing on first object 
    synchronized (lockObjectOne) { 
      System.out.println("Thread \"" + Thread.currentThread().getName() + "\" entered first block"); 
      try { 
        System.out.println("Thread \"" + Thread.currentThread().getName() + "\" performing its task"); 
        // assume current thread is doing some task 
        Thread.sleep(3000); 
      } catch (InterruptedException e) { } 
        // synchronizing on second object 
        synchronized (lockObjectTwo) { 
          System.out.println("Thread " + Thread.currentThread().getName() + " entered second block"); 
        } 
      } 
  } 
}

Output

Above output shows that Thread-1 only begins execution when Thread-0 finishes.
Thus, if Thread-0 hangs up or dies in between, the other thread(Thread-1) will remain in waiting state forever and the application will enter a state of deadlock.
This is a sample program to produce deadlock as per Scenario one explained above.
This program does not produce deadlock in actual scenarios but it may. It will only create deadlock when some abnormal condition will arise.

Variant Two :
This program creates two threads with both threads working on different pieces of code as their task.
Tasks are provided as two different Runnable objects with their separate run methods. But both threads synchronize on same set of objects but in different order.
Thread1 locks on object1 and then tries to gain access to object2 .
By that time, Thread2 gains access to object two and then tries to gain access to object one which is held by object1.
Thread2 waits for object1 to get free while Thread1 is waiting to gain access for object2 which is held by Thread2. Thus, they both are stuck for one another – forever.
This program will always produce deadlock and the program will always be in running state.
In order to prevent deadlock in the above program, just synchronize the blocks on objects in the same order so that a thread is stopped from entering outer synchronized block if another thread holds it.
The thread holding the object will eventually complete its task and other thread would perform its task.

public class DeadlockDifferentRunnable { 
  public static void main(String[] args) { 
    // objects on which thread will synchronize 
    DeadlockDifferentRunnable objectOne = new DeadlockDifferentRunnable(); 
    DeadlockDifferentRunnable objectTwo = new DeadlockDifferentRunnable(); 
    Thread threadOne = new Thread(new Runnable() { 
      @Override 
      public void run() { 
        synchronized (objectOne) { 
          System.out.println("Thread one entered first synchronized block." + 
                                 " Holding first object lock"); 
          synchronized (objectTwo) { 
            System.out.println("Thread one entered second " + 
                                 "synchronized block. Holding second object lock"); 
          } 
        } 
      } 
    }); 
    Thread threadTwo = new Thread(new Runnable() { 
      @Override 
      public void run() { 
        synchronized (objectTwo) { 
          System.out.println("Thread two entered first synchronized block." + 
                                  " Holding second object lock"); 
          synchronized (objectOne) { 
            System.out.println("Thread two entered second " + 
                                  "synchronized block. Holding first object lock"); 
          } 
        } 
      } 
    }); 
    //start threads 
    threadOne.start(); 
    threadTwo.start(); 
  } 
}

Output

Ways to avoid deadlock

Following tips would help in avoiding deadlock.

1. Try no two threads lock on same set of objects.
2. Restrain from nesting synchronized blocks. If synchronized blocks should be nested, then they should be locking on objects in the same order.
3. Never use Thread.sleep to control the behaviour of threads.

Let’s tweak in

1. Each object has only one lock associated with it.
2. A thread is considered to have acquired an object’s lock when it enters a synchronized block on that object.
3. Deadlock can only occur when multiple threads are striving to gain access to the same object. If they are working on different objects, deadlock will never occur.