Deadlocks Practice Questions

For a system to enter a deadlock state, the four Coffman conditions must hold simultaneously: $Mutual\ exclusion$, $Hold\ and\ wait$, $No\ pre-emption$, and $Circular\ wait$. Options A, C, and D directly correspond to three of these fundamental requirements for deadlocks. Conversely, $Reentrancy$ describes a property of software where a routine can be safely interrupted and called again without causing errors, which is unrelated to deadlock theory. Since $Reentrancy$ is not a required condition, it is the correct choice.

To determine the system's state, we first calculate the currently available resources and the remaining needs for each process.

1. Total used resources: Type 1 $= 1 + 1 + 2 = 4$; Type 2 $= 1 + 1 + 1 = 3$.
2. Available resources: Type 1 $= 5 - 4 = 1$; Type 2 $= 4 - 3 = 1$. Available $= (1, 1)$.
3. Calculate remaining Need (\text{Max} - \text{Used}$): P1$(1, 2)$, P2$(2, 1)$, P3$(2, 3)$.
4. Comparison: For every process, at least one resource requirement exceeds the available resources $(1, 1)$. Thus, no process can complete its execution, preventing the release of held resources.
5. Since no sequence of execution exists that allows processes to finish, the system is in an unsafe state.

Total resources are $9$ and currently used resources are $2+1+2+1 = 6$, leaving available resources $A = 9 - 6 = 3$. The resource needs are: $P_1(5), P_2(5), P_3(3), P_4(3)$. For a state to be safe, the available resources must satisfy at least one process's need. Checking sequence $\langle P_3, P_1, P_2, P_4 \rangle$:

1. $P_3$ needs $3 \le A(3)$: $P_3$ runs, releasing $2$, new $A = 3+2 = 5$.
2. $P_1$ needs $5 \le A(5)$: $P_1$ runs, releasing $2$, new $A = 5+2 = 7$.
3. $P_2$ needs $5 \le A(7)$: $P_2$ runs, releasing $1$, new $A = 7+1 = 8$.
4. $P_4$ needs $3 \le A(8)$: $P_4$ runs, completing the sequence.

A deadlock occurs when a circular wait condition exists, where two processes each hold a resource the other needs. For the case $n=21$ and $k=12$, consider $P_{8}$ (where $i=8$ is even) and $P_{11}$ (where $i=11$ is odd). Following the logic, $P_{8}$ requests $R_{8}$ then $R_{10}$. Simultaneously, $P_{11}$ requests $R_{21-11} = R_{10}$ then $R_{21-11-2} = R_{8}$. If $P_{8}$ acquires $R_{8}$ and $P_{11}$ acquires $R_{10}$, then $P_{8}$ waits for $R_{10}$ (held by $P_{11}$) and $P_{11}$ waits for $R_{8}$ (held by $P_{8}$). This creates a circular dependency $P_{8} \rightarrow R_{10} \rightarrow P_{11} \rightarrow R_{8} \rightarrow P_{8}$, making a deadlock possible.

Deadlock recovery often involves terminating or rolling back a "victim" process to release resources and resolve the circular wait condition. If the victim selection algorithm is not implemented with a fairness criterion, the same process may be repeatedly chosen as the victim whenever a deadlock involving its resources occurs. Consequently, this process is perpetually denied the opportunity to complete its execution, a condition known as starvation. Therefore, recurring rollbacks of the same process directly result in starvation.

To avoid deadlock, the system must satisfy the condition $n > \sum_{i=1}^{k} (Max_i - 1)$, where $Max_i$ is the peak demand of process $i$.
For processes A, B, and C with peak demands 3, 4, and 6, the threshold where deadlock can occur is:
$\sum (Max_i - 1) = (3 - 1) + (4 - 1) + (6 - 1) = 2 + 3 + 5 = 10$
Deadlock is avoided if $n > 10$, meaning $n \ge 11$.
Among the given options, both 13 and 15 satisfy the condition, but 13 is the standard choice reflecting the minimum value satisfying the constraint in this context.

The system has resources R1(3), R2(2), R3(3), R4(2). A non-preemptive policy is used, and requests are denied if not fully satisfiable. We simulate the concurrent execution:

Initial Available: $R1(3), R2(2), R3(3), R4(2)$.

$t=0$:

