CPU Scheduling Primer

Linux keeps one run queue per core, because a global queue would need a global lock on every decision. So the question is never which of 800 threads runs — it is which of the threads on this core's queue gets it. Here the task that runs sits in each core and the rest are waiting; add runnable threads:

Notice the cores do not get busier — they were saturated at eight. What grows is the depth of each queue, and depth is latency: at 256 runnable threads, 31 others run between two turns of yours. Load does not slow the CPU down; it moves your task further from it.

The one knob under all of it is the time slice. Short slices buy short waits and spend switch overhead; long ones keep the work flowing and make everyone wait. Drag the first boundary:

Watch the two bars move in opposite directions, and notice neither is wrong. At 4 ms — which is not a constant anyone ships but what §03's model gives a 32-core box with eight threads runnable — 1.1% of the core goes to switching and the worst wait is 28 ms; at 0.25 ms the wait collapses to 1.75 ms and the overhead climbs to 15%.

That overhead is not the switch instruction. The switch itself is the sliver on the left; the rest is refilling the caches the previous task left cold. Drag the working set:

The switch costs about 1.2 µs — what lmbench's lat_ctx reports for two zero-footprint processes on a 3 GHz x86 core, some 3,600 cycles to save the registers, swap mm and run the scheduler. Refilling 256 KB costs 43.7 µs, thirty-six times more, because one core sustains about 6 GB/s of sequential DRAM read on a two-socket Ice Lake (Intel Memory Latency Checker, --bandwidth_matrix), so a 64-byte line lands every 10.6 ns. That is 6% of the shortest slice Linux hands out — and at 2 MB it is 350 µs, half a period.

Fixed slices are how Unix scheduled for two decades, and they break where you can feel it. Put a keystroke handler behind compute-bound tasks with a 10 ms slice each, and add tasks until it crosses the 100 ms budget:

At ten compute tasks the keystroke waits exactly 100 ms, and past that the machine stops feeling like it is listening. Round robin cannot fix this: it has no way to know the handler is worth more right now than the ninth batch job.

Every runnable task carries a counter, vruntime, which advances while it runs at a rate divided by its weight. The rule is: run the runnable task with the smallest vruntime. Below, three equal tasks start level — the smallest is picked and moves past the other two:

Notice nothing in the rule says “take turns”, yet turns are what you get: after nine decisions each task has had exactly 6 ms, a 2 ms slice out of a 6 ms period. That is the invariant — every runnable vruntime stays within one slice of every other.

Nice is that weight. Linux ships forty entries, each about 1.25× the last, and vruntime advances at 1024 / weight times wall clock. Drag the second task away from the fair half:

One nice level moves about 10% of the machine: a nice-1 task takes 44% against nice 0's 56%, and the full −20 to +19 span is a factor of 5,917. Because the weight divides a rate rather than gating a queue, nothing ever stops:

Watch the reniced task at +19 — it still takes 0.73% of the CPU while the other two hold 50% each, and at −20 it takes 98% while they keep 1.1%. nice is a ratio, not a veto; it cannot starve anything, which is exactly why it is safe to hand to users.

“Smallest vruntime” is answered on every tick, so it cannot be a scan. CFS keeps the runnable set in a red-black tree keyed by vruntime and the answer is always the leftmost node. Grow the queue:

At 255 runnable tasks the walk is 8 levels against the 255 a flat list reads — and Linux does not walk it at all, because the leftmost pointer is cached. Picking is O(1); only the re-insertion after a slice is O(log n), so cost lives on the write path.

Which raises what the rule cannot answer alone. A task that slept a second wakes with a vruntime a second stale, so it is leftmost by a mile. Drag how long it slept, then turn the placement clamp off:

With the clamp off, a 200 ms sleeper is owed 200 ms of uninterrupted CPU — one blocking read would monopolise the core, and any program could game it by sleeping. place_entity() pulls a waking vruntime forward to min_vruntime − sched_latency/2, capping the credit at 3 ms however long it was gone.

