GATE CS 2022 Q.26: Deadlock Prevention, Avoidance and Detection

Which of the following statements is/are TRUE with respect to deadlocks?

Circular wait is a necessary condition for the formation of deadlock.

In a system where each resource has more than one instance, a cycle in its wait-for graph indicates the presence of a deadlock.

If the current allocation of resources to processes leads the system to unsafe state, then deadlock will necessarily occur.

In the resource-allocation graph of a system, if every edge is an assignment edge, then the system is not in deadlock state.

Official answer and solution

Solution

Evaluate deadlock necessary conditions, resource allocation graphs, and safety definitions.

Evaluating each statement:

(A) TRUE: Circular wait is one of the four Coffman conditions (mutual exclusion, hold and wait, no preemption, circular wait). All four conditions are strictly necessary for deadlock to occur.
(B) FALSE: In systems with multiple instances per resource type, a cycle in the resource allocation graph is a necessary condition, but not a sufficient condition for deadlock.
(C) FALSE: An unsafe state indicates that the system cannot guarantee that all processes will finish if each requests its maximum resource claim simultaneously. However, processes might not request their maximum claims, so deadlock is possible but not guaranteed to occur.
(D) TRUE: In a resource allocation graph, if all edges are assignment edges ( $R_j \to P_i$ ) and there are no request edges ( $P_i \to R_j$ ), then no process is waiting for any resource. Without waiting processes, deadlock cannot exist.

Final answer

Options (A), (D)

Common trap

Assuming that an unsafe state always implies that deadlock will occur.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.