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@xxxxxxx> wrote:
>
> On 9/17/26 15:08, Vincent Guittot wrote:
> > On Wed, 16 Sept 2026 at 12:01, Christian Loehle
> > <christian.loehle@xxxxxxx> 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@xxxxxxx>
> >> ---
> >>  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