When the Linux scheduler needs an idle CPU to wake a task on, it scans and takes the first suitable one. Arm engineer Christian Loehle has found that this deterministic scan produces a specific failure at scale, and proposes randomising among equally good candidates.

The collision

“Picking the first eligible idle CPU leaves a scan-order bias. Concurrent slow-path selectors can choose the same CPU before either task is enqueued.”

That is the core of it. Two wakeups happening at the same moment both scan, both find the same first idle CPU, and both pick it, because neither has been queued yet when the other looks. One CPU gets two tasks while a neighbouring idle CPU gets none.

On a four-core laptop this is noise. On a machine with 160 cores it happens constantly, and the consequence is uneven distribution across a large pool of otherwise available capacity.

A subtler point about idle states

Loehle also questions the heuristic the scan uses:

“The slow-path CPU picker favours the most recently idle CPU as a proxy for cache warmth. A more recent idle stamp may make ongoing entry more likely. Among CPUs with equal advertised exit latency, this may favour the one with the highest wakeup cost: if entry cannot be aborted, it must finish entry and then exit, while an already-resident CPU only needs to exit.”

Preferring the most recently idle CPU is meant to catch one that still has useful data in cache. But a CPU that went idle moments ago may be midway into entering a deeper idle state, and if that entry cannot be aborted it has to finish going down before it can come back up. A CPU that settled into that state a while ago only has to come up.

Both advertise the same worst-case exit latency, so the scheduler cannot tell them apart. The heuristic intended to pick the cheaper option can select the more expensive one.

The proposed fix

Reservoir sampling among the tied candidates, using the per-CPU scheduler PRNG and reciprocal_scale() to avoid a division or a second scan.

Reservoir sampling picks uniformly from a stream without knowing its length in advance, which fits a scan that does not know how many equally good CPUs it will encounter. The candidate count resets whenever a CPU with genuinely lower exit latency appears, so the randomness only applies among true ties.

Crucially it does not reserve the chosen CPU. There is no new locking, no shared state, no extra scan. Two concurrent selectors can still collide, just far less often than when both deterministically choose the same one.

The numbers, and the doubts

Testing on a dual Ampere Altra with 160 cores using Stress-NG showed up to a few percent throughput improvement.

That is honest and modest, and the open questions are fair ones:

• Does it help at low core counts? With four or eight cores there are rarely many tied candidates, so probably not much
• Does randomness hurt predictability? Latency-sensitive workloads value consistent placement, and a scheduler that makes different choices run to run is harder to reason about

The counter-argument is that the deterministic behaviour was not delivering predictable placement either. It was delivering predictable collisions.

Core counts keep climbing, with AMD EPYC reaching 256 per socket, so scan-order bias becomes more expensive over time rather than less. If a better structural fix exists, this patch is arguing that nobody has proposed one.

# how many cores and what idle states they have
nproc
cpupower idle-info

# watch distribution across cores under load
mpstat -P ALL 1

Anyone running heavily parallel workloads on large machines, which is most VPS and dedicated server hosts, is in the population this targets. It joins a busy month of kernel performance work alongside faster file opens and faster hibernation.