The Scheduler

In the previous article we looked at how the kernel gives every process its own private view of memory. But memory is only half of what a process needs to actually run. The other half is the CPU itself — and there are only so many CPUs in a machine, while there are usually hundreds or thousands of things that want to run on them.So somebody has to decide, constantly, who gets a CPU and for how long. That somebody is the scheduler. Every few milliseconds, on every core, the kernel asks itself the same question — of everything that wants to run right now, who runs next? — and the answer has to be fast, fair, and good enough that your text editor stays responsive even while a compile is pegging every core.Let’s take it step by step, because the scheduler has a lot of moving parts. We’ll start with what the scheduler is even scheduling — what a process and a thread really are under the hood. Then we’ll see that Linux doesn’t have just one scheduler but several, stacked as scheduling classes. From there we’ll look at when a running task stops running (it’s more interesting than it sounds), and look at what it costs to switch from one task to another. And finally we’ll get to the heart of it: how the kernel actually decides who’s next, using an algorithm called EEVDF.📌 A note on scopeEverything here is against Linux 7.1 (the scheduler core lives in kernel/sched/, mostly in fair.c and core.c). And it’s a deliberate simplification: the real implementation has far more going on — load balancing across CPUs, group scheduling through cgroups, CPU bandwidth control, NUMA awareness, and countless edge cases — that I’m skipping over to keep the core ideas clear.So let’s begin where the scheduler itself begins: with the thing it’s actually shuffling on and off the CPU.What the Scheduler Actually SchedulesHere’s the first surprise, and it clears up a lot of confusion: the kernel doesn’t schedule “processes” or “threads.” Those are words we use up in user space. Down in the kernel there’s just one kind of schedulable thing — a task_struct (include/linux/sched.h:820), the kernel’s record of one flow of execution, one thing that can sit on a CPU and run instructions.

What you call a process and what you call a thread are both, underneath, the exact same kind of object. The only difference is what they share. When you fork() a new process, you get a fresh task_struct that shares nothing with its parent — its own memory, its own file descriptors, its own everything. When you create a thread (with clone() and the right flags) you also get a fresh task_struct, except this one shares the address space, the open files, the signal handlers, and so on with the task that spawned it. So a “multi-threaded process” is really just a bunch of task_structs that happen to point at the same memory.From the scheduler’s chair none of that matters anyway — it doesn’t know or care who shares what. It just sees a pile of task_structs, some runnable and some not, and picks among the runnable ones. Everything runnable on a CPU is a task_struct, full stop.Now, a task_struct is huge — it holds basically everything the kernel knows about a task — but the scheduler only cares about a sliver of it. Tucked inside every task is a small embedded bundle of scheduling state (called the sched_entity, include/linux/sched.h:575), and that little bundle — not the giant struct around it — is what the scheduler actually reasons about.It’s where the interesting numbers live, things with names like vruntime, vlag, deadline, and slice. Don’t worry about what any of those mean yet — unpacking them is basically the rest of this article. For now just hold onto the shape of it: each runnable task carries a small wad of accounting state, and that’s the part the scheduler reads when it decides who runs next.But “the scheduler” is a bit of a white lie, because there isn’t just one — so before we go further, let’s see who actually gets handed the decision.Scheduling Classes: Who Even Gets Asked FirstBefore we get to the algorithm, there’s a twist: Linux doesn’t actually have one scheduler. It has several, and they’re stacked in a strict pecking order. These stacked schedulers are called scheduling classes, and each one is a self-contained policy for a different kind of workload.

The way they cooperate is dead simple. When a CPU needs something to run, the kernel goes down the stack from the top and asks each class in turn, “got anything runnable?” The first one to say yes wins, and everything below it doesn’t even get a vote. So a class only ever runs a task when every class above it had nothing to offer.So what’s in those boxes? The three at the top all exist to give some task the right to butt ahead of ordinary work. At the very top sits stop, which isn’t really a scheduling policy so much as a “drop everything” lever the kernel pulls when it needs a CPU to do one urgent thing this instant — like migrating tasks off a core that’s being shut down. Below it, deadline handles tasks with hard timing needs (think audio or robotics), where you don’t ask for a priority but for a guarantee: “this task needs so many milliseconds of CPU every so often.” And then rt is classic real-time priorities — a real-time task runs for as long as it likes and only steps aside for something even higher, which is wonderful for latency-critical code and a great way to freeze your machine if such a task never sleeps.Here’s the thing, though: on a normal desktop or server, those top three boxes are almost always empty. Which brings us to the one that matters for the rest of this article: fair. This is where essentially everything you run actually lives — your shell, your browser, your database, that compile job. None of those tasks has any special timing demand; they just want a reasonable slice of the CPU, and the fair class’s whole job is to hand those slices out fairly. Because the classes above it are usually idle, the fair class is the one running the show nearly all the time — so when people say “the Linux scheduler,” this is the one they almost always mean.Rounding out the bottom, just so the picture’s complete: ext is a newer addition that lets you load a whole scheduling policy as a BPF program, handy for experimenting without recompiling the kernel; and idle is the floor, the do-nothing task that runs only when nothing else wants the CPU and quietly puts the core to sleep to save power. We won’t dwell on either — from here on, it’s all about fair.

