Cheat SheetsOperating SystemsDeadlocks

Deadlocks — Cheat Sheet

Operating Systems · 6 topics. Download the PDF or the Instagram carousel and share it.

Cheat Sheet · AiCanCode.org
Deadlocks
Operating Systems6 topicsQuick revision reference
1

Deadlock: Four Necessary Conditions

A deadlock occurs only when all four Coffman conditions hold simultaneously: mutual exclusion, hold and wait, no preemption, and circular wait.

  • ✓All four Coffman conditions must hold simultaneously; removing any one prevents deadlock.
  • ✓Mutual Exclusion is often unavoidable for inherently non-shareable resources like write locks.
  • ✓Hold and Wait can be broken by requiring processes to request all resources upfront or release existing ones before requesting new ones.
  • ✓Circular Wait is the easiest condition to break in practice: enforce a global total ordering on lock acquisition.
  • ✓Java's jstack and ThreadMXBean.findDeadlockedThreads() are the primary tools for diagnosing deadlocks in production.
  • ✓A deadlock differs from a livelock (threads active but making no progress) and starvation (one thread indefinitely delayed).
Java — Two-lock deadlock demonstration
// Classic two-lock deadlock: Thread A locks L1 then L2,
// Thread B locks L2 then L1 — circular wait guaranteed.
Object L1 = new Object();
Object L2 = new Object();

