Deadlock and How to prevent it

A deadlock in Java occurs when two or more threads are blocked forever, each waiting for the other to release a lock. This situation arises when multiple threads try to acquire the same set of locks in a different order, causing a circular dependency. Once in a deadlock, the threads can’t proceed, and the program may hang or freeze.

Example of Deadlock:

Let’s take an example with two threads, Thread1 and Thread2, and two resources, lock1 and lock2.

public class DeadlockExample {
    private final Object lock1 = new Object();
    private final Object lock2 = new Object();

    public void method1() {
        synchronized (lock1) {
            System.out.println("Thread 1: Holding lock 1...");

            // Simulate some work
            try { Thread.sleep(100); } catch (InterruptedException e) {}

            System.out.println("Thread 1: Waiting for lock 2...");
            synchronized (lock2) {
                System.out.println("Thread 1: Acquired lock 2...");
            }
        }
    }

    public void method2() {
        synchronized (lock2) {
            System.out.println("Thread 2: Holding lock 2...");

            // Simulate some work
            try { Thread.sleep(100); } catch (InterruptedException e) {}

            System.out.println("Thread 2: Waiting for lock 1...");
            synchronized (lock1) {
                System.out.println("Thread 2: Acquired lock 1...");
            }
        }
    }

    public static void main(String[] args) {
        DeadlockExample deadlock = new DeadlockExample();

        Thread t1 = new Thread(deadlock::method1);
        Thread t2 = new Thread(deadlock::method2);

        t1.start();
        t2.start();
    }
}

Explanation of Deadlock:

• Thread1 acquires lock1 and then waits for lock2.
• Thread2 acquires lock2 and then waits for lock1.
• Now, both threads are waiting for each other to release their locks, which causes a deadlock.

Conditions for Deadlock:

Deadlock can occur if the following four conditions are met:

1. Mutual Exclusion: Only one thread can hold a lock on a resource at a time.
2. Hold and Wait: A thread holding one lock is waiting to acquire another lock.
3. No Preemption: Locks cannot be forcibly taken away from a thread; they must be released by the thread holding them.
4. Circular Wait: Two or more threads are waiting on each other in a circular chain.

How to Prevent Deadlock in Java:

1. Avoid Nested Locks:

   • Avoid locking multiple resources at the same time. If a thread needs multiple locks, it should release one before acquiring another.

   Example:

   public void method1() {
       synchronized (lock1) {
           // Do something
       }
       synchronized (lock2) {
           // Do something else
       }
   }
   

2. Lock Ordering:

   • Ensure that all threads acquire locks in a predefined order. If multiple locks are needed, always acquire them in the same order to avoid circular waiting.

   Example:

   public void method1() {
       synchronized (lock1) {  // Always acquire lock1 first
           synchronized (lock2) {  // Then acquire lock2
               // Do something
           }
       }
   }
   
   public void method2() {
       synchronized (lock1) {  // Always acquire lock1 first, preventing circular dependency
           synchronized (lock2) {  // Then acquire lock2
               // Do something
           }
       }
   }
   

3. Try-Lock Mechanism (Using java.util.concurrent Package):

   • Use the ReentrantLock class from java.util.concurrent.locks package, which offers the tryLock() method. This method allows threads to attempt to acquire a lock but fail if the lock is already held by another thread, avoiding indefinite waiting.

   Example:

   import java.util.concurrent.locks.Lock;
   import java.util.concurrent.locks.ReentrantLock;
   
   public class DeadlockPrevention {
       private final Lock lock1 = new ReentrantLock();
       private final Lock lock2 = new ReentrantLock();
   
       public void method1() {
           try {
               if (lock1.tryLock()) {
                   System.out.println("Thread 1: Holding lock 1...");
   
                   // Simulate some work
                   try { Thread.sleep(100); } catch (InterruptedException e) {}
   
                   if (lock2.tryLock()) {
                       System.out.println("Thread 1: Acquired lock 2...");
                       // Do something
                   } else {
                       System.out.println("Thread 1: Could not acquire lock 2, releasing lock 1.");
                   }
               }
           } finally {
               lock1.unlock();
           }
       }
   
       public void method2() {
           try {
               if (lock2.tryLock()) {
                   System.out.println("Thread 2: Holding lock 2...");
   
                   // Simulate some work
                   try { Thread.sleep(100); } catch (InterruptedException e) {}
   
                   if (lock1.tryLock()) {
                       System.out.println("Thread 2: Acquired lock 1...");
                       // Do something
                   } else {
                       System.out.println("Thread 2: Could not acquire lock 1, releasing lock 2.");
                   }
               }
           } finally {
               lock2.unlock();
           }
       }
   
       public static void main(String[] args) {
           DeadlockPrevention example = new DeadlockPrevention();
   
           Thread t1 = new Thread(example::method1);
           Thread t2 = new Thread(example::method2);
   
           t1.start();
           t2.start();
       }
   }
   

   In this case, if one thread cannot acquire the second lock, it will release the first lock and try again later, thus preventing deadlock.

4. Timeouts:

   • Use timeouts for acquiring locks. If a thread cannot obtain a lock within a specified period, it can give up and retry or handle the situation gracefully.

   Example:

   if (lock1.tryLock(1, TimeUnit.SECONDS)) {
       try {
           // Critical section
       } finally {
           lock1.unlock();
       }
   } else {
       // Handle the inability to acquire the lock
   }
   

5. Deadlock Detection:

   • Implement a mechanism to detect and recover from deadlocks. This involves tracking thread states and lock ownership to identify cycles in waiting relationships. Though it’s more complex, it can be done in large-scale systems using thread monitoring and graph algorithms.

Conclusion:

A deadlock is a dangerous situation where two or more threads are waiting for each other to release locks, causing the program to freeze. It can be prevented using techniques like avoiding nested locks, ensuring lock ordering, using the tryLock() mechanism, and employing timeouts.