CPU Scheduling Primer

On a busy server you might have 32 cores and 800 runnable threads at any given moment. The scheduler must decide, every ~1 ms (the CFS scheduling tick), which 32 threads run next. Every choice has consequences:

• Fairness. Equal threads should get equal CPU over time — but what is "equal"? Equal cycles? Equal wall-clock time? Equal weighted by priority?
• Throughput. The system should maximise useful work. Switching too often wastes time on overhead; switching too rarely starves I/O-bound tasks.
• Latency. An interactive task that just got input should run soon, even if it's been getting more than its share — the user is waiting.
• Priority. A real-time audio thread missing a deadline produces a click in the speakers; a backup job running 5% slower doesn't matter. These cannot be treated equally.
• Affinity. A thread's cache state lives on the core it last ran on. Bouncing it to a different core costs ~100 μs of cold-cache regret. But pinning it loses load-balancing.
• Power. On a phone or laptop, waking a sleeping core costs milliseconds of latency and energy. Consolidating work on already-awake cores beats spreading it across all available ones.

These goals conflict. Optimising for throughput hurts latency. Strict priority starves low-priority tasks. Perfect affinity loses load balance. Every production scheduler is a compromise that picks one set of trade-offs as the default.

A brief history

Round-robin (1970s–80s). Each task gets a fixed time slice (10–100 ms), then yields. Simple and fair, but unresponsive — an interactive task that just got a keypress waits behind a queue of compute-bound jobs.

Multilevel feedback queues (Unix, BSD, early Linux). Multiple priority queues; tasks move between them based on observed behaviour (CPU-bound tasks drop down, I/O-bound tasks rise up). Better latency, but tuning the policy is an art that varied per Unix flavour.

O(1) scheduler (Linux 2.6, 2003). Per-CPU runqueues, two priority arrays (active and expired), array-walk to find the highest-priority runnable task. Fast on the single-CPU benchmark of the day, but tuning the heuristics was a constant battle.

CFS (Linux 2.6.23, 2007 onward). Replaces heuristic priority boosting with one mathematical rule: "pick the task with the smallest virtual runtime." The next section walks through it.

EEVDF (Linux 6.6, 2023). Replaces CFS with a more flexible scheduler based on the "earliest eligible virtual deadline first" algorithm. Same principle (vruntime) but with better latency guarantees and a cleaner formulation. Still being rolled out; most production kernels at time of writing still use CFS.

Every runnable task has a counter called vruntime, measured in nanoseconds. When a task runs, its vruntime increases — at the wall-clock rate for a nice-0 task, faster for lower priorities, slower for higher. The scheduler keeps tasks in a red-black tree keyed by vruntime, so the leftmost (smallest-vruntime) task can be found in O(log n). That task runs next.

How nice maps to vruntime rate

Linux defines a weight table: nice 0 = weight 1024, each step of nice ±1 changes weight by a factor of ~1.25. Nice +10 ≈ weight 110 (about 9× less), nice -5 ≈ weight 3121 (about 3× more), nice -20 ≈ 88761 (about 87× more).

The vruntime increment for a running task is actual_runtime × (NICE_0_LOAD / task.weight). So a nice-0 task accumulates vruntime at the wall-clock rate. A nice-10 task accumulates ~9× faster — meaning it has to wait until everyone else catches up before being picked again, so it gets ~1/9 the wall-clock share. A nice-(-20) task accumulates ~87× slower, so it dominates the schedule.

Multiplication is the key word. Strict priority would mean "the higher priority task always runs first" — which starves the low one. CFS weights vruntime accumulation, so both tasks always make progress; the higher-priority one just makes proportionally more.

Latency targets and minimum granularity

CFS defines a target latency (default 6 ms on most configurations) — every runnable task should get to run within this window. Divide the latency by the number of runnable tasks to get each task's slice. With 3 equal-nice tasks that's 2 ms each; with 30 it would be 0.2 ms — but that would crush throughput on context-switch overhead. CFS enforces a minimum granularity (default 0.75 ms): no task gets a slice shorter than this, even if it means extending the target latency.