The fair class is built on an algorithm with an intimidating name: EEVDF, Earliest Eligible Virtual Deadline First. Don’t let the name scare you — we’ll take it apart piece by piece later, and it turns out to be a fairly intuitive idea.Before we get to how EEVDF chooses, though, it helps to know when it even gets the chance to — the moments a running task lets go of the CPU.When Does a Running Task Stop Running?Say a task is happily running on a CPU. What makes it stop so something else can run? This is the part people usually hand-wave past, but it’s where the whole system actually lives. There are really only two ways a task gives up the CPU, and understanding both is most of understanding the scheduler. Let’s take the gentler one first.Way One: It Voluntarily BlocksThe most common reason a task stops running is that it asks for something it can’t have yet. It calls read() on a socket with no data, takes a mutex someone else holds, calls sleep(), waits on a condition variable — anything that can’t complete immediately.When that happens, deep inside the blocking primitive, the kernel sets the task’s state to “not runnable” and calls schedule() (kernel/sched/core.c:7273). This is the task voluntarily saying “I have nothing to do right now, give the CPU to someone else.” The scheduler takes the task off the run queue entirely (it’s not runnable, so there’s no point considering it), picks somebody else, and switches to them. The blocked task will get put back on a run queue later, when whatever it was waiting for happens — that’s a wakeup, and we’ll get to it.This is the clean, cooperative case. The task itself initiated the handoff. But not every task is so courteous.Way Two: It Gets PreemptedBut what about a task that never blocks? A tight loop crunching numbers, a while(1), a video encoder pegging the core. If blocking were the only way to give up the CPU, that task would run forever and starve everyone else. So the kernel has to be able to take the CPU away — that’s preemption.Here’s the clever part: preemption is almost never immediate. The kernel doesn’t violently yank a task off the CPU mid-instruction.

Instead, when it decides a task should be preempted, it just sets a flag on it — TIF_NEED_RESCHED, literally “this task needs to reschedule” (resched_curr(), kernel/sched/core.c:1212) — and lets it keep running for now. Setting a flag is cheap and safe to do from awkward spots like inside a timer interrupt, where actually switching tasks would be dangerous. The flag is just a sticky note: “switch this one out at the next safe opportunity.”Those safe opportunities are well-defined points where the kernel checks the flag and, if it’s set, calls schedule() to do the real switch. By far the most common one is returning to user space — every time a task pops back out of the kernel into your code (after a syscall or an interrupt), the kernel peeks at the flag first.So the rhythm is always decide → set flag → run a little longer → hit a safe point → switch. This deferred, flag-driven design is the spine of the whole thing — even a wakeup never switches tasks directly. It just makes a task runnable and, if that task deserves the CPU, sets the flag on whoever’s currently running; the actual switch happens later, at a safe point.For our purposes a task moves between three main states. Running drops to blocked when it voluntarily waits on something, and a wakeup later moves it from blocked to runnable (waiting its turn). From runnable the scheduler promotes it back to running by picking it; and a running task is pushed back down to runnable when it’s preempted. Notice there’s no arrow straight from blocked to running — a woken task always rejoins the queue and waits to be picked.So who decides to set that preemption flag, and based on what? Two main triggers: the periodic tick, and wakeups. Take the tick first.The periodic tick — the heartbeatEach CPU has a timer that fires at a steady, regular beat — this is called the tick. Every time it fires, the kernel runs a small routine, sched_tick() (kernel/sched/core.c:5636), which does two things: it adds up how much CPU time the current task has used so far, and then checks whether that adds up to more than the time slice the task was given.