On this page

CPU Scheduling & Context Switching

The CPU can only run one thread per core at a time. With hundreds of processes competing for CPU time, the kernel needs a policy to decide who runs next, for how long, and what to do when a higher-priority task arrives. That policy is the scheduler.

This page builds the topic from the ground up: what a time slice (quantum) physically is and why it has to exist, the classic algorithms worked through with Gantt charts and real arithmetic, how Linux actually does it (CFS, then EEVDF from 6.6 onwards), and the production problems that come out of it — context-switch overhead, run-queue latency, and the Kubernetes CPU-limit throttling trap.


Why a Scheduler Exists At All

A modern server has, say, 16 cores and 600 threads. At any instant, at most 16 of those threads can be executing instructions. The rest are either:

  • Blocked — waiting for something (a disk read, a network packet, a lock, a timer). They don't want the CPU.
  • Runnable — ready to execute right now, but no core is free. They are sitting in a run queue.

The scheduler answers three questions, thousands of times per second per core:

  1. Who runs next? (selection policy)
  2. For how long? (the time slice / quantum)
  3. When do we interrupt them? (preemption policy)

If the answer to question 2 were "until they finish or block", a single while(true) {} loop would freeze every other program on that core forever. That's exactly what happened on cooperative-multitasking systems like Windows 3.1 and classic Mac OS: one misbehaving program hung the whole machine. The time slice exists to make that impossible.


The Scheduling Problem

Goals (often conflicting):

  • Throughput: maximize completed tasks per second
  • Latency: minimize time from task ready → task starts executing
  • Fairness: no process waits forever (starvation prevention)
  • Utilization: keep the CPU busy
  • Predictability: interactive apps need consistent response time

There is no single optimal scheduler — every scheduling algorithm makes trade-offs between these goals. The right choice depends on the workload.

WorkloadWhat it cares aboutWhat it tolerates
Web/API serverTail latency (p99), quick wakeupsSlightly lower throughput
Batch / ETL / ML trainingThroughput, cache warmthLong latency per task
Desktop / UIResponse time to input (<16ms per frame)Background jobs running slower
Audio / robotics / tradingBounded worst-case latencyLower utilization
Multi-tenant cloud hostFairness and isolation between tenantsSome idle capacity

Key Metrics

CPU burst: The amount of CPU time a process uses before it blocks on I/O.

I/O-bound process: Lots of short CPU bursts, long I/O waits. Example: web server, database client. Wants low latency.

CPU-bound process: Long CPU bursts, rare I/O. Example: video encoding, machine learning training. Wants high throughput.

Turnaround time: completion_time - arrival_time. How long from submission to completion.

Waiting time: turnaround_time - cpu_burst_time. Time spent in the ready queue.

Response time: Time from submission to first response. Critical for interactive systems. (In scheduling exercises this is first_run_time - arrival_time.)

Run-queue latency (scheduler latency): In production Linux terms, the time a thread spends runnable but not running each time it wakes up. This is the metric that shows up in your p99 — measured later on this page with perf sched and bpftrace.

stateDiagram-v2
    [*] --> Runnable: "created / woken up"
    Runnable --> Running: "scheduler picks it"
    Running --> Runnable: "quantum expired (preempted)"
    Running --> Blocked: "waits on I/O, lock, sleep"
    Blocked --> Runnable: "event arrives (wakeup)"
    Running --> [*]: "exit()"

The scheduler only ever chooses among the Runnable set. Waiting time in all the formulas below is time spent in the Runnable state.


The Time Slice (Quantum), Explained Properly

A time slice (also called a quantum) is the maximum amount of CPU time a thread is allowed to run continuously before the kernel takes the CPU back and reconsiders who should run. It is a budget, not a reservation:

  • If the thread blocks (e.g. issues a read() on a socket) before the budget runs out, it gives up the CPU early. The unused remainder is simply not used — an I/O-bound thread usually runs 50–500μs, nowhere near its slice.
  • If the thread is still computing when the budget runs out, the kernel preempts it: it's moved back to the run queue and someone else gets a turn.

How the kernel actually enforces it

The CPU does not "know" about time slices. The kernel enforces them with a hardware timer:

  1. A periodic timer interrupt (the tick) fires CONFIG_HZ times per second — typically 250 Hz (every 4ms) on server distros, 1000 Hz (every 1ms) on some desktop kernels. With high-resolution timers (hrtick), the kernel can also program a one-shot timer for exactly when the current slice ends.
  2. The interrupt yanks the CPU out of whatever user code was running and into the kernel's interrupt handler, regardless of what the program was doing.
  3. The handler calls the scheduler's tick hook (scheduler_tick() / sched_tick()), which charges the elapsed time to the running task and checks whether it has used up its slice (or whether a more deserving task is waiting).
  4. If so, it sets a flag (TIF_NEED_RESCHED) on the current task.
  5. On the way back out of the interrupt, the kernel sees the flag and calls schedule(), which picks the next task and performs a context switch.
sequenceDiagram
    participant T as "Thread A (user code)"
    participant HW as "Timer hardware"
    participant K as "Kernel"
    participant B as "Thread B"
    T->>T: "running a tight loop"
    HW->>K: "timer interrupt (tick)"
    K->>K: "charge 4ms to A, slice used up"
    K->>K: "set TIF_NEED_RESCHED"
    K->>K: "schedule() picks B"
    K->>B: "context switch: restore B registers"
    B->>B: "runs until its slice ends or it blocks"

The tick is how often the kernel checks; the slice is how long a task may run. They are related but different: a 3ms slice on a 250 Hz kernel is effectively rounded to the next 4ms tick unless hrtick is enabled. On "tickless" kernels (CONFIG_NO_HZ_IDLE, nohz_full) the tick is stopped when a CPU is idle or has a single runnable task, because there's nobody to switch to.

Why the quantum size matters: a worked trade-off

Every preemption costs a context switch. Call the switch cost s and the quantum q. While several CPU-bound tasks share a core:

CPU efficiency      = q / (q + s)
Worst-case wait     ≈ (n − 1) × (q + s)        # n runnable tasks, you're last in line

Take s = 30μs (a realistic effective cost once cache and TLB refill is included — the raw register save is only 1–3μs) and n = 10 runnable tasks:

Quantum qEfficiency q/(q+s)Wasted on switchingWorst-case wait for your turn
0.1ms77%23%1.2ms
1ms97.1%2.9%9.3ms
4ms99.3%0.7%36ms
10ms99.7%0.3%90ms
100ms99.97%0.03%900ms

Read it both ways:

  • Too small (0.1ms): the machine spends almost a quarter of its time switching instead of working. Caches never warm up. Throughput collapses.
  • Too large (100ms): switching is free, but a keypress or an incoming HTTP request can wait almost a second behind 9 CPU hogs. In the limit (q → ∞) Round Robin degenerates into FCFS.

The sweet spot for general-purpose systems has historically been 1–10ms: switching overhead under ~3%, worst-case waits that humans and most RPC SLOs tolerate. That's why Linux's slices land in the 0.75ms–24ms range, and why the next sections keep returning to this tension.

The same trade-off on a tiny example

Three tasks arrive at t=0: P1 (24ms of CPU), P2 (3ms), P3 (3ms). Round Robin with different quanta:

QuantumContext switchesAvg waitingAvg response (time to first run)Avg turnaround
q = 1ms95.67ms1.0ms15.67ms
q = 4ms35.67ms3.67ms15.67ms
q = 10ms39.67ms7.67ms19.67ms
q ≥ 24ms (= FCFS)217.0ms17.0ms27.0ms

q = 4ms gets the same waiting time as q = 1ms with a third of the switches, because 4ms is longer than the short jobs' bursts — they finish in one slice. That's the intuition behind the classic rule of thumb further down: make the quantum longer than most CPU bursts.


Scheduling Algorithms

The classic algorithms below are taught for a reason: every real scheduler is a blend of them. For each one, work the numbers yourself — it's the fastest way to internalize the trade-offs.

First-Come, First-Served (FCFS)

Run processes in order of arrival. Non-preemptive — a process runs until it blocks or exits.

