Re: [RFC PATCH] sched/fair: Bias runqueue selection towards almost idle prev CPU

[Chen Yu]

On 2023-10-12 at 18:24:11 +0200, Vincent Guittot wrote:
> On Thu, 12 Oct 2023 at 17:56, Mathieu Desnoyers
> <mathieu.desnoyers@xxxxxxxxxxxx> wrote:
> >
> > On 2023-10-12 11:01, Vincent Guittot wrote:
> > > On Thu, 12 Oct 2023 at 16:33, Mathieu Desnoyers
> > > <mathieu.desnoyers@xxxxxxxxxxxx> wrote:
> > >>
> > >> On 2023-10-11 06:16, Chen Yu wrote:
> > >>> On 2023-10-10 at 09:49:54 -0400, Mathieu Desnoyers wrote:
> > >>>> On 2023-10-09 01:14, Chen Yu wrote:
> > >>>>> On 2023-09-30 at 07:45:38 -0400, Mathieu Desnoyers wrote:
> > >>>>>> On 9/30/23 03:11, Chen Yu wrote:
> > >>>>>>> Hi Mathieu,
> > >>>>>>>
> > >>>>>>> On 2023-09-29 at 14:33:50 -0400, Mathieu Desnoyers wrote:
> > >>>>>>>> Introduce the WAKEUP_BIAS_PREV_IDLE scheduler feature. It biases
> > >>>>>>>> select_task_rq towards the previous CPU if it was almost idle
> > >>>>>>>> (avg_load <= 0.1%).
> > >>>>>>>
> > >>>>>>> Yes, this is a promising direction IMO. One question is that,
> > >>>>>>> can cfs_rq->avg.load_avg be used for percentage comparison?
> > >>>>>>> If I understand correctly, load_avg reflects that more than
> > >>>>>>> 1 tasks could have been running this runqueue, and the
> > >>>>>>> load_avg is the direct proportion to the load_weight of that
> > >>>>>>> cfs_rq. Besides, LOAD_AVG_MAX seems to not be the max value
> > >>>>>>> that load_avg can reach, it is the sum of
> > >>>>>>> 1024 * (y + y^1 + y^2 ... )
> > >>>>>>>
> > >>>>>>> For example,
> > >>>>>>> taskset -c 1 nice -n -20 stress -c 1
> > >>>>>>> cat /sys/kernel/debug/sched/debug | grep 'cfs_rq\[1\]' -A 12 | grep "\.load_avg"
> > >>>>>>>       .load_avg                      : 88763
> > >>>>>>>       .load_avg                      : 1024
> > >>>>>>>
> > >>>>>>> 88763 is higher than LOAD_AVG_MAX=47742
> > >>>>>>
> > >>>>>> I would have expected the load_avg to be limited to LOAD_AVG_MAX somehow,
> > >>>>>> but it appears that it does not happen in practice.
> > >>>>>>
> > >>>>>> That being said, if the cutoff is really at 0.1% or 0.2% of the real max,
> > >>>>>> does it really matter ?
> > >>>>>>
> > >>>>>>> Maybe the util_avg can be used for precentage comparison I suppose?
> > >>>>>> [...]
> > >>>>>>> Or
> > >>>>>>> return cpu_util_without(cpu_rq(cpu), p) * 1000 <= capacity_orig_of(cpu) ?
> > >>>>>>
> > >>>>>> Unfortunately using util_avg does not seem to work based on my testing.
> > >>>>>> Even at utilization thresholds at 0.1%, 1% and 10%.
> > >>>>>>
> > >>>>>> Based on comments in fair.c:
> > >>>>>>
> > >>>>>>     * CPU utilization is the sum of running time of runnable tasks plus the
> > >>>>>>     * recent utilization of currently non-runnable tasks on that CPU.
> > >>>>>>
> > >>>>>> I think we don't want to include currently non-runnable tasks in the
> > >>>>>> statistics we use, because we are trying to figure out if the cpu is a
> > >>>>>> idle-enough target based on the tasks which are currently running, for the
> > >>>>>> purpose of runqueue selection when waking up a task which is considered at
> > >>>>>> that point in time a non-runnable task on that cpu, and which is about to
> > >>>>>> become runnable again.
> > >>>>>>
> > >>>>>
> > >>>>> Although LOAD_AVG_MAX is not the max possible load_avg, we still want to find
> > >>>>> a proper threshold to decide if the CPU is almost idle. The LOAD_AVG_MAX
> > >>>>> based threshold is modified a little bit:
> > >>>>>
> > >>>>> The theory is, if there is only 1 task on the CPU, and that task has a nice
> > >>>>> of 0, the task runs 50 us every 1000 us, then this CPU is regarded as almost
> > >>>>> idle.
> > >>>>>
> > >>>>> The load_sum of the task is:
> > >>>>> 50 * (1 + y + y^2 + ... + y^n)
> > >>>>> The corresponding avg_load of the task is approximately
> > >>>>> NICE_0_WEIGHT * load_sum / LOAD_AVG_MAX = 50.
> > >>>>> So:
> > >>>>>
> > >>>>> /* which is close to LOAD_AVG_MAX/1000 = 47 */
> > >>>>> #define ALMOST_IDLE_CPU_LOAD   50
> > >>>>
> > >>>> Sorry to be slow at understanding this concept, but this whole "load" value
> > >>>> is still somewhat magic to me.
> > >>>>
> > >>>> Should it vary based on CONFIG_HZ_{100,250,300,1000}, or is it independent ?
> > >>>> Where is it documented that the load is a value in "us" out of a window of
> > >>>> 1000 us ?
> > >>>>
> > >>>
> > >>> My understanding is that, the load_sum of a single task is a value in "us" out
> > >>> of a window of 1000 us, while the load_avg of the task will multiply the weight
> > >>> of the task. In this case a task with nice 0 is NICE_0_WEIGHT = 1024.
> > >>>
> > >>> __update_load_avg_se -> ___update_load_sum calculate the load_sum of a task(there
> > >>> is comments around ___update_load_sum to describe the pelt calculation),
> > >>> and ___update_load_avg() calculate the load_avg based on the task's weight.
> > >>
> > >> Thanks for your thorough explanation, now it makes sense.
> > >>
> > >> I understand as well that the cfs_rq->avg.load_sum is the result of summing
> > >> each task load_sum multiplied by their weight:
> > >
> > > Please don't use load_sum but only *_avg.
> > > As already said, util_avg or runnable_avg are better metrics for you
> >
> > I think I found out why using util_avg was not working for me.
> >
> > Considering this comment from cpu_util():
> >
> >   * CPU utilization is the sum of running time of runnable tasks plus the
> >   * recent utilization of currently non-runnable tasks on that CPU.
> >
> > I don't want to include the recent utilization of currently non-runnable
> > tasks on that CPU in order to choose that CPU to do task placement in a
> > context where many tasks were recently running on that cpu (but are
> > currently blocked). I do not want those blocked tasks to be part of the
> > avg.
> 
> But you have the exact same behavior with load_sum/avg.
> 
> >
> > So I think the issue here is that I was using the cpu_util() (and
> > cpu_util_without()) helpers which are considering max(util, runnable),
> > rather than just "util".
> 
> cpu_util_without() only use util_avg but not runnable_avg.
> Nevertheless, cpu_util_without ans cpu_util uses util_est which is
> used to predict the final utilization.
> 
> Let's take the example of task A running 20ms every 200ms on CPU0.
> The util_avg of the cpu will vary in the range [7:365]. When task A