So with 30 runnable tasks: latency stretches to 30 × 0.75 = 22.5 ms instead of staying at 6. This is one of the reasons CFS feels less responsive under high load — the actual latency promise is bounded only by the number of runnable threads.

Wake-up preemption

When a task wakes up (e.g. its I/O finished, or another task did apthread_cond_signal), CFS checks whether its vruntime is small enough that it "deserves" to preempt the currently-running task. If yes — and the running task has been running for at least the minimum granularity — the kernel schedules a switch. This is the mechanism that makes interactive tasks responsive: a thread blocked on a network read accumulates no vruntime while it's sleeping, so when the read returns it has a very low vruntime and immediately gets to run.

What CFS doesn't do

CFS treats all SCHED_NORMAL (a.k.a. SCHED_OTHER) tasks. It does not handle real-time tasks — those are handled by separate scheduling classes (SCHED_FIFO, SCHED_RR, SCHED_DEADLINE) covered in the next section. Real-time tasks always preempt SCHED_NORMAL, regardless of vruntime; CFS only picks once the real-time queues are empty.

Each Linux task belongs to one scheduling class. From highest priority to lowest:

• SCHED_DEADLINE — earliest deadline first with bandwidth enforcement. Each task declares (runtime, deadline, period); the scheduler admits it only if total bandwidth fits, then guarantees it runs runtime within every period before its deadline. Used for hard real-time: industrial control, autonomous-vehicle stacks, low-latency audio pipelines.
• SCHED_FIFO — fixed priority, runs to completion or until it blocks. Higher-priority FIFO tasks always preempt lower ones. No time slicing among same-priority tasks. The classic "real-time" policy from POSIX. Audio servers (JACK), some game engines, robotics.
• SCHED_RR — like FIFO but with a round-robin time slice among same-priority tasks. Same-priority RR tasks alternate; different priorities still strict.
• SCHED_NORMAL (a.k.a. SCHED_OTHER) — CFS. What 99% of everything runs under.
• SCHED_BATCH — like NORMAL but hints to the scheduler that the task is CPU-bound, suppressing wake-up preemption. Used for background compilation, big-data jobs.
• SCHED_IDLE — lowest possible priority within CFS. Only runs when no other SCHED_NORMAL task wants to. Cron jobs, garbage collectors of last resort.

Nice — the SCHED_NORMAL knob

Within SCHED_NORMAL, nice tunes the priority weighting. Range -20 (highest weight) to +19 (lowest). The default is 0. Each unit changes the weight by ~1.25×; the cumulative range is roughly 1000×. Most code never touches nice — the scheduler handles it. The exceptions:

• nice 19 for background compilation or batch jobs so they yield to interactive work. The classic nice -n 19 make idiom.
• nice -10 or lower (requires CAP_SYS_NICE) for low-latency server processes that need preemption priority but not hard real-time guarantees. Database master processes, network packet processors.

The real-time risk

A SCHED_FIFO task that doesn't block can starve the entire system. The scheduler will not preempt it for anything (except a higher-priority FIFO task, kernel work like interrupts, or another SCHED_DEADLINE deadline). A bug like while (true); in a SCHED_FIFO task locks up the machine — no shell, no logging, no SSH login can recover it short of a reboot.

Linux mitigates this with sched_rt_runtime_us: by default the real-time scheduler is allowed at most 95% of any 100 ms window, leaving 5 ms for SCHED_NORMAL. This is what lets you recover from a runaway real-time task. Anyone deploying SCHED_FIFO should know this setting.

cgroup CPU controls — orthogonal to scheduling class

cgroups (covered next) impose a second layer on top of the scheduling class: CPU shares (proportional weight), CPU quota (hard cap), CPU set (allowed cores). A SCHED_NORMAL task in a cgroup with quota 50% of one core will get throttled regardless of how much CPU time it would otherwise deserve. This is how containers limit CPU.

cgroups in 90 seconds