Arrival: P1(burst=24ms), P2(burst=3ms), P3(burst=3ms)
Timeline: [P1──────────────────────][P2───][P3───]
          0                         24     27     30

Waiting: P1=0, P2=24, P3=27  →  Average waiting time = 17ms
Turnaround: P1=24, P2=27, P3=30  →  Average turnaround = 27ms

Problem: convoy effect. One long job blocks all short jobs behind it. Interactive processes (P2, P3) suffer if a batch job (P1) runs first. If the same three jobs had arrived in the order P2, P3, P1, the average wait would be 3ms — FCFS performance depends entirely on luck of arrival order.

Where FCFS still wins: it has zero preemption overhead and perfect cache locality, so it's what you want inside a batch queue, for SCHED_FIFO real-time tasks, and in many job queues (Kafka consumers, worker pools) where ordering matters more than latency.

Shortest Job First (SJF)

Run the process with the shortest CPU burst next. Minimizes average waiting time (provably optimal for batch systems).

Same processes, SJF order: P2(3ms), P3(3ms), P1(24ms)
Timeline: [P2───][P3───][P1──────────────────────]
          0      3      6                         30

Waiting: P1=6, P2=0, P3=3  →  Average waiting time = 3ms (vs 17ms for FCFS)
Turnaround: P1=30, P2=3, P3=6  →  Average turnaround = 13ms

Why it's optimal: moving a short job ahead of a long one reduces the short job's wait by the long job's length, and increases the long job's wait by only the short job's length. Any swap that puts shorter first is a net win, so sorted-by-length is the minimum.

Problem: Requires knowing burst time in advance — impossible in practice. Estimated using exponential averaging of past bursts. Also, long jobs can starve if short jobs keep arriving.

The exponential average predicts the next burst τ(n+1) from the last actual burst t(n) and the previous prediction:

τ(n+1) = α × t(n) + (1 − α) × τ(n)        # α typically 0.5

Example, α = 0.5, initial guess τ0 = 10ms, actual bursts: 6, 4, 6, 4, 13, 13, 13
predictions:  10 → 8 → 6 → 6 → 5 → 9 → 11 → 12

The prediction lags behind sudden changes (the job switched from 4–6ms bursts to 13ms bursts and the estimate takes three rounds to catch up). Linux's old O(1) scheduler and many MLFQ designs used this kind of heuristic to guess "interactivity".

A harder example with arrival times

Real tasks don't all arrive at t=0. Use this classic set for the rest of the comparisons:

ProcessArrivalBurst
P108
P214
P329
P435

Non-preemptive SJF: at t=0 only P1 exists, so it runs to completion even though shorter jobs arrive at t=1..3.

[P1──────][P2──][P4───][P3───────]
0        8    12     17         26

Turnaround (completion − arrival): P1=8, P2=11, P4=14, P3=24  → avg 14.25
Waiting    (turnaround − burst):   P1=0, P2=7,  P4=9,  P3=15  → avg 7.75

Shortest Remaining Time First (SRTF) — Preemptive SJF

Preemptive version of SJF. When a new process arrives, if its burst is shorter than the remaining burst of the current process, preempt.

t=0  P1 starts (remaining 8)
t=1  P2 arrives with 4 < P1's remaining 7  → preempt P1, run P2
t=2  P3 arrives (9) — P2 has 3 left, keep going
t=3  P4 arrives (5) — P2 has 2 left, keep going
t=5  P2 done. Ready: P1(7), P3(9), P4(5) → P4
t=10 P4 done. Ready: P1(7), P3(9) → P1
t=17 P1 done → P3
t=26 P3 done

[P1][P2──][P4───][P1─────][P3───────]
0   1    5     10       17         26

Turnaround: P1=17, P2=4, P3=24, P4=7   → avg 13.0
Waiting:    P1=9,  P2=0, P3=15, P4=2   → avg 6.5   (vs 7.75 non-preemptive SJF)

Best average waiting time for batch workloads. Worst starvation potential. Note P3 — the longest job — waits 15ms and would wait forever if short jobs kept arriving.

Round Robin (RR)

Each process gets a fixed time slice (quantum), typically 10–100ms. When the quantum expires, the process is preempted and moved to the back of the queue.

Quantum = 4ms. P1(burst=24), P2(burst=3), P3(burst=3)
Timeline: [P1──][P2──][P3──][P1──][P1──][P1──][P1──][P1──]
          0    4    7    10   14   18   22   26   30

Waiting:    P1=6, P2=4, P3=7    → avg 5.67ms
Turnaround: P1=30, P2=7, P3=10  → avg 15.67ms
Response:   P1=0, P2=4, P3=7    → avg 3.67ms (FCFS: 17ms)

After t=10 P1 is alone, so each "preemption" at 14, 18, 22, 26 just re-selects P1 — the kernel notices there's nobody else and skips the actual switch.

The arrival-time example under RR, q = 4ms (convention: a newly-arrived process joins the queue before the process that was just preempted):

t=0   P1 runs 0–4 (rem 4). Meanwhile P2, P3, P4 arrived → queue [P2, P3, P4, P1]
t=4   P2 runs 4–8   done
t=8   P3 runs 8–12  (rem 5) → queue [P4, P1, P3]
t=12  P4 runs 12–16 (rem 1) → queue [P1, P3, P4]
t=16  P1 runs 16–20 done
t=20  P3 runs 20–24 (rem 1) → queue [P4, P3]
t=24  P4 runs 24–25 done
t=25  P3 runs 25–26 done

[P1──][P2──][P3──][P4──][P1──][P3──][P4][P3]
0    4    8    12   16   20   24  25  26

Turnaround: P1=20, P2=7, P3=24, P4=22   → avg 18.25
Waiting:    P1=12, P2=3, P3=15, P4=17   → avg 11.75
Response:   P1=0,  P2=3, P3=6,  P4=9    → avg 4.5

Summary for the arrival-time example:

AlgorithmAvg waitingAvg turnaroundPreemptive?Needs burst length?Starvation?
FCFS8.7515.25NoNoNo
SJF7.7514.25NoYesYes
SRTF6.513.0YesYesYes (worst)
RR (q=4)11.7518.25YesNoNo

RR has the worst averages here — and it's still the basis of every interactive scheduler. Why? Because averages aren't what users feel. RR bounds the worst case: no runnable task ever waits more than (n−1) × q for its next turn, without needing to predict the future. SRTF's averages are better, but P3 can be starved indefinitely and the algorithm needs knowledge nobody has.

Trade-off: Smaller quantum → better responsiveness, more context switches. Larger quantum → approaches FCFS.

Rule of thumb: Quantum should be larger than 80% of CPU bursts (so most processes complete in one slice) but small enough that interactive tasks aren't waiting long.

Priority Scheduling

Each process has a priority. Higher priority processes run first. Can be preemptive or non-preemptive.

Worked example (lower number = higher priority, all arrive at t=0, non-preemptive):

ProcessBurstPriority
P1103
P211
P324
P415
P552
[P2][P5────][P1─────────][P3─][P4]
0   1      6            16   18  19

Waiting: P1=6, P2=0, P3=16, P4=18, P5=1  → avg 8.2

Problem: starvation. Low-priority processes may never run if high-priority processes keep arriving.

Solution: aging. Gradually increase the priority of waiting processes over time. Example: raise priority by 1 for every 15 minutes waiting — a priority-127 job on a 0–127 scale reaches priority 0 within about 32 hours, so it eventually runs no matter what.

Problem 2: priority inversion. A high-priority task waits on a lock held by a low-priority task, which can't run because medium-priority tasks keep preempting it. The high-priority task is effectively demoted below the medium ones. The famous case is the 1997 Mars Pathfinder lander, which kept resetting because a high-priority bus-management task was blocked behind a low-priority meteorological task holding a mutex while medium-priority communications tasks ran. The fix — enabling priority inheritance on that mutex (the lock holder temporarily inherits the waiter's priority) — was uploaded to the spacecraft. Linux's PTHREAD_PRIO_INHERIT futexes (and PREEMPT_RT's rt-mutexes) implement the same thing.

