GATE CS 2013 Q10 — CPU Scheduling

We are given that the priority of a process is directly proportional to its waiting time:

$$\text{Priority} \propto \text{Waiting Time}$$

Let there be $n$ processes $P_1, P_2, \dots, P_n$ that all arrive at time $t = 0$. Initially, their waiting times are all $0$, so they all start with the lowest priority ($0$).

Let's trace the scheduling decisions made every $T$ time units:

1. At $t = 0$: All processes have a waiting time of $0$. The scheduler breaks the tie and selects one process, say $P_1$, to run for $T$ time units.
2. At $t = T$:
   • $P_1$ has been running, so its waiting time is $0$.
   • The remaining processes $P_2, \dots, P_n$ have been waiting in the ready queue, so their waiting time is $T$.
   Since $P_2, \dots, P_n$ have a higher waiting time ($T > 0$), they have a higher priority than $P_1$. The scheduler will select one of these waiting processes, say $P_2$, to run for the next $T$ time units.
3. At $t = 2T$:
   • $P_2$ has just finished running, so its accumulated waiting time since its last run is $0$.
   • $P_1$ has waited for $T$ time units (from $t = T$ to $2T$).
   • The remaining processes $P_3, \dots, P_n$ have waited for $2T$ time units.
   The processes that have not run at all ($P_3, \dots, P_n$) have the highest priority, followed by $P_1$, and $P_2$ has the lowest priority. The scheduler will pick one of the processes that has not run yet.

This pattern continues: each process is allocated exactly $T$ time units of CPU time in a cyclic order. Once all processes have run once for $T$ units, the cycle repeats. This behavior is identical to the Round-Robin (RR) scheduling algorithm with a time quantum of $T$.

Therefore, the correct option is B.