Home/Learn/Operating Systems/Deadlock Detection & Recovery

Deadlock Detection & Recovery

Advanced

Deadlocks

Deadlock detection algorithms identify when deadlock has occurred, and recovery strategies break the deadlock by terminating processes or preempting resources.

Overview

Unlike prevention and avoidance, detection allows deadlock to occur but identifies it afterwards. For single-instance resources, the OS maintains a wait-for graph (a RAG with resource nodes collapsed) and runs cycle detection. For multi-instance resources, a reduction algorithm similar to Banker's safety check is used. Detection frequency is a trade-off: run on every request (expensive), periodically, or when CPU utilisation drops below a threshold. Recovery either terminates processes (abort all at once or one by one in order of cost) or preempts resources (select a victim, rollback its state, risk starvation).

Java Deadlock Detection with ThreadMXBean

Java's ThreadMXBean exposes findDeadlockedThreads() which scans all threads for cycles in ownership/waiting relationships. It covers both synchronized blocks (monitor locks) and java.util.concurrent locks. This is the programmatic equivalent of running jstack in production.

Java — Periodic deadlock detection with ThreadMXBean

import java.lang.management.*;

public class DeadlockDetector {

    // Call periodically (e.g., every 30s via ScheduledExecutorService)
    public static void checkForDeadlocks() {
        ThreadMXBean tmx = ManagementFactory.getThreadMXBean();

        // findDeadlockedThreads: synchronized + j.u.c locks
        // findMonitorDeadlockedThreads: synchronized only
        long[] ids = tmx.findDeadlockedThreads();

        if (ids == null) {
            System.out.println("[OK] No deadlock detected.");
            return;
        }

        ThreadInfo[] infos = tmx.getThreadInfo(ids, true, true);
        StringBuilder sb = new StringBuilder("DEADLOCK DETECTED!
");

        for (ThreadInfo ti : infos) {
            sb.append("  Thread: ").append(ti.getThreadName())
              .append(" [").append(ti.getThreadState()).append("]
");
            sb.append("    Blocked on: ").append(ti.getLockName()).append("
");
            sb.append("    Lock held by: ").append(ti.getLockOwnerName()).append("
");
            // Print stack trace of deadlocked thread
            for (StackTraceElement ste : ti.getStackTrace()) {
                sb.append("      at ").append(ste).append("
");
            }
        }
        System.err.println(sb);
        // Recovery: alert ops team, restart affected threads, or JVM
    }
}

// Schedule detection every 30 seconds
ScheduledExecutorService scheduler = Executors.newSingleThreadScheduledExecutor();
scheduler.scheduleAtFixedRate(
    DeadlockDetector::checkForDeadlocks, 0, 30, TimeUnit.SECONDS);

Recovery Strategies

Process termination can abort all deadlocked processes (expensive but simple) or terminate one at a time until the cycle breaks. Victim selection criteria: process priority, how long it has run, how many resources it holds, how many more it needs, how many times it has been preempted (starvation prevention). Resource preemption rolls back a process to a saved checkpoint — requires OS support for process state snapshots.

Java — Deadlock recovery via thread interruption

// Recovery example: interrupt one thread in a detected deadlock
// (application-level — JVM can't forcibly kill threads safely)

public static void recoverFromDeadlock(long[] deadlockedThreadIds) {
    Map<Long, Thread> allThreads = new HashMap<>();
    Thread.getAllStackTraces().forEach((t, st) -> allThreads.put(t.getId(), t));

    // Select victim: thread with lowest priority (simplest heuristic)
    Thread victim = null;
    int lowestPriority = Integer.MAX_VALUE;

    for (long id : deadlockedThreadIds) {
        Thread t = allThreads.get(id);
        if (t != null && t.getPriority() < lowestPriority) {
            lowestPriority = t.getPriority();
            victim = t;
        }
    }

    if (victim != null) {
        System.out.println("Interrupting victim thread: " + victim.getName());
        victim.interrupt(); // breaks any blocking wait; thread must handle it
        // Thread should check Thread.interrupted() and clean up
    }
}

// Production pattern: wrap critical sections in try-finally
// so locks are always released on interrupt/exception
ReentrantLock lock = new ReentrantLock();
try {
    if (lock.tryLock(100, TimeUnit.MILLISECONDS)) {
        try {
            // critical section
        } finally {
            lock.unlock(); // always released
        }
    }
} catch (InterruptedException e) {
    Thread.currentThread().interrupt(); // restore interrupt flag
}

Key Points to Remember

1Detection allows deadlock to occur but identifies and resolves it; it is preferred when deadlock is infrequent.
2Wait-for graph (single-instance) and reduction algorithm (multi-instance) are the two main detection approaches.
3Running detection on every resource request is O(n²) — most systems run it periodically or on CPU utilisation drop.
4Process termination is simple but costly; resource preemption requires rollback support and risks starvation.
5Java's ThreadMXBean.findDeadlockedThreads() detects both monitor locks and java.util.concurrent lock cycles.
6jstack <pid> produces a thread dump; search for "Found one Java-level deadlock" in the output.

Interview Questions

What is the difference between a wait-for graph and a Resource Allocation Graph?

EasyAmazon

How often should a deadlock detection algorithm run, and what are the trade-offs?

MediumGoogle

You are on-call and a Java service is hanging. How do you determine if it is a deadlock and recover?

HardUber

What criteria would you use to select the victim process during deadlock recovery?

MediumAdobe

Ask Aria about Deadlock Detection & Recovery

Your personal AI tutor — ask anything about this concept

Revision Status

Personal Notes

Discussion

Loading discussion…

Deadlock Avoidance: Banker's Algorithm

Livelock & Starvation