10.2 Linux Scheduling Classes, CFS, and EEVDF

Classic scheduling exercises use one ready queue. A real Linux system simultaneously schedules ordinary services, batch jobs, and deadline-constrained control threads across multiple cores. Tasks may belong to different cgroups, while thermal and power policies alter available capacity. One "universal red-black tree" is not enough to explain all of that.

10.1 Scheduling Metrics and Classic Algorithms establishes a baseline evaluation framework. This lesson shifts focus to Linux: it maintains multiple scheduling classes and manages SMP, cgroups, and energy policies. We distinguish stable concepts from version-specific mechanisms; source code fields and selection rules are governed by the running kernel.

Identify the Task’s Scheduling Class

The Linux scheduler core organizes different scheduling strategies via scheduling classes. Ordinary workloads, real-time tasks, and deadline tasks are not governed by the same selection rules.

Common user-visible policies include:

Policy	Use Case Outline	Key Parameters
SCHED_OTHER / SCHED_NORMAL	Ordinary time-sharing tasks	nice/weight, fair scheduling state
SCHED_BATCH	CPU-heavy batch	Reduced wakeup preemption; less emphasis on interactivity
SCHED_IDLE	Low-weight background tasks	A standard class policy weaker than nice 19
SCHED_FIFO	fixed-priority real-time	RT priority, no RR quantum
SCHED_RR	fixed-priority real-time	RT priority + round-robin quantum
SCHED_DEADLINE	reservation/deadline	runtime, deadline, period
SCHED_EXT (when supported)	Extensible BPF scheduling	Loaded scheduler’s rules

With sched_ext enabled, a BPF scheduler may take over SCHED_OTHER/BATCH/IDLE/EXT in full mode, or only SCHED_EXT in partial mode. SCHED_OTHER alone therefore does not prove that a task currently uses EEVDF.

Class precedence and internal stop/idle classes add further implementation details. Ordinary users may not have the permission to set RT/deadline policies; RLIMIT_RTPRIO, capability, cgroup, and security policy all participate.

A continuously runnable SCHED_FIFO task can dominate ordinary tasks on available CPUs if RT bandwidth limits do not intervene. The higher deadline class and RT throttling also affect actual execution. The RT policy isn't a "faster" button, if a program enters an infinite loop, holds a lock, or causes a page fault, the entire system might become unresponsive. Before deployment, CPU reservations, watchdogs, lock protocols, and failure recovery mechanisms are required.

Use an API to Read the Current Policy

Save this Linux program as scheduler_info.c and compile with cc -std=c17 -Wall -Wextra -Werror scheduler_info.c -o scheduler_info. It reads the calling thread’s policy, priority, and nice value:

#define _GNU_SOURCE
#include <errno.h>
#include <sched.h>
#include <stdio.h>
#include <sys/resource.h>

static const char *policy_name(int policy) {
    switch (policy) {
        case SCHED_OTHER: return "SCHED_OTHER";
        case SCHED_BATCH: return "SCHED_BATCH";
        case SCHED_IDLE: return "SCHED_IDLE";
        case SCHED_FIFO: return "SCHED_FIFO";
        case SCHED_RR: return "SCHED_RR";
#ifdef SCHED_EXT
        case SCHED_EXT: return "SCHED_EXT";
#endif
#ifdef SCHED_DEADLINE
        case SCHED_DEADLINE: return "SCHED_DEADLINE";
#endif
        default: return "unknown";
    }
}

int main(void) {
    int policy = sched_getscheduler(0);
    if (policy < 0) {
        perror("sched_getscheduler");
        return 1;
    }

    struct sched_param parameters;
    if (sched_getparam(0, &parameters) != 0) {
        perror("sched_getparam");
        return 1;
    }

    errno = 0;
    int nice_value = getpriority(PRIO_PROCESS, 0);
    if (nice_value == -1 && errno != 0) {
        perror("getpriority");
        return 1;
    }

    printf("policy=%s rt_priority=%d nice=%d\n",
           policy_name(policy), parameters.sched_priority, nice_value);
    return 0;
}

For a standard fair policy, sched_priority must be 0; nice belongs to a separate weighting interface. Do not combine these two values into a single priority number.

You can also observe these values using read-only commands:

chrt -p "$$"
ps -o pid,cls,rtprio,ni,pri,psr,stat,comm -p "$$"
sed -n '1,40p' /proc/self/sched

The final line, /proc/self, points to sed itself, not the parent shell. If you want to see the parent shell, expand $$ into /proc/$$/sched.

