GATE CS 1998 Q2.17 — CPU Scheduling

To find the optimal quantum size $q$, let us analyze the worst-case waiting time for any process in a round-robin system with $n$ processes.

1. Calculating the Maximum Waiting Time

Suppose a process $P_1$ has just finished its current CPU quantum. Before $P_1$ can get its next turn at the CPU, all other $(n-1)$ processes must be scheduled and run for their respective quanta.

• Execution time of other processes: There are $(n-1)$ other processes, each running for at most $q$ seconds. Total execution time = $(n-1)q$ seconds.
• Context switch overhead: To cycle through all $n$ processes and return to $P_1$, there are exactly $n$ context switches (from $P_1 \to P_2$, $P_2 \to P_3$, ..., $P_n \to P_1$). Each switch takes $s$ seconds. Total switching overhead = $ns$ seconds.

Thus, the maximum time a process has to wait between the end of its current turn and the start of its next turn is:

2. Applying the Constraint

To guarantee that each process gets its turn at least every $t$ seconds, this waiting time must not exceed $t$ seconds:

Solving for $q$:

3. Minimizing Overhead

To minimize the overhead caused by frequent context switching, we want the time quantum $q$ to be as large as possible. However, to satisfy the response time guarantee, $q$ must respect the upper bound derived above.

Therefore, the required condition is:

Hence, the correct option is A.