← Previous Lecture
|
Next Lecture →

What You Will Learn

• The exact call chain from schedule() to a scheduler class picking a task
• How modern kernels iterate scheduler classes without a linked list
• How the Linux scheduler runqueue is really structured: one struct rq per CPU with per-class sub-runqueues
• Which data structure each class uses internally (rb-trees, priority arrays)
• A worked example showing which thread wins the CPU when multiple classes have runnable work

Prerequisites

• Part 2A of this series – Linux scheduler classes and the priority ladder
• Comfort reading C structures and macros
• Optional: kernel source of any 6.12+ release to follow along in kernel/sched/

The Scheduling Call Chain

Whenever the kernel decides the current thread should stop running – it blocked, its time allocation expired, or a higher-priority thread woke up – the core entry point is schedule(). The essential path looks like this:

The core walk is beautifully small. Here is a simplified version of what modern kernels do inside the picker when the fast path does not apply:

/* kernel/sched/core.c (simplified for teaching) */
static struct task_struct *pick_task(struct rq *rq)
{
        const struct sched_class *class;
        struct task_struct *p;

        for_each_class(class) {
                p = class->pick_task(rq);
                if (p)
                        return p;
        }

        BUG(); /* impossible: the idle class always has a task */
}

Each class is asked, in priority order, “do you have a runnable task?”. The first class that answers wins – a deadline task beats an RT task, which beats a fair task, and so on. If literally nothing is runnable, the idle class returns the per-CPU idle thread, which is why the final BUG() can never fire on a healthy kernel.

There is also a valuable fast-path optimization: since the overwhelming majority of tasks on a normal system live in the fair class, the picker first checks whether every runnable task on this CPU belongs to the fair (or idle) class. If so, it skips the walk entirely and calls the fair picker directly.

How for_each_class() Works in Modern Kernels

Older kernels chained the classes on a singly linked list using a next pointer inside struct sched_class. That pointer is gone. Modern kernels place each class object into its own named section, and the linker script lays those sections out contiguously in memory, highest priority first. Iteration then becomes plain pointer arithmetic between two boundary symbols:

/* kernel/sched/sched.h (simplified, modern kernels) */
extern struct sched_class __sched_class_highest[];
extern struct sched_class __sched_class_lowest[];

#define for_class_range(class, _from, _to) \
        for (class = (_from); class < (_to); class++)

#define for_each_class(class) \
        for_class_range(class, __sched_class_highest, __sched_class_lowest)

Why did the kernel developers bother? Two reasons: walking a small contiguous array is faster and friendlier to CPU caches than chasing pointers, and a link-time-fixed order allows the compiler and the fast path to make safe assumptions about class positions.

The Linux Scheduler Runqueue: One Per CPU, Sub-Runqueues Per Class

Here is the misconception worth correcting: older explanations often make it sound like the kernel keeps a completely separate runqueue object for every (CPU × class) combination. The real structure is cleaner. The kernel maintains exactly one main runqueue – struct rq – per CPU core, implemented as a per-CPU variable so each core mostly touches only its own data (a powerful, largely lock-contention-free technique). Inside that per-CPU runqueue, each scheduler class embeds its own class-specific sub-runqueue:

The choice of internal data structure belongs entirely to each class – the core never peeks inside:

Worked Example: Who Wins the CPU?

Imagine a multicore system with 100 threads alive, of which five are runnable on CPU 0 at the moment __schedule() runs:

The class walk asks the deadline class first, and D1 is returned immediately – the RT and fair classes are never even consulted on this pass. When D1 later exhausts its runtime budget or completes its period’s work, the next __schedule() pass will find the deadline sub-runqueue empty and fall through to the real-time class, where R1 beats R2 on static priority. Only when both the deadline and RT sub-runqueues are empty does F1’s EEVDF tree get a chance, and swapper/0 runs only when everyone else sleeps.

Observing Runqueues on Your Machine

You can watch runqueue lengths and per-class state live – a great exercise in this free Linux device drivers course companion track:

# Runnable-thread counts and load per CPU
cat /proc/loadavg

# Rich per-CPU runqueue detail (requires debugfs)
sudo cat /sys/kernel/debug/sched/debug | less

# Per-task scheduling statistics
cat /proc/self/sched | head -15

# Watch context switches per second, system wide
vmstat 1 5

Inside /sys/kernel/debug/sched/debug you will literally see each CPU’s runqueue, the EEVDF fields for fair tasks, and per-class counters – the exact structures we discussed above, live on your hardware.

Common Mistakes and Troubleshooting

• Believing there is one global runqueue. There has not been a single global runqueue for two decades; each CPU owns its runqueue, and load balancers move tasks between them.
• Multiplying CPUs by classes to count runqueue objects. The accurate mental model is one struct rq per CPU with per-class sub-structures inside it.
• Quoting the old linked-list iteration in interviews. The next pointer in struct sched_class is gone; classes now sit in a linker-ordered array walked by pointer arithmetic.
• Expecting O(1) picks from the fair class. The EEVDF pick is O(log n) via the rb-tree; only the RT class offers a true O(1) pick through its priority bitmap.
• Ignoring the idle class in reasoning. Because it always has a task, code after the class walk can safely assume a task was found – that invariant simplifies the entire core scheduler.

Best Practices

• When debugging latency, first identify which class your thread is in – the diagnosis path differs completely between fair, RT, and deadline tasks.
• Use /sys/kernel/debug/sched/debug before reaching for heavier tracing; it often answers “why isn’t my thread running?” instantly.
• On multicore embedded targets, remember per-CPU runqueues mean per-CPU decisions – pin latency-critical threads with CPU affinity so balancing does not surprise you.
• Prefer reading the current kernel source in kernel/sched/core.c over old blog posts – the scheduler evolves quickly, as this lecture shows.

Key Takeaways

• The call chain is schedule() → __schedule() → pick_next_task(), with a fast path for the common all-fair case.
• Classes are consulted highest-priority-first via for_each_class(), now an array walk fixed at link time.
• Each CPU has exactly one runqueue (struct rq), a per-CPU variable that minimizes lock contention; each class embeds its own sub-runqueue in it.
• Fair uses an EEVDF rb-tree, RT uses O(1) priority arrays, deadline uses an EDF rb-tree, and sched_ext uses BPF-managed dispatch queues.
• The idle class guarantees the picker always succeeds – every CPU always has something to run.

Frequently Asked Questions (FAQ)

Conclusion

You now know exactly how a modern Linux kernel turns “something changed, reschedule!” into a concrete thread on a concrete CPU: a locked per-CPU runqueue, a fixed-order walk across six scheduler classes, and class-owned data structures tuned for their job – from O(1) RT bitmaps to EEVDF rb-trees. This mental model will serve you constantly, whether you are chasing latency in an embedded product, writing drivers that wake threads, or answering kernel-internals interview questions. Continue this free Linux kernel development course with the next lecture, where we look at the fair class and EEVDF in depth.