[PATCH 0/8] Improving latency of short slice tasks

[PATCH 0/8] Improving latency of short slice tasks

[Vincent Guittot]

This is another round of scheduling latency improvements which fix
some remaining corner cases and start to fix somes cases when multi
short slice tasks are running simultaneously on the system.

I run my usual set of scheduling latency tests on dragonboard rb5
- cyclictest with a 3777us period and a 8ms slice alone
- cyclictest with a 3777us period and a 8ms slice. 2xNR_CPUS rt-app
  tasks that run (8177us) and sleep (17777us) with a 16ms slice.
- cyclictest with a 3777us period and a 8ms slice. Hackbench with
  1 group using thread and pipe and a 16ms slice.

NB: periods and run duration have been chosen to minimize alignment
with tick or other periodic activities.

Each test is 130 seconds long

scheduling latency (us) for cyclictest
                   tip/sched/core| this patchset
slice                 8ms        |  8ms         
99th Percentile               91 |    90 (+ 1 %)
99.9th Percentile            126 |   108 (+14 %)
Maximum                     2273 |  1018 (+55 %)

scheduling latency (us) for cyclictest and rt-app
                   tip/sched/core| this patchset
slice                 8ms / 16ms |  8ms  / 16 ms
99th Percentile               66 |    66 (  0 %)
99.9th Percentile           1104 |   832 (+25 %)
Maximum                     6165 |  3041 (+51 %)

scheduling latency (us) for cyclictest and hackbench
                   tip/sched/core| this patchset
slice                 8ms / 16ms |  8ms  / 16 ms
99th Percentile               75 |    75 (  0 %)
99.9th Percentile            730 |   637 (+13 %)
Maximum                    15996 |  8124 (+49 %)

Beside the results above I noticed significants performance improvements
for hackbench with pipe which were not expected.
"sched/eevdf: Decay positive lag of sleeping entities" is the patch that
provides most of the performance improvements

The test were run with the default 2.8ms slice to check for some
performance regressions

hackbench             tip/sched/core   this patchset
 1 group process pipe 0,863(+/-2.6%)   0,764(+/-2.6%) (+11%)
 4 group process pipe 0,721(+/-2.6%)   0,561(+/-2.1%) (+22%)
 8 group process pipe 0,661(+/-2.3%)   0,496(+/-1.9%) (+25%)
16 group process pipe 0,630(+/-1.4%)   0,498(+/-1.6%) (+21%)
 1 group thread  pipe 0,925(+/-2.4%)   0,813(+/-2.2%) (+12%)
 4 group thread  pipe 0,846(+/-2.8%)   0,614(+/-4.4%) (+27%)
 8 group thread  pipe 0,750(+/-6.3%)   0,524(+/-0.9%) (+30%)
16 group thread  pipe 0,640(+/-3.1%)   0,506(+/-0.9%) (+21%)

Those tests have been run with perf scheduler (Using schedutil and EAS
provides similar results)

Vincent Guittot (8):
  sched/eevdf: Ensure that vprot will never go above a min slice
  sched/eevdf: Align update_protect_slice to set_protect_slice
  sched/eevdf: Handle more short slice waking cases
  sched/eevdf: Decay positive lag of sleeping entities
  sched/eevdf: Reset lag when waking up on idle cpu
  sched/eevdf: Add per cpu cached min_slice
  sched/eevdf: Compare min slice during wake_affine
  sched/eevdf: Add min slice check when selecting CPU

 kernel/sched/fair.c | 174 ++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 159 insertions(+), 15 deletions(-)

-- 
2.53.0

[PATCH 1/8] sched/eevdf: Ensure that vprot will never go above a min slice

[Vincent Guittot]

