CPU scheduling

Why this matters

There are always more processes than cores, so something has to decide who gets the CPU next and for how long. That decision is made thousands of times a second.

You can see the results with the naked eye: the interface stays responsive while a project compiles; nice -n 19 barely slows a background job down, while nice -n -20 noticeably speeds one up; a video call stutters when an archiver is running next to it, even though the CPU is nowhere near a hundred percent. All of this follows from how the scheduler makes its decision.

Prerequisites. Process states and the context switch (module 6), timer interrupts (module 2).

What we optimize

There is no best algorithm, because the goals contradict each other.

Metric	What it means	Who cares
Throughput	processes completed per unit of time	batch computation
Turnaround time	from start to completion	builds, rendering
Waiting time	how long a process sat in the ready queue	everyone
Response time	from an action to the first reaction	interactive programs
Fairness	nobody starves	multi-user systems

The easiest way to raise throughput is to run long jobs back to back and never switch at all. The easiest way to cut response time is to switch as often as possible. A scheduler always lives somewhere between these two extremes.

Classic algorithms

Three basic strategies on the same set of processes. Process A is long, B and C are short, and all of them are ready at time zero.

The total time is the same in all three cases, because the CPU did not get any faster. The only thing that changes is who has to wait.

FCFS (first-come, first-served) is a queue in its purest form. Simple and fair in order of arrival, but disastrous when a long job arrives first: two trivial processes wait 24 units each because of one job that isn’t theirs. This is called the convoy effect, where one long job collects a tail of short ones behind it.

SJF (shortest job first) runs the shortest jobs first. It is mathematically proven to give the minimum average waiting time, and at the same time it can’t be used in pure form. The length of the next job isn’t known in advance, and long processes will starve as long as short ones keep arriving.

Round Robin gives everyone one quantum, in a circle. It isn’t the best on average waiting time, but it is the only one of the three with a predictable response time: within one pass through the queue, everyone is guaranteed to get the CPU. Every interactive system is built on this idea.

The quantum size here is always a compromise. A large quantum degenerates the algorithm into FCFS; a small one improves response, but the share of CPU time spent on the context switches themselves quickly becomes unacceptable.

Preemptive and non-preemptive

A non-preemptive scheduler takes the CPU back only when a process gives it up on its own: it exits or blocks. A preemptive one can take it away at any time, relying on the timer interrupt. Without preemption a single infinite loop hangs the whole system, which is why all general-purpose systems are preemptive.

Multilevel feedback queues

MLFQ is the practical answer to the problem “SJF is ideal, but the lengths are unknown”. Instead of asking for the length, the scheduler watches behavior.

It works like this:

• processes are spread across several queues with different priorities;
• a new process goes into the highest one, because it is assumed to be short until proven otherwise;
• if it uses up its whole quantum without blocking, it moves down a level;
• if it blocks before the quantum ends, waiting for the disk, network or keyboard, it stays where it was.

Interactive processes spend most of their time waiting for input, so they naturally settle in the high queues and get fast response. Compute-bound ones eat whole quanta and sink down, where they get the CPU less often but in longer stretches, which is good for their caches.

So that long jobs don’t starve forever, every so often all processes are moved back up to the top. This is called aging.

How Linux does it today

Most courses stop at MLFQ, but Linux has moved on since.

CFS, the completely fair scheduler, was in use from 2007 to 2023 and did away with fixed queues and quanta. Instead, for each process it tracked virtual runtime, that is, how much CPU the process had already received, adjusted for its weight, and always ran the process with the smallest value. Processes with a lower weight accumulate virtual time faster and come back less often, and nice sets exactly this weight.

In kernel 6.6, CFS was replaced by EEVDF, earliest eligible virtual deadline first. The difference is that EEVDF considers not only overall fairness but also urgency: each process is assigned a virtual deadline, and the one with the nearest deadline goes first. Interactive tasks that need short, frequent slices get the CPU sooner, and the overall balance doesn’t suffer for it.

On top of that, Linux has scheduling classes, and they matter more than any priority within a class:

Class	What for
SCHED_OTHER	ordinary processes, managed by EEVDF
SCHED_BATCH	computation with no response-time requirements
SCHED_IDLE	runs only when nobody else wants to
SCHED_FIFO, SCHED_RR	real time: preempt everything in SCHED_OTHER
SCHED_DEADLINE	tasks with an explicitly set period and deadline

