The Linux scheduler

The kernel scheduler answers a single, relentless question: which task should this CPU run, right now? Every few hundred microseconds, on every core, that question is asked again.

This page walks through how that decision is made today — the data structures, the policy classes, and the way schedule() actually picks the next task.

Scheduling classes, in priority order

Linux organizes runnable tasks into scheduling classes, each with its own policy. They are queried in a fixed order:

1. stop_sched_class — CPU stoppers (highest priority, used for things like CPU hotplug)
2. dl_sched_class — SCHED_DEADLINE (EDF for real-time deadlines)
3. rt_sched_class — SCHED_FIFO / SCHED_RR
4. fair_sched_class — the default: CFS, now EEVDF since 6.6
5. idle_sched_class — the idle task

The first class that has a runnable task wins. The vast majority of tasks live in fair_sched_class.

CFS → EEVDF

For more than a decade, fair_sched_class was the Completely Fair Scheduler: each task accumulated virtual runtime, and the scheduler picked the task with the lowest vruntime. The leftmost node of a per-CPU red-black tree was, by definition, "next."

In 6.6, that was replaced with EEVDF (Earliest Eligible Virtual Deadline First). Each task still has a vruntime, but EEVDF also tracks a virtual deadline based on the task's allocated slice. The runqueue is still a red-black tree, but now keyed on the earliest eligible deadline, which gives much better latency for short, interactive tasks without sacrificing fairness for long-running ones.

The runqueue, per CPU

Each CPU owns a struct rq. The two pieces of state that matter most:

struct rq {
    struct cfs_rq cfs;     /* fair class runqueue */
    struct rt_rq  rt;      /* RT class runqueue  */
    struct dl_rq  dl;      /* deadline runqueue   */
    struct task_struct *curr;
    /* ... lots more ... */
};

cfs_rq.tasks_timeline is the red-black tree EEVDF picks from. curr is what the CPU is running this instant.

When does schedule() run?

schedule() is called whenever the kernel needs to reconsider who runs:

• a task blocks (waits on I/O, on a lock, on a futex)
• a timer interrupt fires and TIF_NEED_RESCHED is set
• a task voluntarily yields
• a higher-priority task becomes runnable
• on return from an interrupt or syscall, if TIF_NEED_RESCHED is set

The flow looks roughly like:

void __sched schedule(void) {
    /* pick next task across all scheduling classes */
    next = pick_next_task(rq, prev, &rf);
    if (next != prev) {
        rq->curr = next;
        context_switch(rq, prev, next, &rf);
    }
}

pick_next_task walks the classes in priority order. context_switch swaps stack, page tables (for cross-mm switches), and CPU registers.

Wake-up and load balancing

When try_to_wake_up() runs (because a futex was released, a timer fired, an I/O completed…), the scheduler must place the waking task on some CPU's runqueue. The wake-up balancing logic picks an idle or lightly-loaded sibling, ideally one that shares cache with the waker.

Periodically, the load balancer pulls work from busy CPUs to idle ones. This is bounded by scheduler domains — hierarchical groupings (SMT siblings → core → cluster → NUMA node) so balancing prefers locality.

Where to look in the source

Next up: a step-by-step animated flow of a wake-up across two CPUs — coming soon.