Course contentsShow
← Computer Science
Lesson 1326 of 2,87230. Process SynchronizationFree lesson

Deadlock Detection Algorithms

Algorithms for periodically examining resource allocation state to detect existing deadlocks after they occur.

Deadlock Detection Algorithms

What you'll learn: How operating systems periodically inspect resource allocations to discover if processes are already stuck in deadlock.

The Core Idea

Unlike prevention (which stops deadlocks before they form) or avoidance (which carefully checks before granting resources), detection takes a different approach: let deadlocks happen, then find and fix them. The OS periodically runs a detection algorithm that examines the current state of resource allocation and waiting to determine if any processes are deadlocked right now.

How Detection Works

Think of it like a security camera that reviews footage after a theft occurs. The system snapshots:

  • Which resources each process currently holds
  • Which resources each process is waiting for

The detection algorithm then checks if the resource allocation graph contains a cycle (remember: cycles indicate potential deadlock). More sophisticated variants examine whether the system can complete any waiting process with available resources. If no process can proceed, deadlock exists.

Detection Frequency Trade-offs

The OS must decide how often to run detection:

  • Frequent checks (e.g., every request): catch deadlocks quickly but waste CPU on repeated checks
  • Infrequent checks (e.g., when CPU utilization drops): lower overhead but processes wait longer while deadlocked

Once detected, the system must recover—typically by terminating processes or preempting resources to break the cycle.

Key Insight

Detection algorithms assume deadlocks are rare enough that letting them happen and cleaning up afterward is cheaper than the overhead of prevention or avoidance for every single resource request.

Key Takeaway: Deadlock detection algorithms periodically examine resource allocation state to identify existing deadlocks after they've already formed, trading proactive prevention for reactive discovery and recovery.