Deadlock Detection

Deadlock detection is a reactive strategy. Unlike deadlock prevention or avoidance, it allows the system to enter a deadlocked state and then identifies it. This approach is often chosen when the cost of constraining resource allocation (as in prevention) is higher than the cost of occasionally recovering from a deadlock. The system periodically invokes a detection algorithm to examine the current resource allocation graph (RAG) or wait-for graph for cycles.

The primary data structure for deadlock detection is the Resource Allocation Graph (RAG). It is a directed graph where:

• Nodes represent either agents (processes) or resources.
• Edges represent allocations or requests:
  • An edge from a resource to an agent means the resource is currently allocated to that agent.
  • An edge from an agent to a resource means the agent is waiting for that resource. A cycle in this graph is a necessary and sufficient condition for a deadlock (assuming single-instance resources). Detection algorithms, like a depth-first search, are run on this graph to find cycles.

For detection efficiency, the RAG is often condensed into a Wait-For Graph. This graph contains only agent nodes. A directed edge from Agent A to Agent B indicates that Agent A is waiting for a resource currently held by Agent B. A cycle in the wait-for graph directly indicates a deadlock among the agents in that cycle. This simplification makes cycle detection faster and is central to algorithms like those used in distributed database systems.

The detection algorithm can be invoked according to different policies:

• Periodic Invocation: The detector runs at fixed time intervals (e.g., every minute). This balances overhead with timely detection but means deadlocks may persist between intervals.
• On-Demand Invocation: The detector runs when system performance degrades below a threshold (e.g., CPU utilization drops, queue lengths grow). This is more efficient but requires accurate heuristics for when to trigger.
• On Every Request: Theoretically possible but prohibitively expensive, as it would check for cycles after every resource request.

The output of a deadlock detection algorithm is not just a Boolean 'deadlock exists.' It must identify the set of deadlocked agents (and resources) involved in the cycle. This precise identification is critical for the subsequent deadlock recovery phase. Recovery strategies depend on knowing exactly which agents to target for victim selection, which may involve abortion (rolling back the agent's state) or resource preemption (forcibly taking a resource from one agent to give to another).

Deadlock detection introduces inherent system overhead. The computational cost of running the cycle detection algorithm (often O(n²) for n agents) and the memory cost of maintaining the RAG must be weighed against the cost of deadlocks going undetected. In distributed multi-agent systems, this overhead is magnified, as constructing a consistent global wait-for graph requires message passing between nodes, leading to algorithms like the Obermarck algorithm or edge-chasing protocols. The frequency of detection is a key tunable parameter in this trade-off.

Deadlock prevention is a proactive strategy that constrains an agent system's design or operational rules to ensure one or more of the four necessary conditions for deadlock (Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait) can never hold. This guarantees deadlocks cannot occur but often reduces concurrency and resource utilization.

• Key Techniques: Enforcing a total order on resource acquisition (preventing circular wait) or requiring agents to request all resources at once (eliminating hold and wait).
• Trade-off: Sacrifices some system flexibility and performance for absolute safety, making it suitable for highly critical, predictable environments.

Deadlock avoidance is a dynamic strategy where the system evaluates each resource request in real-time to determine if granting it could lead to a future deadlock. If a request would lead to an unsafe state, it is delayed. This requires advance knowledge of agent resource needs.

• Primary Algorithm: The Banker's Algorithm is the classic example. It models the system's maximum resources, allocated resources, and remaining needs to simulate if a sequence exists where all agents could still potentially finish.
• Use Case: Ideal for systems where the maximum resource claims of all agents are known a priori, such as in static batch processing environments.

Wait-Die and Wound-Wait are timestamp-based deadlock prevention protocols used in database systems and can be applied to agent transactions. They use agent age (timestamp) to enforce a unidirectional waiting pattern, preventing circular wait.

• Wait-Die: An older agent waits for a resource held by a younger one. A younger agent requesting a resource held by an older one is aborted (dies) and restarted.
• Wound-Wait: An older agent preempts (wounds) a younger one holding a needed resource. A younger agent waits if the resource is held by an older one.
• Outcome: Both guarantee no deadlock but may cause unnecessary aborts or preemptions.

A Resource Allocation Graph (RAG) is a directed graph used to model the state of a system for deadlock analysis. It is the primary data structure for many detection algorithms.

• Nodes: Represent Agent processes and Resource types (with multiple instances).
• Edges: An Assignment Edge (Resource → Agent) indicates the agent holds an instance. A Request Edge (Agent → Resource) indicates the agent is waiting for an instance.
• Detection: A cycle in the graph where all resource nodes have only a single instance indicates a deadlock. For multi-instance resources, more sophisticated cycle analysis is required.

Two-Phase Commit (2PC) is a distributed consensus protocol that ensures atomicity across multiple agents participating in a transaction. While not a deadlock resolution tool per se, it manages a related distributed coordination problem: achieving unanimous agreement to commit or abort.

• Phase 1 (Prepare): A coordinator asks all participant agents if they are ready to commit. Agents reply YES or NO.
• Phase 2 (Commit/Rollback): If all agents vote YES, the coordinator sends a COMMIT message. If any agent votes NO, it sends a ROLLBACK (ABORT) message.
• Blocking Problem: 2PC is a blocking protocol; if the coordinator fails, participants may remain in an uncertain state indefinitely, a form of operational deadlock.

Optimistic Concurrency Control (OCC) is a conflict management strategy that assumes conflicts are rare. Agents proceed with local work without acquiring locks, deferring conflict detection until a transaction's commit phase.

• Three Phases: 1) Read Phase: Agents execute, recording read/write sets. 2) Validation Phase: The system checks for serializability conflicts with other committed transactions. 3) Write Phase: If validation passes, changes are written; otherwise, the transaction is rolled back and retried.
• Contrast with Deadlock: OCC avoids deadlock entirely by not using locks, but it trades this for the cost of potential rollbacks and retries under high contention.