Thread threadA = new Thread(() -> {
    synchronized (L1) {                        // holds L1
        System.out.println("A: acquired L1");
        try { Thread.sleep(50); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
        synchronized (L2) {                    // waits for L2
            System.out.println("A: acquired L2");
        }
    }
}, "Thread-A");

Thread threadB = new Thread(() -> {
    synchronized (L2) {                        // holds L2
        System.out.println("B: acquired L2");
        try { Thread.sleep(50); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
        synchronized (L1) {                    // waits for L1 → DEADLOCK
            System.out.println("B: acquired L1");
        }
    }
}, "Thread-B");

threadA.start();
threadB.start();
threadA.join();
threadB.join();
// Program hangs — both threads blocked forever
2

Resource Allocation Graph

A Resource Allocation Graph (RAG) is a directed graph used to represent the state of resource allocation and detect deadlocks in single- and multi-instance resource systems.

  • ✓In a RAG, request edges go from process to resource; assignment edges go from resource to process.
  • ✓For single-instance resources, a cycle in the RAG is both necessary and sufficient for deadlock.
  • ✓For multi-instance resources, a cycle is necessary but not sufficient — use the reduction algorithm to confirm deadlock.
  • ✓Each dot inside a resource rectangle represents one instance; the number of dots equals total instances.
  • ✓The RAG can be converted to a wait-for graph (only processes) by collapsing resource nodes for simpler cycle detection.
Java — RAG adjacency list with DFS cycle detection
import java.util.*;

// RAG represented as adjacency list
// Nodes: "P1","P2","P3" = processes; "R1","R2" = resources (single-instance)
Map<String, List<String>> graph = new HashMap<>();

// Assignment edges (R → P): R1 assigned to P1, R2 assigned to P2
graph.put("R1", List.of("P1"));
graph.put("R2", List.of("P2"));

// Request edges (P → R): P2 wants R1, P3 wants R2, P1 wants R3 (cycle!)
graph.put("P1", List.of("R2"));   // P1 holds R1, wants R2
graph.put("P2", List.of("R1"));   // P2 holds R2, wants R1 → CYCLE
graph.put("P3", List.of());

// DFS cycle detection
Set<String> visited = new HashSet<>();
Set<String> inStack = new HashSet<>();

boolean hasCycle = false;
for (String node : graph.keySet()) {
    if (!visited.contains(node) && dfs(node, graph, visited, inStack)) {
        hasCycle = true;
        break;
    }
}
System.out.println("Deadlock detected: " + hasCycle); // true

static boolean dfs(String node, Map<String, List<String>> graph,
                   Set<String> visited, Set<String> inStack) {
    visited.add(node);
    inStack.add(node);
    for (String neighbor : graph.getOrDefault(node, List.of())) {
        if (!visited.contains(neighbor) && dfs(neighbor, graph, visited, inStack)) return true;
        if (inStack.contains(neighbor)) return true;  // back edge = cycle
    }
    inStack.remove(node);
    return false;
}
3

Deadlock Prevention

Deadlock prevention eliminates deadlock by ensuring at least one of the four Coffman conditions can never hold in the system.

  • ✓Prevention targets one Coffman condition structurally, making deadlock impossible at design time.
  • ✓Lock ordering (enforcing total order on acquisition) is the most widely used prevention strategy in Java.
  • ✓tryLock() with timeout breaks hold-and-wait but requires careful retry logic to avoid livelock.
  • ✓Eliminating mutual exclusion is only possible for inherently shareable resources (e.g., read-only data, ReadWriteLock).
  • ✓Prevention is safer than detection but may underutilise resources (e.g., holding all locks upfront blocks other processes).
  • ✓Java's ReadWriteLock reduces mutual exclusion by allowing concurrent readers, preventing deadlocks on read-heavy data.
Java — Lock ordering to prevent circular wait
import java.util.concurrent.locks.ReentrantLock;

// Assign a numeric ID to each lock — always acquire lower ID first
ReentrantLock lockA = new ReentrantLock(); // id = 1
ReentrantLock lockB = new ReentrantLock(); // id = 2

// SAFE: both threads acquire in the same order (A before B)
Runnable safeTask = () -> {
    lockA.lock();
    try {
        System.out.println(Thread.currentThread().getName() + ": acquired A");
        lockB.lock();
        try {
            System.out.println(Thread.currentThread().getName() + ": acquired B");
            // critical section
        } finally {
            lockB.unlock();
        }
    } finally {
        lockA.unlock();
    }
};

Thread t1 = new Thread(safeTask, "T1");
Thread t2 = new Thread(safeTask, "T2");
t1.start();
t2.start();
// No deadlock: circular wait condition is broken
// T2 will block on lockA.lock() until T1 releases it
4

Deadlock Avoidance: Banker's Algorithm

The Banker's Algorithm dynamically evaluates each resource request to ensure the system stays in a safe state — a state from which all processes can eventually complete.

  • ✓A safe state guarantees a safe sequence exists; an unsafe state may or may not lead to deadlock.
  • ✓The Banker's Algorithm requires processes to declare maximum resource needs upfront — impractical for general-purpose OS.
  • ✓Time complexity of the safety algorithm is O(n² × r) where n is processes and r is resource types.
  • ✓The algorithm prevents deadlock dynamically at runtime without imposing permanent structural restrictions.
  • ✓Cloud and database admission control systems use Banker's-style reasoning to avoid overcommitting resources.
  • ✓A process in an unsafe state is made to wait, not killed — the system may eventually become safe as others release resources.
Java — Banker's Algorithm safety check
// Banker's Algorithm — Safety Check
// 3 processes (P0, P1, P2), 3 resource types (A, B, C)

int[] available   = {3, 3, 2};             // free instances

int[][] allocation = {                      // currently allocated
    {0, 1, 0},  // P0
    {2, 0, 0},  // P1
    {3, 0, 2},  // P2
};

int[][] max = {                             // maximum demand
    {7, 5, 3},  // P0
    {3, 2, 2},  // P1
    {9, 0, 2},  // P2
};

int n = 3, r = 3;
int[][] need = new int[n][r];
for (int i = 0; i < n; i++)
    for (int j = 0; j < r; j++)
        need[i][j] = max[i][j] - allocation[i][j];

boolean[] finished = new boolean[n];
int[] safeSeq = new int[n];
int count = 0;

int[] work = available.clone();

while (count < n) {
    boolean found = false;
    for (int i = 0; i < n; i++) {
        if (!finished[i]) {
            boolean canRun = true;
            for (int j = 0; j < r; j++)
                if (need[i][j] > work[j]) { canRun = false; break; }

            if (canRun) {
                for (int j = 0; j < r; j++) work[j] += allocation[i][j];
                safeSeq[count++] = i;
                finished[i] = true;
                found = true;
            }
        }
    }
    if (!found) { System.out.println("UNSAFE STATE"); break; }
}
// Safe sequence: P1 → P2 → P0 (need[P1]≤avail, then P2, then P0)
5

Deadlock Detection & Recovery

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

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

Livelock & Starvation

Livelock occurs when processes keep changing state in response to each other but make no progress, while starvation occurs when a process is indefinitely denied the resources it needs.

  • ✓Livelock threads are active (not blocked) but make no progress — they consume CPU unlike deadlocked threads.
  • ✓Randomised backoff with exponential delay (like Ethernet's CSMA/CD) is the standard livelock remedy.
  • ✓Starvation occurs when scheduling policy indefinitely postpones a process — common with strict priority scheduling.
  • ✓Aging gradually increases a waiting process's priority to guarantee it eventually runs.
  • ✓ReentrantLock(true) enables fairness (FIFO ordering) at the cost of ~10-30% throughput reduction.
  • ✓Java's ForkJoinPool uses work-stealing: idle threads steal tasks from busy threads, preventing starvation of long-queued tasks.
Java — Livelock demo and random-backoff fix
import java.util.concurrent.atomic.AtomicBoolean;

// LIVELOCK: two "polite" threads each yield endlessly
AtomicBoolean resource = new AtomicBoolean(false); // false = available

Runnable politeThread = () -> {
    String name = Thread.currentThread().getName();
    int attempts = 0;
    while (!resource.compareAndSet(false, true)) {
        // Resource busy — politely back off
        System.out.println(name + ": resource busy, yielding...");
        Thread.yield(); // both threads yield forever — livelock!
        attempts++;
        if (attempts > 1000) {
            System.out.println(name + ": giving up after 1000 attempts (livelock)");
            return;
        }
    }
    System.out.println(name + ": acquired resource!");
    resource.set(false); // release
};

// FIX: randomised backoff breaks symmetry
Runnable fixedThread = () -> {
    String name = Thread.currentThread().getName();
    while (!resource.compareAndSet(false, true)) {
        try {
            // Random sleep: one thread will wait longer than the other
            long backoff = (long)(Math.random() * 50); // 0-50ms
            System.out.println(name + ": backing off for " + backoff + "ms");
            Thread.sleep(backoff);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
            return;
        }
    }
    System.out.println(name + ": acquired resource!");
    resource.set(false);
};
Learn this free with Aria, your AI tutor → AiCanCode.org/learn/operating-systems