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

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