Explain deadlock and how to prevent it.

Deadlock is a critical issue in concurrent programming, where two or more threads are blocked indefinitely, waiting for each other to release resources. In Java, this typically involves threads waiting to acquire `synchronized` monitors or `Lock` objects that are held by other blocked threads, leading to a complete halt in execution for the involved threads.

What is Deadlock?

A deadlock occurs when a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process. Imagine Thread A holds Resource X and wants Resource Y, while Thread B holds Resource Y and wants Resource X. Both threads will wait forever.

For a deadlock to occur, four necessary conditions (Coffman conditions) must be present simultaneously:

• Mutual Exclusion: At least one resource must be held in a non-sharable mode, meaning only one process at a time can use the resource.
• Hold and Wait: A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.
• No Preemption: Resources cannot be preempted; that is, a resource can only be released voluntarily by the process holding it, after that process has completed its task.
• Circular Wait: A set of processes {P0, P1, ..., Pn} must exist such that P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2, ..., Pn-1 is waiting for a resource held by Pn, and Pn is waiting for a resource held by P0.

Illustrative Example (Java)

Consider two String objects used as locks and two threads attempting to acquire them in different orders:

public class DeadlockExample {

    private static Object lock1 = new Object();
    private static Object lock2 = new Object();

    public static void main(String[] args) {
        Thread thread1 = new Thread(() -> {
            synchronized (lock1) {
                System.out.println("Thread 1: Holding lock 1...");
                try { Thread.sleep(10); } catch (InterruptedException e) {}
                System.out.println("Thread 1: Waiting for lock 2...");
                synchronized (lock2) {
                    System.out.println("Thread 1: Acquired lock 2.");
                }
            }
        });

        Thread thread2 = new Thread(() -> {
            synchronized (lock2) {
                System.out.println("Thread 2: Holding lock 2...");
                try { Thread.sleep(10); } catch (InterruptedException e) {}
                System.out.println("Thread 2: Waiting for lock 1...");
                synchronized (lock1) {
                    System.out.println("Thread 2: Acquired lock 1.");
                }
            }
        });

        thread1.start();
        thread2.start();
    }
}

In this example, thread1 tries to acquire lock1 then lock2, while thread2 tries to acquire lock2 then lock1. If thread1 acquires lock1 and thread2 acquires lock2 simultaneously (or near-simultaneously), they will both be blocked indefinitely when trying to acquire the other lock, leading to a deadlock.

Preventing Deadlock

Preventing deadlock involves breaking one or more of the four Coffman conditions. Here are common strategies:

1. Break Circular Wait (Resource Ordering)

This is often the most practical and effective strategy. Impose a total ordering of all resources, and require that each thread request resources in an increasing (or decreasing) order of enumeration. This ensures that a circular wait can never form.

// Consistent order: always acquire lock1 then lock2
public class NoDeadlockExample {
    private static Object lock1 = new Object();
    private static Object lock2 = new Object();

    public static void main(String[] args) {
        Thread thread1 = new Thread(() -> {
            synchronized (lock1) {
                System.out.println("Thread 1: Holding lock 1...");
                synchronized (lock2) {
                    System.out.println("Thread 1: Acquired lock 2.");
                }
            }
        });

        Thread thread2 = new Thread(() -> {
            synchronized (lock1) { // Thread 2 also tries for lock1 first
                System.out.println("Thread 2: Holding lock 1...");
                synchronized (lock2) {
                    System.out.println("Thread 2: Acquired lock 2.");
                }
            }
        });
        thread1.start();
        thread2.start();
    }
}

2. Break Hold and Wait

A thread should either acquire all its required resources at once, or release all resources it currently holds if it cannot acquire the full set. This can be achieved using a 'try-finally' block or ReentrantLock's tryLock() method.

import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class NoHoldAndWaitExample {
    private static Lock lock1 = new ReentrantLock();
    private static Lock lock2 = new ReentrantLock();

    public static void main(String[] args) {
        Thread thread1 = new Thread(() -> {
            while (true) {
                try {
                    if (lock1.tryLock(10, TimeUnit.MILLISECONDS)) {
                        System.out.println("Thread 1: Acquired lock 1");
                        if (lock2.tryLock(10, TimeUnit.MILLISECONDS)) {
                            System.out.println("Thread 1: Acquired lock 2");
                            // Do work
                            lock2.unlock();
                            lock1.unlock();
                            break;
                        } else {
                            System.out.println("Thread 1: Could not acquire lock 2, releasing lock 1");
                            lock1.unlock();
                        }
                    }
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            }
        });
        // Similar logic for thread 2, ensuring consistent order or backoff
        // Or for thread 2, if it needs lock2 then lock1, it would release lock2 if lock1 is not available.
        thread1.start();
    }
}

3. Break No Preemption (Allow Preemption/Timeouts)

While resources like CPU cannot generally be preempted, a thread can be made to release resources if it cannot obtain additional required resources within a certain timeout. The tryLock(long timeout, TimeUnit unit) method of ReentrantLock is excellent for this, allowing a thread to give up its lock if it can't acquire another one in time.

4. Avoid Mutual Exclusion (If Possible)

This condition is usually inherent in many resource access scenarios (e.g., writing to a file, updating a shared data structure) and hard to avoid. However, if a resource can be accessed concurrently without issues (e.g., read-only access), then mutual exclusion is not needed. Using ReadWriteLock can improve concurrency for read-heavy scenarios, but write operations still require mutual exclusion.

Other Prevention Techniques and Best Practices

• Avoid Nested Locks: Try to avoid acquiring a lock while holding another one. If unavoidable, strictly enforce a consistent locking order.
• Use java.util.concurrent Utilities: Classes like ReentrantLock (with tryLock()), Semaphore, CyclicBarrier, CountDownLatch, and Executors provide more sophisticated and flexible mechanisms for managing concurrency and can help in preventing deadlocks compared to raw synchronized blocks.
• Minimize Lock Scope: Keep the sections of code protected by locks as small and brief as possible. This reduces the time a lock is held, decreasing the chance of contention and deadlock.
• Deadlock Detection and Recovery: While not strictly prevention, some systems implement algorithms to detect deadlocks (e.g., using resource-allocation graphs) and then recover by preempting resources or terminating processes. Java itself doesn't offer built-in deadlock detection and recovery, but tools like JConsole or VisualVM can detect deadlocked threads in a running JVM.

In summary, careful design of resource acquisition order, disciplined use of locks, and leveraging the advanced concurrency utilities in Java are key to building robust, deadlock-free concurrent applications.