Question
Consider an arbitrary set of CPU-bound processes with unequal CPU burst lengths submitted at the same time to a computer system. Which one of the following process scheduling algorithms would minimize the average waiting time in the ready queue?
Official answer and solution
- Official answer
- A
- From
- Official GATE 2016 answer key
Solution
Recall the optimality theorem of Shortest Job First / Shortest Remaining Time First for average waiting time.
When all processes arrive at the same time (), preemptive SRTF behaves identically to non-preemptive Shortest Job First (SJF) because all processes are immediately available in the ready queue.
By scheduling the process with the shortest CPU burst first, the waiting times of all subsequent processes are accumulated in increasing order of burst lengths. Mathematical proof by exchange argument confirms that SJF/SRTF yields the provably minimum average waiting time among all scheduling algorithms.
Round-robin introduces context switching overhead and spreads completion times across all processes, increasing average waiting time. Thus, Shortest Remaining Time First minimizes average waiting time.
A
Thinking Round-Robin minimizes waiting time, confusing responsiveness (response time) with average waiting time.
The answer is the one in the official GATE answer key. The solution is this site's own explanation.
Source
- Paper
- GATE 2016 Computer Science and Information Technology (CS) Session 1
- Question
- 30 of 65, printed as CS Q.20
- 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.