Re: [PATCH 01/20 v3] sched/eevdf: Decay positive lag of sleeping entities
From: Kayra Cizmeci
Date: Mon Nov 16 2026 - 08:57:45 EST
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.
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