Multithreading Concepts Part 3 : Deadlock

Welcome to Part 3 of our multithreading series!

• In Part 1, we explored Atomicity and Immutability.
• In Part 2, we discussed Starvation.

In this part, we’ll dive into the mechanics of Deadlock in multithreading. What causes it, How to identify and preventive strategies you can use to avoid turning your code into a gridlocked intersection. Application grinds to a halt, often without any visible errors, leaving developers puzzled and systems frozen.

Navigating the Complex Tracks of Concurrency

A useful analogy to understand deadlock is to imagine a railway network with multiple trains on intersecting tracks.

Since each train is waiting for the next one to move, none can proceed, leading to a deadlock. In this scenario, the inefficient signaling system allowed each train to enter its respective section without first confirming that the next section would be free, trapping all trains in an unbreakable cycle.

This train example illustrates a typical deadlock in multithreading, where threads (like the trains) hold onto resources (track sections) while waiting for other resources to be freed, but none can progress. To prevent this kind of deadlock in software, effective resource management strategies—analogous to smarter railway signaling—must be implemented to avoid circular dependencies and ensure safe passage for each thread.

Deadlock is a situation in which threads (or processes) are indefinitely blocked, waiting for resources that other threads hold. This scenario leads to an unbreakable cycle of dependencies, where no involved thread can make progress. Understanding the basics of deadlock is essential before exploring the methods for detection, prevention, and resolution.

For a deadlock to occur, four conditions must be met simultaneously, known as the Coffman conditions:

• Mutual Exclusion: At least one resource must be held in a non-shareable mode, meaning only one thread can use it at a time.

• Hold and Wait: A thread must hold one resource and wait to acquire additional resources that other threads hold.

• No Preemption: Resources cannot be forcibly taken away from threads. They must be released voluntarily.

• Circular Wait: A closed chain of threads exists, where each thread holds at least one resource needed by the next thread in the chain.

Let’s understand as a sequence diagram

In above animation,

• Thread A holds Resource 1 and waits for Resource 2
• While Thread B holds Resource 2 and waits for Resource 1

All four conditions shared above for deadlock are present, which results indefinite block. Breaking any one of them can prevent deadlock.

Detecting deadlocks, especially in large-scale applications, can be challenging. However, the following approaches can help identify deadlocks

• Tooling: Java’s JConsole, VisualVM, and thread analyzers in IDEs can detect deadlocks in real-time.
• Thread Dumps and Logs: Analyzing thread dumps can reveal waiting threads and the resources they’re holding.

For detailed overview to understand how to debug/monitor deadlocks please visit Debug and Monitor Deadlock using VisualVM and jstack

• Applying the Wait-Die and Wound-Wait Schemes
  Wait-Die Scheme: When a thread requests a lock held by another thread, the database assesses the relative priority (usually based on the timestamp of each thread). If the requesting thread has a higher priority, it waits; otherwise, it dies (restarts).
  Wound-Wait Scheme: If the requesting thread has a higher priority, it wounds (preempts) the lower-priority thread by forcing it to release the lock.

• Immutable Objects for Shared State
  Design shared state as immutable wherever possible. Since immutable objects cannot be modified, they require no locks for concurrent access, reducing the risk of deadlock and simplifying code.

• Using tryLock with Timeout for Lock Acquisition: Unlike a standard synchronized block, ReentrantLock allows using tryLock(timeout, unit) to attempt acquiring a lock within a specified period. If the lock isn’t acquired within that time, it releases resources, preventing indefinite blocking.

ReentrantLock lock1 = new ReentrantLock();
ReentrantLock lock2 = new ReentrantLock();

public void acquireLocks() {
    try {
        if (lock1.tryLock(100, TimeUnit.MILLISECONDS)) {
            try {
                if (lock2.tryLock(100, TimeUnit.MILLISECONDS)) {
                    // Critical section
                }
            } finally {
                lock2.unlock();
            }
        }
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    } finally {
        lock1.unlock();
    }
}

• Lock Ordering and Releasing
  Set a strict, global order for lock acquisition. If all threads acquire locks in a consistent order, cyclic dependencies are less likely to form, thus avoiding deadlocks. For example, always acquire lock1 before lock2 throughout the codebase. This practice can be challenging in larger applications but is very effective in reducing deadlock risk.

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

public class LockOrderingExample {

    private static final Lock lock1 = new ReentrantLock();
    private static final Lock lock2 = new ReentrantLock();

    public static void main(String[] args) {
        Thread thread1 = new Thread(() -> {
            acquireLocksInOrder(lock1, lock2);
        });

        Thread thread2 = new Thread(() -> {
            acquireLocksInOrder(lock1, lock2);
        });

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

    private static void acquireLocksInOrder(Lock firstLock, Lock secondLock) {
        try {
            firstLock.lock();
            System.out.println(Thread.currentThread().getName() + " acquired lock1");

            secondLock.lock();
            System.out.println(Thread.currentThread().getName() + " acquired lock2");

            // Perform some operations

        } finally {
            secondLock.unlock();
            System.out.println(Thread.currentThread().getName() + " released lock2");

            firstLock.unlock();
            System.out.println(Thread.currentThread().getName() + " released lock1");
        }
    }
}

• Use Thread-Safe/Concurrent Collections: Java’s java.util.concurrent package provides thread-safe implementations of common data structures (ConcurrentHashMap, CopyOnWriteArrayList, etc.) that handle synchronization internally, reducing the need for explicit locks. These collections minimize deadlocks as they’re designed to avoid the need for explicit locking, using techniques like internal partitioning.

• Avoid Nested Locks
  Minimize acquiring multiple locks within the same block to avoid circular dependencies. If nested locks are necessary, use consistent lock ordering

• Whenever you create a design that requires locking, you open up the possibility for deadlocks.
• Deadlock is a blocking issue caused by a cycle of dependencies between processes. No process can make progress because each one is waiting for a resource held by another, and none can proceed to release resources.
• Deadlock is more severe, as it completely halts the involved processes and requires breaking the deadlock cycle for recovery.
• Deadlock can occur only when there are two different locks, i.e. when you are holding a lock and waiting for another lock to release. (There are more conditions on deadlocks, however).
• Thread-safety does not mean deadlock free. It only guarantees that the code will operate according to its interface, even when called from multiple threads. Making a class thread-safe usually includes adding locks to guarantee safe execution.

Whether you’re a beginner or a seasoned developer, understanding deadlock is crucial for writing robust, efficient code in concurrent systems. In this article, we explored what deadlocks are, their causes, and practical ways to prevent them. By implementing effective resource allocation strategies, analyzing task dependencies, and utilizing tools like thread dumps and deadlock detection tools, developers can minimize deadlock risk and optimize their code for smooth concurrency.

As we continue our journey through the core concepts of multithreading, stay tuned for the next articles in this series. We’ll dive into Critical Sections, understanding how to manage shared resources safely among multiple thread. We will also discuss the concept of Race Conditions, a common concurrency issue that can lead to unpredictable behavior and bugs if left unchecked.

With each step, you’ll gain deeper insights into how to make your applications thread-safe, efficient, and resilient. Keep pushing the boundaries of your multithreading knowledge to build better, more performant software!