sched/pelt: avoid underestimate of task utilization

  It has been reported that thread's util_est can significantly decrease as
a result of sharing the CPU with other threads. The use case can be easily
reproduced with a periodic task TA that runs 1ms and sleeps 100us.
When the task is alone on the CPU, its max utilization and its util_est is
around 888. If another similar task starts to run on the same CPU, TA will
have to share the CPU runtime and its maximum utilization will decrease
around half the CPU capacity (512) then TA's util_est will follow this new
maximum trend which is only the result of sharing the CPU with others
tasks. Such situation can be detected with runnable_avg wich is close or
equal to util_avg when TA is alone but increases above util_avg when TA
shares the CPU with other threads and wait on the runqueue.

Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
---

This patch implements what I mentioned in [1]. I have been able to
reproduce such pattern with rt-app.

[1] https://lore.kernel.org/lkml/CAKfTPtDd-HhF-YiNTtL9i5k0PfJbF819Yxu4YquzfXgwi7voyw@mail.gmail.com/#t

 kernel/sched/fair.c | 13 +++++++++++++
 1 file changed, 13 insertions(+)
  

On 11/22/23 15:01, Vincent Guittot wrote:
> It has been reported that thread's util_est can significantly decrease as
> a result of sharing the CPU with other threads. The use case can be easily
> reproduced with a periodic task TA that runs 1ms and sleeps 100us.
> When the task is alone on the CPU, its max utilization and its util_est is
> around 888. If another similar task starts to run on the same CPU, TA will
> have to share the CPU runtime and its maximum utilization will decrease
> around half the CPU capacity (512) then TA's util_est will follow this new
> maximum trend which is only the result of sharing the CPU with others
> tasks. Such situation can be detected with runnable_avg wich is close or
> equal to util_avg when TA is alone but increases above util_avg when TA
> shares the CPU with other threads and wait on the runqueue.
> 
> Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> ---

So effectively if have two always running tasks on the same CPU their util_est
will converge to 1024 instead of 512 now, right?

I guess this is more accurate, yes. And I think this will hit the same
limitation we can hit with uclamp_max. If for example there are two tasks that
are 650 if they run alone, they would appear as 1024 now (instead of 512) if
they share the CPU because combined running there will be no idle time on the
CPU and appear like always running tasks, I think.

If I got it right, I think this should not be a problem in practice because the
only reason these two tasks will be stuck on the same CPU is because the load
balancer can't do anything about it to spread them; which indicates the system
must be busy anyway. Once there's more idle time elsewhere, they should be
spread and converge to 650 again.

Not my forte, but LGTM anyway.


Cheers

--
Qais Yousef
  

Hi Vincent,

On 22/11/2023 14:01, Vincent Guittot wrote:
> It has been reported that thread's util_est can significantly decrease as
> a result of sharing the CPU with other threads. The use case can be easily
> reproduced with a periodic task TA that runs 1ms and sleeps 100us.
> When the task is alone on the CPU, its max utilization and its util_est is
> around 888. If another similar task starts to run on the same CPU, TA will
> have to share the CPU runtime and its maximum utilization will decrease
> around half the CPU capacity (512) then TA's util_est will follow this new
> maximum trend which is only the result of sharing the CPU with others
> tasks. Such situation can be detected with runnable_avg wich is close or
> equal to util_avg when TA is alone but increases above util_avg when TA
> shares the CPU with other threads and wait on the runqueue.

Thanks for bringing this case up. I'm a bit nervous skipping util_est 
updates this way. While it is true that this avoids dropping util_est 
when the task is still busy doing stuff, it also avoids dropping 
util_est when the task really is becoming less busy. If a task has a 
legitimate reason to drop its utilization, it looks weird to me that its 
util_est dropping can be stopped by a new task joining this rq which 
pushes up runnable_avg.

Also, something about rt-app. Is there an easy way to ask an rt-app 
thread to achieve a certain amount of throughput (like loops per 
second)? I think 'runs 1ms and sleeps 100us' may not entirely simulate a 
task that really wants to preserve a util_est of 888. If its utilization 
really is that high, its sleep time will become less and less when 
sharing the rq with another task, or even has no idle time and become 
1024 which will trigger overutilization and migration.