CFS's Historical Model: Catching Up to Ideal Fair CPU

The Completely Fair Scheduler (CFS) was integrated into Linux 2.6.23. It establishes a weighted fairness model for ordinary tasks based on the concept of an "ideal multitasking CPU": if n runnable tasks with equal priority could run simultaneously, each would receive 1/n of the CPU time.

The classic CFS maintains a virtual runtime for each scheduling entity. Actual execution time is normalized by the nice weight:

delta_vruntime ≈ delta_exec × NICE_0_LOAD / weight

Tasks with higher weights experience slower growth in their virtual runtime, resulting in a larger share of CPU time over the long term. Entities in the run queue are ordered by their virtual runtime, and the classic selection logic favors the one with the smallest virtual runtime. min_vruntime provides a baseline for newly woken or migrated entities, preventing infinite accumulation of "sleeper bonuses."

A red-black tree is a key structural component in this historical implementation. However, the practice of "selecting the entity with the smallest virtual runtime from the leftmost end" should no longer serve as the complete pick-next contract for all modern Linux systems. The official CFS documentation explicitly states that CFS is being superseded by EEVDF.

CFS is not "slice-free." The official documentation's claim that it "lacks traditional fixed timeslices" refers to its departure from the old scheduler's model of fixed quanta derived from HZ/nice. Fair classes still need to determine how long an entity runs at a time, and mechanisms like base slice or granularity are used to control preemption and cache thrashing.

Nice Controls Relative Weight

The nice value for a typical task ranges from -20 to 19, where lower numbers indicate higher weight. Adjacent nice levels follow an approximate multiplicative scaling, ensuring that the relative share of CPU time does not depend on an absolute baseline.

Two common limitations are often overlooked:

• nice determines the relative CPU share when two processes compete for the same fair scheduling hierarchy; it does not guarantee that a request will respond within a specific number of milliseconds;
• autogroup, cgroup task groups, CPU quotas, and multi-core load balancing can alter the actual share between two processes.

Regular users can typically increase their task's nice value (making it more courteous), but reducing it requires appropriate permissions or limits. The permissions and container behaviors for nice(1), renice, and setpriority should be verified in the target environment.

EEVDF: The Scheduler First Determines Eligibility, Then Compares Virtual Deadlines

EEVDF does not collapse "how much fair service is owed" and "who runs next" into one metric. It first uses lag to determine eligibility, then selects the earliest virtual deadline among eligible entities. This deadline belongs to the scheduling model, not to a business promise of completion time.

Starting with Linux 6.6, fair scheduling has gradually shifted toward Earliest Eligible Virtual Deadline First (EEVDF). EEVDF continues to use virtual time and weight to measure fair share, but it no longer simply picks the entity with the smallest vruntime.

According to the official EEVDF documentation:

1. Compute the entity's lag, indicating whether it has been under-served or over-served relative to its fair share;
2. Only entities with non-negative lag are considered eligible;
3. Among eligible entities, select the one with the earliest virtual deadline;
4. The requested slice influences the virtual deadline, enabling latency-sensitive tasks to request shorter slices and improve responsiveness.

A positive lag means the entity is owed additional CPU time; a negative lag means it has already consumed more than its fair share. Formulas and fields may evolve over time, and applications should not rely on the stable formatting of internal values in /proc.

EEVDF also addresses lag for sleeping tasks. If a task immediately clears its negative lag upon entering sleep, it could repeatedly short-sleep to gain responsiveness advantages. The current design employs mechanisms like deferred dequeue and lag decay, allowing fair debt to be processed over time via virtual time. This aspect remains an area of ongoing implementation evolution, this lesson only preserves the motivation and provides access to the official documentation.

Virtual Deadline Is Not a Business Deadline

The virtual deadline in EEVDF is used internally for fair scheduling among fair-class workloads and cannot substitute for product SLA guarantees or the reservation parameter in SCHED_DEADLINE.

An SCHED_DEADLINE task specifies runtime, deadline, and period. The kernel performs admission control and bandwidth allocation to cap total reserved resources. Even if admission succeeds, applications must still avoid uncontrolled page faults, lock dependencies, device latency, and exceeding their runtime budget.

Business-level request deadlines exist at a higher layer. A single web request may span multiple threads, network hops, and databases. Simply adjusting the priority (nice value) of a worker thread does not automatically propagate the end-to-end deadline across the entire request flow.

Real-Time Scheduling and Priority Inversion

