[PATCH 0/2] sched/fair: Randomize equally shallow idle CPU picks

[PATCH 0/2] sched/fair: Randomize equally shallow idle CPU picks

[Christian Loehle]

Concurrent slow-path selectors can converge on the same idle CPU before
either task is enqueued. Remove the idle-recency preference and randomize
equal-latency choices in a single scan.

The testing platform 160-CPU, dual-socket Altra has unusually large 80-CPU
candidate groups at NUMA level, making this particularly prone to stale
idle picks.

Median stress-ng throughput (bogo ops/s):

  --fork  --fork-max      Baseline       Patched    Change
  ------------------------------------------------------
       1           1        779.19        811.38    +4.13%
       8           1       2958.32       2960.18    +0.06%
      16           1       5070.95       5247.63    +3.48%
      16           4       7692.64       7831.60    +1.81%
      32           1       8662.82       8643.39    -0.22%
      64           1      11880.47      12096.69    +1.82%

Separate instrumented runs observed lower conditional stale-pick rates,
i.e. a busy candidate at final return:

Workload                Baseline       Patched
----------------------------------------------
fork, 32 creators          0.771%       0.407%
fork, 64 creators          1.242%       0.672%

Christian Loehle (2):
  sched/fair: Drop idle recency from slow-path CPU selection
  sched/fair: Randomize equally shallow slow-path candidates

 kernel/sched/fair.c | 24 ++++++++----------------
 1 file changed, 8 insertions(+), 16 deletions(-)


base-commit: fd73f4a6659897191fa0d40695fe370925dd3780
-- 
2.34.1

[PATCH 1/2] sched/fair: Drop idle recency from slow-path CPU selection

[Christian Loehle]

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. The same
advertised worst-case latency covers both cases.

idle_stamp does not track the current CPUIdle entry, so an older
scheduler-idle CPU may also be re-entering.

A recent scheduler-idle transition may also mark a short gap in recurring
task activity, so the CPU may soon be busy again.

Drop the timestamp tie-break, retaining the first idle candidate unless
a lower advertised exit latency is found.

