A scheduling algorithm assigns priority proportional to the waiting time of a…
2013
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-serve 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
Attempted by 264 students.
Show answer & explanation
Correct answer: B
Answer: This algorithm is equivalent to the round-robin algorithm with time quantum T.
Explanation: Priority is proportional to waiting time and is re-evaluated every T time units.
All processes arrive at time zero and start with equal (zero) priority.
At the first scheduling point a tie is broken arbitrarily and one process runs for T time units.
When priorities are re-evaluated after T, the process that just ran has a much smaller waiting time than the others, so its priority is lower; the other processes have larger waiting times and higher priorities.
The scheduler therefore selects a different process to run for the next T time units. Repeating this produces a cyclic rotation where each process receives the CPU for T units in turn.
Thus the observable behavior is identical to round-robin scheduling with time quantum T. Initial tie-breaking does not change the long-term cyclic time-slicing because waiting-time–based priorities force rotation.
A video solution is available for this question — log in and enroll to watch it.