It took me some time to find out where 7 and 365 comes from(Although
Dietmar has once told me about it, but I forgot, sorry :P ). If I understand
correctly, we are checking two scenarios. One scenario is that A runs
now and this has the least decayed running time(max). The other scenario is
that A has slept for a while in the latest 1024us window, thus the min value.

For a task running A ms every B ms,

scenario1:

                     now
                      ^
                      |
 ...|--------|--A ms--|
 ...|--------B ms-----| 

util_sum = 1024(y^0+...+y^(A-1) + y^B+...+y^(B+A-1) + ...)
util_avg = util_sum/(y^0+...+y^n)
         = 1024(1-y^A)/(1-y^B)

When A = 20, B = 200, util_avg is 365

scenario2:
                     now
                      ^
                      |
 ...|--A ms--|--------|
 ...|--------B ms-----|

util_sum = 1024(y^(B-A)+y^(B-A+1)+...+y^(B-1)+y^(2B-A)+y^(2B-A+1)+...y^(2B-1) +...)
         = 1024 y^(B-A)(y^0+...+y^(A-1) + y^B+...+y^(B+A-1) + ...)

util_avg = 1024 y^(B-A)(1-y^A)/(1-y^B)
When A = 20, B = 200, util_avg is 7.

Just wonder if there is any description for this in the kernel, and if not
does it make sense to put this description in it(either in the comments or
doc)? As it might be useful to estimate the util_avg based on the task's behavior.

> wakes up on CPU0, CPU0 util_avg = 7 (below 1%) but taskA will run for
> 20ms which is not really almost idle. On the other side, CPU0 util_est
> will be 365 as soon as task A is enqueued (which will be the value of
> CPU0 util_avg just before going idle)
>
> Let's now take a task B running 100us every 1024us
> The util_avg of the cpu should vary in the range [101:103] and once

May I know how we get 101, 103? I thought for task B, the util_sum
is 100 * (1+y+..y^n), and the util_avg is util_sum/(1+y+...+y^n), so it
is always 100? Am I missing something?

thanks,
Chenyu