GATE CS 1996 Q2.20 — CPU Scheduling

To find the completion time of job $A$ under Round Robin (RR) scheduling with a time quantum ($q$) of $1$ time unit, we can trace the execution order using a Gantt chart.

Given Data:

• Jobs: $A, B, C, D$ (arriving at time $0$ in this order)
• Burst Times: $A = 4$, $B = 1$, $C = 8$, $D = 1$
• Time Quantum ($q$): $1$

Execution Trace:

Initially, at $t = 0$, the ready queue is: [A, B, C, D].

1. Interval $[0 - 1]$: $A$ executes for $1$ unit. Remaining burst of $A = 3$.
   Ready queue becomes: [B, C, D, A]
2. Interval $[1 - 2]$: $B$ executes for $1$ unit. Remaining burst of $B = 0$.
   $B$ completes at $t = 2$. Ready queue becomes: [C, D, A]
3. Interval $[2 - 3]$: $C$ executes for $1$ unit. Remaining burst of $C = 7$.
   Ready queue becomes: [D, A, C]
4. Interval $[3 - 4]$: $D$ executes for $1$ unit. Remaining burst of $D = 0$.
   $D$ completes at $t = 4$. Ready queue becomes: [A, C]
5. Interval $[4 - 5]$: $A$ executes for $1$ unit. Remaining burst of $A = 2$.
   Ready queue becomes: [C, A]
6. Interval $[5 - 6]$: $C$ executes for $1$ unit. Remaining burst of $C = 6$.
   Ready queue becomes: [A, C]
7. Interval $[6 - 7]$: $A$ executes for $1$ unit. Remaining burst of $A = 1$.
   Ready queue becomes: [C, A]
8. Interval $[7 - 8]$: $C$ executes for $1$ unit. Remaining burst of $C = 5$.
   Ready queue becomes: [A, C]
9. Interval $[8 - 9]$: $A$ executes for $1$ unit. Remaining burst of $A = 0$.
   $A$ completes at $t = 9$.

Thus, the completion time of job $A$ is $9$.