> 
> Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> ---
> 
> This patch implements what I mentioned in [1]. I have been able to
> reproduce such pattern with rt-app.
> 
> [1] https://lore.kernel.org/lkml/CAKfTPtDd-HhF-YiNTtL9i5k0PfJbF819Yxu4YquzfXgwi7voyw@mail.gmail.com/#t
> 
>   kernel/sched/fair.c | 13 +++++++++++++
>   1 file changed, 13 insertions(+)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 07f555857698..eeb505d28905 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -4774,6 +4774,11 @@ static inline unsigned long task_util(struct task_struct *p)
>   	return READ_ONCE(p->se.avg.util_avg);
>   }
>   
> +static inline unsigned long task_runnable(struct task_struct *p)
> +{
> +	return READ_ONCE(p->se.avg.runnable_avg);
> +}
> +
>   static inline unsigned long _task_util_est(struct task_struct *p)
>   {
>   	struct util_est ue = READ_ONCE(p->se.avg.util_est);
> @@ -4892,6 +4897,14 @@ static inline void util_est_update(struct cfs_rq *cfs_rq,
>   	if (task_util(p) > arch_scale_cpu_capacity(cpu_of(rq_of(cfs_rq))))
>   		return;
>   
> +	/*
> +	 * To avoid underestimate of task utilization, skip updates of ewma if
> +	 * we cannot grant that thread got all CPU time it wanted.
> +	 */
> +	if ((ue.enqueued + UTIL_EST_MARGIN) < task_runnable(p))
> +		goto done;
> +
> +
>   	/*
>   	 * Update Task's estimated utilization
>   	 *
  

The same but with plain text instead of html ...

 On Wed, 22 Nov 2023 at 17:40, Hongyan Xia <hongyan.xia2@arm.com> wrote:
>
> Hi Vincent,
>
> On 22/11/2023 14:01, Vincent Guittot wrote:
> > It has been reported that thread's util_est can significantly decrease as
> > a result of sharing the CPU with other threads. The use case can be easily
> > reproduced with a periodic task TA that runs 1ms and sleeps 100us.
> > When the task is alone on the CPU, its max utilization and its util_est is
> > around 888. If another similar task starts to run on the same CPU, TA will
> > have to share the CPU runtime and its maximum utilization will decrease
> > around half the CPU capacity (512) then TA's util_est will follow this new
> > maximum trend which is only the result of sharing the CPU with others
> > tasks. Such situation can be detected with runnable_avg wich is close or
> > equal to util_avg when TA is alone but increases above util_avg when TA
> > shares the CPU with other threads and wait on the runqueue.
>
> Thanks for bringing this case up. I'm a bit nervous skipping util_est
> updates this way. While it is true that this avoids dropping util_est
> when the task is still busy doing stuff, it also avoids dropping
> util_est when the task really is becoming less busy. If a task has a
> legitimate reason to drop its utilization, it looks weird to me that its
> util_est dropping can be stopped by a new task joining this rq which
> pushes up runnable_avg.

 We prefer an util_est that overestimate rather than under estimate
because in 1st case you will not provide enough performance to the
task which will remain under provisioned whereas in the other case you
will create some idle time which will enable to reduce contention and
as a result reduce the util_est so the overestimate will be transient
whereas the underestimate will be remain

> Also, something about rt-app. Is there an easy way to ask an rt-app
> thread to achieve a certain amount of throughput (like loops per
> second)? I think 'runs 1ms and sleeps 100us' may not entirely simulate a
> task that really wants to preserve a util_est of 888. If its utilization


 We can do this in rt-app with timer instead of sleep but in this case
there is no sleep and as a result no update of util_est. In the case
raised in [1] by lukasz and according to the shared charts, there are
some sleep phases even when the task must share the cpu. This can
typically happen when you have a pipe of threads:  A task prepares
some data, wakes up next step and waits for the result. Then the 1st
task is woken up when it's done and to prepare the next data and so on
... In this case, the task will slow down because of time sharing and
there is still sleep phase

>
>
> really is that high, its sleep time will become less and less when
> sharing the rq with another task, or even has no idle time and become
> 1024 which will trigger overutilization and migration.
>
> >
> > Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> > ---
> >
> > This patch implements what I mentioned in [1]. I have been able to
> > reproduce such pattern with rt-app.
> >
> > [1] https://lore.kernel.org/lkml/CAKfTPtDd-HhF-YiNTtL9i5k0PfJbF819Yxu4YquzfXgwi7voyw@mail.gmail.com/#t
> >
  

On 11/22/23 14:01, Vincent Guittot wrote:
> It has been reported that thread's util_est can significantly decrease as
> a result of sharing the CPU with other threads. The use case can be easily
> reproduced with a periodic task TA that runs 1ms and sleeps 100us.
> When the task is alone on the CPU, its max utilization and its util_est is
> around 888. If another similar task starts to run on the same CPU, TA will
> have to share the CPU runtime and its maximum utilization will decrease
> around half the CPU capacity (512) then TA's util_est will follow this new
> maximum trend which is only the result of sharing the CPU with others
> tasks. Such situation can be detected with runnable_avg wich is close or
> equal to util_avg when TA is alone but increases above util_avg when TA
> shares the CPU with other threads and wait on the runqueue.
> 
> Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> ---
> 
> This patch implements what I mentioned in [1]. I have been able to
> reproduce such pattern with rt-app.
> 
> [1] https://lore.kernel.org/lkml/CAKfTPtDd-HhF-YiNTtL9i5k0PfJbF819Yxu4YquzfXgwi7voyw@mail.gmail.com/#t

Thanks Vincet for looking at it! I didn't have to to come
back to this issue.

> 
>   kernel/sched/fair.c | 13 +++++++++++++
>   1 file changed, 13 insertions(+)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 07f555857698..eeb505d28905 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -4774,6 +4774,11 @@ static inline unsigned long task_util(struct task_struct *p)
>   	return READ_ONCE(p->se.avg.util_avg);
>   }
>   
> +static inline unsigned long task_runnable(struct task_struct *p)
> +{
> +	return READ_ONCE(p->se.avg.runnable_avg);
> +}
> +
>   static inline unsigned long _task_util_est(struct task_struct *p)
>   {
>   	struct util_est ue = READ_ONCE(p->se.avg.util_est);
> @@ -4892,6 +4897,14 @@ static inline void util_est_update(struct cfs_rq *cfs_rq,
>   	if (task_util(p) > arch_scale_cpu_capacity(cpu_of(rq_of(cfs_rq))))
>   		return;
>   
> +	/*
> +	 * To avoid underestimate of task utilization, skip updates of ewma if
> +	 * we cannot grant that thread got all CPU time it wanted.
> +	 */
> +	if ((ue.enqueued + UTIL_EST_MARGIN) < task_runnable(p))
> +		goto done;
> +
> +
>   	/*
>   	 * Update Task's estimated utilization
>   	 *

That looks reasonable to do. I cannot test it right now on my pixel6.
It should do the trick to the task util that we need in bigger apps
than rt-app as well.

Reviewed-by: Lukasz luba <lukasz.luba@arm.com>
  

On 11/21/23 23:01, Qais Yousef wrote:
> On 11/22/23 15:01, Vincent Guittot wrote:
>> It has been reported that thread's util_est can significantly decrease as
>> a result of sharing the CPU with other threads. The use case can be easily
>> reproduced with a periodic task TA that runs 1ms and sleeps 100us.
>> When the task is alone on the CPU, its max utilization and its util_est is
>> around 888. If another similar task starts to run on the same CPU, TA will
>> have to share the CPU runtime and its maximum utilization will decrease
>> around half the CPU capacity (512) then TA's util_est will follow this new
>> maximum trend which is only the result of sharing the CPU with others
>> tasks. Such situation can be detected with runnable_avg wich is close or
>> equal to util_avg when TA is alone but increases above util_avg when TA
>> shares the CPU with other threads and wait on the runqueue.
>>
>> Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
>> ---
> 
> So effectively if have two always running tasks on the same CPU their util_est
> will converge to 1024 instead of 512 now, right?
> 
> I guess this is more accurate, yes. And I think this will hit the same
> limitation we can hit with uclamp_max. If for example there are two tasks that
> are 650 if they run alone, they would appear as 1024 now (instead of 512) if
> they share the CPU because combined running there will be no idle time on the
> CPU and appear like always running tasks, I think.

Well they might not converge to 1024. It will just prevent them to not
drop the highest seen util_est on them before this contention happen.

> 
> If I got it right, I think this should not be a problem in practice because the
> only reason these two tasks will be stuck on the same CPU is because the load
> balancer can't do anything about it to spread them; which indicates the system
> must be busy anyway. Once there's more idle time elsewhere, they should be
> spread and converge to 650 again.

It can be applicable for the real app. That chrome thread that I
reported (which is ~950 util) drops it's util and util_est in some
scenarios when there are some other tasks in the runqueue, because
of some short sleeps. Than this situation attracts other tasks to
migrate but next time when the big thread wakes-up it has to share
the CPU and looses it's util_est (which was the last information
that there was such big util on it).

Those update moments when we go via util_est_update() code path
are quite often in short time and don't fit into the PELT world,
IMO. It's like asynchronous force-update to the util_est signal,
not the same way wrt how slowly util is built. I think Peter
had something like this impression, when he asked me of often
and fast this update could be triggered that we loose the value...

I would even dare to call this patch a fix and a candidate to
stable-tree.
  

On 11/23/23 14:27, Lukasz Luba wrote:
> 
> 
> On 11/21/23 23:01, Qais Yousef wrote:
> > On 11/22/23 15:01, Vincent Guittot wrote:
> > > It has been reported that thread's util_est can significantly decrease as
> > > a result of sharing the CPU with other threads. The use case can be easily
> > > reproduced with a periodic task TA that runs 1ms and sleeps 100us.
> > > When the task is alone on the CPU, its max utilization and its util_est is
> > > around 888. If another similar task starts to run on the same CPU, TA will
> > > have to share the CPU runtime and its maximum utilization will decrease
> > > around half the CPU capacity (512) then TA's util_est will follow this new
> > > maximum trend which is only the result of sharing the CPU with others
> > > tasks. Such situation can be detected with runnable_avg wich is close or
> > > equal to util_avg when TA is alone but increases above util_avg when TA
> > > shares the CPU with other threads and wait on the runqueue.
> > > 
> > > Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> > > ---
> > 
> > So effectively if have two always running tasks on the same CPU their util_est
> > will converge to 1024 instead of 512 now, right?
> > 
> > I guess this is more accurate, yes. And I think this will hit the same
> > limitation we can hit with uclamp_max. If for example there are two tasks that
> > are 650 if they run alone, they would appear as 1024 now (instead of 512) if
> > they share the CPU because combined running there will be no idle time on the
> > CPU and appear like always running tasks, I think.
> 
> Well they might not converge to 1024. It will just prevent them to not
> drop the highest seen util_est on them before this contention happen.

Right, we just ignore the decay and hold on to the last seen value.

> 
> > 
> > If I got it right, I think this should not be a problem in practice because the
> > only reason these two tasks will be stuck on the same CPU is because the load
> > balancer can't do anything about it to spread them; which indicates the system
> > must be busy anyway. Once there's more idle time elsewhere, they should be
> > spread and converge to 650 again.
> 
> It can be applicable for the real app. That chrome thread that I
> reported (which is ~950 util) drops it's util and util_est in some
> scenarios when there are some other tasks in the runqueue, because
> of some short sleeps. Than this situation attracts other tasks to
> migrate but next time when the big thread wakes-up it has to share
> the CPU and looses it's util_est (which was the last information
> that there was such big util on it).
> 
> Those update moments when we go via util_est_update() code path
> are quite often in short time and don't fit into the PELT world,
> IMO. It's like asynchronous force-update to the util_est signal,
> not the same way wrt how slowly util is built. I think Peter
> had something like this impression, when he asked me of often
> and fast this update could be triggered that we loose the value...
> 
> I would even dare to call this patch a fix and a candidate to
> stable-tree.

It seems a genuine fix yes. I am generally worried of the power impact of
util_est. But I tend to agree this is something worth considering for
a backport.


Cheers

--
Qais Yousef
  

On 22/11/2023 17:37, Vincent Guittot wrote:
> The same but with plain text instead of html ...
> 
>   On Wed, 22 Nov 2023 at 17:40, Hongyan Xia <hongyan.xia2@arm.com> wrote:
>>
>> Hi Vincent,
>>
>> On 22/11/2023 14:01, Vincent Guittot wrote:
>>> It has been reported that thread's util_est can significantly decrease as
>>> a result of sharing the CPU with other threads. The use case can be easily
>>> reproduced with a periodic task TA that runs 1ms and sleeps 100us.
>>> When the task is alone on the CPU, its max utilization and its util_est is
>>> around 888. If another similar task starts to run on the same CPU, TA will
>>> have to share the CPU runtime and its maximum utilization will decrease
>>> around half the CPU capacity (512) then TA's util_est will follow this new
>>> maximum trend which is only the result of sharing the CPU with others
>>> tasks. Such situation can be detected with runnable_avg wich is close or
>>> equal to util_avg when TA is alone but increases above util_avg when TA
>>> shares the CPU with other threads and wait on the runqueue.
>>
>> Thanks for bringing this case up. I'm a bit nervous skipping util_est
>> updates this way. While it is true that this avoids dropping util_est
>> when the task is still busy doing stuff, it also avoids dropping
>> util_est when the task really is becoming less busy. If a task has a
>> legitimate reason to drop its utilization, it looks weird to me that its
>> util_est dropping can be stopped by a new task joining this rq which
>> pushes up runnable_avg.
> 
>   We prefer an util_est that overestimate rather than under estimate
> because in 1st case you will not provide enough performance to the
> task which will remain under provisioned whereas in the other case you
> will create some idle time which will enable to reduce contention and
> as a result reduce the util_est so the overestimate will be transient
> whereas the underestimate will be remain

My concern is mostly about energy efficiency, although I have no 
concrete evidence on energy impact so I'm not firmly against this patch.

> 
>> Also, something about rt-app. Is there an easy way to ask an rt-app
>> thread to achieve a certain amount of throughput (like loops per
>> second)? I think 'runs 1ms and sleeps 100us' may not entirely simulate a
>> task that really wants to preserve a util_est of 888. If its utilization
> 
> 
>   We can do this in rt-app with timer...
Thanks. Looking at the rt-app doc, I think a timer with absolute time 
stamps does what I want.
  

On 22/11/2023 14:01, Vincent Guittot wrote:
> [...]
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 07f555857698..eeb505d28905 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -4774,6 +4774,11 @@ static inline unsigned long task_util(struct task_struct *p)
>   	return READ_ONCE(p->se.avg.util_avg);
>   }
>   
> +static inline unsigned long task_runnable(struct task_struct *p)
> +{
> +	return READ_ONCE(p->se.avg.runnable_avg);
> +}
> +
>   static inline unsigned long _task_util_est(struct task_struct *p)
>   {
>   	struct util_est ue = READ_ONCE(p->se.avg.util_est);
> @@ -4892,6 +4897,14 @@ static inline void util_est_update(struct cfs_rq *cfs_rq,
>   	if (task_util(p) > arch_scale_cpu_capacity(cpu_of(rq_of(cfs_rq))))
>   		return;
>   
> +	/*
> +	 * To avoid underestimate of task utilization, skip updates of ewma if
> +	 * we cannot grant that thread got all CPU time it wanted.
> +	 */
> +	if ((ue.enqueued + UTIL_EST_MARGIN) < task_runnable(p))
> +		goto done;
> +
> +

Actually, does this also skip util_est increases as well, assuming no 
FASTUP? When a task is ramping up, another task could join and then 
blocks this task from ramping up its util_est.

Or do we think this is intended behavior for !FASTUP?

>   	/*
>   	 * Update Task's estimated utilization
>   	 *
  

On Fri, 24 Nov 2023 at 11:44, Hongyan Xia <hongyan.xia2@arm.com> wrote:
>
> On 22/11/2023 14:01, Vincent Guittot wrote:
> > [...]
> >
> > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > index 07f555857698..eeb505d28905 100644
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -4774,6 +4774,11 @@ static inline unsigned long task_util(struct task_struct *p)
> >       return READ_ONCE(p->se.avg.util_avg);
> >   }
> >
> > +static inline unsigned long task_runnable(struct task_struct *p)
> > +{
> > +     return READ_ONCE(p->se.avg.runnable_avg);
> > +}
> > +
> >   static inline unsigned long _task_util_est(struct task_struct *p)
> >   {
> >       struct util_est ue = READ_ONCE(p->se.avg.util_est);
> > @@ -4892,6 +4897,14 @@ static inline void util_est_update(struct cfs_rq *cfs_rq,
> >       if (task_util(p) > arch_scale_cpu_capacity(cpu_of(rq_of(cfs_rq))))
> >               return;
> >
> > +     /*
> > +      * To avoid underestimate of task utilization, skip updates of ewma if
> > +      * we cannot grant that thread got all CPU time it wanted.
> > +      */
> > +     if ((ue.enqueued + UTIL_EST_MARGIN) < task_runnable(p))
> > +             goto done;
> > +
> > +
>
> Actually, does this also skip util_est increases as well, assuming no
> FASTUP? When a task is ramping up, another task could join and then
> blocks this task from ramping up its util_est.
>
> Or do we think this is intended behavior for !FASTUP?

sched_feat(UTIL_EST_FASTUP) has been there to disable faster ramp up
in case of regression but I'm not aware of anybody having to disable
it during the last 3 year so we should just delete the sched_feat()
and make faster ramp up  permanent.

>
> >       /*
> >        * Update Task's estimated utilization
> >        *