Signed-off-by: Christian Loehle <christian.loehle@arm.com>
---
 kernel/sched/fair.c | 15 +--------------
 1 file changed, 1 insertion(+), 14 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 7455a83a6a99..ff5793bddc35 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -8459,7 +8459,6 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
 {
 	unsigned long load, min_load = ULONG_MAX;
 	unsigned int min_exit_latency = UINT_MAX;
-	u64 latest_idle_timestamp = 0;
 	int least_loaded_cpu = this_cpu;
 	int shallowest_idle_cpu = -1;
 	int i;
@@ -8480,23 +8479,11 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
 
 		if (available_idle_cpu(i)) {
 			struct cpuidle_state *idle = idle_get_state(rq);
 			if (idle && idle->exit_latency < min_exit_latency) {
-				/*
-				 * We give priority to a CPU whose idle state
-				 * has the smallest exit latency irrespective
-				 * of any idle timestamp.
-				 */
 				min_exit_latency = idle->exit_latency;
-				latest_idle_timestamp = rq->idle_stamp;
 				shallowest_idle_cpu = i;
 			} else if ((!idle || idle->exit_latency == min_exit_latency) &&
-				   rq->idle_stamp > latest_idle_timestamp) {
-				/*
-				 * If equal or no active idle state, then
-				 * the most recently idled CPU might have
-				 * a warmer cache.
-				 */
-				latest_idle_timestamp = rq->idle_stamp;
+				   shallowest_idle_cpu == -1) {
 				shallowest_idle_cpu = i;
 			}
 		} else if (shallowest_idle_cpu == -1) {
-- 
2.34.1

[PATCH 2/2] sched/fair: Randomize equally shallow slow-path candidates

[Christian Loehle]

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.

Use reservoir sampling in the tie branch, resetting the candidate count
when a lower advertised exit latency is found. Use the per-CPU scheduler
PRNG and reciprocal_scale() to avoid variable division or a second scan.

This reduces deterministic convergence without reserving the chosen CPU.

Signed-off-by: Christian Loehle <christian.loehle@arm.com>
---
 kernel/sched/fair.c | 11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index ff5793bddc35..6836a8364440 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -24,6 +24,7 @@
 #include <linux/mmap_lock.h>
 #include <linux/hugetlb_inline.h>
 #include <linux/jiffies.h>
+#include <linux/math.h>
 #include <linux/mm_api.h>
 #include <linux/highmem.h>
 #include <linux/hrtimer.h>
@@ -8459,6 +8460,7 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
 {
 	unsigned long load, min_load = ULONG_MAX;
 	unsigned int min_exit_latency = UINT_MAX;
+	unsigned int nr_candidates = 0;
 	int least_loaded_cpu = this_cpu;
 	int shallowest_idle_cpu = -1;
 	int i;
@@ -8482,9 +8484,12 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
 			if (idle && idle->exit_latency < min_exit_latency) {
 				min_exit_latency = idle->exit_latency;
 				shallowest_idle_cpu = i;
+				nr_candidates = 1;
-			} else if ((!idle || idle->exit_latency == min_exit_latency) &&
-				   shallowest_idle_cpu == -1) {
-				shallowest_idle_cpu = i;
+			} else if (!idle || idle->exit_latency == min_exit_latency) {
+				nr_candidates++;
+				if (nr_candidates == 1 ||
+				    !reciprocal_scale(sched_rng(), nr_candidates))
+					shallowest_idle_cpu = i;
 			}
 		} else if (shallowest_idle_cpu == -1) {
 			load = cpu_load(cpu_rq(i));
-- 
2.34.1

Re: [PATCH 2/2] sched/fair: Randomize equally shallow slow-path candidates

[Kayra Cizmeci]

Hello Christian :>

> 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.

> Use reservoir sampling in the tie branch, resetting the candidate count
> when a lower advertised exit latency is found. Use the per-CPU scheduler
> PRNG and reciprocal_scale() to avoid variable division or a second scan.

> This reduces deterministic convergence without reserving the chosen CPU.

OK. 

But, your test platform was 160 Cores too. I don't think randomization has the same effect on lower
CPU systems.

Let's create a scenario:

On a 80 Core System, that %50 of it's CPU's are idle the randomization's chance of choosing the same CPU
is low. Since there are 40 CPU's to choose from.

But on a 8 Core System in the same idle conditions, randomization's chance of choosing the same CPU
is really higher. Since there are only 4 CPU's to choose from.

I think this solution works better on higher CPU counted systems. 

And I don't think it fully removes the issue. Just better than the original tho.
Thinks can still go bad on this one too, just harder.

Maybe we could add a fallback. Because the real concern is the selected CPU's state
changes when we come to enqueue. If possible tho, I did not really test anything.

Thanks,
Kayra :>>>

Re: [PATCH 2/2] sched/fair: Randomize equally shallow slow-path candidates

[Christian Loehle]

On 9/16/26 12:06, Kayra Cizmeci wrote:
> Hello Christian :>
> 
>> 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.
> 
>> Use reservoir sampling in the tie branch, resetting the candidate count
>> when a lower advertised exit latency is found. Use the per-CPU scheduler
>> PRNG and reciprocal_scale() to avoid variable division or a second scan.
> 
>> This reduces deterministic convergence without reserving the chosen CPU.
> 
> OK. 
> 
> But, your test platform was 160 Cores too. I don't think randomization has the same effect on lower
> CPU systems.
> 
> Let's create a scenario:
> 
> On a 80 Core System, that %50 of it's CPU's are idle the randomization's chance of choosing the same CPU
> is low. Since there are 40 CPU's to choose from.
> 
> But on a 8 Core System in the same idle conditions, randomization's chance of choosing the same CPU
> is really higher. Since there are only 4 CPU's to choose from.
> 
> I think this solution works better on higher CPU counted systems. 

Yes, this mostly works for higher CPU count domains, but the
issue I'm trying to fix basically doesn't exist in the 8 CPU domain
in the first place (first of all fewer chances of having simultaneous
slow paths running that can race and also the slow path is much faster,
i.e. the race window much smaller).

> 
> And I don't think it fully removes the issue. Just better than the original tho.
> Thinks can still go bad on this one too, just harder.

Fully removing the issue would require some synchronisation which the
numbers (which admittedly are pretty modest already) just don't justify.

> 
> Maybe we could add a fallback. Because the real concern is the selected CPU's state
> changes when we come to enqueue. If possible tho, I did not really test anything.

And then do what? rescan?
I don't think increasing the slow path is justified at all, when this relatively
straightforward randomization already significantly reduces the chance
for the 'pathological' test platform.

Re: [PATCH 2/2] sched/fair: Randomize equally shallow slow-path candidates

[Christian Loehle]

On 9/16/26 11:01, Christian Loehle wrote:
> 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.
> 
> Use reservoir sampling in the tie branch, resetting the candidate count
> when a lower advertised exit latency is found. Use the per-CPU scheduler
> PRNG and reciprocal_scale() to avoid variable division or a second scan.
> 
> This reduces deterministic convergence without reserving the chosen CPU.
> 
> Signed-off-by: Christian Loehle <christian.loehle@arm.com>
> ---
>  kernel/sched/fair.c | 11 ++++++++---
>  1 file changed, 8 insertions(+), 3 deletions(-)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index ff5793bddc35..6836a8364440 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -24,6 +24,7 @@
>  #include <linux/mmap_lock.h>
>  #include <linux/hugetlb_inline.h>
>  #include <linux/jiffies.h>
> +#include <linux/math.h>
>  #include <linux/mm_api.h>
>  #include <linux/highmem.h>
>  #include <linux/hrtimer.h>
> @@ -8459,6 +8460,7 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
>  {
>  	unsigned long load, min_load = ULONG_MAX;
>  	unsigned int min_exit_latency = UINT_MAX;
> +	unsigned int nr_candidates = 0;
>  	int least_loaded_cpu = this_cpu;
>  	int shallowest_idle_cpu = -1;
>  	int i;
> @@ -8482,9 +8484,12 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
>  			if (idle && idle->exit_latency < min_exit_latency) {
>  				min_exit_latency = idle->exit_latency;
>  				shallowest_idle_cpu = i;
> +				nr_candidates = 1;
> -			} else if ((!idle || idle->exit_latency == min_exit_latency) &&
> -				   shallowest_idle_cpu == -1) {
> -				shallowest_idle_cpu = i;
> +			} else if (!idle || idle->exit_latency == min_exit_latency) {


Sashiko:
"Can this branch cause the CPU picker to replace an optimal idle CPU with
a non-idle CPU?
In sched_balance_find_dst_group_cpu(), if a !idle CPU is scanned after an
idle CPU has already been found, min_exit_latency will be < UINT_MAX.
However, the condition !idle || idle->exit_latency == min_exit_latency
unconditionally evaluates to true for !idle CPUs.
This allows the !idle CPU to increment nr_candidates and enter the
reservoir, treating its unknown latency as a tie with the optimal known
latency. It then has a 1/nr_candidates chance to overwrite the optimal
shallowest_idle_cpu choice.
Doesn't this reintroduce a scan-order bias during normal load balancing where
non-idle CPUs can replace optimal idle CPUs just because they appear later
in the scan?"

Disagree, this is in the if block of if (available_idle_cpu(i)), so except for
the obvious race which is deliberately taken in the original code too, this
can't be right?

> +				nr_candidates++;
> +				if (nr_candidates == 1 ||
> +				    !reciprocal_scale(sched_rng(), nr_candidates))
> +					shallowest_idle_cpu = i;
>  			}
>  		} else if (shallowest_idle_cpu == -1) {
>  			load = cpu_load(cpu_rq(i));

Re: [PATCH 2/2] sched/fair: Randomize equally shallow slow-path candidates

[Kayra Cizmeci]

> > Hello Christian :>
> > 
> >> 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.
> > 
> >> Use reservoir sampling in the tie branch, resetting the candidate count
> >> when a lower advertised exit latency is found. Use the per-CPU scheduler
> >> PRNG and reciprocal_scale() to avoid variable division or a second scan.
> > 
> >> This reduces deterministic convergence without reserving the chosen CPU.
> > 
> > OK. 
> > 
> > But, your test platform was 160 Cores too. I don't think randomization has the same effect on lower
> > CPU systems.
> > 
> > Let's create a scenario:
> > 
> > On a 80 Core System, that %50 of it's CPU's are idle the randomization's chance of choosing the same CPU
> > is low. Since there are 40 CPU's to choose from.
> > 
> > But on a 8 Core System in the same idle conditions, randomization's chance of choosing the same CPU
> > is really higher. Since there are only 4 CPU's to choose from.
> > 
> > I think this solution works better on higher CPU counted systems. 

> Yes, this mostly works for higher CPU count domains, but the
> issue I'm trying to fix basically doesn't exist in the 8 CPU domain
> in the first place (first of all fewer chances of having simultaneous
> slow paths running that can race and also the slow path is much faster,
> i.e. the race window much smaller).

> > 
> > And I don't think it fully removes the issue. Just better than the original tho.
> > Thinks can still go bad on this one too, just harder.

> Fully removing the issue would require some synchronisation which the
> numbers (which admittedly are pretty modest already) just don't justify.

> > 
> > Maybe we could add a fallback. Because the real concern is the selected CPU's state
> > changes when we come to enqueue. If possible tho, I did not really test anything.

> And then do what? rescan?
> I don't think increasing the slow path is justified at all, when this relatively
> straightforward randomization already significantly reduces the chance
> for the 'pathological' test platform.

Fair. 

My real concern is that randomization is not predictable while the other solutions are.
I don't really care about their speed when it comes to that.

That's just a concern tho. I think this version is better than just placing the task
to the CPU anyways. (in terms of approach)

Re: [PATCH 2/2] sched/fair: Randomize equally shallow slow-path candidates

[Shubhang]

Hi Christian,

On Wed, 16 Sep 2026, Christian Loehle wrote:

> +			} else if (!idle || idle->exit_latency == min_exit_latency) {
> +				nr_candidates++;
> +				if (nr_candidates == 1 ||
> +				    !reciprocal_scale(sched_rng(), nr_candidates))
> +					shallowest_idle_cpu = i;

available_idle_cpu(i) ensures that this is an idle CPU, but !idle 
means that no active cpuidle state, meaning no exit latency is 
available for comparison.

[PATCH 1/2] treats such a CPU as a fallback i.e. it is selected only when 
no idle candidate has been found yet. Here it becomes an equal reservoir 
candidate, even after selecting a CPU with the minimum known exit latency. 
That is, it is added to the random selection pool and can replace 
shallowest_idle_cpu.

Is that intentional ? If not, should reservoir sampling be limited to
candidates with `idle->exit_latency == min_exit_latency`, while 
retaining the first !idle CPU only as the fallback?

Regards,
Shubhang Kaushik