A real-time process with priority 1 always beats a SCHED_OTHER process with nice -20. These are different leagues, and priorities in one class aren’t compared with priorities in another.

Scheduling on many cores is a different problem

Everything above is about a single CPU. With 64 cores, questions come up that classic theory doesn’t have at all: keep a queue per core, or one shared queue that doesn’t scale because of lock contention; move a process to an idle core or leave it on its own, where the caches are still warm; what to do when the process’s memory is attached to another socket; and whether it pays to pack all the work onto a few cores so the rest can sleep and save battery.

How it actually works in Linux

chrt -p $$

The scheduling class and priority of the current shell. For an ordinary process this is SCHED_OTHER with priority 0.

ps -eo pid,cls,rtprio,ni,pri,comm --sort=-rtprio | head

CLS shows the class (TS ordinary, FF/RR real time, IDL), RTPRIO shows the real-time priority, NI the nice value.

cat /proc/$$/sched | head -12

Scheduler statistics for the process: sum_exec_runtime shows how much CPU time it has used, nr_switches counts how many times it was switched, and nr_involuntary_switches how many of those were preemptions.

grep -E 'ctxt|processes|procs_' /proc/stat

ctxt shows the total number of context switches since boot. Two samples with a pause between them give the switch rate. This is a useful indicator when the system is “busy but doing nothing”.

taskset -c 0 nice -n 19 sh -c 'while :; do :; done' &
sleep 3; ps -o pid,psr,ni,pcpu,comm -p $!; kill $!

The process is pinned to core zero with the lowest priority. PSR shows which core it is actually running on.

Common misconceptions

“nice sets a percentage of the CPU.” It doesn’t: nice changes the process’s weight relative to others, so if there are no competitors, a process with nice 19 will happily get the full hundred percent, since there is simply no one to share with.

“The scheduler chooses what to run.” It chooses only among ready processes. A blocked process doesn’t take part in the choice at all, whatever its priority.

“A high priority will speed the process up.” Only if the process is waiting for the CPU. When it is waiting for the disk, the scheduling priority changes nothing, and what you need is I/O priority, that is, ionice.

“Real time means fast.” It means predictable. SCHED_FIFO guarantees that ordinary tasks won’t preempt the process, which is why a real-time task stuck in a loop can hang the system: nobody can stop it.

“The smaller the quantum, the better the response.” Up to a point, yes, but beyond it the switching overhead starts eating the very CPU time you were trying to share more fairly.

Check yourself

1. Three processes are ready at the same time: A needs 24 units of time, B and C need 3 each. Which order gives the lowest average waiting time?

A, B, CB, C, AThe order makes no differenceA, C, B

2. Why is SJF not used in pure form in general-purpose systems?

It gives the worst average waiting timeThe length of a job is not known in advance, and long processes starveIt does not work on multi-core CPUsIt needs too much memory

3. In MLFQ, a process that always blocks on I/O before its quantum ends stays in a high queue. Why?

To make up for a slow diskThis behavior is typical of interactive tasks, and they need fast responseTo reduce the number of interruptsSo that it does not take up memory

4. A process with SCHED_FIFO and priority 1, and a process with SCHED_OTHER and nice -20. Which one gets the CPU?

SCHED_OTHER, because nice -20 is the highest prioritySCHED_FIFO: real-time classes preempt ordinary ones regardless of niceThey take turns, equallyIt depends on the number of cores

5. Why isn't the time quantum made very small, even though that would improve response time?

The hardware timer does not support small intervalsThe share of CPU time spent on the context switches themselves and on warming up caches growsProcesses start to starveFairness goes down

6. A process is marked nice 19 but uses 100% of one core. Is that a bug?

Yes, nice 19 limits the process to 5% of the timeNo: nice sets a weight relative to competitors, and with no competitors there is no one to share withYes, the scheduler needs to be restartedNo, because nice only works for real-time processes

Lab

A2: a scheduler simulator. FCFS, SJF, RR and MLFQ on the same set of tasks, computing waiting, turnaround and response times. The goal: to see that no configuration wins on every metric at once.

Sources

• OSTEP, Scheduling: Introduction and MLFQ
• Silberschatz, Operating System Concepts, chapter 5
• man 7 sched, man 1 chrt, man 1 nice, man 2 sched_setscheduler
• Documentation/scheduler: including a description of EEVDF
• An EEVDF CPU scheduler for Linux: LWN on replacing CFS