← Interview Prep

Linux Kernel — Process Scheduling

How Linux picks the next task: scheduling classes (deadline/RT/CFS/idle), CFS/EEVDF fairness via vruntime + nice weight & the red-black tree, preemption (need_resched, PREEMPT levels) and the context switch cost, per-CPU run queues, load balancing over scheduling domains, and CPU affinity/isolation.

How the kernel decides which task runs next on each CPU — priorities, fairness, preemption, and the context switch. Original, interview-focused notes on the Linux scheduler.

The scheduler picks the next task per-CPU from scheduling classes in priority order: stop → deadline → real-time → CFS (normal) → idle. Most tasks live in CFS, whose goal is fairness: give every runnable task a proportional share of CPU.

Scheduling classes

Class	For	Policy
Deadline (`SCHED_DEADLINE`)	Hard timing	EDF — earliest deadline first (runtime/period/deadline).
Real-time (`SCHED_FIFO`/`SCHED_RR`)	Latency-critical	Fixed priority 1–99; RT always beats normal tasks.
CFS / EEVDF (`SCHED_NORMAL`)	Everything else	Proportional fair share, weighted by nice.
Idle (`SCHED_IDLE`)	Background	Runs only when nothing else is runnable.

A higher class always preempts a lower one, so a busy SCHED_FIFO task can starve normal tasks — why RT priorities are used sparingly.

CFS — the fair scheduler

The Completely Fair Scheduler (in recent kernels, refined by EEVDF) models an ideal "everyone runs at once" CPU and picks whoever is most behind:

vruntime — each task's accumulated runtime, weighted by nice. Low-nice (high-priority) tasks accrue vruntime slower, so they get more CPU.
Runnable tasks sit in a per-CPU red-black tree keyed by vruntime; the scheduler runs the leftmost (smallest vruntime) task. O(log n) pick.
nice (−20…+19) sets the weight; each nice level ≈ a 1.25× CPU-share change. There are no fixed time slices — a task runs until its vruntime catches up to its peers (bounded by a target latency).
A task that sleeps and wakes doesn't get punished for the time it was idle — it keeps roughly its place, so interactive tasks stay responsive.

Preemption & the context switch

When does a switch happen? A task blocks/sleeps; a higher-priority task wakes; the running task's fair share is used up; or a return-to-user / preemption point is reached. The tick and wakeups set TIF_NEED_RESCHED; schedule() then runs.
Preemptible kernel: configurable — PREEMPT_NONE (server, only at syscall boundaries), PREEMPT_VOLUNTARY, PREEMPT (low-latency), PREEMPT_RT (real-time, nearly everything preemptible).
Context switch = save the old task's registers/stack, switch the address space (CR3, if the mm differs — threads of one process skip this), restore the new task. Costs cycles plus TLB/cache disturbance — the real price.

Multiprocessor: run queues & balancing

Each CPU has its own run queue — no global lock in the hot path.
Load balancing periodically (and on idle) migrates tasks between CPUs, guided by scheduling domains that model the topology (SMT siblings → cores → sockets/NUMA), preferring to keep a task near its memory and warm caches.
CPU affinity (taskset, sched_setaffinity) pins tasks; isolation (isolcpus, cgroup cpuset) reserves CPUs — the low-latency/trading toolkit. See Low-Latency.

Likely interview questions

Name the scheduling classes in priority order; where do normal tasks sit?
How does CFS achieve fairness? (vruntime + nice weight, run the smallest, RB-tree)
What does nice actually change? (weight → CPU share, not a fixed slice)
What triggers a context switch, and what makes it expensive? (need_resched; TLB/cache cost)
SCHED_FIFO vs SCHED_RR vs SCHED_NORMAL — and the risk of RT priorities? (starvation)
How does the scheduler scale across CPUs? (per-CPU run queues + load balancing over sched domains)
How do you pin/isolate CPUs for latency-sensitive work? (affinity, isolcpus, cpuset)
What is kernel preemption and what do PREEMPT levels change?

Kernel Internals series. Related: Processes · Low-Latency.