ineligible_vruntime() can be after the duration of a min slice but we
want to make sure that current will not run more than a min slice.

Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
---
 kernel/sched/fair.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index a42360ca94c3..1c171cb7e4af 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -1127,10 +1127,9 @@ static inline void set_protect_slice(struct cfs_rq *cfs_rq, struct sched_entity
 
 	/* If there are shorter slices than se's one */
 	if (slice != se->slice) {
+		vprot = min_vruntime(vprot, se->vruntime + calc_delta_fair(slice, se));
 		if (sched_feat(PREEMPT_SHORT))
 			vprot = min_vruntime(vprot, ineligible_vruntime(cfs_rq));
-		else
-			vprot = min_vruntime(vprot, se->vruntime + calc_delta_fair(slice, se));
 	}
 
 	se->vprot = vprot;
-- 
2.53.0

[PATCH 2/8] sched/eevdf: Align update_protect_slice to set_protect_slice

[Vincent Guittot]

Apply the same logic as for set_protect_slice when updating it.

Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
---
 kernel/sched/fair.c | 19 +++++++++++--------
 1 file changed, 11 insertions(+), 8 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 1c171cb7e4af..92382db1d297 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -820,12 +820,6 @@ static u64 ineligible_vruntime(struct cfs_rq *cfs_rq)
 	if (curr && !curr->on_rq)
 		curr = NULL;
 
-	/*
-	 * This is called from set_next_task_fair(.first=true) /
-	 * set_protect_slice() so curr had better be set and on_rq.
-	 */
-	WARN_ON_ONCE(!curr);
-
 	if (weight) {
 		s64 runtime = cfs_rq->sum_w_vruntime;
 
@@ -1137,10 +1131,19 @@ static inline void set_protect_slice(struct cfs_rq *cfs_rq, struct sched_entity
 
 static inline void update_protect_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
-	u64 slice = cfs_rq_min_slice(cfs_rq);
 	u64 vruntime = min_vruntime(se->vruntime, avg_vruntime(cfs_rq));
+	u64 slice = normalized_sysctl_sched_base_slice;
+	u64 vprot;
+
+	if (sched_feat(RUN_TO_PARITY))
+		slice = cfs_rq_min_slice(cfs_rq);
+
+	vprot = min_vruntime(se->vprot, vruntime + calc_delta_fair(slice, se));
 
-	se->vprot = min_vruntime(se->vprot, vruntime + calc_delta_fair(slice, se));
+	if (sched_feat(PREEMPT_SHORT) && slice != se->slice)
+		vprot = min_vruntime(vprot, ineligible_vruntime(cfs_rq));
+
+	se->vprot = vprot;
 }
 
 static inline bool protect_slice(struct sched_entity *se)
-- 
2.53.0

[PATCH 3/8] sched/eevdf: Handle more short slice waking cases

[Vincent Guittot]

Handle better the cases with several short slice tasks waking up
simultaneously.

Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
---
 kernel/sched/fair.c | 10 ++++++++--
 1 file changed, 8 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 92382db1d297..e6eb9a4c03be 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -9853,8 +9853,14 @@ static inline bool set_preempt_buddy(struct cfs_rq *cfs_rq, struct sched_entity
 
 static inline bool set_short_buddy(struct cfs_rq *cfs_rq, struct sched_entity *pse)
 {
-	if (cfs_rq->next && cfs_rq->next->slice < pse->slice)
-		return false;
+	if (cfs_rq->next) {
+		if (cfs_rq->next->slice < pse->slice)
+			return false;
+
+		if (cfs_rq->next->slice == pse->slice &&
+		    entity_before(cfs_rq->next, pse))
+			return false;
+	}
 
 	set_next_buddy(cfs_rq, pse);
 	return true;
-- 
2.53.0

[PATCH 4/8] sched/eevdf: Decay positive lag of sleeping entities

[Vincent Guittot]

Similarly to delayed dequeue that 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 of the entity is used to decay the
positive lag at wakeup.

Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
---
 kernel/sched/fair.c | 33 +++++++++++++++++++++++++++++++--
 1 file changed, 31 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index e6eb9a4c03be..4230954d10d0 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -896,6 +896,32 @@ bool update_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se)
 	return avruntime - vlag != se->vruntime;
 }
 
+static __always_inline
+void decay_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
+{
+	s64 vlag = se->vlag;
+	s64 delta_exec;
+
+	WARN_ON_ONCE(se->on_rq);
+
+	/* Negative lag implies delayed dequeue */
+	if (vlag <= 0)
+		return;
+
+	if (flags & ENQUEUE_MIGRATED)
+		return;
+
+	/* Compute the sleep time */
+	delta_exec = rq_clock_task(rq_of(cfs_rq)) - se->exec_start;
+	if (unlikely(delta_exec <= 0))
+		return;
+
+	vlag -= calc_delta_fair(delta_exec, se);
+
+	/* vlag can't become negative while sleeping */
+	se->vlag = max(0, vlag);
+}
+
 /*
  * Entity is eligible once it received less service than it ought to have,
  * eg. lag >= 0.
@@ -7986,7 +8012,7 @@ static void
 enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
 {
 	int rq_h_nr_queued = rq->cfs.h_nr_queued;
-	int task_new = !(flags & ENQUEUE_WAKEUP);
+	int task_wake = flags & ENQUEUE_WAKEUP;
 	struct sched_entity *se = &p->se;
 	struct cfs_rq *cfs_rq = &rq->cfs;
 	unsigned long weight;
@@ -8019,6 +8045,9 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
 	if (p->in_iowait)
 		cpufreq_update_util(rq, SCHED_CPUFREQ_IOWAIT);
 
+	if (task_wake)
+		decay_entity_lag(cfs_rq, se, flags);
+
 	/*
 	 * XXX comment on the curr thing
 	 */
@@ -8057,7 +8086,7 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
 	 * into account, but that is not straightforward to implement,
 	 * and the following generally works well enough in practice.
 	 */
-	if (!task_new)
+	if (task_wake)
 		check_update_overutilized_status(rq);
 
 	assert_list_leaf_cfs_rq(rq);
-- 
2.53.0

[PATCH 5/8] sched/eevdf: Reset lag when waking up on idle cpu

[Vincent Guittot]

When several tasks wake up simultaneously on an idle CPU, their final vlag
will depend of the ordering as the first one will lose its lag but not
the next ones.
Reset the lag when the enqueue happens while no fair task has already been
picked et set as the running task.

As a typical example:
CPU0 is idle
TA with vlag 0ms and TB with vlag 5ms wake up on CPU0 simultaneously.
Depending which grab the lock 1st the behavior will be different:
If TA is enqueued 1st, TB will be enqueued with a positive lag and will
be picked 1st.
But if TB is enqueued 1st, it will loose its positive vlag and both TA and
TB will have 0 vlag when fair will pick a task.

Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
---
 kernel/sched/fair.c | 27 +++++++++++++++++----------
 1 file changed, 17 insertions(+), 10 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 4230954d10d0..739a3af60520 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -900,7 +900,7 @@ static __always_inline
 void decay_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 {
 	s64 vlag = se->vlag;
-	s64 delta_exec;
+	struct rq *rq;
 
 	WARN_ON_ONCE(se->on_rq);
 
@@ -908,18 +908,25 @@ void decay_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 	if (vlag <= 0)
 		return;
 
-	if (flags & ENQUEUE_MIGRATED)
-		return;
+	rq = rq_of(cfs_rq);
 
-	/* Compute the sleep time */
-	delta_exec = rq_clock_task(rq_of(cfs_rq)) - se->exec_start;
-	if (unlikely(delta_exec <= 0))
-		return;
+	if (rq->curr == rq->idle) {
+		/* You can't claim any lag when waking on idle CPU */
+		vlag = 0;
+	} else if (!(flags & ENQUEUE_MIGRATED)) {
+		u64 now = rq_clock_task(rq);
+		s64 delta_exec;
 
-	vlag -= calc_delta_fair(delta_exec, se);
+		/* Compute the sleep time */
+		delta_exec = now - se->exec_start;
+		if (unlikely(delta_exec <= 0))
+			return;
 
-	/* vlag can't become negative while sleeping */
-	se->vlag = max(0, vlag);
+		vlag -= calc_delta_fair(delta_exec, se);
+
+		/* vlag can't become neg while sleeping */
+		se->vlag = max(0, vlag);
+	}
 }
 
 /*
-- 
2.53.0

[PATCH 6/8] sched/eevdf: Add per cpu cached min_slice

[Vincent Guittot]

In order to use min_slice during cpu selection, update a cached value when
needed after en/dequeing a new task. This cached value includes current
task.

Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
---
 kernel/sched/fair.c | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 739a3af60520..a01a88dde811 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -1089,6 +1089,21 @@ static inline bool min_vruntime_update(struct sched_entity *se, bool exit)
 RB_DECLARE_CALLBACKS(static, min_vruntime_cb, struct sched_entity,
 		     run_node, min_vruntime, min_vruntime_update);
 
+static DEFINE_PER_CPU(u64, rq_min_slice) = INT_MAX;
+
+static u64 get_rq_min_slice(struct rq *rq)
+{
+	return READ_ONCE(per_cpu(rq_min_slice, cpu_of(rq)));
+}
+
+static void __update_rq_min_slice(struct rq *rq)
+{
+	u64 min = cfs_rq_min_slice(&rq->cfs);
+
+	if (min != get_rq_min_slice(rq))
+		WRITE_ONCE(per_cpu(rq_min_slice, cpu_of(rq)), min);
+}
+
 /*
  * Enqueue an entity into the rb-tree:
  */
@@ -8073,6 +8088,8 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
 		__enqueue_entity(cfs_rq, se);
 	}
 
+	__update_rq_min_slice(rq);
+
 	if (!rq_h_nr_queued && rq->cfs.h_nr_queued)
 		dl_server_start(&rq->fair_server);
 
@@ -8195,6 +8212,8 @@ static bool __dequeue_task(struct rq *rq, struct task_struct *p, int flags)
 	if (se != cfs_rq->curr)
 		__dequeue_entity(cfs_rq, se);
 
+	__update_rq_min_slice(rq);
+
 	sub_nr_running(rq, 1);
 
 	/* balance early to pull high priority tasks */
-- 
2.53.0

[PATCH 7/8] sched/eevdf: Compare min slice during wake_affine

[Vincent Guittot]

Add a new level in wake affine where we check on which CPU the task
would most probably run 1st between this and prev CPUs.

Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
---
 kernel/sched/fair.c | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index a01a88dde811..452da94289fe 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -8402,6 +8402,9 @@ static int wake_wide(struct task_struct *p)
  * wake_affine_idle() - only considers 'now', it check if the waking CPU is
  *			cache-affine and is (or	will be) idle.
  *
+ * wake_affine_slice() - only considers 'now', it check if the waking CPU can
+ *			 be preempted because using longer slice.
+ *
  * wake_affine_weight() - considers the weight to reflect the average
  *			  scheduling latency of the CPUs. This seems to work
  *			  for the overloaded case.
@@ -8437,6 +8440,20 @@ wake_affine_idle(int this_cpu, int prev_cpu, int sync)
 	return nr_cpumask_bits;
 }
 
