The GATE Grind

GATE 2016 CS – Question 30

Operating System · CPU and I/O Scheduling · 1 mark · Multiple choice

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?

  1. Shortest remaining time first
  2. Round-robin with time quantum less than the shortest CPU burst
  3. Uniform random
  4. Highest priority first with priority proportional to CPU burst length

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) Shortest remaining time first

Explanation

Running the shortest job first gives the minimum possible average waiting time. When all processes arrive together, shortest remaining time first behaves exactly like shortest job first. Round-robin and random order keep long jobs ahead of short ones, and giving priority to longer bursts does the opposite of what is wanted.