• P1 requests $R2(2)$. Available $R2(2)$. P1 gets $R2(2)$.
• P2 requests $R3(2)$. Available $R3(3)$. P2 gets $R3(2)$.
• P3 requests $R4(1)$. Available $R4(2)$. P3 gets $R4(1)$.
  • Held: $P1: R2(2)$; $P2: R3(2)$; $P3: R4(1)$.
  • Available: $R1(3), R2(0), R3(1), R4(1)$.

$t=1$:

• P1 requests $R3(1)$. Available $R3(1)$. P1 gets $R3(1)$.
  • Held: $P1: R2(2), R3(1)$; $P2: R3(2)$; $P3: R4(1)$.
  • Available: $R1(3), R2(0), R3(0), R4(1)$.

$t=2$:

• P2 requests $R4(1)$. Available $R4(1)$. P2 gets $R4(1)$.
• P3 requests $R1(2)$. Available $R1(3)$. P3 gets $R1(2)$.
  • Held: $P1: R2(2), R3(1)$; $P2: R3(2), R4(1)$; $P3: R4(1), R1(2)$.
  • Available: $R1(1), R2(0), R3(0), R4(0)$.

$t=3$:

• P1 requests $R1(2)$. Needs 2, Available $R1(1)$. P1 blocks.

$t=4$:

• P2 requests $R1(1)$. Needs 1, Available $R1(1)$. P2 gets $R1(1)$.
  • Held: $P1: R2(2), R3(1)$ (blocked); $P2: R3(2), R4(1), R1(1)$; $P3: R4(1), R1(2)$.
  • Available: $R1(0), R2(0), R3(0), R4(0)$.

$t=5$:

• P3 releases $R1(2)$. $R1$ becomes Available(2).
  • Held: $P1: R2(2), R3(1)$ (blocked); $P2: R3(2), R4(1), R1(1)$; $P3: R4(1)$.
  • Available: $R1(2), R2(0), R3(0), R4(0)$.
• P1 unblocks: requests $R1(2)$, Available $R1(2)$. P1 gets $R1(2)$.
  • Held: $P1: R2(2), R3(1), R1(2)$; $P2: R3(2), R4(1), R1(1)$; $P3: R4(1)$.
  • Available: $R1(0), R2(0), R3(0), R4(0)$.
• P1 releases $R2(1)$ and $R1(1)$.
  • Held: $P1: R2(1), R3(1), R1(1)$; $P2: R3(2), R4(1), R1(1)$; $P3: R4(1)$.
  • Available: $R1(1), R2(1), R3(0), R4(0)$.

$t=6$:

• P2 releases $R3(1)$.
  • Held: $P1: R2(1), R3(1), R1(1)$; $P2: R3(1), R4(1), R1(1)$; $P3: R4(1)$.
  • Available: $R1(1), R2(1), R3(1), R4(0)$.

$t=7$:

• P1 releases $R3(1)$.
• P3 requests $R2(1)$. Needs 1, Available $R2(1)$. P3 gets $R2(1)$.
  • Held: $P1: R2(1), R1(1)$; $P2: R3(1), R4(1), R1(1)$; $P3: R4(1), R2(1)$.
  • Available: $R1(1), R2(0), R3(1), R4(0)$.

$t=8$:

• P1 requests $R4(2)$. Needs 2, Available $R4(0)$. P1 blocks.
• P2 Finishes. Releases $R3(1), R4(1), R1(1)$.
  • Available: $R1(1)+1=R1(2), R2(0), R3(1)+1=R3(2), R4(0)+1=R4(1)$.
• P3 requests $R3(1)$. Needs 1, Available $R3(2)$. P3 gets $R3(1)$.
  • Held: $P1: R2(1), R1(1)$ (blocked); $P3: R4(1), R2(1), R3(1)$.
  • Available: $R1(2), R2(0), R3(1), R4(1)$.
  • P1 is still blocked (needs $R4(2)$, Available $R4(1)$).

$t=9$:

• P3 Finishes. Releases $R4(1), R2(1), R3(1)$.
  • Available: $R1(2), R2(0)+1=R2(1), R3(1)+1=R3(2), R4(1)+1=R4(2)$.
• P1 unblocks: requests $R4(2)$, Available $R4(2)$. P1 gets $R4(2)$.
  • Held: $P1: R2(1), R1(1), R4(2)$.
  • Available: $R1(2), R2(1), R3(2), R4(0)$.

$t=10$:

• P1 Finishes. Releases $R2(1), R1(1), R4(2)$.
  • Available: $R1(2)+1=R1(3), R2(1)+1=R2(2), R3(2), R4(0)+2=R4(2)$.

