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

[Kayra Cizmeci <kayracizmeci@gmail.com>]

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