CFS starts from a promise: every runnable task gets the CPU within sched_latency, 6 ms by default. Divide by the number of runnable tasks and you have each one's slice. Below, the period and the slice share one axis:

Notice what happens at eight. Below it the promise holds and the slice shrinks to keep it; above it the slice would fall under the 0.75 ms minimum granularity, so CFS stretches the period instead. At 32 runnable tasks the “6 ms target” is 24 ms; at 64 it is 48 ms.

Worse, neither constant is the constant. Both are multiplied at boot by 1 + ilog2(ncpus), so the target latency your kernel actually runs depends on how many cores it found. Drag the core count:

A 32-core box boots with a 36 ms target latency and a 4.5 ms granularity — six times the numbers in the paragraph above, and the period at 32 runnable tasks is 144 ms, not 24. Read /sys/kernel/debug/sched/latency_ns before quoting 6 ms at anybody.

A slice ends early when someone deserves the core more. On wake, CFS compares vruntimes and preempts only if the gap beats the wakeup granularity. Drag the waker closer and further:

Inside 1 ms the waker is not worth a switch — 44.9 µs spent to gain under a millisecond — so the kernel lets the running task finish and picks up the change at the next tick. That is the classic “my thread woke on time but ran 4 ms later”, and no amount of nice moves it.

Because the check happens at the tick, the tick is the real resolution of everything above. Here a 0.75 ms slice ends between two ticks, and what it keeps past the end is overrun. Change CONFIG_HZ, then the preemption model:

At the common CONFIG_HZ=250 the tick is 4 ms, so a 0.75 ms slice runs 4 ms — over five times its budget — before anyone notices, and that overrun is your p99. PREEMPT_FULL takes it to zero and pays in throughput; PREEMPT_VOLUNTARY is the server default because most servers prefer the throughput.

CFS's weak point was never fairness; it was that every knob near latency was a heuristic. The sleeper credit of §02 is one, the wakeup granularity of §03 is another, and both are constants somebody tuned once.

That quantity is lag: the service a task was owed by now minus what it actually got. A task with lag ≥ 0 is eligible; one that got ahead is not, and may not be picked at all. Here T2 arrives 4 ms ahead — drag service forward and watch it earn its way back:

Notice that eligibility is a gate, not a penalty. T2 is never punished and never loses the 4 ms; it simply cannot be picked until the other two catch up, at 8 ms of total service, where all three lags are zero. The invariant is that lag sums to zero across the runnable set, always.

The second word is the virtual deadline: each task names a request size r and gets a deadline of ve + r/weight. Among the eligible, earliest deadline wins. Drag the request:

Because a smaller request means an earlier deadline, asking for less time buys more turns and pays in switches. The 0.75 ms default gives four tasks a 2.25 ms wake-to-run bound at 1,333 switches a second; ask for 0.1 ms and the bound is 0.3 ms at 10,000 switches, which at 44.9 µs each eats 45% of the core.

The point is that the task chooses, and that share and latency have come apart. Here the same three tasks run under both schedulers, with T2 asking for 0.75 ms where the others take 3 ms. Both strips are finished — scrub back to watch either one fill:

Both schedulers give T2 exactly 33% of the CPU — EEVDF is no more generous. What changed is the shape: 5 turns instead of 3, and a longest gap of 3.0 ms instead of 4.0 ms. Under CFS, T2 had no way to ask; its slice was the period over the number of runnable tasks, so a latency-sensitive thread could only pretend to be high-priority.

Linux puts five more classes around the fair one in strict order: whichever class has a runnable task highest in the stack wins, and nice never enters into it. Walk a task up and down past the classes it outranks:

Notice this is precedence, not weighting: a runnable SCHED_FIFO task preempts the four classes below it and keeps the core until it blocks. Where nice moved a ratio, a class moves an absolute veto.

SCHED_DEADLINE goes further and is the one place the scheduler says no. Declare (runtime, deadline, period) and the kernel sums the utilisation against the bandwidth cap. Raise what the new task asks for:

Past 20% the total crosses 95% and sched_setattr() returns EBUSY — the task never starts, rather than starting and missing deadlines later. That is the difference between a guarantee and a priority: a guarantee has to be able to refuse you.

