Most Linux threads do not request a real-time priority or a CPU reservation. They use the normal fair scheduling policy and expect the kernel to share the processor reasonably.

That simple expectation hides a difficult problem. The scheduler must divide one logical CPU among many runnable threads, respect different nice values, respond quickly when an interactive thread wakes, and avoid switching so frequently that scheduling overhead consumes the benefit.

For many years, Linux addressed this with the Completely Fair Scheduler (CFS). Linux began transitioning the fair class to Earliest Eligible Virtual Deadline First (EEVDF) in version 6.6. EEVDF retains the weighted-fairness foundation of CFS but makes latency and selection decisions more explicit.

The transition is easiest to understand by starting with an impossible machine: a CPU that can run every runnable thread simultaneously.

Suppose two equally important CPU-bound threads remain runnable for ten seconds on one CPU. A fair scheduler should give each approximately five seconds of CPU service:

If A has twice B's scheduling weight, the intended division becomes:

This is weighted fairness. Over a suitable interval, each runnable thread should receive CPU service in proportion to its weight:

Fairness is measured among work that is eligible and runnable. A thread sleeping while it waits for a network packet does not need CPU service during that interval.

Fair scheduling is also work-conserving. If only one normal thread is runnable, it can use the whole CPU even if it has an unfavorable nice value. A weight controls relative service under contention; it is not a CPU usage limit.

Fairness alone is not enough. A scheduler must also consider:

CFS and EEVDF pursue the same broad goal but use different selection rules to balance these concerns.

Imagine an ideal CPU that can divide its processing power continuously among every runnable thread.

With three equal-weight threads, each executes at one-third speed:

On an ideal CPU, A, B, and C would each receive one third of the capacity at every instant.

After three milliseconds of wall-clock time, each thread has received one millisecond of CPU service. No thread waits for a turn because all three progress simultaneously.

A real CPU cannot usually execute three software threads on one logical processor at the same instant. It must approximate the ideal result by alternating:

On a real CPU, they take turns instead: A, then B, then C, then A again.

The scheduler's task is not to reproduce simultaneous execution at every instant. It is to keep each thread's accumulated service close to what the ideal CPU would have supplied while using practical, discrete execution intervals.

CFS was merged in Linux 2.6.23. Its central idea is to measure a thread's progress in virtual runtime, usually written as vruntime.

Virtual runtime is CPU execution time adjusted by scheduling weight. In simplified form:

For a thread with the reference weight, one millisecond of actual execution adds approximately one millisecond of virtual runtime.

A higher-weight thread accumulates virtual runtime more slowly:

A lower-weight thread accumulates it more quickly:

CFS generally favors the runnable entity with the smallest virtual runtime. That is the entity furthest behind on the ideal weighted timeline.

A Weighted Example

Consider an illustrative pair of weights:

A should receive twice as much CPU service as B.

If A runs for two milliseconds:

If B runs for one millisecond:

After A receives two milliseconds and B receives one, both have advanced by the same amount in virtual time:

The unequal real execution produces equal progress on the ideal weighted timeline. Repeated over time, this gives A roughly two-thirds of the CPU and B roughly one-third.

The numbers above use simplified weights. Linux maps nice levels to a fixed table of weights rather than exposing arbitrary task weights through nice.

For normal fair-scheduled threads, Linux nice values range from -20 to +19.

The mapping is multiplicative. Moving by one nice level changes the weight by approximately a factor of 1.25.

This means the effect depends primarily on the difference between two nice values. A pair at nice 0 and 1 has approximately the same share ratio as a pair at nice 10 and 11.

For two continuously runnable threads:

Their approximate shares on one otherwise idle CPU are:

These are long-run proportions under sustained contention, not fixed reservations. Wakeups, migrations, other runnable work, and measurement duration can all affect a short observation.

Each CPU maintains scheduling state for its runnable fair entities. Under the classic CFS model, runnable entities are arranged in a red-black tree ordered by virtual runtime:

The scheduler always takes the leftmost entity, so selection costs nothing more than reading the front of the ordered set.

The entity on the left has received the least weighted service relative to the others, so CFS chooses it next.

As A executes, its virtual runtime increases. It moves toward the right side of the ordering:

The red-black tree keeps insertion, removal, and ordered selection efficient as the number of runnable entities grows.