+static int
+wake_affine_slice(struct task_struct *p, int this_cpu, int prev_cpu)
+{
+	struct sched_entity *se = &p->se;
+
+	if (se->slice < get_rq_min_slice(cpu_rq(prev_cpu)))
+		return prev_cpu;
+
+	if (se->slice < get_rq_min_slice(cpu_rq(this_cpu)))
+		return this_cpu;
+
+	return nr_cpumask_bits;
+}
+
 static int
 wake_affine_weight(struct sched_domain *sd, struct task_struct *p,
 		   int this_cpu, int prev_cpu, int sync)
@@ -8488,6 +8505,9 @@ static int wake_affine(struct sched_domain *sd, struct task_struct *p,
 	if (sched_feat(WA_IDLE))
 		target = wake_affine_idle(this_cpu, prev_cpu, sync);
 
+	if (sched_feat(PREEMPT_SHORT) && target == nr_cpumask_bits)
+		target = wake_affine_slice(p, this_cpu, prev_cpu);
+
 	if (sched_feat(WA_WEIGHT) && target == nr_cpumask_bits)
 		target = wake_affine_weight(sd, p, this_cpu, prev_cpu, sync);
 
-- 
2.53.0

[PATCH 8/8] sched/eevdf: Add min slice check when selecting CPU

[Vincent Guittot]

Add a new level for selecting CPU when select_task_rq_fair() fails to find
an idle CPU. This last level will compare the slice to select a CPU where
the task could run 1st.
This helps a waking task to select a CPU where a longer slice runs
instead of one where a task with the same or shorter slice already runs.

Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
---
 kernel/sched/fair.c | 63 ++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 62 insertions(+), 1 deletion(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 452da94289fe..5c9add3e853c 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -9023,6 +9023,59 @@ static inline bool asym_fits_cpu(unsigned long util,
 	return true;
 }
 
+static int select_slice_cpu(struct task_struct *p, struct sched_domain *sd, int target)
+{
+	unsigned long task_util, util_min, util_max;
+	int cpu, nr = INT_MAX;
+	u64 slice = p->se.slice;
+	struct cpumask *cpus;
+
+	if (sched_feat(SIS_UTIL) && sd->shared) {
+		/*
+		 * Same nr_idle_scan hint as select_idle_cpu(), nr only limits
+		 * the scan when not preferring an idle core.
+		 */
+		nr = READ_ONCE(sd->shared->nr_idle_scan) + 1;
+		/* overloaded domain is unlikely to have idle cpu/core */
+		if (nr == 1)
+			return -1;
+	}
+
+	cpus = this_cpu_cpumask_var_ptr(select_rq_mask);
+	cpumask_and(cpus, sched_domain_span(sd), p->cpus_ptr);
+
+	if (sched_asym_cpucap_active()) {
+		task_util = task_util_est(p);
+		util_min = uclamp_eff_value(p, UCLAMP_MIN);
+		util_max = uclamp_eff_value(p, UCLAMP_MAX);
+	}
+
+	/* Those CPUs have been tested not being idle and fiting */
+	for_each_cpu_wrap(cpu, cpus, target) {
+		/*
+		 * Stop when the nr_idle_scan is exhausted (mirrors
+		 * select_idle_cpu() logic).
+		 */
+		if (--nr <= 0)
+			return -1;
+
+		if (slice >= get_rq_min_slice(cpu_rq(cpu)))
+			continue;
+
+		if (sched_asym_cpucap_active()) {
+			int fits = util_fits_cpu(task_util, util_min, util_max, cpu);
+
+			/* Perfect fit: capacity satisfies util + uclamp */
+			if (fits > 0)
+				return cpu;
+		} else {
+			return cpu;
+		}
+	}
+
+	return -1;
+}
+
 /*
  * Try and locate an idle core/thread in the LLC cache domain.
  */
@@ -9117,7 +9170,10 @@ static int select_idle_sibling(struct task_struct *p, int prev, int target)
 		 */
 		if (sd) {
 			i = select_idle_capacity(p, sd, target);
-			return ((unsigned)i < nr_cpumask_bits) ? i : target;
+			if ((unsigned int)i < nr_cpumask_bits)
+				return i;
+
+			goto select_slice;
 		}
 	}
 
@@ -9150,6 +9206,11 @@ static int select_idle_sibling(struct task_struct *p, int prev, int target)
 	if ((unsigned int)recent_used_cpu < nr_cpumask_bits)
 		return recent_used_cpu;
 
+select_slice:
+	i = select_slice_cpu(p, sd, target);
+	if ((unsigned int)i < nr_cpumask_bits)
+		return i;
+
 	return target;
 }
 
-- 
2.53.0

Re: [PATCH 5/8] sched/eevdf: Reset lag when waking up on idle cpu

[Kayra Cizmeci]

Hi Vincent,

> @@ -908,18 +908,25 @@ void decay_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
>  	if (vlag <= 0)
>  		return;
>  
> -	if (flags & ENQUEUE_MIGRATED)
> -		return;
> +	rq = rq_of(cfs_rq);
>  
> -	/* Compute the sleep time */
> -	delta_exec = rq_clock_task(rq_of(cfs_rq)) - se->exec_start;
> -	if (unlikely(delta_exec <= 0))
> -		return;
> +	if (rq->curr == rq->idle) {
> +		/* You can't claim any lag when waking on idle CPU */
> +		vlag = 0;
> +	} else if (!(flags & ENQUEUE_MIGRATED)) {
> +		u64 now = rq_clock_task(rq);
> +		s64 delta_exec;
>  
> -	vlag -= calc_delta_fair(delta_exec, se);
> +		/* Compute the sleep time */
> +		delta_exec = now - se->exec_start;
> +		if (unlikely(delta_exec <= 0))
> +			return;
>  
> -	/* vlag can't become negative while sleeping */
> -	se->vlag = max(0, vlag);
> +		vlag -= calc_delta_fair(delta_exec, se);
> +
> +		/* vlag can't become neg while sleeping */
> +		se->vlag = max(0, vlag);
> +	}
>  }

When if (rq->curr == rq->idle) runs the else if does not. So on that branch
we just set local vlag to 0. I think you wanted to set se->vlag to 0?


Thanks,
Kayra :>

Re: [PATCH 5/8] sched/eevdf: Reset lag when waking up on idle cpu

[Vincent Guittot]