Control groups (cgroups) are a kernel mechanism for grouping processes and applying resource limits to the group as a whole. cgroup v2 (the default on every modern distro) exposes a hierarchical filesystem at /sys/fs/cgroup/; each directory is a group, each file in it is a knob.

For CPU specifically, three controls matter:

• cpu.weight — proportional share, similar to nice. A cgroup with weight 200 gets twice the CPU share of one with weight 100 when both are competing. If only one cgroup has runnable work, it gets the whole CPU.
• cpu.max — absolute hard cap, expressed as "quota / period" in microseconds. cpu.max = "50000 100000" means "at most 50 ms of CPU per 100 ms wall-clock" — half a core. This is what Docker / Kubernetes --cpus=0.5 translates to.
• cpuset.cpus — set of allowed CPUs. cpuset.cpus = "0-7" means the cgroup can only run on cores 0 through 7. Used for NUMA pinning and core isolation.

These compose orthogonally with the scheduling class. A cgroup-throttled SCHED_NORMAL task still respects nice within the cgroup; a SCHED_FIFO task inside a cgroup still preempts SCHED_NORMAL in that cgroup but also gets throttled by cpu.max.

The throttling trap

cpu.max throttling is the most common source of mysterious latency spikes in containerised workloads. The mechanism: every period (default 100 ms) the cgroup gets a fresh quota. If the workload uses its quota in 30 ms, it's frozen for the remaining 70 ms. That 70 ms is the spike — no scheduler explanation, no obvious CPU starvation, just dead silence in the application's logs followed by a sudden burst when the next period begins.

Worse: cpu.max is enforced per cgroup, not per thread. A Java application with 200 threads and a 1-core quota can have one thread burn the entire quota in 4 ms, leaving the other 199 with nothing for 96 ms. JVM tunings like -XX:ActiveProcessorCount exist to tell the runtime "you actually only have 1 core" so it sizes thread pools accordingly. Same idea in Node (UV_THREADPOOL_SIZE), Go (GOMAXPROCS), Python (asyncio default), etc.

NUMA — non-uniform memory access

A multi-socket server (2 sockets × 32 cores = 64 cores, common) has physical memory attached to each socket. A core can access its local-socket memory in ~100 ns; accessing memory on the other socket takes 200–400 ns (over the inter-socket link). This is NUMA (Non-Uniform Memory Access), and ignoring it costs 2–4× memory latency on cross-socket accesses.

Linux's scheduler is NUMA-aware: it prefers to schedule a task on a CPU close to where its memory lives, and prefers to allocate memory on the same NUMA node where the requesting task is currently running (first-touch policy). It also does periodic balancing to migrate tasks toward their data, or move data to where tasks have clustered. None of this is perfect; high-performance databases and JVMs often pin themselves explicitly with numactl for predictability.

Practical observation

• cat /sys/fs/cgroup/$(cat /proc/self/cgroup | cut -d: -f3)/cpu.max — what CPU cap is on the current process.
• cat /sys/fs/cgroup/.../cpu.stat shows nr_throttled and throttled_usec. If those are nonzero and growing, you're being throttled.
• numactl --hardware shows the machine's NUMA topology;numastat shows cross-node memory traffic per process.

Red flags in code review

• SCHED_FIFO with no sched_rt_runtime_us awareness. A runaway real-time task can lock the box. Document the priority choice; pair real-time threads with watchdogs.
• Thread pool sized by nproc inside a container. nproc reports the host's core count, not the container's CPU quota. Use the runtime-specific knob, or readcpu.max directly.
• Polling loops without sched_yield or sleep. A tight while (!flag) can starve other tasks on the same core. Use a condvar or futex instead.
• nice 0 production daemons that should be nice 5–10. Batch jobs, log shippers, monitoring agents all compete with interactive request handlers under CFS's default fairness. Nicing them down preserves request-handling latency under load.
• NUMA-blind big-heap allocations. A 200 GB heap allocated by one thread at startup ends up on one NUMA node, hurting every other thread that's scheduled on the other socket. Either pin or use first-touch parallel allocation.