10.2 Linux Scheduling Classes, CFS, and EEVDF

The paper-based scheduling diagram on the central control desk shows only one ready queue. In reality, the control console handles ordinary services, batch jobs, and deadline-constrained control threads simultaneously. The system also features multiple cores, tasks may belong to different cgroups, and thermal and power management policies dynamically alter available compute capacity. Simply stuffing all tasks into a single "universal red-black tree" no longer suffices.

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. Here, only cross-version-stable concepts are retained; source code fields and selection rules are governed by the running kernel.

First confirm which scheduling category the task belongs to

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-based task	nice/weight, fair scheduling state
SCHED_BATCH	CPU-heavy batch	Reduced tendency to interrupt interactive processes
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

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

A runnable SCHED_FIFO task can indefinitely block ordinary tasks. 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

The following Linux/POSIX program reads only its own policy, priority, and nice values, without modifying any system state:

#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_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;
}

sched_priority For a standard fair policy, this is typically 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 is relative weight, not a deadline

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

The control plane must not blend the concept of "how much fair service is owed" with "who gets selected next" into a single metric. EEVDF first evaluates whether an entity is eligible using lag, then among eligible entities, selects the one with the earliest virtual deadline. This deadline belongs to the scheduling model, not to any business-level 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 class 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 Increasing the quantum for time-slicing among tasks of the same priority also helps. 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.

cgroup and quota alter 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 paths and files apply to common mount points for cgroup v2. Container-level permissions and namespaces may only expose subtrees. Avoid directly modifying host cgroup configurations in tutorial experiments.

SMP Load Balance Makes Fairness No Longer a Tree

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.

Hands-on Verify Runtime 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. Place one process into a cgroup with quota limits 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, Lock Implementation and Dynamic Storage, will separate the originally combined lock and allocator components into two distinct sections.