On Mon, 21 Sept 2026 at 18:06, Kayra Cizmeci <kayracizmeci@gmail.com> wrote:
>
> Hi Vincent,
>
> > @@ -908,18 +908,25 @@ void decay_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
> >       if (vlag <= 0)
> >               return;
> >
> > -     if (flags & ENQUEUE_MIGRATED)
> > -             return;
> > +     rq = rq_of(cfs_rq);
> >
> > -     /* Compute the sleep time */
> > -     delta_exec = rq_clock_task(rq_of(cfs_rq)) - se->exec_start;
> > -     if (unlikely(delta_exec <= 0))
> > -             return;
> > +     if (rq->curr == rq->idle) {
> > +             /* You can't claim any lag when waking on idle CPU */
> > +             vlag = 0;
> > +     } else if (!(flags & ENQUEUE_MIGRATED)) {
> > +             u64 now = rq_clock_task(rq);
> > +             s64 delta_exec;
> >
> > -     vlag -= calc_delta_fair(delta_exec, se);
> > +             /* Compute the sleep time */
> > +             delta_exec = now - se->exec_start;
> > +             if (unlikely(delta_exec <= 0))
> > +                     return;
> >
> > -     /* vlag can't become negative while sleeping */
> > -     se->vlag = max(0, vlag);
> > +             vlag -= calc_delta_fair(delta_exec, se);
> > +
> > +             /* vlag can't become neg while sleeping */
> > +             se->vlag = max(0, vlag);
> > +     }
> >  }
>
> When if (rq->curr == rq->idle) runs the else if does not. So on that branch
> we just set local vlag to 0. I think you wanted to set se->vlag to 0?

Argh, I messed up when cleaning the patch

yes it should be se->vlag = 0 for idle case

I re-ran tests, and the latency with hackbench decreased a bit

scheduling latency (us) for cyclictest and hackbench
                   tip/sched/core| this patchset
slice                 8ms / 16ms |  8ms  / 16 ms
99th Percentile               75 |    70 (  7 %)
99.9th Percentile            730 |   532 (+27 %)
Maximum                    15996 |  5290 (+67 %)

Thanks

>
>
> Thanks,
> Kayra :>

Re: [PATCH 4/8] sched/eevdf: Decay positive lag of sleeping entities

[Peter Zijlstra]

On Mon, Sep 21, 2026 at 05:22:34PM +0200, Vincent Guittot wrote:
> Similarly to delayed dequeue that 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 of the entity is used to decay the
> positive lag at wakeup.
> 
> Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> ---
>  kernel/sched/fair.c | 33 +++++++++++++++++++++++++++++++--
>  1 file changed, 31 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index e6eb9a4c03be..4230954d10d0 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -896,6 +896,32 @@ bool update_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se)
>  	return avruntime - vlag != se->vruntime;
>  }
>  
> +static __always_inline
> +void decay_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
> +{
> +	s64 vlag = se->vlag;
> +	s64 delta_exec;
> +
> +	WARN_ON_ONCE(se->on_rq);
> +
> +	/* Negative lag implies delayed dequeue */
> +	if (vlag <= 0)
> +		return;
> +
> +	if (flags & ENQUEUE_MIGRATED)
> +		return;

Is not this a rather prevalent case?

> +
> +	/* Compute the sleep time */
> +	delta_exec = rq_clock_task(rq_of(cfs_rq)) - se->exec_start;
> +	if (unlikely(delta_exec <= 0))
> +		return;

Urgh, are we going to try and bring back all that sleep time stuff
again? ;-)

> +
> +	vlag -= calc_delta_fair(delta_exec, se);

Should this not be 'W+w' at the very least?, ideally it would be the
complete sum of all decaying weight rather than just 'w', but that might
be a tad tricky. 

> +
> +	/* vlag can't become negative while sleeping */
> +	se->vlag = max(0, vlag);
> +}

Anyway, the basic observation is that were this thing runnable, it would
have only a w/W share of runtime, not a w/w share.

Using the full fraction of sleep time like this will make the decay too
fast.

And dealing with that MIGRATED case is somewhat important; in which case
I suppose we can try and approximate by doing something like '(W1+W2)/2
+ w'.

Re: [PATCH 5/8] sched/eevdf: Reset lag when waking up on idle cpu

[Peter Zijlstra]

On Mon, Sep 21, 2026 at 05:22:35PM +0200, Vincent Guittot wrote:
> When several tasks wake up simultaneously on an idle CPU, their final vlag
> will depend of the ordering as the first one will lose its lag but not
> the next ones.
> Reset the lag when the enqueue happens while no fair task has already been
> picked et set as the running task.
> 
> As a typical example:
> CPU0 is idle
> TA with vlag 0ms and TB with vlag 5ms wake up on CPU0 simultaneously.
> Depending which grab the lock 1st the behavior will be different:
> If TA is enqueued 1st, TB will be enqueued with a positive lag and will
> be picked 1st.
> But if TB is enqueued 1st, it will loose its positive vlag and both TA and
> TB will have 0 vlag when fair will pick a task.
> 
> Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> ---
>  kernel/sched/fair.c | 27 +++++++++++++++++----------
>  1 file changed, 17 insertions(+), 10 deletions(-)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 4230954d10d0..739a3af60520 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -900,7 +900,7 @@ static __always_inline
>  void decay_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
>  {
>  	s64 vlag = se->vlag;
> -	s64 delta_exec;
> +	struct rq *rq;
>  
>  	WARN_ON_ONCE(se->on_rq);
>  
> @@ -908,18 +908,25 @@ void decay_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
>  	if (vlag <= 0)
>  		return;
>  
> -	if (flags & ENQUEUE_MIGRATED)
> -		return;
> +	rq = rq_of(cfs_rq);
>  
> -	/* Compute the sleep time */
> -	delta_exec = rq_clock_task(rq_of(cfs_rq)) - se->exec_start;
> -	if (unlikely(delta_exec <= 0))
> -		return;
> +	if (rq->curr == rq->idle) {
> +		/* You can't claim any lag when waking on idle CPU */
> +		vlag = 0;

Right. As I mentioned during OSPM, one of the crazy ideas I had was to
do something like the below. All of the lag stuff only makes sense while
there is contention.

Now, I've not actually tried this -- and at the very least the migation
case is broken. But it should very much capture the rq->curr == rq->idle
case and then some.


diff --git a/include/linux/sched.h b/include/linux/sched.h
index dac15ec36d1e..70fe8fadafac 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -592,6 +592,7 @@ struct sched_entity {
 	u64				vruntime;
 	/* Approximated virtual lag: */
 	s64				vlag;
+	u32				vlag_seq;
 	/* 'Protected' deadline, to give out minimum quantums: */
 	u64				vprot;
 	u64				slice;
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 2ad46fb2eafe..3e3dde5f2117 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -898,6 +898,7 @@ bool update_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se)
 			vlag = min(vlag, 0);
 	}
 	se->vlag = vlag;
+	se->vlag_seq = cfs_rq->idle_seq;
 
 	return avruntime - vlag != se->vruntime;
 }
@@ -6397,6 +6398,9 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 	if (flags & ENQUEUE_QUEUED)
 		nr_queued -= 1;
 
