GATE CS 2013 Q.10 (CS Q.10): CPU Scheduling

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?

This algorithm is equivalent to the first-come-first-serve algorithm.

This algorithm is equivalent to the round-robin algorithm.

This algorithm is equivalent to the shortest-job-first algorithm.

This algorithm is equivalent to the shortest-remaining-time-first algorithm.

Official answer and solution

Official answer: B
From: Official GATE 2013 answer key

Solution

Trace the dynamic priority changes over successive time slices of duration T.

All processes arrive at time 0 with priority 0, and have no I/O operations.

At time $t = 0$ , all processes have priority 0. The scheduler selects one process $P_1$ to run for duration $T$ .
During interval $[0, T]$ , process $P_1$ executes, so its waiting time remains 0 (priority remains 0).
All other processes are waiting in the ready queue, so their waiting times increase by $T$ , increasing their priorities to $T$ .
At $t = T$ , the scheduler re-evaluates priorities. The waiting processes all have higher priority ( $T$ ) than $P_1$ (priority 0).
The scheduler picks one of the waiting processes (say $P_2$ ) to run for duration $T$ .
During $[T, 2T]$ , $P_2$ executes, while all other processes (including $P_1$ ) accumulate waiting time.
In this manner, every process runs for one time slice of duration $T$ before any previously executed process can run again.

This behavior is identical to Round-Robin scheduling with time quantum $T$ .

Final answer

Option (B)

Common trap

Confusing this with FCFS, but because all processes arrived at time 0 and execution is interrupted every $T$ , it cycles periodically like Round-Robin.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2013 Computer Science and Information Technology (CS)
Question: 10 of 65, printed as CS Q.10
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source