From: Peter Zijlstra <peterz@infradead.org>
To: mingo@kernel.org, vincent.guittot@linaro.org
Cc: linux-kernel@vger.kernel.org, peterz@infradead.org,
juri.lelli@redhat.com, dietmar.eggemann@arm.com,
rostedt@goodmis.org, bsegall@google.com, mgorman@suse.de,
bristot@redhat.com, corbet@lwn.net, qyousef@layalina.io,
chris.hyser@oracle.com, patrick.bellasi@matbug.net,
pjt@google.com, pavel@ucw.cz, qperret@google.com,
tim.c.chen@linux.intel.com, joshdon@google.com, timj@gnu.org,
kprateek.nayak@amd.com, yu.c.chen@intel.com,
youssefesmat@chromium.org, joel@joelfernandes.org, efault@gmx.de
Subject: [PATCH 15/17] [RFC] sched/eevdf: Sleeper bonus
Date: Tue, 28 Mar 2023 11:26:37 +0200 [thread overview]
Message-ID: <20230328110354.641979416@infradead.org> (raw)
In-Reply-To: 20230328092622.062917921@infradead.org
Add a sleeper bonus hack, but keep it default disabled. This should
allow easy testing if regressions are due to this.
Specifically; this 'restores' performance for things like starve and
stress-futex, stress-nanosleep that rely on sleeper bonus to compete
against an always running parent (the fair 67%/33% split vs the
50%/50% bonus thing).
OTOH this completely destroys latency and hackbench (as in 5x worse).
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
kernel/sched/fair.c | 47 ++++++++++++++++++++++++++++++++++++++++-------
kernel/sched/features.h | 1 +
kernel/sched/sched.h | 3 ++-
3 files changed, 43 insertions(+), 8 deletions(-)
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -4819,7 +4819,7 @@ static inline void update_misfit_status(
#endif /* CONFIG_SMP */
static void
-place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
+place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
u64 vslice = calc_delta_fair(se->slice, se);
u64 vruntime = avg_vruntime(cfs_rq);
@@ -4878,22 +4878,55 @@ place_entity(struct cfs_rq *cfs_rq, stru
if (WARN_ON_ONCE(!load))
load = 1;
lag = div_s64(lag, load);
+
+ vruntime -= lag;
+ }
+
+ /*
+ * Base the deadline on the 'normal' EEVDF placement policy in an
+ * attempt to not let the bonus crud below wreck things completely.
+ */
+ se->deadline = vruntime;
+
+ /*
+ * The whole 'sleeper' bonus hack... :-/ This is strictly unfair.
+ *
+ * By giving a sleeping task a little boost, it becomes possible for a
+ * 50% task to compete equally with a 100% task. That is, strictly fair
+ * that setup would result in a 67% / 33% split. Sleeper bonus will
+ * change that to 50% / 50%.
+ *
+ * This thing hurts my brain, because tasks leaving with negative lag
+ * will move 'time' backward, so comparing against a historical
+ * se->vruntime is dodgy as heck.
+ */
+ if (sched_feat(PLACE_BONUS) &&
+ (flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED)) {
+ /*
+ * If se->vruntime is ahead of vruntime, something dodgy
+ * happened and we cannot give bonus due to not having valid
+ * history.
+ */
+ if ((s64)(se->vruntime - vruntime) < 0) {
+ vruntime -= se->slice/2;
+ vruntime = max_vruntime(se->vruntime, vruntime);
+ }
}
- se->vruntime = vruntime - lag;
+ se->vruntime = vruntime;
/*
* When joining the competition; the exisiting tasks will be,
* on average, halfway through their slice, as such start tasks
* off with half a slice to ease into the competition.
*/
- if (sched_feat(PLACE_DEADLINE_INITIAL) && initial)
+ if (sched_feat(PLACE_DEADLINE_INITIAL) && (flags & ENQUEUE_INITIAL))
vslice /= 2;
/*
* EEVDF: vd_i = ve_i + r_i/w_i
*/
- se->deadline = se->vruntime + vslice;
+ se->deadline += vslice;
}
static void check_enqueue_throttle(struct cfs_rq *cfs_rq);
@@ -4910,7 +4943,7 @@ enqueue_entity(struct cfs_rq *cfs_rq, st
* update_curr().
*/
if (curr)
- place_entity(cfs_rq, se, 0);
+ place_entity(cfs_rq, se, flags);
update_curr(cfs_rq);
@@ -4937,7 +4970,7 @@ enqueue_entity(struct cfs_rq *cfs_rq, st
* we can place the entity.
*/
if (!curr)
- place_entity(cfs_rq, se, 0);
+ place_entity(cfs_rq, se, flags);
account_entity_enqueue(cfs_rq, se);
@@ -11933,7 +11966,7 @@ static void task_fork_fair(struct task_s
curr = cfs_rq->curr;
if (curr)
update_curr(cfs_rq);
- place_entity(cfs_rq, se, 1);
+ place_entity(cfs_rq, se, ENQUEUE_INITIAL);
rq_unlock(rq, &rf);
}
--- a/kernel/sched/features.h
+++ b/kernel/sched/features.h
@@ -7,6 +7,7 @@
SCHED_FEAT(PLACE_LAG, true)
SCHED_FEAT(PLACE_FUDGE, true)
SCHED_FEAT(PLACE_DEADLINE_INITIAL, true)
+SCHED_FEAT(PLACE_BONUS, false)
/*
* Prefer to schedule the task we woke last (assuming it failed
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -2143,7 +2143,7 @@ extern const u32 sched_prio_to_wmult[40
* ENQUEUE_HEAD - place at front of runqueue (tail if not specified)
* ENQUEUE_REPLENISH - CBS (replenish runtime and postpone deadline)
* ENQUEUE_MIGRATED - the task was migrated during wakeup
- *
+ * ENQUEUE_INITIAL - place a new task (fork/clone)
*/
#define DEQUEUE_SLEEP 0x01
@@ -2163,6 +2163,7 @@ extern const u32 sched_prio_to_wmult[40
#else
#define ENQUEUE_MIGRATED 0x00
#endif
+#define ENQUEUE_INITIAL 0x80
#define RETRY_TASK ((void *)-1UL)
next prev parent reply other threads:[~2023-03-28 11:07 UTC|newest]
Thread overview: 55+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-03-28 9:26 [PATCH 00/17] sched: EEVDF using latency-nice Peter Zijlstra
2023-03-28 9:26 ` [PATCH 01/17] sched: Introduce latency-nice as a per-task attribute Peter Zijlstra
2023-03-28 9:26 ` [PATCH 02/17] sched/fair: Add latency_offset Peter Zijlstra
2023-03-28 9:26 ` [PATCH 03/17] sched/fair: Add sched group latency support Peter Zijlstra
2023-03-28 9:26 ` [PATCH 04/17] sched/fair: Add avg_vruntime Peter Zijlstra
2023-03-28 23:57 ` Josh Don
2023-03-29 7:50 ` Peter Zijlstra
2023-04-05 19:13 ` Peter Zijlstra
2023-03-28 9:26 ` [PATCH 05/17] sched/fair: Remove START_DEBIT Peter Zijlstra
2023-03-28 9:26 ` [PATCH 06/17] sched/fair: Add lag based placement Peter Zijlstra
2023-04-03 9:18 ` Chen Yu
2023-04-05 9:47 ` Peter Zijlstra
2023-04-06 3:03 ` Chen Yu
2023-04-13 15:42 ` Chen Yu
2023-04-13 15:55 ` Chen Yu
2023-03-28 9:26 ` [PATCH 07/17] rbtree: Add rb_add_augmented_cached() helper Peter Zijlstra
2023-03-28 9:26 ` [PATCH 08/17] sched/fair: Implement an EEVDF like policy Peter Zijlstra
2023-03-29 1:26 ` Josh Don
2023-03-29 8:02 ` Peter Zijlstra
2023-03-29 8:06 ` Peter Zijlstra
2023-03-29 8:22 ` Peter Zijlstra
2023-03-29 18:48 ` Josh Don
2023-03-29 8:12 ` Peter Zijlstra
2023-03-29 18:54 ` Josh Don
2023-03-29 8:18 ` Peter Zijlstra
2023-03-29 14:35 ` Vincent Guittot
2023-03-30 8:01 ` Peter Zijlstra
2023-03-30 17:05 ` Vincent Guittot
2023-04-04 12:00 ` Peter Zijlstra
2023-03-28 9:26 ` [PATCH 09/17] sched: Commit to lag based placement Peter Zijlstra
2023-03-28 9:26 ` [PATCH 10/17] sched/smp: Use lag to simplify cross-runqueue placement Peter Zijlstra
2023-03-28 9:26 ` [PATCH 11/17] sched: Commit to EEVDF Peter Zijlstra
2023-03-28 9:26 ` [PATCH 12/17] sched/debug: Rename min_granularity to base_slice Peter Zijlstra
2023-03-28 9:26 ` [PATCH 13/17] sched: Merge latency_offset into slice Peter Zijlstra
2023-03-28 9:26 ` [PATCH 14/17] sched/eevdf: Better handle mixed slice length Peter Zijlstra
2023-03-31 15:26 ` Vincent Guittot
2023-04-04 9:29 ` Peter Zijlstra
2023-04-04 13:50 ` Joel Fernandes
2023-04-05 5:41 ` Mike Galbraith
2023-04-05 8:35 ` Peter Zijlstra
2023-04-05 20:05 ` Joel Fernandes
2023-04-14 11:18 ` Phil Auld
2023-04-16 5:10 ` Joel Fernandes
[not found] ` <20230401232355.336-1-hdanton@sina.com>
2023-04-02 2:40 ` Mike Galbraith
2023-03-28 9:26 ` Peter Zijlstra [this message]
2023-03-29 9:10 ` [PATCH 15/17] [RFC] sched/eevdf: Sleeper bonus Mike Galbraith
2023-03-28 9:26 ` [PATCH 16/17] [RFC] sched/eevdf: Minimal vavg option Peter Zijlstra
2023-03-28 9:26 ` [PATCH 17/17] [DEBUG] sched/eevdf: Debug / validation crud Peter Zijlstra
2023-04-03 7:42 ` [PATCH 00/17] sched: EEVDF using latency-nice Shrikanth Hegde
2023-04-10 3:13 ` David Vernet
2023-04-11 2:09 ` David Vernet
[not found] ` <20230410082307.1327-1-hdanton@sina.com>
2023-04-11 10:15 ` Mike Galbraith
[not found] ` <20230411133333.1790-1-hdanton@sina.com>
2023-04-11 14:56 ` Mike Galbraith
[not found] ` <20230412025042.1413-1-hdanton@sina.com>
2023-04-12 4:05 ` Mike Galbraith
2023-04-25 12:32 ` Phil Auld
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=20230328110354.641979416@infradead.org \
--to=peterz@infradead.org \
--cc=bristot@redhat.com \
--cc=bsegall@google.com \
--cc=chris.hyser@oracle.com \
--cc=corbet@lwn.net \
--cc=dietmar.eggemann@arm.com \
--cc=efault@gmx.de \
--cc=joel@joelfernandes.org \
--cc=joshdon@google.com \
--cc=juri.lelli@redhat.com \
--cc=kprateek.nayak@amd.com \
--cc=linux-kernel@vger.kernel.org \
--cc=mgorman@suse.de \
--cc=mingo@kernel.org \
--cc=patrick.bellasi@matbug.net \
--cc=pavel@ucw.cz \
--cc=pjt@google.com \
--cc=qperret@google.com \
--cc=qyousef@layalina.io \
--cc=rostedt@goodmis.org \
--cc=tim.c.chen@linux.intel.com \
--cc=timj@gnu.org \
--cc=vincent.guittot@linaro.org \
--cc=youssefesmat@chromium.org \
--cc=yu.c.chen@intel.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;
as well as URLs for NNTP newsgroup(s).