GATE CS 2009 Q30 — Deadlock

To determine if a deadlock occurs, we trace the concurrent execution of the three processes. Let $e_i$ denote the active execution time (excluding blocked states) of process $P_i$.

The total available resources initially are: $R1 = 3$, $R2 = 2$, $R3 = 3$, $R4 = 2$.

1. At $t = 0$:
   • $P1$ (at $e_1=0$) requests $2$ units of $R2$ $\rightarrow$ Granted.
   • $P2$ (at $e_2=0$) requests $2$ units of $R3$ $\rightarrow$ Granted.
   • $P3$ (at $e_3=0$) requests $1$ unit of $R4$ $\rightarrow$ Granted.
   • Available: $R1=3, R2=0, R3=1, R4=1$.
2. At $t = 1$:
   • $P1$ (at $e_1=1$) requests $1$ unit of $R3$ $\rightarrow$ Granted.
   • Available: $R1=3, R2=0, R3=0, R4=1$.
3. At $t = 2$:
   • $P2$ (at $e_2=2$) requests $1$ unit of $R4$ $\rightarrow$ Granted.
   • $P3$ (at $e_3=2$) requests $2$ units of $R1$ $\rightarrow$ Granted.
   • Available: $R1=1, R2=0, R3=0, R4=0$.
4. At $t = 3$:
   • $P1$ (at $e_1=3$) requests $2$ units of $R1$. Since only $1$ unit of $R1$ is available, $P1$ is Blocked.
   • $P2$ and $P3$ continue executing ($e_2=3, e_3=3$).
5. At $t = 4$:
   • $P2$ (at $e_2=4$) requests $1$ unit of $R1$ $\rightarrow$ Granted.
   • Available: $R1=0, R2=0, R3=0, R4=0$.
6. At $t = 5$:
   • $P3$ (at $e_3=5$) releases $2$ units of $R1$.
   • Available: $R1=2, R2=0, R3=0, R4=0$.
   • Since $2$ units of $R1$ are now available, the blocked request of $P1$ is Granted, and $P1$ unblocks.
   • Available: $R1=0, R2=0, R3=0, R4=0$.
7. At $t = 6$:
   • $P2$ (at $e_2=6$) releases $1$ unit of $R3$.
   • Available: $R1=0, R2=0, R3=1, R4=0$.
8. At $t = 7$:
   • $P1$ (at $e_1=5$) releases $1$ unit of $R2$ and $1$ unit of $R1$.
   • $P3$ (at $e_3=7$) requests $1$ unit of $R2$ $\rightarrow$ Granted.
   • Available: $R1=1, R2=0, R3=1, R4=0$.
9. At $t = 8$:
   • $P2$ (at $e_2=8$) finishes and releases all its held resources ($1 \times R3, 1 \times R4, 1 \times R1$).
   • $P3$ (at $e_3=8$) requests $1$ unit of $R3$ $\rightarrow$ Granted.
   • Available: $R1=2, R2=0, R3=1, R4=1$.
10. At $t = 9$:
    • $P1$ (at $e_1=7$) releases $1$ unit of $R3$.
    • $P3$ (at $e_3=9$) finishes and releases all its held resources ($1 \times R4, 1 \times R2, 1 \times R3$).
    • Available: $R1=2, R2=1, R3=3, R4=2$.
11. At $t = 10$:
    • $P1$ (at $e_1=8$) requests $2$ units of $R4$ $\rightarrow$ Granted.
12. At $t = 12$:
    • $P1$ finishes successfully.

Since all three processes run to completion, no deadlock occurs.