+	if (se->vlag_seq != cfs_rq->idle_seq)
+		se->vlag = 0;
+
 	/*
 	 * Due to how V is constructed as the weighted average of entities,
 	 * adding tasks with positive lag, or removing tasks with negative lag
@@ -8374,6 +8378,9 @@ static bool __dequeue_task(struct rq *rq, struct task_struct *p, int flags)
 
 	dequeue_hierarchy(p, flags);
 
+	if (!cfs_rq->h_nr_queued)
+		cfs_rq->idle_seq++;
+
 	if (sched_feat(PLACE_REL_DEADLINE) && !task_sleep) {
 		se->deadline -= se->vruntime;
 		se->rel_deadline = 1;
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 6c3ad70e58b8..0f0edb77e235 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -689,6 +689,7 @@ struct cfs_rq {
 	u64			sum_weight;
 	u64			zero_vruntime;
 	unsigned int		sum_shift;
+	u32			idle_seq;
 
 #ifdef CONFIG_SCHED_CORE
 	unsigned int		forceidle_seq;

Re: [PATCH 6/8] sched/eevdf: Add per cpu cached min_slice

[Peter Zijlstra]

On Mon, Sep 21, 2026 at 05:22:36PM +0200, Vincent Guittot wrote:
> In order to use min_slice during cpu selection, update a cached value when
> needed after en/dequeing a new task. This cached value includes current
> task.
> 
> Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> ---
>  kernel/sched/fair.c | 19 +++++++++++++++++++
>  1 file changed, 19 insertions(+)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 739a3af60520..a01a88dde811 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -1089,6 +1089,21 @@ static inline bool min_vruntime_update(struct sched_entity *se, bool exit)
>  RB_DECLARE_CALLBACKS(static, min_vruntime_cb, struct sched_entity,
>  		     run_node, min_vruntime, min_vruntime_update);
>  
> +static DEFINE_PER_CPU(u64, rq_min_slice) = INT_MAX;

Would it not be better to place this in struct rq, near data that is
already accessed in select_idle_siblings()? This more or less guarantees
a cache miss.

> +static u64 get_rq_min_slice(struct rq *rq)
> +{
> +	return READ_ONCE(per_cpu(rq_min_slice, cpu_of(rq)));
> +}
> +
> +static void __update_rq_min_slice(struct rq *rq)
> +{
> +	u64 min = cfs_rq_min_slice(&rq->cfs);
> +
> +	if (min != get_rq_min_slice(rq))
> +		WRITE_ONCE(per_cpu(rq_min_slice, cpu_of(rq)), min);
> +}
> +
>  /*
>   * Enqueue an entity into the rb-tree:
>   */

Re: [PATCH 4/8] sched/eevdf: Decay positive lag of sleeping entities

[Peter Zijlstra]

On Tue, Sep 22, 2026 at 12:02:33PM +0200, Peter Zijlstra wrote:
> On Mon, Sep 21, 2026 at 05:22:34PM +0200, Vincent Guittot wrote:

> > +
> > +	vlag -= calc_delta_fair(delta_exec, se);
> 
> Should this not be 'W+w' at the very least?, ideally it would be the
> complete sum of all decaying weight rather than just 'w', but that might
> be a tad tricky. 

One crazy way would be to add a second tree, then on dequeu, set
sched_delayed (to 2 or whatnot) and move it into the second tree (rather
than keep it in the normal tree).

Then have update_curr() or thereabout advance this decay tree's zero-lag
point (rather than moving each individual vruntime entity) at W+Wd rate
and check if the leftmost entities have 'aged' out; if so, reset their
vlag and properly dequeue them.

If they get woken in the interim, compute their new lag based on their
relative position to the zero lag of the decay tree.

Definitely non-trivial, and I'm not at all sure its worth it. But it
should sorta do the right thing.

Juri, did not the BFQ folks also have something like that at some point?

Re: [PATCH 8/8] sched/eevdf: Add min slice check when selecting CPU

[Peter Zijlstra]

On Mon, Sep 21, 2026 at 05:22:38PM +0200, Vincent Guittot wrote:
> Add a new level for selecting CPU when select_task_rq_fair() fails to find
> an idle CPU. This last level will compare the slice to select a CPU where
> the task could run 1st.
> This helps a waking task to select a CPU where a longer slice runs
> instead of one where a task with the same or shorter slice already runs.
> 
> Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> ---
>  kernel/sched/fair.c | 63 ++++++++++++++++++++++++++++++++++++++++++++-
>  1 file changed, 62 insertions(+), 1 deletion(-)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 452da94289fe..5c9add3e853c 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -9023,6 +9023,59 @@ static inline bool asym_fits_cpu(unsigned long util,
>  	return true;
>  }
>  
> +static int select_slice_cpu(struct task_struct *p, struct sched_domain *sd, int target)
> +{
> +	unsigned long task_util, util_min, util_max;
> +	int cpu, nr = INT_MAX;
> +	u64 slice = p->se.slice;
> +	struct cpumask *cpus;
> +
> +	if (sched_feat(SIS_UTIL) && sd->shared) {
> +		/*
> +		 * Same nr_idle_scan hint as select_idle_cpu(), nr only limits
> +		 * the scan when not preferring an idle core.
> +		 */
> +		nr = READ_ONCE(sd->shared->nr_idle_scan) + 1;
> +		/* overloaded domain is unlikely to have idle cpu/core */
> +		if (nr == 1)
> +			return -1;
> +	}
> +
> +	cpus = this_cpu_cpumask_var_ptr(select_rq_mask);
> +	cpumask_and(cpus, sched_domain_span(sd), p->cpus_ptr);
> +
> +	if (sched_asym_cpucap_active()) {
> +		task_util = task_util_est(p);
> +		util_min = uclamp_eff_value(p, UCLAMP_MIN);
> +		util_max = uclamp_eff_value(p, UCLAMP_MAX);
> +	}

This all seems duplicated from select_idle_siblings(), and while I
appreciated the breaking into functions, I do worry about the duplicate
work done too.

> +	/* Those CPUs have been tested not being idle and fiting */
> +	for_each_cpu_wrap(cpu, cpus, target) {
> +		/*
> +		 * Stop when the nr_idle_scan is exhausted (mirrors
> +		 * select_idle_cpu() logic).
> +		 */
> +		if (--nr <= 0)
> +			return -1;
> +
> +		if (slice >= get_rq_min_slice(cpu_rq(cpu)))
> +			continue;
> +
> +		if (sched_asym_cpucap_active()) {
> +			int fits = util_fits_cpu(task_util, util_min, util_max, cpu);
> +
> +			/* Perfect fit: capacity satisfies util + uclamp */
> +			if (fits > 0)
> +				return cpu;
> +		} else {
> +			return cpu;
> +		}
> +	}

And it does seem like a waste to re-scan the CPUs we've already visited.
Can't we keep track of the minimal slice CPU that was not idle during
our initial scan?


diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 2ad46fb2eafe..d3ab945f50ba 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -9179,6 +9179,7 @@ static int select_idle_sibling(struct task_struct *p, int prev, int target)
 	struct sched_domain *sd;
 	unsigned long task_util, util_min, util_max;
 	int i, recent_used_cpu, prev_aff = -1;
+	int best = target;
 
 	/*
 	 * On asymmetric system, update task utilization because we will check
@@ -9263,8 +9264,10 @@ static int select_idle_sibling(struct task_struct *p, int prev, int target)
 		 * capacity path.
 		 */
 		if (sd) {
-			i = select_idle_capacity(p, sd, target);
-			return ((unsigned)i < nr_cpumask_bits) ? i : target;
+			i = select_idle_capacity(p, sd, target, &best)
+			if ((unsigned)i < nr_cpumask_bits)
+				return i;
+			return best;
 		}
 	}
 
@@ -9282,7 +9285,7 @@ static int select_idle_sibling(struct task_struct *p, int prev, int target)
 		}
 	}
 
