Consider an arbitrary set of CPU-bound processes with unequal CPU burst…
2016
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?
- A.
Shortest remaining time first
- B.
Round-robin with time quantum less than the shortest CPU burst
- C.
Uniform random
- D.
Highest priority first with priority proportional to CPU burst length
Attempted by 404 students.
Show answer & explanation
Correct answer: A
Answer: Shortest remaining time first
Why this minimizes average waiting time:
Key idea: scheduling shorter jobs before longer ones reduces the time other jobs spend waiting.
Sketch of the exchange argument: if two jobs of lengths a and b (a < b) are run with the longer job first, swapping their order reduces total waiting time by (b - a). Repeating such swaps leads to an order from shortest to longest, which is optimal.
With all processes arriving at the same time, the preemptive shortest remaining time first policy implements this principle dynamically and therefore minimizes average waiting time.
A video solution is available for this question — log in and enroll to watch it.