GATE CS 2003 Q77 — CPU Scheduling

To find the scheduling strategy that results in the least CPU utilization, let us analyze the execution timelines for the processes $P_1$ and $P_2$ under the given strategies. Each process has a CPU burst of $10\text{ ms}$ and an I/O burst of $90\text{ ms}$.

1. FCFS, SRTF, and Static Priority Scheduling:

Under these non-preemptive or priority-based schemes, one process completes its entire CPU burst before the other starts:

• At $t = 0$, $P_1$ runs on the CPU until $t = 10\text{ ms}$, then goes for I/O (ready at $t = 100\text{ ms}$).
• At $t = 10\text{ ms}$, $P_2$ runs on the CPU until $t = 20\text{ ms}$, then goes for I/O (ready at $t = 110\text{ ms}$).
• The CPU remains idle from $t = 20\text{ ms}$ to $t = 100\text{ ms}$.
• At $t = 100\text{ ms}$, $P_1$ returns and the cycle repeats.

The total cycle length is $100\text{ ms}$ (from $t = 100$ to $t = 200$), during which the CPU is busy for $20\text{ ms}$ ($10\text{ ms}$ for $P_1$ and $10\text{ ms}$ for $P_2$).

2. Round Robin (RR) with Time Quantum = $5\text{ ms}$:

Because of preemption, the execution interleaves:

• $t = 0 \text{ to } 5\text{ ms}$: $P_1$ runs (remaining = $5\text{ ms}$).
• $t = 5 \text{ to } 10\text{ ms}$: $P_2$ runs (remaining = $5\text{ ms}$).
• $t = 10 \text{ to } 15\text{ ms}$: $P_1$ runs and finishes, going to I/O (ready at $15 + 90 = 105\text{ ms}$).
• $t = 15 \text{ to } 20\text{ ms}$: $P_2$ runs and finishes, going to I/O (ready at $20 + 90 = 110\text{ ms}$).
• The CPU is idle from $t = 20\text{ ms}$ to $t = 105\text{ ms}$.
• At $t = 105\text{ ms}$, $P_1$ returns and runs until $t = 110\text{ ms}$ (remaining = $5\text{ ms}$).
• At $t = 110\text{ ms}$, $P_2$ returns. Since $P_1$ has completed its $5\text{ ms}$ quantum, a context switch occurs. $P_2$ runs from $t = 110 \text{ to } 115\text{ ms}$ (remaining = $5\text{ ms}$).
• $t = 115 \text{ to } 120\text{ ms}$: $P_1$ finishes and goes to I/O (ready at $120 + 90 = 210\text{ ms}$).
• $t = 120 \text{ to } 125\text{ ms}$: $P_2$ finishes and goes to I/O (ready at $125 + 90 = 215\text{ ms}$).

The repeating cycle now runs from $t = 105\text{ ms}$ to $t = 210\text{ ms}$, which has a duration of $105\text{ ms}$. During this cycle, the CPU is active for $20\text{ ms}$ (from $t = 105$ to $t = 125$).

Since $19.05\% < 20\%$, Round Robin scheduling with a time quantum of $5\text{ ms}$ results in the least CPU utilization.