Re: [PATCH 01/20 v3] sched/eevdf: Decay positive lag of sleeping entities
From: Vincent Guittot
Date: Wed Nov 18 2026 - 04:20:32 EST
On Mon, 16 Nov 2026 at 14:57, Kayra Cizmeci <kayracizmeci@xxxxxxxxx> 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@xxxxxxxxxx>
> > ---
> > 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
>
>
> 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.
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.
>
>
> 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