Linux also tracks a per-run-queue value called min_vruntime. It is a monotonically advancing reference for the run queue's virtual timeline. It helps the kernel place newly runnable and migrating entities sensibly instead of comparing unrelated lifetime CPU totals.

The stored values are therefore accounting coordinates, not timestamps that can be compared directly with wall-clock time.

CFS is preemptive, but it is not classical Round Robin.

Round Robin normally gives each ready process a fixed quantum and rotates through a FIFO queue. CFS calculates execution opportunities from the target scheduling granularity, the number and weights of runnable entities, and wakeup behavior.

Conceptually, an entity's expected portion of a scheduling period is:

The actual kernel calculation includes minimum granularity and implementation details. When many threads are runnable, Linux cannot keep shrinking slices without limit. Extremely short intervals would cause excessive context switches and cache disruption.

A running thread is charged for the CPU time it consumes. When another entity becomes sufficiently more deserving according to fair-class rules, the running thread can be preempted.

This produces rotation without requiring every thread to receive the same fixed quantum.

An interactive thread often behaves like this:

A CPU-bound thread behaves differently:

The sleeping thread should not be charged for CPU time it did not consume. When it wakes, it may legitimately be behind runnable CPU-bound work and deserve prompt service.

However, sleep must not create unlimited credit. Otherwise, a thread could sleep for a long time, wake with an ancient virtual runtime, and monopolize the CPU while it spends an enormous accumulated advantage.

CFS places a waking entity relative to the run queue's current virtual-time reference. This preserves a responsiveness benefit without allowing unbounded sleeper credit.

Wakeup behavior is one of the places where fairness and latency meet. A purely long-run share calculation does not decide whether a freshly awakened thread should preempt the thread currently using the CPU.

CFS's minimum-vruntime rule provides a strong and understandable fairness foundation. It does not, by itself, express two separate questions:

Under CFS, virtual runtime is central to both fairness and selection. Additional granularity and wakeup rules help balance throughput against interactive response.

EEVDF separates the decision more clearly. It uses lag to determine whether an entity is eligible, then a virtual deadline to order the eligible entities.

This permits a latency-sensitive entity to request a shorter service interval and receive an earlier virtual deadline, while still preventing an entity that is ahead of its fair share from repeatedly winning.

EEVDF was originally described in scheduling research in 1995. Linux began adopting a new implementation of the algorithm in version 6.6.

EEVDF is not a new user-visible policy and not a new scheduling class. It is the selection algorithm used inside the Linux fair scheduling class. Normal applications still use policies such as SCHED_OTHER, and nice values still determine their relative weights.

The name describes its two-stage choice:

Understanding those stages requires two new quantities.

An entity's lag compares the service it should have received on the ideal weighted CPU with the service it actually received:

The sign has a direct meaning:

EEVDF considers an entity eligible when its lag is nonnegative:

Suppose two equal-weight threads should each have received four milliseconds by the current point on the ideal timeline:

A is owed service and is eligible. B is ahead and is temporarily ineligible, even if another part of its ordering state would otherwise look favorable.

Lag preserves the fairness constraint. It stops latency-oriented selection from continually rewarding a task that has already received more than its share.

Each entity receives a service request, often described as a slice. EEVDF places a virtual deadline at the end of that request on the entity's weighted virtual timeline.

Conceptually:

The kernel uses scaled virtual-time arithmetic, so these values should be understood as an ordering model rather than literal wall-clock timestamps.

Among eligible entities, the one with the earliest virtual deadline runs first:

A shorter request usually produces a nearer virtual deadline when other conditions are comparable. This lets latency-sensitive work ask to be reconsidered sooner without granting it a permanently larger CPU share.

An entity with a larger weight also advances through virtual time more slowly for the same real service. Weight therefore remains part of both long-run fairness and virtual-deadline calculation.

Assume three entities currently have the following illustrative state:

C has the earliest virtual deadline, but its lag is negative. It has already received more than its fair share, so it is not eligible.

A and B both have nonnegative lag. Between them, A has the earlier virtual deadline:

As A executes, its actual service increases and its lag falls. It may cease to be eligible, allowing B or another owed entity to run.

The example captures the purpose of both tests:

The shortest request does not always win. It must first be eligible.

The word deadline can be misleading.

An EEVDF virtual deadline is an internal ordering value in the fair scheduler. Missing it does not have the application-level meaning of missing an audio, control, or transaction deadline. It does not create an admission-tested CPU reservation.

