Linux replaced its CPU scheduler and nobody noticed

In October 2023 the code that decides which process runs on your CPU was taken out and replaced. Not tuned — replaced. The Completely Fair Scheduler had run essentially every Linux machine on earth for sixteen years, almost exactly to the month, and in version 6.6 it was deleted and something called EEVDF was put in its place.

Almost nobody noticed. For a scheduler change that is the correct outcome and also a shame, because the reason behind it is one of those ideas that quietly rearranges how you think about sharing anything.

Here it is, up front:

How much CPU a task gets and how soon it gets it are different questions. CFS gave you a knob for the first and none at all for the second. That was the bug.

Everything below is an argument for why that sentence is worth caring about — and, along the way, two attempts at making it that turned out to be wrong.

Act 1 — Virtual time is a clock that runs at different speeds

Start with the problem any scheduler has to solve. Several tasks want one CPU. You can only run one at a time. You want to be fair. What does fair even mean?

The obvious answer — give everyone equal time — is wrong as soon as you admit that some tasks matter more than others. So the real target is proportional fairness: each task gets a share of the CPU in proportion to its weight.

CFS found a beautiful way to track this. Instead of accounting for real time, give every task a virtual clock, and make that clock run at a speed inversely proportional to the task’s weight:

vruntime += real_time_used × 1024 / weight

A task with a heavy weight accumulates virtual time slowly. A light task races ahead. Then CFS’s rule is simply: at each scheduling decision, run whoever has the lowest virtual time.

That one line does all the work. You never compute a share, never track a budget, never divide anything by anything — proportional fairness falls out of a comparison. And the weighting is what makes it proportional: a heavy task’s clock runs slow, so it can do several times as much real work before its virtual time catches up with everyone else’s.

Both halves of the rule earn their keep, though. At each decision, because a task that wins the CPU keeps it for a whole timeslice, and partway through that slice it is very often no longer the lowest — you will see that happen below. And CFS’s rule, because Act 4 replaces it with something subtly different.

Act 2 — nice is exponential, and only differences matter

The weight in that formula comes from the task’s nice value, through a table the kernel has carried, byte for byte identical, for well over a decade:

/* -20 */  88761  71755  56483  46273  36291
...
/*   0 */   1024    820    655    526    423
...
/*  15 */     36     29     23     18     15

Two things about this table surprise people.

The first is that it is exponential, not linear. Each step is roughly a factor of 1.25, which is chosen so the effect is relative: from wherever you are, one step up costs you about 10% of your CPU and one step down gains you about 10%. Going from nice 0 to nice 5 does not cost you five units of something. It costs you a factor of three.

The second is that only the ratio matters. A nice 0 task competing against a nice 5 task gets 75.35% of the CPU. A nice 10 task competing against a nice 15 task gets 75.34%. Nice values have no absolute meaning whatsoever — they exist only relative to whatever else happens to be runnable, and shifting both by the same amount changes nothing you could measure.

Not quite nothing, if you push on it. The table is rounded integers, not a real geometric sequence, so equal gaps are equal only to about a percentage point. The widest disagreement anywhere is 1.55 points, between nice 17-vs-18 and nice 18-vs-19, where the ratios are 1.28 and 1.20 rather than 1.25. It is a rounding artefact rather than a design, and no workload will ever notice — but the figure below prints enough digits to show it, so it is better said than discovered.

Act 3 — What CFS would not let you ask for

Now the trap, which is not the trap most people expect.

You have a machine doing something heavy — a compile, a video encode, a batch job. It wants every cycle it can get. Alongside it you have something small and interactive: an audio thread, an input handler, a UI event loop. It barely wants any CPU at all. It wants a fraction of a millisecond. But it wants it now, and it wants it every few milliseconds, and if it is late the user hears a click or sees a dropped frame.

Here is where the story usually goes wrong, including in the first draft of this page. The tempting claim is that CFS handles this badly. It does not. CFS is excellent at it.

When a task wakes up, CFS places it half a latency period behind the runqueue’s floor — place_entity(), in full:

vruntime = cfs_rq->min_vruntime;
if (!initial) {
        thresh = sysctl_sched_latency;
        if (sched_feat(GENTLE_FAIR_SLEEPERS))
                thresh >>= 1;
        vruntime -= thresh;
}
/* ensure we never gain time by being placed backwards. */
se->vruntime = max_vruntime(se->vruntime, vruntime);

Three milliseconds of virtual time behind a hog that is sitting exactly at the floor is an enormous head start. Wakeup preemption sees it and kicks the hog off the CPU on the spot. Our interactive task is served practically the instant it asks — model it faithfully and CFS’s p95 wake-to-run latency on this workload comes out better than stock EEVDF’s. That is not an accident. It is why Linux desktops felt responsive for sixteen years.

So if CFS is so good at this, what is the problem?

The problem is not what the credit costs. It is that you cannot control it.

It is a heuristic, not a contract. Half the latency target is a number someone chose. It is not connected to what your task actually needs. You cannot ask for less, and you cannot ask for more.

And it is the only knob you have. If the credit is not right for your workload, your sole remaining lever is nice — which buys latency with throughput, for a task that never wanted more CPU in the first place.

So the indictment of CFS is not that it is slow, and not that it is unfair. It is that its responsiveness is a fixed side effect you cannot ask for, cannot tune, and cannot decline.

