All of lore.kernel.org
 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

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

Thread overview: 74+ 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-06 15:43   ` sashiko-bot
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-06 15:40   ` sashiko-bot
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:39   ` sashiko-bot
2026-11-06 15:19 ` [PATCH 08/20 v3] sched/fair: Add push task mechanism for fair Vincent Guittot
2026-11-06 16:15   ` sashiko-bot
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 16:00   ` sashiko-bot
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 16:16   ` sashiko-bot
2026-11-06 15:19 ` [PATCH 12/20 v3] sched/fair: Support not wakeup case in select_idle_sibling Vincent Guittot
2026-11-06 15:51   ` sashiko-bot
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-06 16:12   ` sashiko-bot
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 16:14   ` sashiko-bot
2026-11-06 15:19 ` [PATCH 15/20 v3] sched/fair: Enable push task for preempt short Vincent Guittot
2026-11-06 16:27   ` sashiko-bot
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 16:30   ` sashiko-bot
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 16:26   ` sashiko-bot
2026-11-06 15:19 ` [PATCH 20/20 v3] sched/fair: Fix tasks stacking on same idle CPU Vincent Guittot
2026-11-06 16:53   ` sashiko-bot

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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.