[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

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

[Christian Loehle]

On 9/16/26 20:43, Shubhang wrote:
> 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?

Hi Shubhang,

Thanks for taking a look. Including !idle candidates was intentional,
although you're right that this changes their treatment.

I think there's a case for giving NULL a zero ranking. With a working
cpuidle driver, NULL can mean the CPU is preparing for entry or finishing
after exit, making it a good low-latency candidate.
Architecture fallbacks are also reasonable candidates AFAICS.
In any case, I'd prefer to address that separately (perhaps through a
helper in the idle/cpuidle code rather than embedding those assumptions
in fair.c and will drop !idle CPUs competing with min_exit_latency CPUs,
the patch doesn't need it.
Thanks!
Christian

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

[Christian Loehle]

On 9/17/26 08:47, Christian Loehle wrote:
> On 9/16/26 20:43, Shubhang wrote:
>> 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?
> 
> Hi Shubhang,
> 
> Thanks for taking a look. Including !idle candidates was intentional,
> although you're right that this changes their treatment.
> 
> I think there's a case for giving NULL a zero ranking. With a working
> cpuidle driver, NULL can mean the CPU is preparing for entry or finishing
> after exit, making it a good low-latency candidate.
> Architecture fallbacks are also reasonable candidates AFAICS.
> In any case, I'd prefer to address that separately (perhaps through a
> helper in the idle/cpuidle code rather than embedding those assumptions
> in fair.c and will drop !idle CPUs competing with min_exit_latency CPUs,
> the patch doesn't need it.
Actually about the last part, I'm leaning towards sticking with v1, because
that is actually the current upstream behaviour. !idle CPUs currently trump
any CPU seen so far, but preserve min_exit_latency, therefore sticking it
into the shallowest seen reservoir is consistent IMO (although we can
certainly debate if that should be the case).
I'd prefer sending a follow-up with an idle helper and making a properly
defined policy there, but that's adjacent to this patch.

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

[Vincent Guittot]

On Wed, 16 Sept 2026 at 12:01, Christian Loehle
<christian.loehle@arm.com> wrote:
>
> 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.

Reviewed-by: Vincent Guittot <vincent.guittot@linaro.org>

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

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

[Vincent Guittot]

On Thu, 17 Sept 2026 at 11:58, Christian Loehle
<christian.loehle@arm.com> wrote:
>
> On 9/17/26 08:47, Christian Loehle wrote:
> > On 9/16/26 20:43, Shubhang wrote:
> >> 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?
> >
> > Hi Shubhang,
> >
> > Thanks for taking a look. Including !idle candidates was intentional,
> > although you're right that this changes their treatment.
> >
> > I think there's a case for giving NULL a zero ranking. With a working
> > cpuidle driver, NULL can mean the CPU is preparing for entry or finishing
> > after exit, making it a good low-latency candidate.
> > Architecture fallbacks are also reasonable candidates AFAICS.
> > In any case, I'd prefer to address that separately (perhaps through a
> > helper in the idle/cpuidle code rather than embedding those assumptions
> > in fair.c and will drop !idle CPUs competing with min_exit_latency CPUs,
> > the patch doesn't need it.
> Actually about the last part, I'm leaning towards sticking with v1, because
> that is actually the current upstream behaviour. !idle CPUs currently trump
> any CPU seen so far, but preserve min_exit_latency, therefore sticking it
> into the shallowest seen reservoir is consistent IMO (although we can
> certainly debate if that should be the case).
> I'd prefer sending a follow-up with an idle helper and making a properly
> defined policy there, but that's adjacent to this patch.

When a CPU idle driver is present, !idle means the CPU is entering or
leaving an idle state. A CPU entering idle could be a good candidate
but we don't want to select the one exiting its idle state, as it is
already scheduled for activity. The current version is trying to do so
with idle_stamp comparison although this is far from being robust.
That being said, a random choice might not be worse.

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

[Vincent Guittot]

On Wed, 16 Sept 2026 at 12:01, Christian Loehle
<christian.loehle@arm.com> 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;

You clear the number of candidate when you find a lower exit_latency
but !idle CPUs that have already been checked will be cleared whereas
they still get a chance if they are checked later.

> -                       } 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]

