GATE CS 2015 Set 3 Q52 — Deadlock

To prevent deadlocks, a system must violate at least one of the four Coffman conditions: Mutual Exclusion, Hold and Wait, No Preemption, or Circular Wait.

Let's analyze each of the given policies:

1. Policy I: "Process should acquire all their resources at the beginning of execution. If any resource is not available, all resources acquired so far are released."
   This policy prevents the Hold and Wait condition. Since a process cannot hold some resources while waiting for others (it either gets all of them or none), a deadlock cannot occur.


2. Policy II: "The resources are numbered uniquely, and processes are allowed to request for resources only in increasing resource numbers."
   This is Havender's linear ordering scheme. It prevents the Circular Wait condition. If resources are requested in a strictly increasing order, a cycle of waiting processes cannot form.


3. Policy III: "The resources are numbered uniquely, and processes are allowed to request for resources only in decreasing resource numbers."
   Similar to Policy II, ordering the resources in a strictly decreasing order also prevents the Circular Wait condition. The direction of the ordering (increasing or decreasing) does not affect the prevention of cycles.


4. Policy IV: "The resources are numbered uniquely. A process is allowed to request for resources only for a resource with resource number larger than its currently held resources."
   This is a dynamic variation of the increasing resource ordering. Since any new resource requested must have a strictly larger index than any resource currently held by the process, a cycle of the form $R_1 \rightarrow R_2 \rightarrow \dots \rightarrow R_k \rightarrow R_1$ (where each arrow represents a dependency) is mathematically impossible because it would require $index(R_1) < index(R_2) < \dots < index(R_k) < index(R_1)$, which is a contradiction. Thus, it prevents Circular Wait.

Since all four policies successfully prevent deadlock, any one of them can be used.

Therefore, the correct option is D.