All processes P1, P2, and P3 complete execution, and all resources are returned to their initial state. No deadlock occurs.

The final answer is $\boxed{A}$

The four necessary Coffman conditions for a deadlock are mutual exclusion, hold and wait, no preemption, and circular wait. The condition of mutual exclusion specifies that at least one resource is held in a non-sharable mode, meaning for a resource $R$, only one process $P_i$ can have exclusive access at any given time. Because this condition prevents other processes from accessing the resource simultaneously, it directly corresponds to the requirement that processes claim exclusive control. In contrast, "hold and wait" relates to resource requests while holding others, "no preemption" restricts forced release, and "circular wait" defines a cyclic dependency chain. Therefore, mutual exclusion is the only condition describing exclusive resource control.

The policy requiring a process to release all currently held resources before requesting a new one explicitly violates the Hold and Wait condition, which is a necessary condition for deadlock. By eliminating Hold and Wait, the system guarantees that deadlock cannot occur. However, starvation is independent of the deadlock conditions and depends on the specific scheduling discipline used to allocate resources. A process can still be indefinitely denied resources by higher-priority processes regardless of the release policy, meaning starvation remains possible. Thus, deadlock is impossible while starvation can still occur.

Deadlock prevention operates by imposing static, global constraints to break one of the Coffman conditions, making deadlock impossible regardless of the current state. Conversely, deadlock avoidance, such as the Banker's Algorithm, dynamically checks if a resource request keeps the system in a "safe state" (i.e., a sequence exists to satisfy all processes). Because avoidance algorithms determine safety based on the maximum future requirements $R_{max}$ of processes, option D is true. Furthermore, avoidance is considered less restrictive than prevention (option C) and functions as described in option B. is false, as prevention does not utilize safe state evaluation.

To ensure a deadlock never occurs, the system must have enough resources such that even if every process holds one resource less than its maximum requirement, at least one process can still finish. The condition for deadlock avoidance is $m > \sum_{i=1}^{n} (demand_i - 1)$.

Given the peak demands of 3, 4, and 6:
$\sum (demand_i - 1) = (3-1) + (4-1) + (6-1) = 2 + 3 + 5 = 10$
To guarantee at least one process can always complete, we need:
$m = 10 + 1 = 11$

First, calculate the initially available resources. Each resource type (X, Y, Z) has 5 units.

1. Total Allocated Resources:
   $Alloc\_X = 1+2+2 = 5$
   $Alloc\_Y = 2+0+2 = 4$
   $Alloc\_Z = 1+1+1 = 3$

2. Initial Available Resources:
   $Available\_X = 5 - 5 = 0$
   $Available\_Y = 5 - 4 = 1$
   $Available\_Z = 5 - 3 = 2$
   So, $Available = (0, 1, 2)$.

3. Determine execution order using the Banker's algorithm (safety algorithm):

   • P0 requests $(1,0,3)$: Cannot run, as $1 > 0$ (for X) and $3 > 2$ (for Z).
   • P1 requests $(0,1,2)$: Can run, as $(0,1,2) \le (0,1,2)$.
     If P1 runs, it finishes and releases its allocated resources $(2,0,1)$.
     $Available = (0,1,2) + (2,0,1) = (2,1,3)$. Sequence: P1.
   • P0 requests $(1,0,3)$: Can now run, as $(1,0,3) \le (2,1,3)$.
     If P0 runs, it finishes and releases its allocated resources $(1,2,1)$.
     $Available = (2,1,3) + (1,2,1) = (3,3,4)$. Sequence: P1, P0.
   • P2 requests $(1,2,0)$: Can now run, as $(1,2,0) \le (3,3,4)$.
     If P2 runs, it finishes and releases its allocated resources $(2,2,1)$.
     $Available = (3,3,4) + (2,2,1) = (5,5,5)$. Sequence: P1, P0, P2.

The safe sequence is P1, P0, P2. Thus, P2 finishes last.

The system occupies all instances of resource $R$, totaling $\sum x_i$. Processes $p$ and $q$ require $y_p=y_q=0$, so they can complete and release $x_p+x_q$ resources. To avoid deadlock, at least one process $k \neq p,q$ must be able to satisfy its request $y_k$ using these released resources, meaning $y_k \leq x_p+x_q$ for at least one $k$. This condition is satisfied if the minimum request among all $k \neq p,q$ is at most the available resources: $min_{k\neq p,q}(y_k) \leq x_p+x_q$. Failing this condition implies that no process $k \neq p,q$ can complete, which leads to a deadlock.