EEVDF remains a best-effort fair scheduler. A normal thread can be delayed by higher scheduling classes, interrupt handling, CPU contention, or other kernel activity. Applications that require bounded completion cannot treat EEVDF's virtual deadlines as timing guarantees.

EEVDF is also not Shortest Job First. The requested slice is an interval of service before reconsideration, not a prediction of the thread's entire remaining CPU burst.

Sleeping tasks create the same accounting challenge under EEVDF that they did under CFS. A task should benefit from having consumed no CPU while asleep, but it should not manufacture unlimited positive lag by repeatedly sleeping and waking.

Current Linux EEVDF implementations use deferred dequeue and virtual-time-based lag decay for sleeping entities. At a high level:

An eligible waking entity can preempt the current entity when its virtual deadline is earlier. This gives short-request, latency-sensitive work a principled path to faster response.

The exact sleeper-accounting mechanics have continued to evolve during Linux's EEVDF transition. The stable mental model is that sleep does not consume service, but it also does not provide an unlimited scheduling credit.

The move from CFS selection to EEVDF is an evolution of the fair class, not a replacement of every CFS concept.

Nice values and weights still matter. Per-CPU fair run queues still matter. Virtual runtime still matters. The kernel implementation remains in the fair scheduling code, and fields such as se.vruntime remain visible in scheduler diagnostics.

For that reason, tools and discussions may continue to use CFS informally when referring to normal Linux scheduling, even on a kernel whose selection logic is EEVDF-based. When exact behavior matters, the kernel version and distribution patches matter more than the label used by a monitoring tool.

On a multiprocessor system, each CPU normally makes fair-class selections from local scheduling state. Load balancing moves runnable work when useful, but there is not one red-black tree containing every normal thread in the machine.

When an entity migrates, its virtual accounting must be translated relative to the destination run queue. Otherwise, unrelated vruntime baselines could give the migrated thread an artificial advantage or penalty.

Linux can also perform group scheduling. A scheduling entity may represent an individual thread or a group containing more entities. The scheduler can first divide service among groups, then divide each group's service among its threads:

Group A's two threads divide one share between them rather than collecting one share each, which is what stops a group from gaining CPU time simply by creating more threads.

Consequently, counting threads alone may not predict CPU share on a system whose workload manager has configured scheduling groups. Fairness follows the active hierarchy and weights.

Linux exposes per-thread scheduler accounting in /proc/<tid>/sched. Field availability and names can vary with kernel configuration, but common fair-scheduler fields include:

A typical result resembles:

se.sum_exec_runtime is accumulated CPU execution. se.vruntime is weighted virtual accounting. se.load.weight is the kernel's scaled scheduling weight, which may include an internal scale factor rather than displaying the familiar nice-0 value directly.

Do not compare raw vruntime values from unrelated CPUs or widely separated observations as if they were wall-clock timestamps. Their useful meaning comes from the run queue and accounting context in which the kernel uses them.

The effect of weighted fairness is easiest to see with two CPU-bound processes forced to contend on one logical CPU.

First, inspect which CPUs the current shell may use:

Choose one CPU from the reported set and substitute it for 0 below:

Both processes perform the same endless computation and are pinned to the same CPU. The only intentional scheduling difference is that one has nice 0 and the other nice 5.

Over a sufficiently long observation, the nice-0 process should receive roughly three times as much CPU service:

The numbers will not be exact. The shell, interrupts, virtual-machine scheduling, container CPU limits, and the measurement window all introduce noise. The important result is the sustained weighted ratio, not a precise five-second percentage.

This experiment demonstrates a property shared by both classic CFS and EEVDF: nice values influence proportional service when fair-class work contends.

Linux fair scheduling approximates an ideal processor that supplies runnable entities with CPU service in proportion to their weights. CFS implemented this model using weighted virtual runtime and generally selected the runnable entity with the smallest vruntime.

EEVDF preserves weighted fairness while separating eligibility from ordering. Nonnegative lag identifies entities that are owed service, and the earliest virtual deadline selects among them. Shorter service requests can therefore improve response without allowing a task that is already ahead to ignore fairness.

The transition does not turn normal scheduling into real-time scheduling. Nice values remain weights, virtual deadlines remain internal ordering values, and observed CPU shares remain best-effort outcomes shaped by runnable work, per-CPU queues, and scheduling groups.