-	i = select_idle_cpu(p, sd, has_idle_core, target);
+	i = select_idle_cpu(p, sd, has_idle_core, target, &best);
 	if ((unsigned)i < nr_cpumask_bits)
 		return i;
 
@@ -9297,7 +9300,7 @@ static int select_idle_sibling(struct task_struct *p, int prev, int target)
 	if ((unsigned int)recent_used_cpu < nr_cpumask_bits)
 		return recent_used_cpu;
 
-	return target;
+	return best;
 }
 
 /**

Re: [PATCH 8/8] sched/eevdf: Add min slice check when selecting CPU

[Vincent Guittot]

On Tue, 22 Sept 2026 at 12:46, Peter Zijlstra <peterz@infradead.org> wrote:
>
> On Mon, Sep 21, 2026 at 05:22:38PM +0200, Vincent Guittot wrote:
> > Add a new level for selecting CPU when select_task_rq_fair() fails to find
> > an idle CPU. This last level will compare the slice to select a CPU where
> > the task could run 1st.
> > This helps a waking task to select a CPU where a longer slice runs
> > instead of one where a task with the same or shorter slice already runs.
> >
> > Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> > ---
> >  kernel/sched/fair.c | 63 ++++++++++++++++++++++++++++++++++++++++++++-
> >  1 file changed, 62 insertions(+), 1 deletion(-)
> >
> > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > index 452da94289fe..5c9add3e853c 100644
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -9023,6 +9023,59 @@ static inline bool asym_fits_cpu(unsigned long util,
> >       return true;
> >  }
> >
> > +static int select_slice_cpu(struct task_struct *p, struct sched_domain *sd, int target)
> > +{
> > +     unsigned long task_util, util_min, util_max;
> > +     int cpu, nr = INT_MAX;
> > +     u64 slice = p->se.slice;
> > +     struct cpumask *cpus;
> > +
> > +     if (sched_feat(SIS_UTIL) && sd->shared) {
> > +             /*
> > +              * Same nr_idle_scan hint as select_idle_cpu(), nr only limits
> > +              * the scan when not preferring an idle core.
> > +              */
> > +             nr = READ_ONCE(sd->shared->nr_idle_scan) + 1;
> > +             /* overloaded domain is unlikely to have idle cpu/core */
> > +             if (nr == 1)
> > +                     return -1;
> > +     }
> > +
> > +     cpus = this_cpu_cpumask_var_ptr(select_rq_mask);
> > +     cpumask_and(cpus, sched_domain_span(sd), p->cpus_ptr);
> > +
> > +     if (sched_asym_cpucap_active()) {
> > +             task_util = task_util_est(p);
> > +             util_min = uclamp_eff_value(p, UCLAMP_MIN);
> > +             util_max = uclamp_eff_value(p, UCLAMP_MAX);
> > +     }
>
> This all seems duplicated from select_idle_siblings(), and while I

Yes it is

> appreciated the breaking into functions, I do worry about the duplicate
> work done too.

I agree that this can fold into the current loops instead of a new one
but I wanted to show the changes for this version instead of mixing
them into the current loops. I'd like to even merge
select_idle_capacity, select_idle_cpu and select_slice_cpu into one
loop because they are all the same loop in order ot not duplicate the
slice selection in select_idle_capacity and select_idle_cpu

>
> > +     /* Those CPUs have been tested not being idle and fiting */
> > +     for_each_cpu_wrap(cpu, cpus, target) {
> > +             /*
> > +              * Stop when the nr_idle_scan is exhausted (mirrors
> > +              * select_idle_cpu() logic).
> > +              */
> > +             if (--nr <= 0)
> > +                     return -1;
> > +
> > +             if (slice >= get_rq_min_slice(cpu_rq(cpu)))
> > +                     continue;
> > +
> > +             if (sched_asym_cpucap_active()) {
> > +                     int fits = util_fits_cpu(task_util, util_min, util_max, cpu);
> > +
> > +                     /* Perfect fit: capacity satisfies util + uclamp */
> > +                     if (fits > 0)
> > +                             return cpu;
> > +             } else {
> > +                     return cpu;
> > +             }
> > +     }
>
> And it does seem like a waste to re-scan the CPUs we've already visited.
> Can't we keep track of the minimal slice CPU that was not idle during
> our initial scan?
>
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 2ad46fb2eafe..d3ab945f50ba 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -9179,6 +9179,7 @@ static int select_idle_sibling(struct task_struct *p, int prev, int target)
>         struct sched_domain *sd;
>         unsigned long task_util, util_min, util_max;
>         int i, recent_used_cpu, prev_aff = -1;
> +       int best = target;
>
>         /*
>          * On asymmetric system, update task utilization because we will check
> @@ -9263,8 +9264,10 @@ static int select_idle_sibling(struct task_struct *p, int prev, int target)
>                  * capacity path.
>                  */
>                 if (sd) {
> -                       i = select_idle_capacity(p, sd, target);
> -                       return ((unsigned)i < nr_cpumask_bits) ? i : target;
> +                       i = select_idle_capacity(p, sd, target, &best)
> +                       if ((unsigned)i < nr_cpumask_bits)
> +                               return i;
> +                       return best;
>                 }
>         }
>
> @@ -9282,7 +9285,7 @@ static int select_idle_sibling(struct task_struct *p, int prev, int target)
>                 }
>         }
>
> -       i = select_idle_cpu(p, sd, has_idle_core, target);
> +       i = select_idle_cpu(p, sd, has_idle_core, target, &best);
>         if ((unsigned)i < nr_cpumask_bits)
>                 return i;
>
> @@ -9297,7 +9300,7 @@ static int select_idle_sibling(struct task_struct *p, int prev, int target)
>         if ((unsigned int)recent_used_cpu < nr_cpumask_bits)
>                 return recent_used_cpu;
>
> -       return target;
> +       return best;
>  }
>
>  /**

Re: [PATCH 4/8] sched/eevdf: Decay positive lag of sleeping entities

[Vincent Guittot]

On Tue, 22 Sept 2026 at 12:02, Peter Zijlstra <peterz@infradead.org> wrote:
>
> On Mon, Sep 21, 2026 at 05:22:34PM +0200, Vincent Guittot wrote:
> > Similarly to delayed dequeue that 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 of the entity is used to decay the
> > positive lag at wakeup.
> >
> > Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> > ---
> >  kernel/sched/fair.c | 33 +++++++++++++++++++++++++++++++--
> >  1 file changed, 31 insertions(+), 2 deletions(-)
> >
> > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > index e6eb9a4c03be..4230954d10d0 100644
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -896,6 +896,32 @@ bool update_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se)
> >       return avruntime - vlag != se->vruntime;
> >  }
> >
> > +static __always_inline
> > +void decay_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
> > +{
> > +     s64 vlag = se->vlag;
> > +     s64 delta_exec;
> > +
> > +     WARN_ON_ONCE(se->on_rq);
> > +
> > +     /* Negative lag implies delayed dequeue */
> > +     if (vlag <= 0)
> > +             return;
> > +
> > +     if (flags & ENQUEUE_MIGRATED)
> > +             return;
>
> Is not this a rather prevalent case?

Yes, but this means getting the clock from the prev rq with its lock
which is costly so I wanted to start simple