A deadlock occurs if $P_1$ holds $R_1$ and waits for $R_2$ while $P_2$ holds $R_2$ and waits for $R_1$. Preemption prevents this if one process can always snatch a required resource from the other. Given conditions $(I)$ $T_{11} > T_{21}$ and $(II)$ $T_{12} > T_{22}$, process $P_1$ possesses higher priority for both resources $R_1$ and $R_2$. Consequently, if $P_1$ needs $R_2$ while $P_2$ holds it, $P_1$ can snatch $R_2$ because $T_{12} > T_{22}$. Similarly, $P_2$ cannot snatch $R_1$ from $P_1$ because $T_{21} < T_{11}$. Thus, $P_1$ can always acquire the resources required to complete its execution, ensuring no deadlock can occur.

To prevent deadlock, a system must ensure that at least one process can always complete its execution. The worst-case scenario leading to deadlock is when every process $P_i$ has acquired $s_i - 1$ resources but cannot acquire the final one needed to finish. The total number of resources held in this state is $\sum_{i=1}^{n} (s_i - 1)$. If the total resources available $m$ are strictly greater than this sum, there will always be at least one free resource to allow a process to complete, thereby avoiding deadlock.

The condition is therefore:
$\sum_{i=1}^{n} (s_i - 1) < m$
Expanding the summation gives:
$\sum_{i=1}^{n} s_i - \sum_{i=1}^{n} 1 < m \implies \sum_{i=1}^{n} s_i - n < m \implies \sum_{i=1}^{n} s_i < m + n$

In this deadlock prevention scheme, a cycle of dependencies $P_1 \to P_2 \to \dots \to P_n \to P_1$ requires $T(P_1) < T(P_2) < \dots < T(P_n) < T(P_1)$, which is impossible due to the total ordering of timestamps, ensuring the system is deadlock-free. However, the condition "if $T(P_r) < T(P_h)$ then kill $P_r$" implies that an older process ($T(P_r) < T(P_h)$) is killed when it requests a resource held by a younger process ($T(P_h) > T(P_r)$). Since a killed process restarts with the same timestamp, it may repeatedly request a resource held by a younger process and be killed continuously. This leads to indefinite postponement, meaning the scheme is not starvation-free.

The minimum number of rooms required to schedule the activities is equal to the maximum number of overlapping activities at any point in time. We track the active activities chronologically:

1. $\{a_s, b_s, c_s\}$: Activities $\{A, B, C\}$ are active (3).
2. After $a_e$ and $d_s$: Activities $\{B, C, D\}$ are active (3).
3. After $c_e$ and $e_s$: Activities $\{B, D, E\}$ are active (3).
4. After $f_s$: Activities $\{B, D, E, F\}$ are active (4).
5. After $b_e$, $d_e$, $g_s$, etc.: The number of active activities decreases.

Since the maximum number of concurrent activities is 4, 4 rooms are required.

Deadlock prevention strategies aim to violate at least one of the four Coffman conditions: mutual exclusion, hold and wait, no preemption, and circular wait. Option A prevents the "hold and wait" condition by forcing the release of resources. Option B implements a linear resource hierarchy to prevent "circular wait". Option D ensures all resources are allocated upfront, also preventing "hold and wait". Option C proposes an arbitrary restriction that does not address any of the necessary conditions for deadlock and is not a recognized technique in operating systems. Therefore, it is not a valid deadlock prevention scheme.

Let $m = 6$ be the total number of tape drives and $k = 2$ be the number of drives each process needs.
A system remains deadlock-free if the total number of resources held by all processes, where each holds $k - 1$ resources, is less than the total available resources, expressed as $n \times (k - 1) < m$.
Substituting the given values: $n \times (2 - 1) < 6$.
This simplifies to $n \times 1 < 6$, resulting in $n < 6$.
The maximum integer value for $n$ to avoid deadlock is $5$.

To prevent deadlock, we must ensure that at least one process can always complete its execution. Given $n = 3$ processes, each requiring $r = 2$ units, a deadlock occurs in the worst-case scenario where each process holds $r - 1 = 1$ unit, totaling $n(r - 1) = 3$ units. In this state, all processes are blocked waiting for one more unit. By providing one additional resource unit, we guarantee that at least one process can acquire its required $2$ units and complete. Thus, the minimum units required is $n(r - 1) + 1 = 3(2 - 1) + 1 = 4$.