Multilevel Queue Scheduling

Divide processes into queues based on type (foreground/interactive, background/batch). Each queue has its own scheduling algorithm and priority.

Queue 1 (interactive, high priority): Round Robin, quantum=8ms
Queue 2 (batch, low priority): FCFS

Interactive processes always get CPU before batch processes.

The weakness: a process is assigned to a queue up front and stays there. The OS has to know what kind of process it is. MLFQ fixes that by learning.

Multilevel Feedback Queue (MLFQ)

MLFQ (Corbató, CTSS, 1962 — a Turing Award contribution) is the algorithm that solved "SJF without knowing burst lengths". It observes behavior and moves processes between queues. The modern formulation (from OSTEP) has five rules:

  1. If Priority(A) > Priority(B), A runs.
  2. If Priority(A) = Priority(B), A and B run round-robin with that queue's quantum.
  3. A new job enters at the highest priority (assume it's short/interactive until proven otherwise).
  4. Once a job uses up its total time allotment at a level (regardless of how many times it gave up the CPU), it moves down one level.
  5. Every period S (e.g. 1 second), boost all jobs to the top queue.
flowchart TD
    NEW["New job"] --> Q0["Q0: highest priority, quantum 8ms"]
    Q0 -->|"used full 8ms allotment"| Q1["Q1: quantum 16ms"]
    Q1 -->|"used full 16ms allotment"| Q2["Q2: lowest, FCFS or long RR"]
    Q0 -->|"blocks on I/O early"| Q0
    Q1 -->|"blocks on I/O early"| Q1
    BOOST["Priority boost every S seconds"] -.-> Q0

Trace: a CPU-bound job A (needs 40ms) arrives at t=0, and an interactive job B arrives at t=30 doing 1ms of work then 10ms of I/O, repeatedly.

t=0–8    A in Q0, uses full 8ms   → demoted to Q1
t=8–24   A in Q1, uses full 16ms  → demoted to Q2 (16ms left)
t=24–30  A in Q2 runs
t=30     B arrives in Q0 → preempts A immediately
t=30–31  B runs 1ms, blocks on I/O (stays in Q0, allotment not used up)
t=31–41  A runs in Q2 while B waits for I/O
t=41     B wakes, preempts A again, runs 1ms ...

B gets near-instant response (it's always top priority) and A soaks up all the leftover CPU. MLFQ has approximated SRTF — short, interactive jobs first — without being told anything.

Why rules 4 and 5 exist:

  • Without the allotment accounting in rule 4, a process can game the scheduler: run for 7.9ms, do a trivial I/O, and stay at top priority forever while consuming 99% of the CPU.
  • Without the boost in rule 5, CPU-bound jobs in Q2 starve if enough interactive jobs exist, and a job that becomes interactive (a batch job that starts handling user input) never gets promoted back.

Windows, macOS (XNU's Mach scheduler), FreeBSD's ULE and Solaris all use MLFQ-family schedulers. Linux used priority arrays with interactivity heuristics (the O(1) scheduler, 2.6.0–2.6.22) before replacing heuristics entirely with CFS.


Preemption

Non-preemptive (cooperative): A process voluntarily yields the CPU (by blocking on I/O or calling yield()). Simple, but one bad process can monopolize the CPU.

Preemptive: The kernel can forcibly take the CPU from a running process when its time slice expires or a higher-priority process becomes ready. Requires a hardware timer interrupt.

Modern general-purpose OSes (Linux, Windows, macOS) are preemptive.

There are two distinct questions here that people conflate:

  1. Can user code be preempted? Yes, on every modern OS — via the timer interrupt described above.
  2. Can kernel code be preempted? That depends on the kernel's preemption model. If a thread is in the middle of a long system call (say, freeing a huge memory mapping), can a newly-woken high-priority task take the CPU before the syscall finishes?

Linux preemption models

Model (Kconfig)Kernel code preemptible?Typical useWorst-case latency (order of magnitude)
PREEMPT_NONEOnly at explicit schedule points / return to userThroughput servers, HPCCan reach many milliseconds
PREEMPT_VOLUNTARYAt might_sleep()/cond_resched() points sprinkled through the kernelMany distro defaults (desktop & server)~1–10ms
PREEMPT (full)Anywhere, except when holding a spinlock or with preemption/interrupts disabledDesktops, low-latency audio~100μs–1ms
PREEMPT_RTAlmost everywhere: most spinlocks become sleeping rt-mutexes, IRQ handlers run as threadsIndustrial control, pro audio, roboticsTens of μs, bounded
PREEMPT_LAZY (6.13+)Full preemption for RT tasks, but fair-class preemption deferred to the next tickAims to replace NONE/VOLUNTARYBetween VOLUNTARY and full

PREEMPT_RT spent ~20 years as an out-of-tree patch set and was merged into mainline in Linux 6.12 (2024). PREEMPT_DYNAMIC lets one kernel binary choose at boot: preempt=none|voluntary|full on the kernel command line. Check yours:

$ uname -v
#1 SMP PREEMPT_DYNAMIC Thu Oct  2 10:12:31 UTC 2025
$ cat /sys/kernel/debug/sched/preempt     # needs debugfs mounted, root
none voluntary (full)

When preemption model matters for your service

For a normal web service it almost never does — your latency is dominated by network and application code. It matters when you see p99.9 spikes of a few ms that correlate with kernel work (huge munmap, large page-cache reclaim, fsync storms) on a PREEMPT_NONE kernel. Moving to voluntary/full costs a few percent of throughput in exchange for shorter worst-case delays.


Context Switching

A context switch is the process of saving the state of the current process and loading the state of the next process to run.

What the kernel saves/restores:

- Program counter (where to resume)
- CPU registers (all general-purpose registers)
- Stack pointer
- Memory management registers (page table base register)
- FPU/SIMD state (if the process used floating-point/SIMD instructions)

On x86-64 Linux, the switch happens in two steps inside schedule() → context_switch():

  1. switch_mm() — if the next task belongs to a different process, load its page-table root into CR3. Threads of the same process skip this. Kernel threads borrow the previous task's address space ("lazy TLB") and skip it too.
  2. switch_to() — swap kernel stacks and callee-saved registers, then return on the new task's kernel stack. User registers were already saved on that task's kernel stack when it entered the kernel (via syscall or interrupt). FPU/AVX state is saved with XSAVE and restored lazily on return to user space — an AVX-512 register file is ~2.5KB, which is not free.
flowchart LR
    A["Task A running"] --> E["Trap into kernel: timer IRQ or syscall"]
    E --> S["schedule(): pick next task"]
    S --> M{"Same address space?"}
    M -->|"no: other process"| CR3["switch_mm: load CR3, PCID tag"]
    M -->|"yes: sibling thread"| SW["switch_to: swap kernel stack and registers"]
    CR3 --> SW
    SW --> R["Return to user mode as Task B"]

Cost of a context switch:

  • Pure CPU state save/restore: ~1–5μs
  • TLB flush (if switching between processes with different address spaces): +10–100μs of indirect cost
    • TLB flush is the expensive part — the kernel must reload the CPU's address translation cache
    • Thread switches within the same process don't require TLB flush
    • On CPUs with PCID (Process-Context IDs, used by Linux since 4.14), TLB entries are tagged per address space, so a CR3 load does not have to wipe the TLB. The cost is mostly the refill of entries that were evicted, which depends on working-set size — a small process pays little, a 50GB database pays a lot.
  • Cache warming: the new process's data isn't in CPU cache → cache misses for the next few ms

Real numbers to calibrate against (modern x86 server, order of magnitude):

OperationTypical cost
Syscall round trip (getppid), no KPTI~50–100ns
Syscall round trip with KPTI (Meltdown mitigation)~200–500ns
Thread → thread switch, same CPU, same process~1–2μs
Process → process switch, same CPU~2–5μs direct
Cross-CPU wakeup (IPI) + switch~5–10μs
Indirect cost: refilling L1/L2/TLB after a switch10–100μs+ for large working sets
Goroutine switch (user-space)~100–200ns

Measure your own box:

# Two processes ping-ponging over a pipe: each op = 2 context switches + 2 syscalls
$ perf bench sched pipe -l 1000000
# Running 'sched/pipe' benchmark:
# Executed 1000000 pipe operations between two processes
     Total time: 4.871 [sec]
       4.871 usecs/op           # illustrative, cross-CPU
      205296 ops/sec

# Pin both ends to one CPU to measure the pure switch path (no IPI)
$ taskset -c 0 perf bench sched pipe -l 1000000
       2.105 usecs/op           # illustrative

Voluntary vs involuntary switches. Every switch is either voluntary (the task blocked: I/O, lock, sleep) or involuntary (preempted: slice expired or a higher-priority task woke). The ratio is diagnostic:

$ grep ctxt_switches /proc/$(pgrep -o nginx)/status
voluntary_ctxt_switches:        184223      # blocked on epoll/IO — normal for a server
nonvoluntary_ctxt_switches:     912         # rarely preempted — CPU isn't contended

$ pidstat -w 1          # per-task cswch/s (voluntary) and nvcswch/s (involuntary)
$ vmstat 1             # 'cs' column = system-wide switches/sec, 'r' = runnable tasks

High involuntary switches mean CPU contention: more runnable threads than cores. High voluntary switches with low throughput often mean lock contention or tiny I/O.

This is why:

  • Thread pools are better than creating a new thread per request
  • Async/event-loop models can handle more concurrent connections than thread-per-request models
  • Goroutines and green threads are cheaper than OS threads (user-space context switch, no kernel involvement)

War Story (illustrative)

A Java service was moved from 32 to 400 worker threads "to handle more load". Throughput dropped by 30%. vmstat showed ~250,000 context switches per second and r (runnable) around 60 on a 16-core box; perf showed most cycles in cache misses. Each request touched a ~2MB working set; with 400 threads rotating on 16 cores, nothing stayed in L2. Dropping back to 48 threads (cores × 3, since requests spent ~2/3 of their time waiting on a database) restored throughput and cut p99 in half. More threads than the CPU can usefully run is not "more capacity" — it's more switching.


Linux CFS: Completely Fair Scheduler

Linux's scheduler since kernel 2.6.23. The core idea: every runnable process should get an equal share of CPU time. CFS doesn't use fixed time quanta.

Instead of "each task gets a 10ms quantum", CFS models an ideal multitasking CPU: with n runnable tasks of equal weight, each one would receive exactly 1/n of the CPU continuously, as if the CPU could run them all simultaneously at 1/n speed. Real hardware can't do that, so CFS runs one task at a time and tracks how far each has fallen behind the ideal — then always runs the one furthest behind. The time slice falls out of the calculation instead of being fixed.

(CFS was written by Ingo Molnar, inspired by Con Kolivas's Rotating Staircase Deadline scheduler. From Linux 6.6 it was replaced by EEVDF, which keeps the same vruntime machinery — covered after this section.)

Virtual Runtime (vruntime)

Each process tracks a vruntime — the amount of CPU time it has received, weighted by priority. Lower-priority processes accumulate vruntime faster than high-priority ones (so they yield sooner).

CFS always runs the process with the lowest vruntime — the process that has received the least CPU time relative to its priority.

vruntime increases at rate: 1024 / weight
where weight is derived from the nice value:
nice -20 (highest priority) → weight = 88761
nice  0  (default)          → weight = 1024
nice +19 (lowest priority)  → weight = 15

A process with nice=-5 accumulates vruntime ~3x slower than nice=0, so it runs ~3x more.

Precisely, every time the kernel accounts runtime (each tick, each switch):

// kernel/sched/fair.c (simplified)
delta_exec = now - curr->exec_start;            // real ns just run
curr->sum_exec_runtime += delta_exec;
curr->vruntime += delta_exec * NICE_0_LOAD / curr->load.weight;   // NICE_0_LOAD = 1024

A nice-0 task's vruntime advances at wall-clock speed. A nice -5 task (weight 3121) advances at 1024/3121 ≈ 0.33× speed. A nice +5 task (weight 335) advances at ≈ 3.06× speed.

The nice → weight table (the 1.25× rule)

The weights come from a fixed table in kernel/sched/core.c (sched_prio_to_weight). Each nice step multiplies weight by about 1.25. The design goal: each nice level is worth ~10% CPU relative to a neighbour. Two tasks at nice 0 and nice 1 get 1024/(1024+820) = 55.5% and 44.5% — a ~10 percentage-point gap.

niceweightniceweightniceweightniceweight
-2088761-1095480102410110
-1971755-9762018201187
-1856483-8610026551270
-1746273-7490435261356
-1636291-6390644231445
-1529154-5312153351536
-1423254-4250162721629
-1318705-3199172151723
-1214949-2158681721818
-1111916-1127791371915

Because the scale is geometric, only differences in nice matter: nice 0 vs nice 5 splits CPU the same way (75/25) as nice 10 vs nice 15. And the full range is huge: a nice -20 task against a nice +19 task gets 88761/(88761+15) = 99.98% of the CPU.

Red-Black Tree

All runnable processes are stored in a red-black tree keyed by vruntime. The leftmost node (lowest vruntime = most deserving of CPU) is always cached for O(1) access.

         /             \
  [vruntime=3]    [vruntime=8]
  /         \         /      \
[2]         [4]    [6]       [10]

Next to run: leftmost node = [2]

When a process is preempted, its vruntime is updated and it's reinserted into the tree.

Costs: picking the next task is O(1) (cached leftmost), inserting/removing is O(log n). With 1,000 runnable tasks on one CPU that's ~10 comparisons — negligible next to the switch itself. Blocked tasks are not in the tree; the tree holds only runnable tasks (the currently-running one is kept outside it while it runs).

flowchart TD
    W["Task wakes or is preempted"] --> U["update vruntime: += delta x 1024 / weight"]
    U --> I["insert into per-CPU rbtree, keyed by vruntime"]
    I --> P["pick_next: leftmost node = smallest vruntime"]
    P --> R["run it for its computed slice"]
    R --> C{"slice used up, or a waking task has much smaller vruntime?"}
    C -->|"yes"| U
    C -->|"no, blocked on I/O"| B["dequeue: leaves the tree until woken"]
    B --> W

Scheduling Latency and Minimum Granularity

CFS targets a scheduling latency (default 6ms): every runnable process should get at least one CPU turn within this window. The time slice for each process is:

time_slice = scheduling_latency × (process_weight / total_weight)

The minimum granularity (default 0.75ms) prevents tiny time slices that would cause excessive context switching when many processes compete.

Three details matter in practice:

  • The defaults scale with CPU count. The 6ms / 0.75ms values are base values multiplied by 1 + log2(min(ncpus, 8)). On any machine with 8 or more CPUs the factor is 4, so the effective values are 24ms latency and 3ms minimum granularity (and 4ms wakeup granularity).
  • The period stretches when the queue is long. sched_nr_latency = latency / min_granularity = 8. With more than 8 runnable tasks, CFS cannot give everyone ≥ min_granularity within the latency target, so the period becomes nr_running × min_granularity. With 20 tasks on an 8+ CPU box: period = 20 × 3ms = 60ms.
  • Where to find the knobs. Until 5.13 they were sysctls (/proc/sys/kernel/sched_latency_ns, sched_min_granularity_ns, sched_wakeup_granularity_ns). Since 5.13 they live in debugfs: /sys/kernel/debug/sched/latency_ns etc. Since 6.6 (EEVDF) latency_ns is gone and base_slice_ns replaces min granularity.

Worked example: three tasks with different nice values

One CPU (on a 16-CPU machine, so sched_latency = 24ms), three CPU-bound tasks:

Taskniceweightshare = weight / 4480slice = 24ms × sharevruntime gained per slice
A-5312169.7%16.72ms16.72 × 1024/3121 = 5.49ms
B0102422.9%5.49ms5.49 × 1024/1024 = 5.49ms
C+53357.5%1.79ms1.79 × 1024/335 = 5.49ms

Total weight = 3121 + 1024 + 335 = 4480.

Look at the last column: every task gains the same vruntime per period (24ms × 1024 / 4480 = 5.49ms). That's the whole trick. Different real runtimes, identical virtual runtimes — so after each 24ms period all three are level in the tree again and the cycle repeats. Over one second A gets ~697ms of CPU, B ~229ms, C ~75ms.

Trace from equal starting vruntime (all 0):

t=0      tree: A(0) B(0) C(0)          → pick A (tie, arbitrary)
t=16.7   A.vruntime = 5.49             → pick B (0)
t=22.2   B.vruntime = 5.49             → pick C (0)
t=24.0   C.vruntime = 5.49             → all equal again, repeat

C's computed slice (1.79ms) is below the 3ms minimum granularity. CFS mainly enforced the minimum through the period-stretch rule above (it only kicks in with >8 tasks); some later CFS versions also clamp individual slices up to the minimum. Either way the long-run share is still 7.5% — clamping only changes how chunky C's turns are.

Now suppose B is an I/O-bound task that only wants 1ms every 10ms. It sleeps most of the time, so its vruntime stays low. When it wakes, its vruntime is far left in the tree → it preempts A almost immediately (if it's behind by more than the wakeup granularity). That is how CFS gives interactive tasks low latency without any "interactivity heuristic": sleeping tasks are naturally behind on vruntime.

Two guards stop this from being abused:

  • New tasks start at the queue's min_vruntime (slightly after, with the START_DEBIT feature), not at 0 — otherwise every new process would monopolize the CPU until it "caught up" with tasks that have been running for days.
  • Long sleepers are woken with vruntime = max(own vruntime, min_vruntime − latency/2) (the GENTLE_FAIR_SLEEPERS rule), so a task that slept for an hour gets a modest boost, not an hour of exclusive CPU.

Group scheduling: fairness between users and containers

With CONFIG_FAIR_GROUP_SCHED, CFS is hierarchical: a cgroup is itself a schedulable entity with a weight (cpu.weight in cgroup v2, default 100; cpu.shares in v1, default 1024), containing its own run queue. If container X has 1 thread and container Y has 100 threads, and both have equal weight, each container gets 50% — not 1% vs 99%. This is what Kubernetes CPU requests map to (covered below). autogroup (/proc/sys/kernel/sched_autogroup_enabled) applies the same idea per terminal session on desktops, so a make -j64 in one terminal doesn't starve your browser.

NUMA Awareness

On multi-socket machines, memory access to a remote NUMA node is 2-3x slower. The Linux scheduler tries to keep processes running on the NUMA node where their memory lives (NUMA affinity). It also implements task migration across cores to balance load, but balances it against the cost of cache invalidation.

Automatic NUMA balancing (/proc/sys/kernel/numa_balancing = 1) periodically unmaps a sample of a task's pages so the next access takes a "NUMA hinting" fault; the kernel then learns which node the task is actually using and migrates either the memory toward the task or the task toward its memory. The multicore section below covers the rest.


EEVDF: Linux 6.6+ (What Replaced CFS)

In Linux 6.6 (October 2023), Peter Zijlstra replaced CFS's pick logic with EEVDF — Earliest Eligible Virtual Deadline First, an algorithm from a 1995 paper by Stoica and Abdel-Wahab. The vruntime and weight machinery above is unchanged; what changed is how the next task is chosen and how latency is expressed.

Why CFS needed replacing

CFS has one dial — weight — and it controls how much CPU you get. But many tasks need to say something different: "I don't need more CPU, I need it sooner." A latency-sensitive audio thread or RPC handler and a video encoder at the same nice level were treated identically. CFS papered over this with heuristics (wakeup granularity, sleeper credit, LAST_BUDDY/NEXT_BUDDY hints) that were hard to reason about and occasionally produced latency spikes.

The three ideas

  1. Lag. For each task, lag = (CPU time it should have had under ideal fair sharing) − (CPU time it actually got). Positive lag: the system owes you. Negative lag: you've had more than your share. In vruntime terms: with V = the weighted average vruntime of the queue, lag_i ∝ V − vruntime_i.
  2. Eligibility. A task is eligible to run only if lag ≥ 0, i.e. vruntime_i ≤ V. Tasks that are ahead of their fair share must wait — this is what bounds unfairness.
  3. Virtual deadline. Each task requests a slice r (default base_slice, 0.75ms base → 3ms on 8+ CPUs). Its virtual deadline is deadline_i = vruntime_i + r × 1024 / weight_i. Among eligible tasks, pick the earliest virtual deadline.

A task with a shorter requested slice gets an earlier deadline, so it runs sooner and more often, in smaller pieces — but its total CPU share is still set by its weight. Latency and bandwidth are finally separate knobs.

flowchart TD
    Q["Runnable tasks on this CPU"] --> V["Compute V = weighted average vruntime"]
    V --> E{"vruntime of task <= V ?"}
    E -->|"no: ahead of fair share"| X["not eligible, skip"]
    E -->|"yes: lag >= 0"| D["candidate"]
    D --> PICK["pick the eligible task with earliest virtual deadline"]
    PICK --> RUN["run for its requested slice"]
    RUN --> UPD["vruntime += runtime x 1024 / weight, deadline = vruntime + slice x 1024 / weight"]
    UPD --> V

Worked example: same weight, different slices

Two nice-0 tasks. A uses the default 3ms slice; B (latency-sensitive) requests 1ms. Both start at vruntime 0.

step  V (avg)  A: vrt/deadline  B: vrt/deadline  eligible        pick
1     0        0 / 3            0 / 1            A, B            B (deadline 1)
2     0.5      0 / 3            1 / 2            A only          A
3     2        3 / 6            1 / 2            B only          B
4     2.5      3 / 6            2 / 3            B (2 ≤ 2.5)     B
5     3        3 / 6            3 / 4            A, B            B (4 < 6)
6     3.5      3 / 6            4 / 5            A only          A
7     5        6 / 9            4 / 5            B               B ...

Over time both get 50% of the CPU (same weight), but B gets it in 1ms pieces and never waits more than about one of A's 3ms slices. Under CFS, B would have had to wait for A's whole computed slice.

What changed in practice

CFS (2.6.23 – 6.5)EEVDF (6.6+)
Pick ruleSmallest vruntimeEarliest virtual deadline among eligible (lag ≥ 0)
Latency controlHeuristics: wakeup granularity, sleeper credit, buddiesPer-task requested slice
Main tunableslatency_ns, min_granularity_ns, wakeup_granularity_nsbase_slice_ns
Sleep handlingSleeper credit (GENTLE_FAIR_SLEEPERS)Lag is preserved and decays; 6.12 adds delayed dequeue so tasks can't shed negative lag by briefly sleeping
Data structurerbtree by vruntime, cached leftmostAugmented rbtree that can find the earliest eligible deadline in O(log n)

From 6.12, a SCHED_OTHER task can request a custom slice via sched_setattr() — the sched_runtime field is reinterpreted as the requested slice for fair tasks (clamped to roughly 0.1–100ms). Most applications never touch it; the default behavior is already reasonable.

Upgrades can shift latency profiles

Moving a fleet from a 6.1 kernel (CFS) to 6.6+ (EEVDF) changed tail latencies for some workloads — usually better, sometimes worse (a few database and game-server workloads reported regressions that were fixed over subsequent releases). Treat a major kernel upgrade like any other performance-affecting change: canary it and compare run-queue latency histograms before and after.

sched_ext: BPF-defined schedulers (6.12+)

Linux 6.12 also merged sched_ext (SCHED_EXT), a scheduling class whose policy is implemented by a BPF program loaded at runtime. Meta and Google drove it to experiment with scheduling policies (e.g. scx_rusty, scx_lavd for gaming latency, scx_layered) without rebuilding kernels. If the BPF scheduler misbehaves or stalls a task, the kernel kicks it out and falls back to the fair class. It's the first time Linux has offered pluggable schedulers in production.


Scheduling Classes in Linux

Linux uses a modular scheduling framework with multiple scheduling classes, ordered by priority:

ClassPolicyUse Case
SCHED_DEADLINEEDF (earliest deadline first)Hard real-time tasks
SCHED_FIFOFIFO, no preemption by same classSoft real-time (audio, robotics)
SCHED_RRRound Robin within prioritySoft real-time
SCHED_OTHERCFSNormal processes (default)
SCHED_BATCHCFS variantBatch jobs (slightly lower priority)
SCHED_IDLEBackgroundOnly runs when nothing else can

Real-time classes (SCHED_FIFO, SCHED_RR) always preempt SCHED_OTHER processes. Used by audio daemons, kernel threads.

(SCHED_OTHER is called SCHED_NORMAL inside the kernel; since 6.6 it's EEVDF rather than CFS, and SCHED_EXT sits between the fair and idle classes when a BPF scheduler is loaded. Strictly, SCHED_DEADLINE gives guarantees only within the limits of admission control; truly hard real-time systems also need PREEMPT_RT and careful hardware.)

flowchart LR
    STOP["stop class: CPU hotplug, migration"] --> DL["SCHED_DEADLINE"]
    DL --> RT["SCHED_FIFO / SCHED_RR, priority 1-99"]
    RT --> FAIR["SCHED_OTHER / BATCH, EEVDF"]
    FAIR --> EXT["SCHED_EXT, BPF policy"]
    EXT --> IDLE["SCHED_IDLE, then idle task"]

On every pick, the kernel asks each class in that order "do you have a runnable task?" and the first class that says yes wins. A runnable RT task therefore always beats any fair task, no matter its nice value.

SCHED_FIFO and SCHED_RR

  • Static priority 1–99 (higher wins). Fair tasks are effectively priority 0.
  • SCHED_FIFO: runs until it blocks, yields, or a higher RT priority wakes. No time slice at all.
  • SCHED_RR: same, but tasks at the same priority rotate with a quantum — 100ms by default (/proc/sys/kernel/sched_rr_timeslice_ms). This is a true classic Round Robin quantum, unlike the computed slices of the fair class.
$ cat /proc/sys/kernel/sched_rr_timeslice_ms
100
$ chrt -f 50 ./audio_engine          # run as SCHED_FIFO priority 50
$ chrt -r 10 ./control_loop          # SCHED_RR priority 10
$ chrt -p $(pgrep pipewire)          # show a running task's policy and priority
pid 1423's current scheduling policy: SCHED_OTHER
pid 1423's current scheduling priority: 0
$ chrt -m                            # min/max priority per policy
#include <sched.h>
struct sched_param p = { .sched_priority = 50 };
if (sched_setscheduler(0, SCHED_FIFO, &p) == -1)   // needs CAP_SYS_NICE or RLIMIT_RTPRIO
    perror("sched_setscheduler");

A spinning SCHED_FIFO task can lock up a CPU

A SCHED_FIFO thread in an infinite loop never yields, so nothing of lower priority — including your shell and most kernel housekeeping on that CPU — runs again. Linux's safety net is RT throttling: sched_rt_runtime_us = 950000 out of sched_rt_period_us = 1000000 means RT tasks may use at most 95% of each second, leaving 50ms for everyone else. Newer kernels (6.12+) replace this with a "deadline server" that reserves time for fair tasks more precisely. Never set sched_rt_runtime_us = -1 (unlimited) on a machine you can't reboot remotely.

SCHED_DEADLINE

The most expressive class. A task declares three numbers: runtime (CPU time needed), deadline (by when, relative to the period start), and period:

# Needs 2ms of CPU every 10ms, finished within 5ms of each period start
$ chrt -d --sched-runtime 2000000 --sched-deadline 5000000 --sched-period 10000000 0 ./video_decoder

The kernel runs these tasks Earliest Deadline First and enforces each task's budget with a Constant Bandwidth Server: overrun your runtime and you're throttled until the next period, so a buggy task can't steal other deadline tasks' time. Admission control refuses sched_setattr() if the total requested bandwidth (Σ runtime/period) would exceed what the CPUs can provide — so guarantees are checked up front rather than discovered at runtime.


Multicore Scheduling

Everything above describes one CPU. A 64-core server runs 64 copies of that logic, plus a layer that moves tasks between them.

Per-CPU run queues

Linux has a separate run queue per CPU (struct rq), each with its own rbtree and its own lock. A single global queue would need a global lock touched on every switch on every core — at hundreds of thousands of switches per second on 64 cores, that lock would be the bottleneck (this was a real problem in Linux 2.4's scheduler). Per-CPU queues also keep tasks on the CPU whose caches already hold their data.

The cost: queues can become unbalanced — CPU 3 has 6 runnable tasks while CPU 7 is idle. Hence load balancing.

Load balancing and scheduling domains

The kernel organizes CPUs into a hierarchy of scheduling domains that mirrors the hardware topology, and balances more eagerly at the cheap levels:

flowchart TD
    NUMA["NUMA domain: balance rarely, migration is expensive"] --> S0["Socket 0"]
    NUMA --> S1["Socket 1"]
    S0 --> MC0["MC domain: cores sharing L3"]
    MC0 --> C0["Core 0"]
    MC0 --> C1["Core 1"]
    C0 --> SMT0["SMT: hyperthreads 0 and 32, share L1/L2"]
    S1 --> MC1["MC domain"]
MechanismWhen it runsWhat it does
Periodic balancingFrom the tick, at intervals that grow with domain level (ms at SMT/MC, longer at NUMA)Busiest CPU in the domain pushes/pulls tasks
Idle balancing (newidle)When a CPU is about to go idleTries to pull work from a busy sibling before sleeping
Wakeup placement (select_task_rq_fair)Every wakeupPrefer the previous CPU (cache hot) or an idle CPU sharing L3 with the waker ("wake affine")
NOHZ idle balancingPeriodically, by one designated CPUBalances on behalf of tickless idle CPUs

Migrating a task costs its cache warmth, so the balancer deliberately tolerates small imbalances. Tasks that ran very recently are considered "cache hot" and are less likely to be moved.

CPU affinity and isolation

$ taskset -c 0-3 ./worker            # start pinned to CPUs 0-3
$ taskset -pc 2 12345                # pin running PID 12345 to CPU 2
$ numactl --cpunodebind=0 --membind=0 ./db   # CPU and memory on NUMA node 0
$ cat /proc/12345/status | grep Cpus_allowed_list
Cpus_allowed_list:      2
#define _GNU_SOURCE
#include <sched.h>
cpu_set_t set;
CPU_ZERO(&set);
CPU_SET(2, &set);
sched_setaffinity(0, sizeof(set), &set);   // pin the calling thread to CPU 2

For latency-critical systems (trading, packet processing with DPDK), operators go further: isolcpus= / cpusets remove CPUs from general scheduling, nohz_full= stops the tick on CPUs running a single task, and IRQ affinity (/proc/irq/*/smp_affinity) moves interrupts elsewhere. The pinned thread then runs essentially uninterrupted.

Pinning is a trade, not a free win

Pinning removes the balancer's ability to help. If you pin 8 busy threads to 4 CPUs while 12 other CPUs sit idle, you've built a run-queue bottleneck by hand. Pin when you have measured cache/NUMA effects or need determinism; otherwise let the scheduler balance.

NUMA in numbers

On a two-socket server, local DRAM access is ~80–100ns and remote ~130–200ns; remote bandwidth is also lower. A memory-bound process whose threads drift to the other socket can lose 20–40% throughput. numastat -p <pid> shows where a process's memory lives; large numa_miss/other_node counts are the symptom.


cgroup CPU Control and the Kubernetes Throttling Problem

Containers add two more controls on top of the per-CPU schedulers, and they behave very differently.

Controlcgroup v2 filecgroup v1 fileKubernetes fieldSemantics
Weight (proportional share)cpu.weight (1–10000, default 100)cpu.shares (default 1024)resources.requests.cpuOnly matters under contention. Work-conserving: idle CPU can be used by anyone.
Quota (hard cap)cpu.max = "$QUOTA $PERIOD"cpu.cfs_quota_us, cpu.cfs_period_usresources.limits.cpuAt most QUOTA μs of CPU per PERIOD μs, across all CPUs. Not work-conserving: throttled even if the machine is idle.

limits.cpu: 2 becomes cpu.max = "200000 100000" — 200ms of CPU time per 100ms period.

How throttling hurts latency: a worked example

The quota is consumed across all threads on all CPUs. A container limited to 2 CPUs, running a service with 10 busy threads on a 16-core node:

Period starts at t=0 (100ms period, 200ms quota)
t=0–20ms   10 threads run in parallel on 10 cores → 10 × 20ms = 200ms consumed
t=20ms     quota exhausted → every thread in the cgroup is THROTTLED
t=20–100ms nothing in the container runs, though 14+ cores are idle
t=100ms    new period, quota refilled, threads resume

Average usage is exactly 2 CPUs — the limit is "working" — but any request that arrived at t=21ms waits ~80ms before it can even start. A service with a 5ms median can show a 100ms p99 for this reason alone, while dashboards show CPU at 60% of the limit (averaged over a minute, the bursts disappear).

sequenceDiagram
    participant App as "Container, 10 threads"
    participant Q as "CFS bandwidth controller"
    App->>Q: "t=0: period starts, quota 200ms"
    App->>Q: "t=0 to 20ms: 10 threads burn 200ms"
    Q-->>App: "t=20ms: quota exhausted, throttle all threads"
    Note over App: "requests queue for 80ms, idle cores unused"
    Q-->>App: "t=100ms: new period, unthrottle"

Confirm it from inside the cgroup:

$ cat /sys/fs/cgroup/cpu.max
200000 100000
$ cat /sys/fs/cgroup/cpu.stat
usage_usec 81234567
user_usec 70011223
system_usec 11223344
nr_periods 51234
nr_throttled 9120          # 17.8% of periods hit the limit
throttled_usec 412345678   # 412 seconds spent throttled

Alert on the ratio nr_throttled / nr_periods (Prometheus: container_cpu_cfs_throttled_periods_total / container_cpu_cfs_periods_total). Anything persistently above a few percent on a latency-sensitive service deserves a look.

History worth knowing: before Linux 5.4, a bug in how per-CPU quota slices expired caused throttling even for containers using far less than their limit — especially multi-threaded apps on many-core nodes. Commit de53fd7aedb1 ("sched/fair: Fix low cpu usage with high throttling by removing expiration of cpu-local slices") fixed it. If you run very old kernels and see throttling at low usage, that's the likely cause. Linux 5.14 added cpu.max.burst, letting a cgroup bank unused quota to absorb short bursts.

Decision guidance for CPU limits

SituationRecommendation
Latency-sensitive service in a trusted clusterSet requests accurately, consider no CPU limit (weight still guarantees its share under contention). Many large operators run this way.
Multi-tenant / untrusted workloadsKeep limits for isolation, but size them for peak bursts, not averages; consider a shorter period or cpu.max.burst.
Need exclusive, dedicated coresKubernetes static CPU manager policy with Guaranteed QoS and integer CPU requests pins the pod to whole cores via cpusets.
Runtime sizes its thread pool from CPU countMake sure it sees the limit, not the node's core count (see below).

Runtimes that guess CPU count wrong: a Go program on a 64-core node with a 2-CPU limit historically set GOMAXPROCS=64 and ran 64 threads into a 2-CPU quota — burning the quota in ~3ms of each period. Go 1.25 made GOMAXPROCS cgroup-limit aware by default; older versions need go.uber.org/automaxprocs or an explicit env var. The JVM has been container-aware since JDK 10 / 8u191 (-XX:ActiveProcessorCount overrides it). Node's libuv threadpool, .NET, and Python multiprocessing pools have similar knobs. See Namespaces & cgroups for the cgroup mechanics.


Observability: Seeing the Scheduler

You can't tune what you can't see. These are the tools, from cheapest to most detailed.

System-wide pressure

$ vmstat 1
procs -----------memory---------- ---swap-- -----io---- -system-- ------cpu-----
 r  b   swpd   free   buff  cache   si   so    bi    bo   in   cs us sy id wa st
 22  0      0 812344  10240 9123456   0    0     0    12 9120 48211 88 10  2  0  0

r = runnable tasks (running + waiting). Persistently r > number of CPUs means tasks are queuing. cs = context switches per second.

$ cat /proc/pressure/cpu        # PSI, Linux 4.20+
some avg10=31.42 avg60=27.80 avg300=20.11 total=982734123

some avg10=31.42 means: in the last 10 seconds, for 31% of the time at least one runnable task was waiting for a CPU. PSI is also available per cgroup (/sys/fs/cgroup/<grp>/cpu.pressure) — the best single "is this container CPU-starved?" signal.

Per-task scheduler stats

$ cat /proc/12345/schedstat
4712345678 912345678 18234
# field 1: ns spent running on CPU
# field 2: ns spent waiting on a run queue (runnable, not running)
# field 3: number of timeslices run on this CPU

Wait time / timeslices = average run-queue delay per scheduling: here 912ms / 18,234 ≈ 50μs. Sample it twice and diff to get a rate.

$ cat /proc/12345/sched
myservice (12345, #threads: 24)
-------------------------------------------------------------------
se.exec_start                                :     912345678.123456
se.vruntime                                  :        123456.789012
se.sum_exec_runtime                          :          4712.345678
se.nr_migrations                             :                 1834
nr_switches                                  :                18234
nr_voluntary_switches                        :                17010
nr_involuntary_switches                      :                 1224
se.load.weight                               :              1048576
policy                                       :                    0
prio                                         :                  120

prio 120 = nice 0 (kernel priority = 120 + nice for fair tasks); policy 0 = SCHED_NORMAL. The weight is shown scaled by 1024 on 64-bit kernels (1048576 = 1024 × 1024). /proc/schedstat gives the same run/wait counters per CPU.

perf sched

$ perf sched record -- sleep 10          # records sched tracepoints system-wide
$ perf sched latency --sort max
 Task                  |  Runtime ms | Switches | Avg delay ms | Max delay ms |
 ----------------------------------------------------------------------------
 java:(48)             |   8123.456  |   91234  |    0.412     |   38.902     |
 nginx:(16)            |   1203.110  |   40211  |    0.031     |    2.114     |

$ perf sched timehist -p 12345           # per-switch timeline: wait time, sch delay, run time
$ perf sched map                         # ASCII map of which task ran on which CPU when

Max delay is the worst time a task sat runnable before running. A 38ms maximum on a service with a 50ms SLO is the scheduler eating most of your budget.

Run-queue latency histogram with bpftrace

This is the scheduler metric that matters most for tail latency: from "task became runnable" to "task got the CPU".

#!/usr/bin/env bpftrace
// runqlat.bt — histogram of run-queue latency in microseconds
tracepoint:sched:sched_wakeup,
tracepoint:sched:sched_wakeup_new
{
    @qtime[args.pid] = nsecs;
}

tracepoint:sched:sched_switch
{
    // A task preempted while still runnable (prev_state == 0, TASK_RUNNING) re-enters the queue now
    if (args.prev_state == 0) {
        @qtime[args.prev_pid] = nsecs;
    }
    $ts = @qtime[args.next_pid];
    if ($ts) {
        @usecs = hist((nsecs - $ts) / 1000);
        delete(@qtime[args.next_pid]);
    }
}

END { clear(@qtime); }
@usecs:
[0]                  412 |@                                                   |
[1]                 9123 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                    |
[2, 4)             14201 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|
[4, 8)              6210 |@@@@@@@@@@@@@@@@@@@@@@                              |
[8, 16)             1820 |@@@@@@                                              |
[16, 32)             301 |@                                                   |
[32, 64)              41 |                                                    |
[64, 128)             12 |                                                    |
[8K, 16K)              9 |                                                    |   ← 8–16ms waits: investigate

The bcc-tools version (runqlat, runqlat -P per PID, runqlen for queue length, cpudist for on-CPU time distribution) does the same with less typing. Older bpftrace versions write args->pid instead of args.pid.

Reading the histogram

A healthy, uncontended host has most samples under ~10μs. A bimodal shape with a second hump at 4–24ms usually means tasks waiting out full slices behind CPU hogs (contention). A hump around 20–100ms in a container is the cgroup quota throttling signature — confirm with cpu.stat.


Failure Modes

SymptomLikely causeHow to confirmFix
p99 spikes of ~(100ms − x) every so often, CPU "below limit"cgroup quota throttlingcpu.stat nr_throttled, runqlat hump at tens of msRaise/remove limit, cpu.max.burst, fix GOMAXPROCS / thread count
Throughput drops as threads are addedOversubscription: switch + cache-refill overheadvmstat cs and r high, pidstat -w nvcswch/s highSize pools to cores (see Processes & Threads)
One CPU at 100%, others idleAffinity mistake, single hot thread, IRQs concentrated on one CPUmpstat -P ALL 1, /proc/interrupts, taskset -pSpread IRQs / RSS queues, remove pinning, parallelize
System freezes but responds to pingRunaway SCHED_FIFO tasktop shows an RT task (PR = rt or negative) at 100%Keep RT throttling enabled, fix the loop
High-priority task blocked for long periodsPriority inversion on a lockOff-CPU analysis (offcputime), lock tracingPriority-inheritance mutexes, shorter critical sections
Latency regressed after a kernel upgradeScheduler change (e.g. CFS → EEVDF)Compare runqlat before/after on canaryTune slice, report upstream, pin kernel version meanwhile
Memory-bound job 30% slower on a two-socket boxNUMA remote access after migrationnumastat -p, perf stat LLC missesnumactl binding, enable NUMA balancing, one process per socket
Background batch job slows foreground serviceSame weight, competing on same coresrunqlat on service, topnice -n 19, SCHED_BATCH/SCHED_IDLE, separate cgroup with lower cpu.weight
# Quick recipes
$ nice -n 19 ./backup.sh                       # lowest fair priority
$ chrt -b 0 ./etl_job                          # SCHED_BATCH: no wakeup preemption of others
$ chrt -i 0 ./indexer                          # SCHED_IDLE: runs only when CPU is otherwise idle
$ renice -n 5 -p 12345                         # change a running process
$ systemd-run --scope -p CPUWeight=20 ./batch  # cgroup weight via systemd

Decision Guidance

flowchart TD
    START["What does the task need?"] --> Q1{"Bounded worst-case latency, missing a deadline is a failure?"}
    Q1 -->|"yes"| Q2{"Known runtime and period?"}
    Q2 -->|"yes"| DL["SCHED_DEADLINE, plus PREEMPT_RT kernel"]
    Q2 -->|"no"| FIFO["SCHED_FIFO or SCHED_RR priority 1-99, keep RT throttling"]
    Q1 -->|"no"| Q3{"Interactive or request-serving?"}
    Q3 -->|"yes"| NORMAL["SCHED_OTHER nice 0, right-size threads, avoid tight CPU limits"]
    Q3 -->|"no: batch"| Q4{"Should it ever compete with foreground work?"}
    Q4 -->|"a bit"| BATCH["SCHED_BATCH or nice 10-19"]
    Q4 -->|"never"| IDLEC["SCHED_IDLE or low cpu.weight cgroup"]

Rules of thumb:

  1. Don't reach for real-time classes to fix a slow service. RT is for bounded latency, not more throughput, and a misbehaving RT task hurts everything else.
  2. Fix oversubscription before tuning the scheduler. Runnable threads ≫ cores is the most common scheduler "problem", and it's an application sizing bug.
  3. Measure run-queue latency, not just CPU %. A host at 60% CPU can still have 20ms scheduling delays if work arrives in bursts.
  4. Treat CPU limits as a latency risk. Weights (requests) give fairness without stalls; quotas (limits) can stall you on an idle machine.
  5. Touch scheduler tunables last, and only with before/after histograms. The defaults are tuned for a wide range of workloads.

Advanced Topics

  • Energy-aware scheduling (EAS). On big.LITTLE / hybrid CPUs (Arm phones, Intel P-cores/E-cores), the scheduler uses an energy model to place tasks on the cheapest core that meets their demand. Utilization is tracked with PELT (per-entity load tracking, a geometrically-decaying average with a ~32ms half-life), and schedutil drives CPU frequency from the same signal.
  • Utilization clamping (uclamp). cpu.uclamp.min/max (cgroup) or sched_setattr() hints tell the scheduler "treat this task as at least/at most X% utilization" — Android uses it to keep the UI thread on big cores at high frequency.
  • Core scheduling (5.14+). For SMT security (L1TF/MDS side channels), only tasks with the same "cookie" may share a physical core's hyperthreads at the same time; used by some cloud providers instead of disabling SMT.
  • Lock-holder preemption in VMs. The guest kernel schedules vCPUs, the hypervisor schedules them onto physical CPUs. If a vCPU is descheduled while holding a spinlock, other vCPUs spin uselessly. Paravirtual spinlocks and pause-loop exiting mitigate it; st (steal) in vmstat/top shows time your vCPU was runnable but the host ran something else.
  • User-space schedulers on top. Go's runtime (G-M-P model), Java virtual threads, Tokio and Erlang's BEAM all run their own schedulers over a fixed pool of OS threads; the OS scheduler sees only those few threads. Their interaction with cgroup limits is where most production surprises come from. See Processes & Threads and Async Patterns.
  • Real-time system design beyond the kernel (rate-monotonic analysis, WCET, jitter budgets) is covered in Real-Time Systems.

Interview Questions

"What is a context switch? Why is it expensive?" Saving all CPU registers + PC of the current process, loading saved state of the next. Expensive because: (1) CPU must execute many kernel instructions, (2) TLB must be flushed when switching between processes with different address spaces — TLB reload causes cache misses until the working set is loaded. With PCID the flush itself is avoided, but the indirect cost — refilling caches and TLB evicted by the other task — usually dominates the 1–5μs direct cost.

"What is the difference between preemptive and cooperative scheduling?" Cooperative: process voluntarily yields. Preemptive: kernel forcibly takes CPU when time slice expires or higher-priority task arrives. Modern OSes are preemptive.

"Why are goroutines/coroutines cheaper than OS threads?" User-space scheduling — context switch doesn't enter the kernel. Smaller stacks (2KB for goroutines vs 1MB for OS threads). Scheduler has application-level context (can yield at await or channel ops). No TLB flush.

"What is the nice value in Linux?" A hint to the CFS scheduler about relative priority. Range: -20 (highest priority, gets more CPU time) to +19 (lowest). Only affects how fast vruntime accumulates — doesn't guarantee CPU time. Each step changes weight by ~1.25×, which works out to about 10% CPU between neighbouring nice levels.

"What is a time quantum, and how would you choose one?" The maximum continuous CPU time a task gets before the scheduler reconsiders, enforced by a timer interrupt. Too small → context-switch overhead dominates (with a 30μs effective switch, a 0.1ms quantum wastes ~23% of the CPU). Too large → response time grows as (n−1) × q and RR degenerates to FCFS. Choose it longer than most CPU bursts (so interactive tasks finish in one slice) and short enough for the latency target — typically 1–10ms.

"How does CFS decide the time slice?" It doesn't use a fixed quantum: slice = sched_latency × weight / total_weight, with the period stretched to nr_running × min_granularity when more than 8 tasks are runnable. Each task's vruntime advances by runtime × 1024 / weight, so in steady state every task's vruntime advances equally per period.

"What changed with EEVDF?" Same vruntime and weights, new pick rule: only tasks with non-negative lag (not ahead of their fair share) are eligible, and among them the earliest virtual deadline (vruntime + slice × 1024/weight) runs. A shorter requested slice means lower latency without more total CPU.

"Why does my container get throttled when the node is mostly idle?" CPU limits are CFS bandwidth quotas: N ms of CPU per 100ms period summed across all threads. A multi-threaded burst can burn the quota in a fraction of the period, and then every thread waits until the next period regardless of idle cores. Check cpu.stat nr_throttled.