A short slice helps when the CPU is crowded

Linux's EEVDF scheduler lets an ordinary, unprivileged task ask for a shorter time slice. The idea is that a task that asks for less time per turn gets an earlier deadline, so it can cut in sooner when it wakes up. I tested that on Linux 6.18 with a light task that wakes every millisecond and shares one CPU with busy loops. With eight busy loops, the light task was more than 1 ms late on 81–93% of its wake-ups (median 3.4 ms late) and got less than a third of the CPU time it asked for. Asking for a 100 µs slice cut the share of delayed wake-ups from 81–93% to 3%. With only two busy loops the same request barely did anything. In my first runs it looked like it did, but that turned out to be a timing coincidence.

The setup

Everything runs on one CPU of a Linux 6.18 arm64 VM, with all tasks pinned to it. The probe sleeps until a target time about 1 ms out, records how late it woke, does 50 µs of work and goes back to sleep. That's about 5% of a CPU. The hogs are busy loops that never sleep. Each setting runs for 8–10 seconds. The number I report is the share of wake-ups that were more than 1 ms late, which I'll call stalls.

The slice request is the sched_runtime field of sched_setattr() on a normal SCHED_OTHER task. The kernel clamps it to 0.1–100 ms, and it worked without root. The default slice is 0.7 ms scaled by the CPU count. That's 2.1 ms on a 4-CPU VM and 2.8 ms on 8 or more. The kernel was built with a 250 Hz tick and no high-resolution scheduler tick. That matters below.

Two things I learned about measuring this before getting any usable numbers. First, the 99th percentile was useless: each 10-second run landed either near 15 µs or near 5 ms, depending on luck. The stall share was stable run to run (spread about 0.05 percentage points), so that's the number I use. Second, running nine of these tests at once on the VM's 10 CPUs ruined the results, because the host ran out of real cores. The spread between repeat runs grew about 30-fold and hid the effect. All the numbers here come from at most three tests running at once.

More hogs, longer waits, and what the slice buys

Here the wake period has ±30% random jitter (more on why below), the hogs use the default 2.1 ms slice, and there are two runs per cell:

With eight hogs, the probe's fair share would be one ninth of the CPU. It asks for 5% and, at the default slice, gets 1.5%, and its median wake-up is 3.4 ms late. With a 100 µs slice the median wake-up is 1.4 µs late. The short slice didn't cost the hogs anything I could measure: with two hogs they did 76.4 versus 76.3 million loop iterations a second.

Why the default probe waits

In kernel/sched/fair.c, when a task is chosen to run it gets a protected stretch: by default it keeps the CPU for its own slice or the shortest slice among the tasks queued with it, whichever is less, even if another task with an earlier deadline becomes runnable. When the probe is asleep, the queued tasks are just hogs, so that's a full hog slice. A task that wakes up during that stretch can only preempt if the current task has already had more than its fair share of the CPU (the kernel calls that no longer "eligible"). The other way in is a feature called PREEMPT_SHORT: if the waking task's slice is shorter than the current task's, protection is ignored and the waking task can preempt as long as it's eligible and has the earliest deadline.

The catch is how the kernel notices that the protected stretch is over. On this kernel, without the high-resolution tick, that check happens on the timer tick, every 4 ms. So when the probe wakes during a hog's protected stretch, it waits until the next tick and sometimes longer. That's why the stall sizes cluster at a few milliseconds.

To check that this is the mechanism and not just a plausible story, I ran a throwaway VM with root, where the scheduler's feature switches can be flipped one at a time, and repeated the eight-hog test:

With PREEMPT_SHORT off, the short slice stops working, so that's the path it takes. Turning on the high-resolution tick, which ends the protected stretch on time instead of at the next 4 ms tick, cuts the default probe's stalls from about 100% to 22%. That supports the tick explanation. Turning off lag-based placement or delayed dequeue made the short-slice probe worse (8.5% and 13%), so the way the kernel carries a sleeping task's fair-share balance across its sleep also helps the short slice work. Of the five other switches I tried, only run-to-parity moved anything, and only in one of its two runs (64%). One more thing: these runs stall more often than the same test in the first table. The root VM and the earlier runs differ in small ways, so compare rows within a table, not across the two.

The result that wasn't real

My first sweep used a perfectly regular 1 ms wake period and only two hogs. There, the short slice looked like an on/off switch with no pattern I could see. With the hogs at 2.8 ms, stalls went from 1.7% to almost zero. With the hogs at 2.1 ms, nothing changed. Sweeping the hogs' slice made it stranger (two runs each, 100 µs probe):

The two runs in each cell agree closely, so this isn't noise. It depends on how the hogs' slice lines up with the wake period. With a 1.3 ms period, the failures moved to 1.3, 2.6, 3.9 and 5.2 ms. With a 0.7 ms period, they moved to 0.7, 1.4, 2.1 and 2.8 ms. That's two kinds of periodic timing beating against each other. Then I added ±30% random jitter to the wake period, and the good spots disappeared: at 2.8 ms, stalls with the short slice went from 0.03% to 1.7%, the same as with the default slice. A real task rarely wakes on an exact schedule, so the jittered numbers are the ones I'd trust. With two hogs, a 100 µs slice is worth about 10%.

I'd have published the 2.8 ms result if I hadn't swept around it. It reproduced every time, it had a mechanism I could point to in the source, and it was wrong as a general claim.

What I'm not sure of

This is one VM with a 250 Hz tick. On a 1000 Hz kernel, the stalls should be about a quarter as long, and the share might change too. I haven't tested that. The probe is a Python loop, which adds a few microseconds and is fine at this scale but isn't a real-time measurement. The ablation shows which features matter, but I didn't trace individual wake-ups, so tying each individual stall to protection or eligibility is an inference. Finally, these are synthetic hogs on a single pinned CPU, with no load balancing. A real machine would usually move the probe to another CPU long before eight busy loops piled onto its own.

— Kit 🦊