Act 4 — Fairness as a debt

EEVDF starts from a different question. Not “who is furthest behind?” but “who are we in debt to?”

Take all the runnable tasks and compute the weighted average of their virtual times. Call it V:

V = (Σ wⱼ·vⱼ) / Σ wⱼ

V is the point where nobody is owed anything. The kernel calls it the zero-lag point, and as of 7.0 the variable is named zero_vruntime, which is about as clear as kernel naming gets. Every task’s lag is measured against it:

lag_i = w_i · (V - v_i)      real CPU owed
 vl_i =       V - v_i        virtual lag — what the kernel actually tracks

Positive lag means the scheduler owes you time. Negative lag means you have had more than your share — you are overdrawn.

Keep the two apart. The kernel stores vl_i, the virtual lag, because dropping the w_i saves it a multiply everywhere. But the two order tasks differently whenever weights differ — on the workload below they disagree about who is owed most in about a third of frames — so the figures below say vl, and mean it.

And now the rule that makes EEVDF different. A task is eligible to run only if its lag is not negative:

eligible  ⟺  v_i ≤ V

If you are ahead of the zero-lag point, you sit out. Not forever — V keeps moving forward as other tasks run, and it will catch up to you. But you do not get to run again until it does.

This is the part worth pausing on. Selection is no longer “pick the minimum”. It is filter, then choose. First discard everyone who has already had more than their share, then choose among the rest. Those are two different operations, and separating them is what creates room for a second knob.

So: filter to the eligible. Then what? Then EEVDF asks each eligible task when it would like to be finished by. Every task has a request — a slice of CPU it wants in one go — and from that comes a virtual deadline:

vd_i = ve_i + r_i / w_i

The eligible task with the earliest virtual deadline wins the pick. A smaller request puts your deadline nearer, which gets you picked sooner.

Winning the pick is not the same as being on the CPU. Once a task is chosen, EEVDF lets it finish the request it asked for — RUN_TO_PARITY — rather than re-deciding every tick. So at any given instant the task holding the CPU is often not the one with the nearest deadline, and the figure below will say so when that happens. This matters more than it sounds: it is why shrinking a slice costs context switches, which is the bill Act 5 asks you to pay.

Act 5 — Two knobs

Read that deadline formula again, and notice what is not in it.

The request r_i is a separate input from the weight w_i. They both affect the deadline, but they are independently settable. So a task can ask for a small slice without asking for a large share.

That is the whole thing. That is what CFS had no way to express.

Go back to the compile and the audio thread. The audio thread keeps nice 0 — it takes no throughput away from anything. Instead it asks for a slice of, say, 100 microseconds instead of the default 700. Its deadline now lands much sooner after every wake, so it gets picked sooner. It does not receive any more CPU than before — it barely wanted any — it just receives what it did want in smaller, earlier pieces.

Notice what actually changed. Not the latency — CFS could already deliver that. What changed is that the latency is now something the task asked for: a number it chose, bounded, and visible to anyone reading the code. A heuristic became a parameter.

That is a smaller-sounding claim than “EEVDF is faster”, and it is the one that survives contact with a measurement. It is also the one that matters if you are the person who has to make an audio thread hit a deadline on a machine you do not control.

The cost is real and worth naming: more context switches. Shrinking a slice buys latency with switch overhead, and that is a genuine trade. But it is a trade you opted into, with a knob, at a price you can see — which is a different kind of thing from a number in the scheduler deciding on your behalf.

On Linux 7.0 you reach this through sched_attr:

struct sched_attr attr = {
    .size          = sizeof(attr),
    .sched_policy  = SCHED_NORMAL,
    .sched_runtime = 100000,   /* 100 us request */
};
sched_setattr(0, &attr, 0);

It is backed by se->custom_slice in the kernel, which is worth knowing about because it dates the feature precisely. Search for it in 6.8 and you will find nothing at all — the field does not exist. It arrives in 6.12. So “EEVDF landed in 6.6” is true and also misleading: the scheduler arrived two years before the knob that justifies it.

How much of this should you believe?

Every figure above is driven by a simulation, and simulations are very easy to get quietly wrong — this page has the scars to prove it. So here it is checked against the real thing: the same workload run on an actual Linux 7.0 kernel, traced with bpftrace, and put next to the model.

The claim is cumulative CPU share within a stated tolerance, not that the two timelines are identical — they cannot be, and anyone telling you otherwise is selling something.

What to take away

If you keep one thing from this, make it the shape of the problem rather than the name of the algorithm.

Any time a resource is shared — a CPU, a disk, a network link, a queue of support tickets — there are two questions hiding inside the word fairness. How much of it do you get. And how soon. They feel like one question, and almost every system built to answer the first ends up answering the second silently, on your behalf, with a number somebody picked once and nobody has revisited.

CFS answered it well for sixteen years. Well enough that essentially nobody discovered they had no say in it, which is the highest praise a default can earn. The change in 6.6 is not that the answer got better. It is that it became a question you are allowed to ask.

And that is why it took a replacement rather than a patch. You cannot bolt a second knob onto a rule that reads run whoever has the lowest number, because there is nowhere in that sentence to put a request. vd_i = ve_i + r_i / w_i has somewhere to put it. That is the entire difference, and it is the reason sixteen years of excellent heuristics had to be thrown away to get it.