Deadlock Detection in Python using Resource Allocation Graphs

Deadlock is a common problem in concurrent programming where two or more processes are blocked indefinitely, waiting for each other to release resources. This challenge asks you to implement a deadlock detection mechanism using a Resource Allocation Graph (RAG). Detecting deadlocks allows a system to take corrective actions, such as process termination, to resolve the situation.

Problem Description

You are tasked with creating a Python class, DeadlockDetector, that can detect deadlocks within a system represented by a Resource Allocation Graph. The RAG will be represented as a dictionary where keys are processes and values are lists of resources they are waiting for. The class should have the following methods:

• __init__(): Initializes the DeadlockDetector with an empty graph.
• add_process(process, resources): Adds a process and the resources it's waiting for to the graph. process is a string representing the process name, and resources is a list of strings representing the resources it's waiting for.
• detect_deadlock(): Detects if a deadlock exists in the graph. This method should return True if a deadlock is detected, and False otherwise. The deadlock detection should be based on cycle detection within the RAG. You can use Depth-First Search (DFS) or other graph traversal algorithms to detect cycles.
• get_deadlocked_processes(): If a deadlock is detected by detect_deadlock(), this method should return a list of processes involved in the deadlock cycle. If no deadlock is detected, it should return an empty list.

Key Requirements:

• The solution must accurately detect cycles in the RAG.
• The get_deadlocked_processes() method should return the processes participating in the cycle, not just indicate the presence of a deadlock.
• The graph should be mutable, allowing processes and resources to be added dynamically.

Expected Behavior:

The DeadlockDetector should correctly identify deadlocks based on the resource dependencies defined in the graph. The detect_deadlock() method should return True only when a cycle exists, and False otherwise. get_deadlocked_processes() should return the processes involved in the cycle when a deadlock is present.

Edge Cases to Consider:

• Empty graph: No deadlock should be detected.
• Single process waiting for a single resource: No deadlock.
• Multiple processes, some waiting for each other, others not involved in any waiting relationships: Only the processes in the cycle should be identified as deadlocked.
• Self-loops (a process waiting for itself): Should be considered a deadlock.

Examples

Example 1:

Input:
detector = DeadlockDetector()
detector.add_process("P1", ["R1"])
detector.add_process("P2", ["R2"])
detector.add_process("P3", ["R1", "R2"])

Output:
detect_deadlock(): False
get_deadlocked_processes(): []
Explanation: No cycle exists.

Example 2:

Input:
detector = DeadlockDetector()
detector.add_process("P1", ["R1"])
detector.add_process("P2", ["R2"])
detector.add_process("P3", ["R1"])
detector.add_process("P4", ["R2"])

Output:
detect_deadlock(): False
get_deadlocked_processes(): []
Explanation: No cycle exists.

Example 3:

Input:
detector = DeadlockDetector()
detector.add_process("P1", ["R1"])
detector.add_process("P2", ["R2"])
detector.add_process("P3", ["R1"])
detector.add_process("P4", ["R2"])
detector.add_process("P5", ["P1"])
detector.add_process("P6", ["P4"])

Output:
detect_deadlock(): True
get_deadlocked_processes(): ['P1', 'P5', 'P6', 'P4']
Explanation: A cycle exists: P1 -> P5 -> P6 -> P4 -> R2 -> P2 -> R1 -> P1.

Example 4: (Edge Case - Self-Loop)

Input:
detector = DeadlockDetector()
detector.add_process("P1", ["P1"])

Output:
detect_deadlock(): True
get_deadlocked_processes(): ['P1']
Explanation: A self-loop indicates a deadlock.

Constraints

• Process and resource names are strings.
• The graph can contain up to 100 processes and 50 resources.
• The detect_deadlock() method should complete within 1 second.
• The input graph will always be valid (no invalid data types).

Notes

• Consider using Depth-First Search (DFS) to detect cycles in the graph. Keep track of visited nodes to avoid infinite loops.
• The order of processes in the get_deadlocked_processes() list is not important.
• The RAG is directed. The dependency is one-way (e.g., P1 waiting for R1 does not imply R1 is waiting for P1).
• Think about how to represent the graph efficiently for cycle detection. A dictionary is a good starting point.
• Be mindful of potential stack overflow errors when using recursion in DFS, especially with larger graphs. Consider iterative DFS if necessary.