SRTF, Round Robin, and choosing the quantum

Under SJF the compile job started at 0 ms and held the core for its full 8 ms, because nothing else had arrived yet.

But at 1 ms the music player turned up needing only 2 ms.

The compile job had 7 ms of work left. The music player had 2 ms of work total. Refusing to interrupt is, in hindsight, obviously wrong.

So: allow the interruption.

Why & what

SRTF — shortest remaining time first. This is preemptive SJF. Every time a new process arrives, compare its burst against the remaining time of the running process. If the newcomer is shorter, preempt.

On our snapshot the compile job runs for exactly 1 ms before the music player throws it off the core.

• Average turnaround: 6.5 ms (SJF managed 9.5, FCFS 10.75)
• Average waiting: 2.5 ms
• But the compile job's own waiting time rises to 8 ms — it now waits longer than its own burst.

SRTF gives the best average of any algorithm here. It also has SJF's fatal flaw — it needs to know burst lengths — plus a new one: long jobs get pushed back every time anything short arrives.

Round Robin. Now drop the idea of knowing burst lengths entirely.

Round Robin gives every process a fixed turn, called the time quantum or time slice. On the Nova-14 it is 4 ms. When your quantum expires, the timer interrupt fires, you go to the back of the ready queue, and the next process runs.

That is the whole algorithm. It needs to know nothing about any process.

Its properties:

• No starvation. With n processes in the queue, nobody waits more than (n − 1) quanta for a turn. That is a hard guarantee.
• Good response time. Everyone gets a turn quickly, even if they finish slowly.
• Worse turnaround than SJF. Jobs are cut into pieces, so almost everyone finishes later.

On our snapshot with a 4 ms quantum: average turnaround 10.5 ms, average response 3.5 ms. Choosing the quantum. This is where the 5 µs from Topic 2.3 comes back.

• Quantum too large: nobody is ever cut off, and Round Robin silently becomes FCFS. With an 8 ms quantum our snapshot produces exactly the FCFS schedule, millisecond for millisecond.
• Quantum too small: great response times, but the 5 µs switching cost is paid constantly. With a 50 µs quantum the CPU spends 50 out of every 55 µs doing real work — 9% of the machine burned on switching.

The rule of thumb: the quantum should be comfortably larger than a context switch, and large enough that most I/O-bound bursts finish inside one turn. 4 ms against a 5 µs switch is about 0.1% overhead, which is why real systems land in the low milliseconds.

How it works

Simulating Round Robin, which is the version most likely to appear in an exam:

1. Keep a queue. Add processes as they arrive.
2. Take the front process and run it for min(quantum, remaining time).
3. Add any process that arrived during that turn to the back of the queue.
4. If the process still has work left, put it at the back — after the new arrivals from step 3. Getting this order wrong is the single most common mistake.
5. Repeat until every process is finished, then read completion times off the chart.

Common confusion

"Round Robin has the best response time, so it is the best algorithm." It has boundedresponse time, which is different and more valuable. SRTF beat it on every average in our snapshot. Round Robin's real selling point is that it makes a promise it can always keep, without knowing anything about the future.

"A preempted process goes back to the front." It goes to the back. If it went to the front it would run forever and nothing else would ever get a turn.

"SRTF and SJF are the same." They pick differently. SJF compares full burst lengths and only chooses when the core is free. SRTF compares remaining time and re-checks every time a process arrives. The word "remaining" is the whole difference, and it is worth saying out loud in an interview.

"Round Robin with a huge quantum is still Round Robin." In name only. Our 8 ms row proves it: the schedule is identical to FCFS. If no process is ever cut off, there is no rotation.

Interview angle

"What happens if the time quantum is too large or too small?" This is the most common Round Robin question, and the answer is two sentences: too large and it degenerates into FCFS; too small and context switch overhead dominates. Quote a number if you can — a 5 µs switch against a 4 ms quantum is 0.1% overhead; against a 50 µs quantum it is 9%.

"Which algorithm gives the best average waiting time?" SRTF. Then immediately add the qualifier, because the follow-up is always coming: it needs burst lengths in advance, and it can starve long jobs.

"Why does Round Robin avoid starvation?" Because the queue rotates, so with n processes your wait is bounded by (n − 1) quanta. Fixed guarantee, no assumptions.