18/32 · 6 min

Deciding who runs next

More runnable processes than cores means choosing. Each rule optimises something different, and each is unfair in its own way.

First come, first served

Run them in arrival order until each finishes. Simple, and it has the convoy effect: one long job at the front delays everything behind it.

code

arrive:  A(24ms)  B(3ms)  C(3ms)
order:   A......................  B...  C...
wait:    A=0  B=24  C=27          average 17ms

Reverse the order and the average wait drops to 3ms for the same work.

Shortest job first

Always run the shortest remaining job. This is provably optimal for average waiting time, and it has two problems: it needs to know the run times in advance, which nobody does, and long jobs starve while short ones keep arriving.

Real schedulers estimate the next burst from recent history, which works because process behaviour is fairly stable over short periods.

Round robin

Each process gets a fixed time slice, then goes to the back of the queue.

The slice length is the whole design:

Slice	Effect
Very short	excellent responsiveness, overhead dominates
Very long	efficient, degenerates into first come first served
Typical	10ms to 100ms

Round robin is fair and is the reason a machine stays responsive while compiling.

Priority, and the trap

Run the highest priority first. Low priority work can then starve indefinitely, and the standard fix is ageing: raise a process's priority the longer it waits, so everything eventually runs.

Multilevel feedback queues

What real systems use. Several queues at different priorities, with a rule for moving between them:

code

new process -> highest priority queue, short slice
uses its whole slice  -> demoted, it is CPU bound
blocks before the end -> stays high, it is interactive
waits too long        -> promoted, ageing

This gets shortest job first's benefit without knowing run times in advance. A process that blocks quickly is interactive and is kept responsive; one that never blocks is batch work and is demoted where it does not hurt anyone.

Algorithm	Optimises	Starves
FCFS	nothing, simplest	no
SJF	average wait	long jobs
Round robin	response time	no
Priority	importance	low priority
MLFQ	both, adaptively	no, with ageing

Preemptive or not

Preemptive means the scheduler can interrupt a running process. Non preemptive means it runs until it blocks or finishes. Every general purpose system is preemptive, because otherwise one program that never yields freezes the machine, which is exactly what early cooperative systems did.