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