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: Wed, 18 Nov 2026 13:58:48 +0300 [thread overview]
Message-ID: <av1uqTFI46wRb0ok@scheduler.schedules> (raw)
In-Reply-To: <CAKfTPtBZ=Dc_X48EQ0yXMym0JrS=pWvbviyVyFri0tv5VdR3Eg@mail.gmail.com>
On Wed, Nov 18, 2026 at 10:20:14AM +0100, Vincent Guittot wrote:
> On Mon, 16 Nov 2026 at 14:57, Kayra Cizmeci <kayracizmeci@gmail.com> wrote:
> >
> >
> > 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.
>
> yes, we assume that TA would have run 1/3 of its sleep time
But if sleep_time + working_time < slice for TA is true, there is no
guarantee that it will run 1/3 of its sleep_time.
>
> >
> >
> > 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?
>
> why is this wrong ?
>
> Assuming TB and TC have the same vruntime before placing TA, the
> average vruntime is avg == V(TB) == V(TC).
> place_entity will do V(TA) = avg - 2
> After placing TA, avg' = (V(TA) + V(TB) + V(TC)) / 3
> avg' = (3*avg - 2) / 3 = avg - 2/3
> TA's lag is : (avg - 2/3) - (avg - 2) = 4/3 which is what we assumed above
> TB's lag equals TC's lag : (avg - 2/3) - avg = -2/3
>
> >
> > If we didn't decayed lag: ((2 + 1) * 2) / 2 equals 3.
> > So we would do V - 3.
>
> Which would end up once placed to
> avg' = (3*avg - 3) / 3 = avg - 1
> TA's lag is : (avg - 1) - (avg - 3) = 2
> TB's lag equals TC's lag : (avg - 1) - avg = -1
>
> >
> > 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.
>
> Why ?
> You assume that the whole sleeping time would have been spent by TA
> running on the CPU but we don't really know. We can assume that a task
> with positive lag should run first, but this also depends on other
> tasks enqueued.
If TA didn't got preempted, and its sleeping_time + working_time is
smaller than its slice, the whole sleeping time would have been spent by
TA. Even if it did get preempted, there is no guarantee that it would
work 1/3 of its sleeping time.
> My first version assumed the whole sleep time would have been used to
> run which is optimistic. Peter suggested using the ratio of weight and
> cfs loads instead which accounts more fairly for the running time.
>
IMO, for a task like TA assuming it will work in its sleeping time
is better than assuming it will work as 1/3 of its sleeping time.
Or atleast less-bad, no? :-).
> >
> >
> > 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.
>
> Keeping eternal positive lag for a long sleeping task is unfair but on
> the other end, clearing all positive lag for a micro sleeping or
> because of waiting on a shared lock is also unfair
>
> >
> > 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.
>
> There is a difference between sleep time and lag. Even with a sleep
> time longer than the slice, the task can still have positive lag after
> sleeping (this is also true for runtime). All this depends on how many
> other tasks are running simultaneously and their weight
>
> >
> > What you think?
> >
> > Sreehc,
> >
> > Kayra
Ah, you didn't understand my joke, sad. :-(.
Sknaht,
Kayra
next prev parent reply other threads:[~2026-11-18 10:58 UTC|newest]
Thread overview: 64+ 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
2026-11-18 9:20 ` Vincent Guittot
2026-11-18 10:58 ` Kayra Cizmeci [this message]
2026-11-18 11:21 ` Vincent Guittot
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=av1uqTFI46wRb0ok@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®