SCHED_FIFO tasks of the same priority typically run until they block, yield, change priority, or are preempted by a higher real-time priority task. SCHED_RR adds a round-robin quantum among tasks at the same priority. Both approaches take precedence over standard fair scheduling.

If a low-priority thread holds a mutex required by a high-priority thread, a medium-priority runnable thread can continuously preempt the low-priority thread, leading to unbounded priority inversion. The POSIX mutex attribute PTHREAD_PRIO_INHERIT can request priority inheritance, but support for this feature, interaction with scheduling policies, and behavior under nested locking must be carefully verified.

Priority inheritance only helps in cases where the mutex dependency has a known owner and does not resolve issues such as semaphore misuse, I/O server priority, page faults, or any lock-free dependency. Real-time analysis must compute blocking bounds, rather than enable the attribute alone.

Cgroups and Quotas Change the Fairness Hierarchy

Container or service workloads typically first allocate CPU across groups, then schedule tasks within those groups. The CPU weight determines relative shares, while CPU quota and period set an upper bandwidth limit for each group. Once a group's quota is exhausted, even if free CPU remains elsewhere on the machine, the group may still be throttled until the next period.

This can result in apparent "scheduler unfairness" in tail latency. When troubleshooting, simultaneously inspect:

cat /proc/self/cgroup
cat /sys/fs/cgroup/cpu.stat
cat /sys/fs/cgroup/cpu.weight
cat /sys/fs/cgroup/cpu.max

These absolute paths inspect the visible mount root, which need not be the current task’s cgroup. Use /proc/self/cgroup and mount information to locate the actual subgroup, and check ancestor limits too. Root groups or groups without the controller enabled may lack cpu.weight/cpu.max. cpu.max limits fair-class bandwidth; it is not a universal quota for RT and deadline tasks. Change only an explicitly authorized test subgroup.

SMP Balances Fairness with CPU Placement

Each CPU's run queue reduces global lock contention while preserving cache locality. The scheduler domain periodically or on idle/wakeup events balances the load. Task migration can improve utilization but at the cost of warm cache, TLB locality, and NUMA placement.

In heterogeneous systems, CPU capacity and energy-aware scheduling must also be considered. Utilization clamping (uclamp) provides hints for frequency and placement, but it does not guarantee hard deadlines.

Therefore, the vruntime of a single task cannot independently predict where it will run in the next nanosecond. CPU affinity, cpuset, IRQs, SMT siblings, and thermal throttling all influence the observed behavior.

Scheduling Debugging Starts with Delay Decomposition

A slow request might spend its time on:

• Being runnable but not getting CPU access: run-queue delay;
• Blocked on a mutex or futex;
• Sleeping for I/O or timer events;
• cgroup throttling;
• Page faults or memory reclamation;
• CPU migration resulting in cache or NUMA penalties;
• Spending too long actually executing on CPU.

Looking only at the process %CPU is insufficient to distinguish between these causes. Instead, combine scheduler tracepoints, perf sched, PSI, cgroup cpu.stat, off-CPU profilers, and application spans. These observability tools introduce overhead, and their fields vary by kernel version, first calibrate them in staging.

yield() is rarely a solution. It merely returns the current execution slot to the scheduler and does not express conditions like "waiting for the queue to become non-empty" or "waiting for a lock to be released"; to convey such waiting reasons, use condition variables, eventfd, or futex-backed primitives so the kernel can understand the actual wait condition.

Inspect the Running Kernel

1. Run the query program and compare results from a regular shell, nice -n 10, and chrt without privilege escalation.
2. Adjust the nice value between two CPU-bound processes and measure long-term CPU share, rather than a single response time alone.
3. Use an authorized, delegated test cgroup to apply a quota to one process and observe changes in nr_throttled and tail latency.
4. Write out separately the pick-next conditions for classic CFS and EEVDF from the official documentation, do not combine them into a single sentence.
5. Design a priority-inversion trace that illustrates how inheritance can reduce the duration of a specific blocking period.
6. Distinguish between EEVDF’s virtual deadline, SCHED_DEADLINE parameter, and HTTP request deadline.

Next Step: How the Scheduler Makes a Mutex Waiter Sleep

The scheduling algorithm determines the order in which runnable tasks are executed, while the mutex implementation decides whether competing threads should continue spinning or enter the kernel wait queue. The next chapter covers lock implementation, then dynamic allocation. Both manage shared state, but their protocols serve different purposes.

Check the Resource-Control Interfaces

• Linux cgroup v2 CPU controller