Operating Systems - Deadlock - Four Necessary Conditions (Coffman)
When using a resource allocation graph to detect deadlocks, what is the worst-case time complexity to detect a cycle in a system with P processes and R resources?
When using a resource allocation graph to detect deadlocks, what is the worst-case time complexity to detect a cycle in a system with P processes and R resources?
medium🪤 Complexity Trap Q6 of Q15
Step-by-Step Solution
Solution:
Step 1: Understand resource allocation graph
The graph has vertices for processes and resources, edges represent allocation and requests.Step 2: Cycle detection complexity
Cycle detection via DFS or BFS runs in O(V + E), where V = P + R and E can be up to P * R in the worst case.Step 3: Why others are incorrect
O(P + R) underestimates complexity because edges can be up to P * R. O(P² + R²) is unrelated, O(P * log R) assumes sorted structures not needed.Final Answer:
Option C -> Option CQuick Check:
Cycle detection in graph -> O(V + E) = O(P + R + P * R) = O(P * R) [OK]
Quick Trick: Cycle detection is linear in vertices and edges [OK]
Common Mistakes:
MISTAKES- Assuming quadratic complexity due to edges
- Confusing number of edges with vertices
Trap Explanation:
PITFALL- Candidates often underestimate complexity by ignoring edges.
Interviewer Note:
CONTEXT- Evaluates understanding of graph-based deadlock detection complexity.
Master "Deadlock - Four Necessary Conditions (Coffman)" in Operating Systems
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Operating Systems Quizzes