A scheduling algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero (the lowest priority). The scheduler re-evaluates the process priorities every T time units and decides the next process to schedule. Which one of the following is TRUE if the processes have no I/O operations and all arrive at time zero?
A. This algorithm is equivalent to the first-come first-served algorithm.
B. This algorithm is equivalent to the round-robin algorithm.
C. This algorithm is equivalent to the shortest-job-first algorithm.
D. This algorithm is equivalent to the shortest-remaining-time-first algorithm.
GATE 2013 · Operating System · Process Scheduling · medium
Answer: B. This algorithm is equivalent to the round-robin algorithm.
Analyze the state at each re-evaluation: At t=0: all n processes have priority 0. Suppose P1 is selected (ties broken arbitrarily).
At t=T: P1 has run T units (waiting time = 0). All other processes have waited T units (priority = T). Any of P2..Pn is selected — say P2.
At t=2T: P2 has run T units (waiting = 0). P1 has now waited T units (priority = T). P3..Pn have waited 2T (priority = 2T). One of P3..Pn is selected.
Identify the equivalent algorithm: Each process receives exactly T time units of CPU in each cycle before any other process gets a second slice. The rotation order respects 'longest waiting first', which in the all-arrive-at-t=0 scenario simply cycles through all processes in order. This is exactly Round Robin with time quantum T.
Rule out other options: A (FCFS): FCFS runs each process to completion, not in T-unit slices — ruled out.
C (SJF): SJF picks shortest burst, not longest waiting — ruled out.
D (SRTF): SRTF picks shortest remaining time — ruled out.
B (RR): Matches exactly — each process gets T-unit slices in rotation.