GATE CS 2022 Q16 — Deadlock

Let us analyze each statement individually to determine its correctness:

• Statement A: True
  According to Coffman's conditions, there are four necessary conditions for a deadlock to occur: Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait. Since all four must hold simultaneously, Circular Wait is indeed a necessary condition.


• Statement B: False
  In a system with multiple instances of resources, a cycle in the resource-allocation graph (or wait-for graph) is a necessary but not sufficient condition for deadlock. It is possible that a process outside the cycle holds an instance of the resource and eventually releases it, breaking the potential deadlock.


• Statement C: False
  An unsafe state is not the same as a deadlock state. An unsafe state merely means that the system cannot guarantee that all processes will finish without deadlocking if they all request their maximum resource claims. However, if processes do not request their maximum claims or release resources early, the system can run to completion without deadlocking.


• Statement D: True
  In a resource-allocation graph, there are two types of edges:
  • Request edges ($P_i \to R_j$): Process $P_i$ is waiting for resource $R_j$.
  • Assignment edges ($R_j \to P_i$): Resource $R_j$ is allocated to process $P_i$.
  If every edge in the graph is an assignment edge, there are no request edges. This implies that no process is waiting for any resource. Since no process is blocked waiting for resources, a deadlock state cannot exist.

Thus, the correct statements are A and D.