« Previous Lecture | Next Lecture »

What You Will Learn

• How CFS defined fairness with vruntime and why that idea still matters
• The one problem CFS could not solve well: latency
• How the EEVDF scheduler in Linux adds eligibility, lag, and virtual deadlines
• How nice values translate into weight and shorter/longer virtual deadlines
• How to observe fair-scheduler behavior on your own machine

Prerequisites

• Lecture 1 of this series: Linux CPU scheduler architecture and scheduling classes
• A Linux system with kernel 6.6 or newer (check with uname -r)

First, the Foundation: How CFS Thought About Fairness

To understand EEVDF you must first understand CFS, because EEVDF is an evolution built on the same foundation, not a from-scratch rewrite. CFS (Completely Fair Scheduler, kernels 2.6.23 to 6.5) modeled an imaginary “perfect” CPU on which N runnable threads each receive exactly 1/N of the processor simultaneously. Real CPUs cannot do that, so CFS approximated it with bookkeeping:

• Each fair thread has a scheduling entity (struct sched_entity) embedded in its task structure.
• The entity tracks vruntime — virtual runtime — a 64-bit nanosecond counter of how much weighted CPU time the thread has consumed.
• Runnable entities sit in a per-CPU red-black tree ordered by this virtual time. A red-black tree is a self-balancing binary search tree, so insert/remove cost O(log n), and caching the leftmost node makes “find the minimum” effectively O(1).
• CFS’s rule: always run the entity with the smallest vruntime — the thread that has had the least CPU so far, i.e., the one fairness owes the most.

Weight enters through the nice value: for a nice 0 thread, vruntime advances at wall-clock speed; for higher-priority (negative nice) threads it advances slower, and for lower-priority threads faster. So a high-priority thread “looks” like it has run less and gets picked more often. Elegant — and this weighting machinery is still in the kernel today.

The Problem: Fairness Says Nothing About Urgency

Imagine two threads that both deserve 50% of the CPU: a video player that must produce a frame every 16 ms, and a compiler crunching files. CFS gives both the right amount of CPU over time, but it has no vocabulary for when each needs it. Both simply compete on “who has the smallest vruntime”. Over the years the kernel accumulated wakeup-preemption heuristics and out-of-tree “latency nice” patches to compensate. EEVDF was merged precisely to replace those heuristics with a principled model.

The EEVDF Scheduler in Linux: Three Simple Ideas

EEVDF comes from a 1995 academic algorithm (Stoica and Abdel-Wahab) and was implemented for Linux by Peter Zijlstra, landing in kernel 6.6. It keeps vruntime, keeps the weights, keeps the tree — and changes the selection rule. Three concepts do all the work:

The selection rule that gives the algorithm its name: among all eligible threads, run the one with the earliest virtual deadline.

Why the EEVDF Scheduler in Linux Fixes Latency

Fairness is enforced by eligibility: nobody can stay ahead of their share, so long-term CPU distribution is still proportional to weight — exactly like CFS. Latency is handled by the deadline: a thread that needs to run soon-but-briefly (an interactive or audio thread) effectively requests a short slice, which produces an early virtual deadline, so it is chosen quickly — it just gives the CPU back sooner. A batch thread with a long slice gets a later deadline but bigger uninterrupted chunks. Same total CPU, very different responsiveness. This is also what made the mainline latency nice hacks unnecessary.

CFS vs the EEVDF Scheduler in Linux: Side-by-Side

Aspect	CFS (2.6.23 – 6.5)	EEVDF (6.6 – today)
Selection rule	Smallest vruntime (leftmost tree node)	Earliest virtual deadline among eligible threads
Fairness	Weighted fair share via vruntime	Same weighted fair share, enforced via lag/eligibility
Latency control	Heuristics (wakeup preemption tweaks)	Built-in, via per-task slice → virtual deadline
Data structure	Per-CPU red-black tree	Still a per-CPU red-black tree (augmented for deadline search)
Nice/weights, cgroups	Weight tables, group scheduling	Unchanged — reused as-is
Class / file	fair_sched_class, kernel/sched/fair.c	Same class and file — only internals changed

This table is why interviewers now love the question “Is CFS gone?” The honest answer: the fair class survives, most of its machinery survives, but the pick algorithm is EEVDF. Calling today’s fair scheduler “CFS” is increasingly a naming leftover.

Observe the EEVDF Scheduler in Linux on Your Machine

The EEVDF scheduler in Linux is fully observable from userspace. Try these on any kernel 6.6+ system:

# 1. Confirm your kernel version (need 6.6+ for EEVDF)
uname -r

