GATE CS 1998 Q7-b — CPU Scheduling

We trace the allocation of jobs to memory partitions using the Best-Fit algorithm and a strict FIFO queue order.

Initial State ($t = 0$):

• Partitions: $P_1(4K)$, $P_2(8K)$, $P_3(20K)$, $P_4(2K)$ (all free).
• Jobs are allocated as follows:
  • $J_1(2K)$ allocated to $P_4(2K)$ [best-fit]. Runs $t = 0 \to 4$.
  • $J_2(14K)$ allocated to $P_3(20K)$ [best-fit]. Runs $t = 0 \to 10$.
  • $J_3(3K)$ allocated to $P_1(4K)$ [best-fit]. Runs $t = 0 \to 2$.
  • $J_4(6K)$ allocated to $P_2(8K)$ [best-fit]. Runs $t = 0 \to 1$.

Timeline of events:

• At $t = 1$: $J_4$ completes. $P_2(8K)$ becomes free. Next job $J_5(6K)$ is allocated to $P_2(8K)$. Runs $t = 1 \to 5$.
• At $t = 2$: $J_3$ completes. $P_1(4K)$ becomes free. Next job $J_6(10K)$ cannot fit in any free partition ($P_1$ is free). The queue is blocked.
• At $t = 4$: $J_1$ completes. $P_4(2K)$ becomes free. $J_6(10K)$ still cannot fit.
• At $t = 5$: $J_5$ completes. $P_2(8K)$ becomes free. $J_6(10K)$ still cannot fit.
• At $t = 10$: $J_2$ completes. $P_3(20K)$ becomes free. $J_6(10K)$ is allocated to $P_3(20K)$ [best-fit]. Runs $t = 10 \to 11$. Next job $J_7(20K)$ must wait.
• At $t = 11$: $J_6$ completes. $P_3(20K)$ becomes free. $J_7(20K)$ is allocated to $P_3(20K)$ [best-fit]. Runs $t = 11 \to 19$.

Thus, the $20K$ job ($J_7$) completes at time 19.