How does the Linux scheduler work (CFS and EEVDF)?
Short answer: For normal tasks, Linux tries to give each runnable task a fair share of CPU time weighted by its nice value. CFS (Completely Fair Scheduler, 2.6.23 to 6.5) tracked each task's virtual runtime (actual runtime scaled by its weight), kept runnable tasks in a red-black tree sorted by vruntime, and always ran the task with the smallest vruntime (the leftmost node). Since Linux 6.6, EEVDF (Earliest Eligible Virtual Deadline First) replaced CFS's picking rule: it still uses weighted virtual time, but among tasks that are "eligible" (not ahead of their fair share) it picks the one with the earliest virtual deadline, which gives better latency control.
Weights and nice values
- Nice ranges from −20 (highest priority) to +19 (lowest). Nice 0 has weight 1024; each nice step changes the weight by about 1.25×, so a task one nice level higher gets about 10% more CPU than its neighbour.
vruntime += actual_runtime × 1024 / weight. A high-weight task's vruntime grows slowly, so it gets picked more often.
Example: two CPU-bound tasks, one at nice 0 (weight 1024) and one at nice 5 (weight 335). CPU shares are 1024 / (1024 + 335) ≈ 75% and ≈ 25%.
Why a red-black tree: insert and delete are O(log n), and the leftmost node (smallest vruntime) is cached, so picking the next task is O(1). A task that blocked for a long time is placed relative to the current minimum vruntime when it wakes, so it gets a quick turn without being able to monopolise the CPU.
EEVDF in one paragraph: each task has a lag (how much service it is owed). A task is eligible if its lag is ≥ 0. Its virtual deadline is roughly its eligible time plus slice / weight. The scheduler picks the eligible task with the earliest virtual deadline. Tasks can request shorter slices (latency-sensitive work) without getting more total CPU.
Scheduling classes (checked in priority order)
| Class | Policies | Use |
|---|---|---|
| stop | – | internal (CPU hotplug, migration) |
| deadline | SCHED_DEADLINE |
runtime/period/deadline reservations (EDF + CBS) |
| real-time | SCHED_FIFO, SCHED_RR (priority 1–99) |
soft real-time, control loops |
| fair | SCHED_NORMAL (SCHED_OTHER), SCHED_BATCH |
everything else |
| idle | SCHED_IDLE |
lowest-priority background work |
Multi-core: each CPU has its own runqueue; the load balancer migrates tasks between CPUs considering cache topology and, on big.LITTLE/DynamIQ systems, energy-aware scheduling (place small tasks on efficient cores).
Tools: nice, renice, chrt (real-time policy), taskset (affinity), /proc/<pid>/sched, perf sched, and sched_ext (6.12+) for BPF-based custom schedulers.