With the introduction of avg_vruntime, it is possible to approximate
lag (the entire purpose of introducing it in fact). Use this to do lag
based placement over sleep+wake.
Specifically, the FAIR_SLEEPERS thing places things too far to the
left and messes up the deadline aspect of EEVDF.
Signed-off-by: Peter Zijlstra (Intel) <[email protected]>
---
include/linux/sched.h | 1
kernel/sched/core.c | 1
kernel/sched/fair.c | 63 +++++++++++++++++++++++++++---------------------
kernel/sched/features.h | 8 ++++++
4 files changed, 46 insertions(+), 27 deletions(-)
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -555,6 +555,7 @@ struct sched_entity {
u64 sum_exec_runtime;
u64 vruntime;
u64 prev_sum_exec_runtime;
+ s64 lag;
u64 nr_migrations;
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -4436,6 +4436,7 @@ static void __sched_fork(unsigned long c
p->se.prev_sum_exec_runtime = 0;
p->se.nr_migrations = 0;
p->se.vruntime = 0;
+ p->se.lag = 0;
INIT_LIST_HEAD(&p->se.group_node);
set_latency_offset(p);
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -4749,39 +4749,45 @@ static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
u64 vruntime = avg_vruntime(cfs_rq);
- u64 sleep_time;
- /* sleeps up to a single latency don't count. */
- if (!initial) {
- unsigned long thresh;
-
- if (se_is_idle(se))
- thresh = sysctl_sched_min_granularity;
- else
- thresh = sysctl_sched_latency;
+ if (sched_feat(FAIR_SLEEPERS)) {
+ u64 sleep_time;
+
+ /* sleeps up to a single latency don't count. */
+ if (!initial) {
+ unsigned long thresh;
+
+ if (se_is_idle(se))
+ thresh = sysctl_sched_min_granularity;
+ else
+ thresh = sysctl_sched_latency;
+
+ /*
+ * Halve their sleep time's effect, to allow
+ * for a gentler effect of sleepers:
+ */
+ if (sched_feat(GENTLE_FAIR_SLEEPERS))
+ thresh >>= 1;
+
+ vruntime -= thresh;
+ }
/*
- * Halve their sleep time's effect, to allow
- * for a gentler effect of sleepers:
+ * Pull vruntime of the entity being placed to the base level of
+ * cfs_rq, to prevent boosting it if placed backwards. If the entity
+ * slept for a long time, don't even try to compare its vruntime with
+ * the base as it may be too far off and the comparison may get
+ * inversed due to s64 overflow.
*/
- if (sched_feat(GENTLE_FAIR_SLEEPERS))
- thresh >>= 1;
-
- vruntime -= thresh;
+ sleep_time = rq_clock_task(rq_of(cfs_rq)) - se->exec_start;
+ if ((s64)sleep_time < 60LL * NSEC_PER_SEC)
+ vruntime = max_vruntime(se->vruntime, vruntime);
}
- /*
- * Pull vruntime of the entity being placed to the base level of
- * cfs_rq, to prevent boosting it if placed backwards. If the entity
- * slept for a long time, don't even try to compare its vruntime with
- * the base as it may be too far off and the comparison may get
- * inversed due to s64 overflow.
- */
- sleep_time = rq_clock_task(rq_of(cfs_rq)) - se->exec_start;
- if ((s64)sleep_time > 60LL * NSEC_PER_SEC)
- se->vruntime = vruntime;
- else
- se->vruntime = max_vruntime(se->vruntime, vruntime);
+ if (sched_feat(PRESERVE_LAG))
+ vruntime -= se->lag;
+
+ se->vruntime = vruntime;
}
static void check_enqueue_throttle(struct cfs_rq *cfs_rq);
@@ -4949,6 +4955,9 @@ dequeue_entity(struct cfs_rq *cfs_rq, st
clear_buddies(cfs_rq, se);
+ if (sched_feat(PRESERVE_LAG) && (flags & DEQUEUE_SLEEP))
+ se->lag = avg_vruntime(cfs_rq) - se->vruntime;
+
if (se != cfs_rq->curr)
__dequeue_entity(cfs_rq, se);
se->on_rq = 0;
--- a/kernel/sched/features.h
+++ b/kernel/sched/features.h
@@ -1,12 +1,20 @@
/* SPDX-License-Identifier: GPL-2.0 */
+
/*
* Only give sleepers 50% of their service deficit. This allows
* them to run sooner, but does not allow tons of sleepers to
* rip the spread apart.
*/
+SCHED_FEAT(FAIR_SLEEPERS, false)
SCHED_FEAT(GENTLE_FAIR_SLEEPERS, true)
/*
+ * Using the avg_vruntime, do the right thing and preserve lag
+ * across sleep+wake cycles.
+ */
+SCHED_FEAT(PRESERVE_LAG, true)
+
+/*
* Prefer to schedule the task we woke last (assuming it failed
* wakeup-preemption), since its likely going to consume data we
* touched, increases cache locality.
On Mon, 2023-03-06 at 14:25 +0100, Peter Zijlstra wrote:
> With the introduction of avg_vruntime, it is possible to approximate
> lag (the entire purpose of introducing it in fact). Use this to do lag
> based placement over sleep+wake.
>
> Specifically, the FAIR_SLEEPERS thing places things too far to the
> left and messes up the deadline aspect of EEVDF.
>
> Signed-off-by: Peter Zijlstra (Intel) <[email protected]>
> ---
> include/linux/sched.h | 1
> kernel/sched/core.c | 1
> kernel/sched/fair.c | 63 +++++++++++++++++++++++++++---------------------
> kernel/sched/features.h | 8 ++++++
> 4 files changed, 46 insertions(+), 27 deletions(-)
>
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -555,6 +555,7 @@ struct sched_entity {
> u64 sum_exec_runtime;
> u64 vruntime;
> u64 prev_sum_exec_runtime;
> + s64 lag;
>
> u64 nr_migrations;
>
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -4436,6 +4436,7 @@ static void __sched_fork(unsigned long c
> p->se.prev_sum_exec_runtime = 0;
> p->se.nr_migrations = 0;
> p->se.vruntime = 0;
> + p->se.lag = 0;
> INIT_LIST_HEAD(&p->se.group_node);
>
> set_latency_offset(p);
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -4749,39 +4749,45 @@ static void
> place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
> {
> u64 vruntime = avg_vruntime(cfs_rq);
> - u64 sleep_time;
>
> - /* sleeps up to a single latency don't count. */
> - if (!initial) {
> - unsigned long thresh;
> -
> - if (se_is_idle(se))
> - thresh = sysctl_sched_min_granularity;
> - else
> - thresh = sysctl_sched_latency;
> + if (sched_feat(FAIR_SLEEPERS)) {
> + u64 sleep_time;
> +
> + /* sleeps up to a single latency don't count. */
> + if (!initial) {
> + unsigned long thresh;
> +
> + if (se_is_idle(se))
> + thresh = sysctl_sched_min_granularity;
> + else
> + thresh = sysctl_sched_latency;
> +
> + /*
> + * Halve their sleep time's effect, to allow
> + * for a gentler effect of sleepers:
> + */
> + if (sched_feat(GENTLE_FAIR_SLEEPERS))
> + thresh >>= 1;
> +
> + vruntime -= thresh;
> + }
>
> /*
> - * Halve their sleep time's effect, to allow
> - * for a gentler effect of sleepers:
> + * Pull vruntime of the entity being placed to the base level of
> + * cfs_rq, to prevent boosting it if placed backwards. If the entity
> + * slept for a long time, don't even try to compare its vruntime with
> + * the base as it may be too far off and the comparison may get
> + * inversed due to s64 overflow.
> */
> - if (sched_feat(GENTLE_FAIR_SLEEPERS))
> - thresh >>= 1;
> -
> - vruntime -= thresh;
> + sleep_time = rq_clock_task(rq_of(cfs_rq)) - se->exec_start;
> + if ((s64)sleep_time < 60LL * NSEC_PER_SEC)
> + vruntime = max_vruntime(se->vruntime, vruntime);
> }
>
> - /*
> - * Pull vruntime of the entity being placed to the base level of
> - * cfs_rq, to prevent boosting it if placed backwards. If the entity
> - * slept for a long time, don't even try to compare its vruntime with
> - * the base as it may be too far off and the comparison may get
> - * inversed due to s64 overflow.
> - */
> - sleep_time = rq_clock_task(rq_of(cfs_rq)) - se->exec_start;
> - if ((s64)sleep_time > 60LL * NSEC_PER_SEC)
> - se->vruntime = vruntime;
> - else
> - se->vruntime = max_vruntime(se->vruntime, vruntime);
> + if (sched_feat(PRESERVE_LAG))
> + vruntime -= se->lag;
> +
> + se->vruntime = vruntime;
I was going to say that
when we migrate a task to a new runqueue, we subtract vruntime
by old queue's min_vruntime and that math needs update.
But then I saw you did that in
https://git.kernel.org/pub/scm/linux/kernel/git/peterz/queue.git/commit/kernel/sched?h=sched/eevdf
With this new lag based placement, I think it should properly fix
the starvation issues we have seen caused by quickly cpu hopping tasks.
Tim
> }
>
> static void check_enqueue_throttle(struct cfs_rq *cfs_rq);
> @@ -4949,6 +4955,9 @@ dequeue_entity(struct cfs_rq *cfs_rq, st
>
> clear_buddies(cfs_rq, se);
>
> + if (sched_feat(PRESERVE_LAG) && (flags & DEQUEUE_SLEEP))
> + se->lag = avg_vruntime(cfs_rq) - se->vruntime;
> +
> if (se != cfs_rq->curr)
> __dequeue_entity(cfs_rq, se);
> se->on_rq = 0;
> --- a/kernel/sched/features.h
> +++ b/kernel/sched/features.h
> @@ -1,12 +1,20 @@
> /* SPDX-License-Identifier: GPL-2.0 */
> +
> /*
> * Only give sleepers 50% of their service deficit. This allows
> * them to run sooner, but does not allow tons of sleepers to
> * rip the spread apart.
> */
> +SCHED_FEAT(FAIR_SLEEPERS, false)
> SCHED_FEAT(GENTLE_FAIR_SLEEPERS, true)
>
> /*
> + * Using the avg_vruntime, do the right thing and preserve lag
> + * across sleep+wake cycles.
> + */
> +SCHED_FEAT(PRESERVE_LAG, true)
> +
> +/*
> * Prefer to schedule the task we woke last (assuming it failed
> * wakeup-preemption), since its likely going to consume data we
> * touched, increases cache locality.
>
>