# 2. Watch a thread's fair-scheduler statistics live
#    vruntime, deadline and slice appear directly in this file
watch -n1 "grep -E 'vruntime|deadline|slice' /proc/self/sched"

# 3. See the scheduler features currently enabled (root required)
sudo cat /sys/kernel/debug/sched/features

# 4. The base time-slice knob used to build virtual deadlines
cat /sys/kernel/debug/sched/base_slice_ns 2>/dev/null || \
sudo cat /sys/kernel/debug/sched/base_slice_ns

A tiny experiment that makes weights tangible — run two CPU hogs at different nice values and watch CPU share follow the weight:

# Terminal 1: a nice 0 CPU hog
sh -c 'while :; do :; done' &

# Terminal 2: a nice +10 CPU hog (lower priority)
nice -n 10 sh -c 'while :; do :; done' &

# Terminal 3: observe the unequal but stable CPU split
top -d 1

# Cleanup when done
kill %1 %2

On a single CPU (try taskset -c 0 before each command to force it), the nice 0 hog receives roughly ten times the CPU of the nice +10 hog — the weight ratio in action, identical in spirit under CFS and EEVDF.

Common Mistakes

• Thinking vruntime is gone. It is not — EEVDF still advances vruntime; it just adds eligibility and deadlines on top.
• Confusing EEVDF’s virtual deadlines with SCHED_DEADLINE. They are unrelated. EEVDF deadlines are internal fairness bookkeeping for normal threads; SCHED_DEADLINE is a separate real-time policy with hard admission control.
• Tuning old CFS knobs. Several classic tunables (like the old wakeup-granularity settings) were removed or relocated during the EEVDF transition; on modern kernels look under /sys/kernel/debug/sched/ instead of expecting the old sysctl set.
• Expecting nice to change latency. Nice changes CPU share (weight). Latency behavior comes from slice length and deadlines.

Performance Considerations

• Picking a task remains cheap: the tree keeps ordering, and leftmost-style caching plus augmented search keeps the hot path effectively constant-time in practice.
• For throughput-oriented embedded workloads, batch-type threads benefit from longer slices (fewer context switches); interactive threads benefit from EEVDF’s early deadlines — you generally get sane behavior without tuning.
• If you truly need custom behavior (e.g., gaming handhelds, telecom dataplanes), kernel 6.12+’s sched_ext is the supported experimentation path — not patching fair.c.

Key Takeaways

• The EEVDF scheduler in Linux replaced the CFS pick rule in kernel 6.6 while reusing vruntime, weights, the rb-tree, and cgroup support.
• Eligibility (lag ≥ 0) preserves fairness; earliest virtual deadline delivers latency awareness.
• Nice values still control long-term CPU share exactly as before.
• Everything is observable via /proc/<pid>/sched and /sys/kernel/debug/sched/.

Conclusion

EEVDF is best understood as CFS growing a sense of time: the same fair-share accounting, now paired with deadlines that let urgent-but-light threads run promptly without stealing anyone’s share. If you are following this free Linux kernel development course for embedded work, this model explains most of the scheduling behavior you will ever debug on a modern target board. Next lecture: hands-on querying of every thread’s scheduling policy and real-time priority with chrt, ps, and a small C program — a practical skill for every free Linux device drivers course student.

FAQ

What is the EEVDF scheduler in Linux?

EEVDF (Earliest Eligible Virtual Deadline First) is the algorithm the fair scheduling class uses since kernel 6.6 to pick which normal thread runs next: among threads that have not exceeded their fair share, run the one with the earliest virtual deadline.

Which kernel version introduced EEVDF?

Kernel 6.6 (October 2023) merged it into the fair class; later releases refined and completed the transition, and all current kernels (including 7.x) use it.

Did EEVDF remove vruntime?

No. vruntime still measures weighted virtual runtime; EEVDF layers lag, eligibility, and deadlines on top of it.

Is EEVDF a real-time scheduler?

No. It schedules normal (SCHED_OTHER/BATCH/IDLE) threads. Real-time work still uses SCHED_FIFO, SCHED_RR, or SCHED_DEADLINE.

Why did Linux replace CFS’s pick logic?

CFS guaranteed fair CPU amounts but had no principled way to express urgency, forcing latency heuristics. EEVDF encodes latency directly through per-task slices and virtual deadlines.

Does nice value still work under EEVDF?

Yes, unchanged: nice maps to weight, and weight determines each thread’s long-term CPU share.

How can I check EEVDF behavior on my system?

Read /proc/<pid>/sched for vruntime/deadline/slice values and /sys/kernel/debug/sched/features for enabled scheduler features (root needed for debugfs).