Deadlock Detection - aryanjoshi0823/5143-Operating-System GitHub Wiki

When deadlocks are not avoided or prevented, the system must be equipped to detect their occurrence and recover to restore normal operations. However, this approach comes with challenges, including performance overhead, potential resource preemption, and the risk of lost work.

Detection Methods

1. Single Instance of Each Resource Type

Figure - (a) Resource allocation graph. (b) Corresponding wait-for graph

For systems where each resource type has only one instance, Wait-for Graphs are used.

Wait-for Graphs

  • Constructed by modifying the Resource Allocation Graph:
    • Eliminate resource nodes.
    • Replace edges with direct process-to-process dependencies.
  • An arc from Pi to Pj in a wait-for graph indicates that process Pi is waiting for a resource that process Pj is currently holding.
  • Deadlock Detection: Cycles in the wait-for graph indicate a deadlock.

Algorithm Workflow

  • Maintain the wait-for graph dynamically.
  • Periodically check for cycles using a cycle-detection algorithm.
  • Cycles in the wait-for graph indicate deadlocks.

2. Several Instances of a Resource Type

For systems with multiple resource instances, the detection algorithm resembles the Banker's Algorithm, with key differences:

Differences from Banker's Algorithm

  1. Initialization:

    • The Finish[i] array:
      • Banker’s Algorithm: Initialized to false for all processes.
      • Detection Algorithm: Set Finish[i] = true for processes with zero allocated resources, as they cannot be involved in a deadlock.

  2. Detection Steps:

    • Check if any process's request can be fulfilled using available resources.
    • Grant the request temporarily and mark the process as completed (Finish[i] = true).
    • Repeat until no further processes can proceed.

  3. Deadlock Identification:

    • If any Finish[i] = false at the end of the algorithm, the corresponding process is part of the deadlock.