>
> > +
> > +     /* Compute the sleep time */
> > +     delta_exec = rq_clock_task(rq_of(cfs_rq)) - se->exec_start;
> > +     if (unlikely(delta_exec <= 0))
> > +             return;
>
> Urgh, are we going to try and bring back all that sleep time stuff
> again? ;-)
>
> > +
> > +     vlag -= calc_delta_fair(delta_exec, se);
>
> Should this not be 'W+w' at the very least?, ideally it would be the
> complete sum of all decaying weight rather than just 'w', but that might
> be a tad tricky.

I spent some time thinking about this. The right solution should be
the one you suggested in your next reply: keeping the sleeping tasks
"enqueued" in another tree and computing a zero decay vruntime.
However, I was afraid of the overhead of managing this new tree and
taking the lock of another rq to dequeue the task. Anything else in
between will be an approximation because W at enqueue doesn't reflect
what happened during the sleep period: The CPU could have been idle
the entire time, but several tasks wake up simultaneously so the 1st
enqueued will not see a W whereas the other one will.

>
> > +
> > +     /* vlag can't become negative while sleeping */
> > +     se->vlag = max(0, vlag);
> > +}
>
> Anyway, the basic observation is that were this thing runnable, it would
> have only a w/W share of runtime, not a w/w share.
>
> Using the full fraction of sleep time like this will make the decay too
> fast.
>
> And dealing with that MIGRATED case is somewhat important; in which case
> I suppose we can try and approximate by doing something like '(W1+W2)/2
> + w'.
>
>

Re: [PATCH 4/8] sched/eevdf: Decay positive lag of sleeping entities

[Peter Zijlstra]

On Tue, Sep 22, 2026 at 02:56:56PM +0200, Vincent Guittot wrote:
> On Tue, 22 Sept 2026 at 12:02, Peter Zijlstra <peterz@infradead.org> wrote:
> > On Mon, Sep 21, 2026 at 05:22:34PM +0200, Vincent Guittot wrote:

> > > +
> > > +     vlag -= calc_delta_fair(delta_exec, se);
> >
> > Should this not be 'W+w' at the very least?, ideally it would be the
> > complete sum of all decaying weight rather than just 'w', but that might
> > be a tad tricky.
> 
> I spent some time thinking about this. The right solution should be
> the one you suggested in your next reply: keeping the sleeping tasks
> "enqueued" in another tree and computing a zero decay vruntime.
> However, I was afraid of the overhead of managing this new tree and
> taking the lock of another rq to dequeue the task. 

Yeah :/

> Anything else in
> between will be an approximation because W at enqueue doesn't reflect
> what happened during the sleep period: The CPU could have been idle
> the entire time, 

Ah but if we let idle reset all the lags, by sequence number or anything
else, then that case doesn't matter.

> but several tasks wake up simultaneously so the 1st
> enqueued will not see a W whereas the other one will.

Right. So this approximation is under estimating, it is the absolute
lowest possible decay time, which seems somewhat unfortunate. OTOH I
agree that keeping the whole second tree and all that comes with that,
might be a tad much.

Still it would be good to find a more reasonable approach. Perhaps using
load_avg ? I think over-estimating it might be a little safer than
under-estimating in this case.

Re: [PATCH 6/8] sched/eevdf: Add per cpu cached min_slice

[Vincent Guittot]

On Tue, 22 Sept 2026 at 12:17, Peter Zijlstra <peterz@infradead.org> wrote:
>
> On Mon, Sep 21, 2026 at 05:22:36PM +0200, Vincent Guittot wrote:
> > In order to use min_slice during cpu selection, update a cached value when
> > needed after en/dequeing a new task. This cached value includes current
> > task.
> >
> > Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> > ---
> >  kernel/sched/fair.c | 19 +++++++++++++++++++
> >  1 file changed, 19 insertions(+)
> >
> > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > index 739a3af60520..a01a88dde811 100644
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -1089,6 +1089,21 @@ static inline bool min_vruntime_update(struct sched_entity *se, bool exit)
> >  RB_DECLARE_CALLBACKS(static, min_vruntime_cb, struct sched_entity,
> >                    run_node, min_vruntime, min_vruntime_update);
> >
> > +static DEFINE_PER_CPU(u64, rq_min_slice) = INT_MAX;
>
> Would it not be better to place this in struct rq, near data that is
> already accessed in select_idle_siblings()? This more or less guarantees
> a cache miss.

Yes, probably.


>
> > +static u64 get_rq_min_slice(struct rq *rq)
> > +{
> > +     return READ_ONCE(per_cpu(rq_min_slice, cpu_of(rq)));
> > +}
> > +
> > +static void __update_rq_min_slice(struct rq *rq)
> > +{
> > +     u64 min = cfs_rq_min_slice(&rq->cfs);
> > +
> > +     if (min != get_rq_min_slice(rq))
> > +             WRITE_ONCE(per_cpu(rq_min_slice, cpu_of(rq)), min);
> > +}
> > +
> >  /*
> >   * Enqueue an entity into the rb-tree:
> >   */

Re: [PATCH 5/8] sched/eevdf: Reset lag when waking up on idle cpu

[Vincent Guittot]

