Thread Deadlock in Java

Deadlock occurs when a group of processes blocks forever because each process is waiting for resources which are held by another process in the group. What happens is that a task is stuck waiting for another task to release a resource which itself is stuck waiting for another task to release a resource and so on such that a circular wait loop ensures. The result is that no task can proceed. Thus a deadlock results.

The classis case of deadlock is the Dining Philosopher problem.
In this problem we have, say 5 philosophers sitting down for dinner at a round table.
To the left and right of each philosopher is a chopstick and there are 5 of these chopsticks F1 – F5, illustrated below:

Dining philosopher problem

Reference: http://samplecodes.files.wordpress.com/2008/11/23.jpg

In order for each philospher to eat, they must pick up the left and right chopsticks.
Each philosopher decides to pick up the chopstick on his right 1st before picking up the one on his left.
After picking up the chopstick on the right, each philosopher attempts to pick up the chopstick on his left and if it is not yet available, has to wait.

Thus we can have the following scenario:

P1 picks up F1, waits to pick up F2
P2 picks up F2, waits to pick up F3
P3 picks up F3, waits to pick up F4
P4 picks up F4, waits to pick up F1
P5 picks up F5, waits to pick up F1

Thus we have a circular wait scenario, where each philosopher is waiting on the next philosopher to his left to drop his right chopstick and so on such that no philosopher can eat.

Here is Java code for a simpler example of deadlock involving 2 tasks:

public class DeadlockDemo
{
  public Integer obj1 = 1;
  public Integer obj2 = 2;

  private class Runnable1 implements Runnable
  {
   public void run()
   {
    synchronized(obj1)
    {
     System.out.println("R1: Obtained lock on obj1:" + obj1);
     System.out.println("R1: Waiting to obtain lock on obj2..."):
     synchronized(obj2)
     {
      System.out.println("R1: Obtained lock on obj2:" + obj2);
     }
    }
   }
  }

  private class Runnable2 implements Runnable
  {
   public void run()
   {
    synchronized(obj2)
    {
     System.out.println("R2: Obtained lock on obj2:" + obj2);
     System.out.println("R2: Waiting to obtain lock on obj1..."):
     synchronized(obj1)
     {
      System.out.println("R2: Obtained lock on obj1:" + obj1);
     }
    }
   }
  }

  public static void main(String[] args)
  {
   DeadlockDemo dDemo=new DeadlockDemo();
   Runnable r1=dDemo.new Runnable1();
   Runnable r2=new Runnable2();
   new Thread(r1).start();
   new Thread(r2).start();
  }
 }

 

I ran the above code and it produced the following result:

R2: Obtained lock on obj2:2
R2: Waiting to obtain lock on obj1...
R1: Obtained lock on obj1:1
R1: Waiting to obtain lock on obj2...

and the program hung with the 2 threads stuck in a circular wait.

Defining and Starting a Thread in Java

There are 3 ways to do this:

1. Subclass Thread class

i. Subclass the Thread class and override the run() method
ii. Instantiate the Thread subclass.
iii. Call Thread.start() method.

public class MyThread extends Thread {
   public void run() { 
      System.out.println("Thread via Extending Thread!"); 
   }
   public static void main(String []args) { 
      (new MyThread()).start(); 
   }

}

 

2. Provide a Runnable object by implementing Runnable

Runnable interface defines a single method run(), meant to contain the code executed in the thread.

i. Implement the Runnable interface by implementing run() method.
ii. Pass instance of Runnable object to the Thread(..) constructor.
iii. Call Thread.start() method.

public class MyRunnable implements Runnable {

   @Override
   public void run() {
      System.out.println("Thread via Implementing Runnable!");
   }

   public static void main(String[] args) {
      (new Thread(new MyRunnable())).start();

   }

}

Notice that both cases above invoke Thread.start() in order to start the new thread. In either case above, the result is a Thread object, where the run() method is the body of the thread. When the start() method of the Thread object is called, the interpreter creates a new thread to execute the run() method. The new thread continues to run until the run() method exits. Meanwhile the original thread continues running itself, starting with the statement following the start() method.

 

3. Using Executor interface

The Executor interface can be used to invoke threads as well. It isn’t really a new idiom, since either a Thread object or object that implements Runnable needs to be created first. The Executor interface provides a layer of indirection between a client and the execution of a task; instead of a client executing a task directly, an intermediate object executes the task. Executors allow you to manage the execution of asynchronous tasks without having to explicitly manage the lifecycle of threads.

 

  1. Implement and create a new instance of Runnable.
  2. Create a concrete instance of ExecutorService by calling one of the Executors factory methods.
  3. Call Executor.execute(..) method, passing the Runnable object as argument.
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class MyExecutor {

	public static void main(String[] args) {
		ExecutorService exec = Executors.newCachedThreadPool(); 
	    for(int i = 0; i < 5; i++) 
	      exec.execute(new MyRunnable()); //MyRunnable implements Runnable
	}

}

Thread vs. Runnable
Which of these idioms should you use? The first idiom, which employs a Runnable object, is more general, because the Runnable object can subclass a class other than Thread. Also using Runnable enhances separation of concerns vi a composition, by separating the method of execution from the interface used to construct the Runnable
The second idiom is easier to use in simple applications, but is limited by the fact that your task class must be a descendant of Thread.
References: http://www.coderanch.com/t/233370/threads/java/Thread-vs-Runnable
http://stackoverflow.com/questions/541487/java-implements-runnable-vs-extends-thread

Executor Factory Methods

FactoryMethod Details
newCachedThreadPool() Creates thread pool that creates new threads as needed, but will reuse previously constructred threads when they’re available
newFixedThreadPool(..) Creates thread pool that reuses a fixed number of threads operating off a shared unbounded queue
newScheduledThreadPool(..) Creates a thread pool that can schedule commands to run after a given delay, or to execute periodically
newSingleThreadExecutor() Creates an Executor that uses a single worker thread operating off an unbounded queue
newSingleThreadScheduledExecutor() Creates a single-threaded executor that can schedule commands to run after a given delay, or to execute periodically