Strict precedence has one obvious failure, and Linux ships a seatbelt. Here a SCHED_FIFO loop that never blocks holds a core and the bandwidth reserve is all your shell has. Drag sched_rt_runtime_us to its maximum:

At the default 950,000 of every 1,000,000 µs, 50 ms per second survives — enough that a 200 ms shell command takes 4 seconds instead of never. Push the reserve to zero and the readout stops giving a number: no shell, no SSH, no logging, and the only recovery is the power button.

The subtler failure needs no bug. Here a low-priority task holds a lock, a high-priority one blocks on it, and a medium-priority task that wants neither preempts the holder. Switch the mutex, then scrub back through either version:

The high-priority task finishes at 11 ms with a plain mutex and 5 ms with a priority-inheriting one — blocked behind a task it outranks for exactly as long as an unrelated task felt like running. This is what killed Mars Pathfinder in 1997. Use PTHREAD_PRIO_INHERIT, and remember it fixes only mutexes: a spinlock or a lock inside a library you did not write still inverts.

cpu.max is a hard cap, not a weight: a group gets a quota of CPU-microseconds per 100 ms period, and when it is spent the group is frozen until the period rolls over. The trap is that the quota is spent in parallel. Add threads, or drag the quota edge:

Watch what a JVM with 200 threads does to a one-core quota on a 32-core box: 32 threads run at once, so the quota is gone in 3.13 ms and the group is frozen for the remaining 97 ms. The application sees a 97 ms stall with no CPU pressure, no GC pause and nothing in its own logs.

The instinct is to shorten the period so the freeze is shorter. Drag cpu.cfs_period_us down and read the worst stall:

It works — a 10 ms period caps the stall at 9.7 ms — and costs 100 enforcement points a second instead of 10, on every core the group touches. The real fix is upstream: tell the runtime how many cores it actually has (GOMAXPROCS, -XX:ActiveProcessorCount), because nproc reports the host.

The second bite is the load balancer doing exactly what it should. Moving a task to an idle core shortens the wait and costs a switch onto a cold cache. Move tasks across, then raise the working set:

With a 256 KB working set, moving three of six tasks saves 1.0 ms of wait for 0.14 ms of migration. At 2 MB the same move costs 1.1 ms to save 1.0 ms, and moving all six saves nothing while paying 2.1 ms — the imbalance changed sides. This is why sched_migration_cost_ns exists.

The last one is not the scheduler's at all, but it arrives through it. On a two-socket box, memory is attached to a socket, so a thread the balancer moved reads across the link instead of locally. Drag the fraction:

Intel's Memory Latency Checker on a two-socket Ice Lake measures 85 ns local against 139 ns remote — a factor of 1.64, and nothing in top will tell you. Linux allocates on first touch, which is why a big heap allocated by one startup thread and used by forty is the shape that always goes wrong.

pick_next(rq):              # the whole policy
  V = avg_vruntime(rq)      # the fair-share clock
  ok = [e for e in rq if e.vruntime <= V]
  return min(ok, key=lambda e: e.deadline)

The gap worth memorising is the third rung to the last: a switch is microseconds, a throttled cgroup period is 97 ms. Above it you tune with slices and nice values; below it you are arguing with a quota.

At 32 runnable tasks the queued version takes 88 ms against the idle core's 2 ms — 44× — and no profiler will show it, because the CPU is 40% busy and your thread is in R state doing nothing. Read cpu.stat for nr_throttled first, then perf sched latency, then vmstat 1's r column.

Red flags in review

• A thread pool sized from nproc in a container. nproc reports the host, not the quota — the 200-threads-on-one-core shape from §06.
• SCHED_FIFO without a watchdog. One loop that forgets to block takes the box; only the 50 ms per second reserve lets you back in.
• A mutex shared by a real-time thread without PTHREAD_PRIO_INHERIT. Inversion needs no bug, only a third task.
• Quoting 6 ms as the latency target. It is scaled by core count at boot and stretched again past eight runnable tasks.