On Tue, 22 Sept 2026 at 12:19, Peter Zijlstra <peterz@infradead.org> wrote:
>
> On Mon, Sep 21, 2026 at 05:22:35PM +0200, Vincent Guittot wrote:
> > When several tasks wake up simultaneously on an idle CPU, their final vlag
> > will depend of the ordering as the first one will lose its lag but not
> > the next ones.
> > Reset the lag when the enqueue happens while no fair task has already been
> > picked et set as the running task.
> >
> > As a typical example:
> > CPU0 is idle
> > TA with vlag 0ms and TB with vlag 5ms wake up on CPU0 simultaneously.
> > Depending which grab the lock 1st the behavior will be different:
> > If TA is enqueued 1st, TB will be enqueued with a positive lag and will
> > be picked 1st.
> > But if TB is enqueued 1st, it will loose its positive vlag and both TA and
> > TB will have 0 vlag when fair will pick a task.
> >
> > Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> > ---
> >  kernel/sched/fair.c | 27 +++++++++++++++++----------
> >  1 file changed, 17 insertions(+), 10 deletions(-)
> >
> > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > index 4230954d10d0..739a3af60520 100644
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -900,7 +900,7 @@ static __always_inline
> >  void decay_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
> >  {
> >       s64 vlag = se->vlag;
> > -     s64 delta_exec;
> > +     struct rq *rq;
> >
> >       WARN_ON_ONCE(se->on_rq);
> >
> > @@ -908,18 +908,25 @@ void decay_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
> >       if (vlag <= 0)
> >               return;
> >
> > -     if (flags & ENQUEUE_MIGRATED)
> > -             return;
> > +     rq = rq_of(cfs_rq);
> >
> > -     /* Compute the sleep time */
> > -     delta_exec = rq_clock_task(rq_of(cfs_rq)) - se->exec_start;
> > -     if (unlikely(delta_exec <= 0))
> > -             return;
> > +     if (rq->curr == rq->idle) {
> > +             /* You can't claim any lag when waking on idle CPU */
> > +             vlag = 0;
>
> Right. As I mentioned during OSPM, one of the crazy ideas I had was to
> do something like the below. All of the lag stuff only makes sense while
> there is contention.
>
> Now, I've not actually tried this -- and at the very least the migation
> case is broken. But it should very much capture the rq->curr == rq->idle
> case and then some.

Yes, I remember the discussion. This one really care about severals
tasks wake up simultaneously on an idle CPU but what we do with their
lags depend on the enqueue order before trying to pick one

I'm going to try your suggestion below and see how I can get it
working with migration too

>
>
> diff --git a/include/linux/sched.h b/include/linux/sched.h
> index dac15ec36d1e..70fe8fadafac 100644
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -592,6 +592,7 @@ struct sched_entity {
>         u64                             vruntime;
>         /* Approximated virtual lag: */
>         s64                             vlag;
> +       u32                             vlag_seq;
>         /* 'Protected' deadline, to give out minimum quantums: */
>         u64                             vprot;
>         u64                             slice;
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 2ad46fb2eafe..3e3dde5f2117 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -898,6 +898,7 @@ bool update_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se)
>                         vlag = min(vlag, 0);
>         }
>         se->vlag = vlag;
> +       se->vlag_seq = cfs_rq->idle_seq;
>
>         return avruntime - vlag != se->vruntime;
>  }
> @@ -6397,6 +6398,9 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
>         if (flags & ENQUEUE_QUEUED)
>                 nr_queued -= 1;
>
> +       if (se->vlag_seq != cfs_rq->idle_seq)
> +               se->vlag = 0;
> +
>         /*
>          * Due to how V is constructed as the weighted average of entities,
>          * adding tasks with positive lag, or removing tasks with negative lag
> @@ -8374,6 +8378,9 @@ static bool __dequeue_task(struct rq *rq, struct task_struct *p, int flags)
>
>         dequeue_hierarchy(p, flags);
>
> +       if (!cfs_rq->h_nr_queued)
> +               cfs_rq->idle_seq++;
> +
>         if (sched_feat(PLACE_REL_DEADLINE) && !task_sleep) {
>                 se->deadline -= se->vruntime;
>                 se->rel_deadline = 1;
> diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
> index 6c3ad70e58b8..0f0edb77e235 100644
> --- a/kernel/sched/sched.h
> +++ b/kernel/sched/sched.h
> @@ -689,6 +689,7 @@ struct cfs_rq {
>         u64                     sum_weight;
>         u64                     zero_vruntime;
>         unsigned int            sum_shift;
> +       u32                     idle_seq;
>
>  #ifdef CONFIG_SCHED_CORE
>         unsigned int            forceidle_seq;

Re: [PATCH 4/8] sched/eevdf: Decay positive lag of sleeping entities

[Vincent Guittot]

On Tue, 22 Sept 2026 at 15:29, Peter Zijlstra <peterz@infradead.org> wrote:
>
> On Tue, Sep 22, 2026 at 02:56:56PM +0200, Vincent Guittot wrote:
> > On Tue, 22 Sept 2026 at 12:02, Peter Zijlstra <peterz@infradead.org> wrote:
> > > On Mon, Sep 21, 2026 at 05:22:34PM +0200, Vincent Guittot wrote:
>
> > > > +
> > > > +     vlag -= calc_delta_fair(delta_exec, se);
> > >
> > > Should this not be 'W+w' at the very least?, ideally it would be the
> > > complete sum of all decaying weight rather than just 'w', but that might
> > > be a tad tricky.
> >
> > I spent some time thinking about this. The right solution should be
> > the one you suggested in your next reply: keeping the sleeping tasks
> > "enqueued" in another tree and computing a zero decay vruntime.
> > However, I was afraid of the overhead of managing this new tree and
> > taking the lock of another rq to dequeue the task.
>
> Yeah :/
>
> > Anything else in
> > between will be an approximation because W at enqueue doesn't reflect
> > what happened during the sleep period: The CPU could have been idle
> > the entire time,
>
> Ah but if we let idle reset all the lags, by sequence number or anything
> else, then that case doesn't matter.
>
> > but several tasks wake up simultaneously so the 1st
> > enqueued will not see a W whereas the other one will.
>
> Right. So this approximation is under estimating, it is the absolute
> lowest possible decay time, which seems somewhat unfortunate. OTOH I
> agree that keeping the whole second tree and all that comes with that,
> might be a tad much.
>
> Still it would be good to find a more reasonable approach. Perhaps using
> load_avg ? I think over-estimating it might be a little safer than
> under-estimating in this case.

I'm going to study this further

Re: [PATCH 5/8] sched/eevdf: Reset lag when waking up on idle cpu

[Kayra Cizmeci]

Hello Peter,

> Right. As I mentioned during OSPM, one of the crazy ideas I had was to
> do something like the below. All of the lag stuff only makes sense while
> there is contention.

> Now, I've not actually tried this -- and at the very least the migation
> case is broken. But it should very much capture the rq->curr == rq->idle
> case and then some.


> diff --git a/include/linux/sched.h b/include/linux/sched.h
> index dac15ec36d1e..70fe8fadafac 100644
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -592,6 +592,7 @@ struct sched_entity {
>  	u64				vruntime;
>  	/* Approximated virtual lag: */
>  	s64				vlag;
> +	u32				vlag_seq;
>  	/* 'Protected' deadline, to give out minimum quantums: */
>  	u64				vprot;
>  	u64				slice;
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 2ad46fb2eafe..3e3dde5f2117 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -898,6 +898,7 @@ bool update_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se)
>  			vlag = min(vlag, 0);
>  	}
>  	se->vlag = vlag;
> +	se->vlag_seq = cfs_rq->idle_seq;
>  
>  	return avruntime - vlag != se->vruntime;
>  }
> @@ -6397,6 +6398,9 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
>  	if (flags & ENQUEUE_QUEUED)
>  		nr_queued -= 1;
>  
> +	if (se->vlag_seq != cfs_rq->idle_seq)
> +		se->vlag = 0;
> +
>  	/*
>  	 * Due to how V is constructed as the weighted average of entities,
>  	 * adding tasks with positive lag, or removing tasks with negative lag
> @@ -8374,6 +8378,9 @@ static bool __dequeue_task(struct rq *rq, struct task_struct *p, int flags)
>  
>  	dequeue_hierarchy(p, flags);
>  
> +	if (!cfs_rq->h_nr_queued)
> +		cfs_rq->idle_seq++;
> +
>  	if (sched_feat(PLACE_REL_DEADLINE) && !task_sleep) {
>  		se->deadline -= se->vruntime;
>  		se->rel_deadline = 1;
> diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
> index 6c3ad70e58b8..0f0edb77e235 100644
> --- a/kernel/sched/sched.h
> +++ b/kernel/sched/sched.h
> @@ -689,6 +689,7 @@ struct cfs_rq {
>  	u64			sum_weight;
>  	u64			zero_vruntime;
>  	unsigned int		sum_shift;
> +	u32			idle_seq;
>  
>  #ifdef CONFIG_SCHED_CORE
>  	unsigned int		forceidle_seq;

I think we could both of these approaches.
On migration, we'll check (rq->curr == rq->idle),
On normal yours.

Or, if possible on migration before se's rq changes,
we could do this idle_seq on there too.
Tho, not really tested or proven. And IDK 
if there's a place that is before se's rq changes.

Thanks,
Kayra :)