> Actually about the last part, I'm leaning towards sticking with v1, because
> that is actually the current upstream behaviour. !idle CPUs currently trump
> any CPU seen so far, but preserve min_exit_latency, therefore sticking it
> into the shallowest seen reservoir is consistent IMO (although we can
> certainly debate if that should be the case).
> I'd prefer sending a follow-up with an idle helper and making a properly
> defined policy there, but that's adjacent to this patch.

Hello Christian,

I could send a patch about this if you want, after making sure about
everything, obviously.

I'm a bit sick, so if you say yes, I could be slow. But I don't think
it will take more than 3 days after your answer.

Thanks,
Kayra :>

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

[Christian Loehle]

On 9/17/26 15:08, Vincent Guittot wrote:
> On Wed, 16 Sept 2026 at 12:01, Christian Loehle
> <christian.loehle@arm.com> 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;
> 
> You clear the number of candidate when you find a lower exit_latency
> but !idle CPUs that have already been checked will be cleared whereas
> they still get a chance if they are checked later.
That is correct. Is this a problem?
(Again, mirroring what upstream currently does, let's say exit_latency(CPU0)=100, exit_latency(CPU2)=1
!idle at CPU3 trumps CPU2 (assuming recent idle_stamp), !idle at CPU1 doesn't trump CPU2, i.e.
the inconsistency around !idle is already there?)
And I'm assuming we really don't wanna keep a cpumask of !idle CPUs, if anything we may just ignore
them completely, given how unlikely it they are to be observed.

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

[Vincent Guittot]

On Thu, 17 Sept 2026 at 16:22, Christian Loehle
<christian.loehle@arm.com> wrote:
>
> On 9/17/26 15:08, Vincent Guittot wrote:
> > On Wed, 16 Sept 2026 at 12:01, Christian Loehle
> > <christian.loehle@arm.com> 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;
> >
> > You clear the number of candidate when you find a lower exit_latency
> > but !idle CPUs that have already been checked will be cleared whereas
> > they still get a chance if they are checked later.
> That is correct. Is this a problem?

I would say we should try to be consistent

> (Again, mirroring what upstream currently does, let's say exit_latency(CPU0)=100, exit_latency(CPU2)=1
> !idle at CPU3 trumps CPU2 (assuming recent idle_stamp), !idle at CPU1 doesn't trump CPU2, i.e.
> the inconsistency around !idle is already there?)

Fair enough but the idle_stamp was also in the party

> And I'm assuming we really don't wanna keep a cpumask of !idle CPUs, if anything we may just ignore
> them completely, given how unlikely it they are to be observed.

We must keep them when there is no cpuidle driver, i.e. until we find
a CPU with an idle state

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

[Christian Loehle]

On 9/17/26 16:08, Vincent Guittot wrote:
> On Thu, 17 Sept 2026 at 16:22, Christian Loehle
> <christian.loehle@arm.com> wrote:
>>
>> On 9/17/26 15:08, Vincent Guittot wrote:
>>> On Wed, 16 Sept 2026 at 12:01, Christian Loehle
>>> <christian.loehle@arm.com> 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;
>>>
>>> You clear the number of candidate when you find a lower exit_latency
>>> but !idle CPUs that have already been checked will be cleared whereas
>>> they still get a chance if they are checked later.
>> That is correct. Is this a problem?
> 
> I would say we should try to be consistent

Ack

> 
>> (Again, mirroring what upstream currently does, let's say exit_latency(CPU0)=100, exit_latency(CPU2)=1
>> !idle at CPU3 trumps CPU2 (assuming recent idle_stamp), !idle at CPU1 doesn't trump CPU2, i.e.
>> the inconsistency around !idle is already there?)
> 
> Fair enough but the idle_stamp was also in the party
> 
>> And I'm assuming we really don't wanna keep a cpumask of !idle CPUs, if anything we may just ignore
>> them completely, given how unlikely it they are to be observed.
> 
> We must keep them when there is no cpuidle driver, i.e. until we find
> a CPU with an idle state

Alright let me make a it a U64_MAX reservoir.
Thanks for reviewing Vincent!