mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
From: Kayra Cizmeci <kayracizmeci@gmail.com>
To: Vincent Guittot <vincent.guittot@linaro.org>
Cc: mingo@redhat.com, peterz@infradead.org, juri.lelli@redhat.com,
	 dietmar.eggemann@arm.com, rostedt@goodmis.org,
	bsegall@google.com, mgorman@suse.de,  vschneid@redhat.com,
	kprateek.nayak@amd.com, linux-kernel@vger.kernel.org,
	 lukasz.luba@arm.com, rafael@kernel.org,
	linux-pm@vger.kernel.org, tj@kernel.org,  void@manifault.com,
	arighi@nvidia.com, changwoo@igalia.com,
	 sched-ext@lists.linux.dev, qyousef@layalina.io,
	christian.loehle@arm.com,  pierre.gondois@arm.com,
	sshegde@linux.ibm.com, tim.c.chen@linux.intel.com
Subject: Re: [PATCH 01/20 v3] sched/eevdf: Decay positive lag of sleeping entities
Date: Mon, 16 Nov 2026 16:57:31 +0300	[thread overview]
Message-ID: <avr4MsRsjGfGHKKk@scheduler.schedules> (raw)
In-Reply-To: <20261106151947.3991524-2-vincent.guittot@linaro.org>


Hi Vincent!

On Fri, Nov 06, 2026 at 04:19:28PM +0100, Vincent Guittot wrote:
> Similarly to delayed dequeue, which enables an entity to decay its negative
> lag while sleeping, a task should not keep a positive lag forever.
> 
> The sleep duration and the weight are used to decay the positive lag at
> wakeup.
> 
> Apply the decay when enqueueing on prev rq for which we hold the lock to
> get rq_clock_task().
> 
> Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> ---
>  kernel/sched/fair.c | 124 ++++++++++++++++++++++++++++++++------------
>  1 file changed, 90 insertions(+), 34 deletions(-)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 0feec172fd37..5cd171f830d8 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -897,6 +897,91 @@ bool update_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se)
>  	return avruntime - vlag != se->vruntime;
>  }
>  
> +/*
> + * Signed add and clamp on underflow.
> + *
> + * Explicitly do a load-store to ensure the intermediate value never hits
> + * memory. This allows lockless observations without ever seeing the negative
> + * values.
> + */
> +#define add_positive(_ptr, _val) do {                           \
> +	typeof(_ptr) ptr = (_ptr);                              \
> +	__signed_scalar_typeof(*ptr) val = (_val);              \
> +	typeof(*ptr) res, var = READ_ONCE(*ptr);                \
> +								\
> +	res = var + val;                                        \
> +								\
> +	if (val < 0 && res > var)                               \
> +		res = 0;                                        \
> +								\
> +	WRITE_ONCE(*ptr, res);                                  \
> +} while (0)
> +
> +/*
> + * Remove and clamp on negative, from a local variable.
> + *
> + * A variant of sub_positive(), which does not use explicit load-store
> + * and is thus optimized for local variable updates.
> + */
> +#define lsub_positive(_ptr, _val) do {				\
> +	typeof(_ptr) ptr = (_ptr);				\
> +	*ptr -= min_t(typeof(*ptr), *ptr, _val);		\
> +} while (0)
> +
> +static inline unsigned long cfs_rq_load_avg(struct cfs_rq *cfs_rq);
> +static unsigned long task_h_load(struct task_struct *p);
> +
> +static __always_inline
> +void decay_entity_lag(struct cfs_rq *cfs_rq, struct task_struct *p, int flags)
> +{
> +	struct sched_entity *se = &p->se;
> +	s64 delta_exec, vlag = se->vlag;
> +	unsigned long cfs_load;
> +	struct rq *rq;
> +
> +	WARN_ON_ONCE(se->on_rq);
> +
> +	/* Negative lag is managed by delayed dequeue path */
> +	if (vlag <= 0)
> +		return;
> +
> +	rq = rq_of(cfs_rq);
> +
> +	/* No fast access to prev rq task clock */
> +	if (flags & ENQUEUE_MIGRATED)
> +		return;
> +
> +	/* Compute sleep time */
> +	delta_exec = rq_clock_task(rq) - se->exec_start;
> +	if (unlikely(delta_exec <= 0))
> +		return;
> +
> +	/* For anything above ~4 seconds, save computation and clear the lag */
> +	if (unlikely(delta_exec >> 32)) {
> +		se->vlag = 0;
> +		return;
> +	}
> +
> +	/*
> +	 * Use cfs' load and p's weight to estimate what would have been the
> +	 * share for p. task's load contribution to cfs' load is replaced by
> +	 * its weight.
> +	 */
> +	cfs_load = cfs_rq_load_avg(cfs_rq);
> +	lsub_positive(&cfs_load, task_h_load(p));
> +	if (cfs_load) {
> +		unsigned long weight = scale_load_down(se->h_load.weight);
> +
> +		delta_exec *= weight;
> +		delta_exec = div64_long(delta_exec, cfs_load + weight);
> +	}
> +
> +	vlag -= calc_delta_fair(delta_exec, se);
> +
> +	/* vlag can't become neg while sleeping */
> +	se->vlag = max(0, vlag);
> +}

