Deadlocks Practice Questions

The Dining Philosophers Problem leads to deadlock when all philosophers simultaneously pick up their first fork, creating a circular wait condition where each waits indefinitely for the second. Options A and B fail because they maintain symmetry; if every philosopher follows the same picking order, they can all seize one fork simultaneously, causing a deadlock. Option C utilizes the resource hierarchy strategy by introducing asymmetry. By making one philosopher pick up forks in a different order (e.g., right then left) compared to the others, the circular dependency is broken, ensuring that it is impossible for every philosopher to be holding a fork while waiting for another, thereby preventing deadlock.

A system will be deadlock-free if the total number of resources $m$ is greater than the sum of the maximum resources required by each process minus one, ensuring at least one process can always complete its task. The condition is given by $m > \sum (n_i - 1)$.
For processes with peak demands $n_A=3, n_B=4,$ and $n_C=6$, the sum of resources required to potentially reach a deadlock state is $(3-1) + (4-1) + (6-1) = 2 + 3 + 5 = 10$.
Thus, to prevent deadlock, we must have $m \ge 10 + 1$, which means $m \ge 11$.
Comparing this requirement with the given options, both 13 and 15 satisfy the condition $m \ge 11$.

[CORRECT_OPTION: D, E]

A system is guaranteed to be deadlock-free if the total number of resources $R$ satisfies the condition $R > \sum_{i=1}^{n} (k_i - 1)$, where $k_i$ is the maximum resource requirement of process $i$. Given $R = 6$ and $k_i = 3$ for all processes, the condition becomes $6 > n(3 - 1)$, which simplifies to $6 > 2n$. Solving for $n$, we obtain $n < 3$. Therefore, the maximum integer value for $n$ that ensures the system is deadlock-free is $n = 2$.

For deadlock to occur, each process could be holding (x-1) resources and waiting for one more. If the total resources m are at least n*(x-1) + 1, then at least one process can get its required resource and complete, releasing resources for others, thus preventing deadlock.

No preemption is required for deadlock.

Banker's Algorithm is a deadlock avoidance method, not a prevention method. Deadlock prevention methods include breaking any of the four necessary conditions: Mutual Exclusion (via spooling), Hold and Wait (via preallocation), No Preemption (via preemption), and Circular Wait (via resource ordering).

To prevent deadlock in the Dining Philosophers problem, a common solution is to break the symmetry by making the last philosopher (or one philosopher) pick up the right fork first instead of the left fork. This prevents the circular wait condition from forming.

An unsafe state in the Banker's algorithm means that there is a possibility of deadlock (i.e., deadlock may occur if processes request resources in a certain order), but it does not guarantee that deadlock will definitely occur. The system may still complete without deadlock depending on future resource requests.

For single-instance resources, a cycle in the wait-for graph is necessary and sufficient for deadlock. This is because each resource can be held by at most one process, so a circular wait directly implies deadlock.

This uses the deadlock avoidance condition for identical resources. If each process can request up to K instances, a sufficient condition for no deadlock is: Total Resources > Sum of (Max Need of each process - 1) = 3*(K-1). Thus, 4 > 3K - 3 => 7 > 3K => K < 2.33. So the largest integer K is 2. With K=2, even if two processes hold 1 each, the third can always get 2 to finish [citation:6].

Total instances = 12, 4 processes each hold 2 instances = total 8 allocated, 4 instances available. Each process needs a maximum of 2, but they already hold 2 each and are waiting for additional instances. However, since each process already has its maximum requirement (2), they would not request more. If they are waiting, it must be for something else. The correct answer is deadlock-free.

Processes p and q do not need any additional resources (Yp=Yq=0), so they can finish and release their resources. For the system to avoid deadlock, they must collectively hold enough resources to satisfy at least one other process's maximum request. If min(Xp, Xq) > 1, it means both p and q hold at least 2 resources. This increases the pool of resources that can be released, helping to satisfy the needs of waiting processes and guaranteeing progress [citation:1][citation:4].

Statement (A) is TRUE: Circular wait is one of the four necessary conditions for deadlock along with Mutual Exclusion, Hold & Wait, and No Preemption. Statement (B) is FALSE: For multi-instance resources, a cycle in the wait-for graph is not sufficient to guarantee deadlock. Statement (C) is FALSE: An unsafe state does not necessarily lead to deadlock; deadlock may occur but is not guaranteed. Statement (D) is TRUE: If all edges are assignment edges (no request edges), all resource requirements are satisfied, so deadlock cannot occur. [Source: GATE Overflow discussion]

The given RAG contains cycles: (P1→R2→P2→R3→P3→R1→P1) forms a cycle, and (P2→R4→P4→R2→P2) forms another cycle. Because all resources have single instances, these cycles indicate deadlock. Aborting P1 breaks the first cycle; aborting P3 also breaks the first cycle; aborting P2 breaks both cycles; aborting P1 and P4 together also breaks both cycles. Hence, all options (I), (II), and (IV) are correct. [Source: GATE CSE 2025 discussed on PracticePaper]

In a multi-instance resource system, a cycle in the RAG is a necessary but not sufficient condition for deadlock. The presence of additional available instances of any resource in the cycle could resolve the deadlock. Therefore, without knowing the exact number of available instances, the system may or may not be deadlocked.

Deadlock Prevention (1) breaks one or more of the four necessary conditions (A). Deadlock Avoidance (2) uses the Banker's algorithm to ensure the system remains in a safe state (B). Deadlock Detection (3) uses the wait-for graph to detect a deadlock if it occurs (C). Deadlock Recovery (4) involves terminating deadlocked processes or preempting resources (D).

Worst case: each process holds max-1=3. Deadlock free if n*(max-1) < total → n3 < 12 → n < 4. But at n=4, 43=12, and one extra resource breaks tie. So max n=4.

The Banker's algorithm is a deadlock avoidance algorithm. It ensures that the system always remains in a safe state by simulating resource allocation before actually granting requests, thus avoiding the possibility of deadlock.

The wait-for graph has vertices representing processes. A directed edge Pi→Pj indicates Pi is waiting for a resource held by Pj. For systems with single-instance resources, a cycle is necessary and sufficient for deadlock. However, this scheme is not applicable to systems with multiple instances of each resource type. Hence, statement C is FALSE.

All the options are valid methods for deadlock recovery. Resource preemption involves taking resources away from some processes and giving them to others. Process termination can be done by terminating all deadlocked processes or terminating them one by one until deadlock is resolved. Process rollback restores a process to a previously saved checkpoint and restarts it.