GATE CS 2006 Q65 — CPU Scheduling

First, we break down the execution phases for each process based on their total execution times:

• $P_1$ (10 units):
  • First I/O: $10 \times 20\% = 2$ units
  • CPU computation: $10 \times 70\% = 7$ units
  • Second I/O: $10 \times 10\% = 1$ unit
• $P_2$ (20 units):
  • First I/O: $20 \times 20\% = 4$ units
  • CPU computation: $20 \times 70\% = 14$ units
  • Second I/O: $20 \times 10\% = 2$ units
• $P_3$ (30 units):
  • First I/O: $30 \times 20\% = 6$ units
  • CPU computation: $30 \times 70\% = 21$ units
  • Second I/O: $30 \times 10\% = 3$ units

Now, we trace the scheduling timeline using the Shortest Remaining Compute Time First (SRCTF) algorithm:

• $t = 0$ to $t = 2$: All three processes are performing their first I/O. The CPU remains idle (2 units).
• At $t = 2$: $P_1$ completes its first I/O and starts its CPU computation (remaining compute = 7).
• At $t = 4$: $P_2$ completes its first I/O (remaining compute = 14). Since $P_1$ has a shorter remaining compute time ($5 < 14$), $P_1$ continues.
• At $t = 6$: $P_3$ completes its first I/O (remaining compute = 21). $P_1$ continues.
• At $t = 9$: $P_1$ finishes its CPU computation and starts its second I/O (finishes at $t = 10$). $P_2$ is scheduled next as its remaining compute time (14) is less than $P_3$'s (21).
• At $t = 23$: $P_2$ finishes its CPU computation and starts its second I/O (finishes at $t = 25$). $P_3$ is scheduled.
• At $t = 44$: $P_3$ finishes its CPU computation and starts its second I/O.
• $t = 44$ to $t = 47$: $P_3$ performs its second I/O. The CPU remains idle (3 units).
• At $t = 47$: All processes have completely finished.

Calculations:

• Total time of the system = $47$ units
• Total CPU idle time = $2 \text{ (at start)} + 3 \text{ (at end)} = 5$ units
• Percentage of CPU idle time = $\frac{5}{47} \times 100\% \approx 10.64\%$