Scheduling Simulator: FCFS, Round Robin, Priority

The simulator has 1–4 CPUs and six processes P1–P6. Each process is a script: run for N ms, then sleep or wait on I/O for M ms, then run again, until its total work is done. Every process is in exactly one state — running (on a CPU), ready (runnable, waiting for a CPU), sleeping (timer wait) or waiting (blocked on I/O) — and the timeline shows which CPU ran which process in each millisecond tick. The numbers are ticks of a model, not measurements; a real kernel’s tick, its wakeup preemption rules and its cache effects are all absent by design.

The three policies are the textbook ones, chosen because each isolates one idea. FCFS (first-come, first-served): run the head of the queue until it blocks or finishes. Round Robin: run the head of the queue for at most one quantum, then move it to the tail. Priority: always run the runnable process with the highest priority, preempting a lower-priority one when a higher one becomes ready. No production general-purpose kernel uses any of these unmodified; they are the vocabulary in which real schedulers are described (see the Linux section of The Scheduling Problem).

Three metrics are computed per process and averaged: waiting time (ms spent in ready), turnaround time (arrival to completion) and response time (arrival to first run). Interactive systems care about response time; batch systems care about turnaround; both hate high variance more than a high mean.

Put P1 (a 40 ms CPU burst) at the head of the queue on a single CPU, followed by P2–P6 that each want 1 ms of CPU before doing 10 ms of I/O. Under FCFS the five short processes wait 40 ms for P1, run for 1 ms each, go to I/O, and by the time they come back P1 — which also went to I/O and came back — is at the head again. The I/O device sits idle while everybody waits for the CPU, then the CPU sits idle while everybody waits for the device. This is the convoy effect: one long burst turns a set of independent I/O-bound processes into a convoy trailing behind it.

The response time numbers make it concrete: with the simulator on one CPU, average response time under FCFS is dominated by the longest burst in front of you, regardless of how little you need. Adding CPUs helps only until there are more long bursts than CPUs. The policy is not unfair in the accounting sense — everyone eventually runs — but it is blind to how much each process needs, and that blindness is what preemption fixes.

FCFS survives in real systems in one place: disk and network request queues, where reordering has its own costs. For CPU scheduling it is the baseline every other policy is measured against.

Round Robin fixes the convoy by preemption: P1 gets a quantum, then goes to the tail, and P2–P6 each get theirs. Response time drops from "the longest burst ahead of you" to "at most (n − 1) × quantum". Set the quantum to 4 ms in the simulator and the short processes respond within 20 ms instead of 40; set it to 1 ms and they respond within 5.

Now count the context switches. At a 1 ms quantum P1’s 40 ms burst is cut into 40 slices, each preceded by a switch; the simulator charges a configurable switch cost (default 0.1 ms, a model value — real switches are 1–5 µs direct plus cache effects, see Context Switching), so P1’s effective run time grows and everyone’s turnaround with it. At a 100 ms quantum Round Robin degenerates into FCFS. Somewhere in between is a quantum that keeps switch overhead under a few percent while bounding response time — which is why real kernels derive the slice from a latency target and the number of runnable tasks rather than fixing it.

Round Robin is fair in the strict sense: every runnable process gets 1/n of the CPU in every round. It is also completely priority-blind, which is a problem the moment one process matters more than another.

Give P1 priority 1 (highest) and a script that runs 5 ms, sleeps 1 ms, repeats forever, and give P6 priority 6 with a 20 ms burst. Under strict priority scheduling P6 never runs: every time it is about to, P1 wakes up and preempts it. This is starvation, and it is not a corner case — any strict-priority scheduler with a busy high-priority task starves the rest. The simulator shows P6’s waiting time climbing without bound while the CPU reads 100% busy.

The standard fix is aging: raise the effective priority of a process the longer it waits, so that eventually even P6 outranks a freshly woken P1 for one slice. The simulator’s aging toggle adds one priority level per 10 ms of waiting; watch P6 finally get its slice, then drop back. Windows implements exactly this idea as a periodic pass that boosts threads that have not run for several seconds; Linux’s fair-share accounting makes explicit aging unnecessary because a task that has not run has a large lag and is always eligible.

A subtler failure is priority inversion: a low-priority process holds a lock the high-priority one needs, and a medium-priority process preempts the low one — so the high-priority task waits on the medium one. This is what hung the Mars Pathfinder lander in 1997; the fix (priority inheritance: the lock holder temporarily takes the waiter’s priority) is implemented in pthread_mutexattr_setprotocol and Linux PI-futex. See Mutexes and Deadlocks.

The comparison below is the point of the simulator. No single policy wins every column, which is why real schedulers combine ideas: preemption from Round Robin, weight from priority, and an accounting rule (fair share, aging, or boosts) that prevents starvation.