Look:

Let's say we have 3 tasks named TA, TB and TC. They all have the same
weight and the same slices. So TA gets picked, works for a while and then
sleeps for less than the rest of its slice.

So the part that I hate and love, math. For your diff, we do:

(sleep_time * weight) / (3 * weight)

3 * weight here is TA + TB + TC, it equals to 3 * weight since they all
have the same weight.

So if sleep_time equals 2, weight equals 1, and slice equals 3 this equals
2/3. If the lag is 2, we do 2 - 2/3 resulting with 4/3.


Later, place_entity() uses this formula to do V - ((Sum(weight) + weight) * lag) / Sum(weight)
So ((2 + 1) * 4/3) / 2 equals to 2. But this is wrong, no?

If we didn't decayed lag: ((2 + 1) * 2) / 2 equals 3.
So we would do V - 3.

Now our objective is to add the sleep_time of the task to -3.
Because if the task didn't slept, in that time it would be working
instead of sleeping.

So, we should do V - 1. But we do V - 2.


AFAICT, we can't already know for sure how much will a task run even
when the sleep_time is smaller than the slice. Because of preemption
:-(.

The cleanest, the simplest and maybe the worst or the best solution I can think of
is just setting lag to 0 on every wakeup with positive lag TBH.

Or maybe, try to calculate when sleep_time is smaller than the slice,
but just set the lag to 0 when sleep_time is bigger or equal to slice.

What you think?

Sreehc,

Kayra

  reply	other threads:[~2026-11-16 13:57 UTC|newest]

Thread overview: 61+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2026-11-06 15:19 [PATCH 00/18 v3] Improving latency of short slice tasks Vincent Guittot
2026-11-06 15:19 ` [PATCH 01/20 v3] sched/eevdf: Decay positive lag of sleeping entities Vincent Guittot
2026-11-16 13:57   ` Kayra Cizmeci [this message]
2026-11-06 15:19 ` [PATCH 02/20 v3] sched/eevdf: Reset lag at wakeup when prev CPU has been idle Vincent Guittot
2026-11-06 16:22   ` Kayra Cizmeci
2026-11-09 15:27     ` Vincent Guittot
2026-11-09 15:45       ` Peter Zijlstra
2026-11-09 16:27         ` Vincent Guittot
2026-11-11  9:03           ` Peter Zijlstra
2026-11-12  7:02             ` Vincent Guittot
2026-11-11 10:04   ` K Prateek Nayak
2026-11-12  7:33     ` Vincent Guittot
2026-11-06 15:19 ` [PATCH 03/20 v3] sched/eevdf: Reset lag at wakeup when migrating and prev " Vincent Guittot
2026-11-06 18:05   ` Kayra Cizmeci
2026-11-06 15:19 ` [PATCH 04/20 v3] sched/eevdf: Reset lag when waking up on idle cpu Vincent Guittot
2026-11-06 18:39   ` Kayra Cizmeci
2026-11-06 15:19 ` [PATCH 05/20 v3] sched/eevdf: Add per cpu cached min_slice Vincent Guittot
2026-11-07  6:53   ` Kayra Cizmeci
2026-11-09 15:27     ` Vincent Guittot
2026-11-06 15:19 ` [PATCH 06/20 v3] sched/eevdf: Add min slice check when selecting CPU Vincent Guittot
2026-11-07  8:57   ` Kayra Cizmeci
2026-11-09 13:55     ` Peter Zijlstra
2026-11-09 14:15       ` Kayra Cizmeci
2026-11-09 15:37         ` Vincent Guittot
2026-11-09 15:34     ` Vincent Guittot
2026-11-09 15:55     ` Vincent Guittot
2026-11-09 19:56       ` Kayra Cizmeci
2026-11-10 13:32         ` Vincent Guittot
2026-11-06 15:19 ` [PATCH 07/20 v3] sched/fair: Prepare select_task_rq_fair() to be called for new cases Vincent Guittot
2026-11-06 15:19 ` [PATCH 08/20 v3] sched/fair: Add push task mechanism for fair Vincent Guittot
2026-11-09 14:43   ` Peter Zijlstra
2026-11-09 16:07     ` Vincent Guittot
2026-11-11  8:59       ` Peter Zijlstra
2026-11-12  7:01         ` Vincent Guittot
2026-11-09 15:54   ` Peter Zijlstra
2026-11-09 16:14     ` Vincent Guittot
2026-11-11  9:01       ` Peter Zijlstra
2026-11-12  7:01         ` Vincent Guittot
2026-11-12  7:36           ` Vincent Guittot
2026-11-12  9:49           ` Peter Zijlstra
2026-11-12 11:29             ` Vincent Guittot
2026-11-12 12:19               ` Peter Zijlstra
2026-11-13  8:47   ` Li kunyu
2026-11-13  9:06     ` Vincent Guittot
2026-11-06 15:19 ` [PATCH 09/20 v3] sched/fair: Optimize " Vincent Guittot
2026-11-06 15:19 ` [PATCH 10/20 v3] sched/core: Add rq flag to tick parameters Vincent Guittot
2026-11-06 15:19 ` [PATCH 11/20 v3] sched/fair: Add force push task mechanism for fair Vincent Guittot
2026-11-06 15:19 ` [PATCH 12/20 v3] sched/fair: Support not wakeup case in select_idle_sibling Vincent Guittot
2026-11-13  5:31   ` kernel test robot
2026-11-06 15:19 ` [PATCH 13/20] sched/eevdf: Try to push short slice task on a better CPU Vincent Guittot
2026-11-13  9:25   ` Li kunyu
2026-11-13 10:49     ` Vincent Guittot
2026-11-13 11:20       ` Li kunyu
2026-11-06 15:19 ` [PATCH 14/20 v3] sched/eevdf: Push short slice task that are not picked Vincent Guittot
2026-11-06 15:19 ` [PATCH 15/20 v3] sched/fair: Enable push task for preempt short Vincent Guittot
2026-11-06 15:19 ` [PATCH 16/20 v3] energy model: Add a get previous state function Vincent Guittot
2026-11-10 19:55   ` Rafael J. Wysocki (Intel)
2026-11-06 15:19 ` [PATCH 17/20 v3] sched/fair: Rework feec() to use cost instead of spare capacity Vincent Guittot
2026-11-06 15:19 ` [PATCH 18/20 v3] energy model: Remove unused em_cpu_energy() Vincent Guittot
2026-11-06 15:19 ` [PATCH 19/20 v3] sched/fair: Take into account slice in EAS Vincent Guittot
2026-11-06 15:19 ` [PATCH 20/20 v3] sched/fair: Fix tasks stacking on same idle CPU Vincent Guittot

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=avr4MsRsjGfGHKKk@scheduler.schedules \
    --to=kayracizmeci@gmail.com \
    --cc=arighi@nvidia.com \
    --cc=bsegall@google.com \
    --cc=changwoo@igalia.com \
    --cc=christian.loehle@arm.com \
    --cc=dietmar.eggemann@arm.com \
    --cc=juri.lelli@redhat.com \
    --cc=kprateek.nayak@amd.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-pm@vger.kernel.org \
    --cc=lukasz.luba@arm.com \
    --cc=mgorman@suse.de \
    --cc=mingo@redhat.com \
    --cc=peterz@infradead.org \
    --cc=pierre.gondois@arm.com \
    --cc=qyousef@layalina.io \
    --cc=rafael@kernel.org \
    --cc=rostedt@goodmis.org \
    --cc=sched-ext@lists.linux.dev \
    --cc=sshegde@linux.ibm.com \
    --cc=tim.c.chen@linux.intel.com \
    --cc=tj@kernel.org \
    --cc=vincent.guittot@linaro.org \
    --cc=void@manifault.com \
    --cc=vschneid@redhat.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox

all inboxes | Powered by JetHome®