Skip to contentSkip to conversation

Morphing CFS into FDL, The Fair Deadline Scheduling Class

RFC PATCH New Xi Wang 1 participant 2 messages Apr 1, 2023 Scheduler

lore
Share & tools
lore

Xi Wang

author
#0 lore raw

cover Morphing CFS into FDL, The Fair Deadline Scheduling Class

This is about putting every thread under some aggregated deadline.

Note: In draft status, one big patch, not always conforming to coding style etc. Only hooked to cgroup v1 at the moment. Based on 6.1.21. Usage case, scheduling model and sched policy are more important than the details.

Motivation:

Shared servers running multiple, often unrelated jobs in cgroup based containers. Ideally each job runs under the illusion that it has the whole machine or a slice of the machine, not affected by other jobs. A challenge is that we want to maintain the illusion while overcommitting cpu bandwidth for efficiency. Most of the time this is possible due to statistical multiplexing effect, at least in theory.

Another challenge is some jobs on the shared machines are by definition real time workloads, which often happens due to the fan-out pattern. An upper layer service may need to query many lower layer services before it can assemble the result and respond to a query resulting in amplified tail latency. The median latency of the upper layer query is determined by the tail latency of the lower layer queries. Bonded tail latency for lower layer services becomes much more important. We can end up running real-time servers without knowing it.

Main goals:

- Sched latency guarantees
- CPU bandwidth guarantees
- Real time support for all workloads, be generic and scalable
- Per cgroup policies
- Hierarchical scheduling - typically real-time for first level cgroups and best effort for lower cgroups
- Seamless transition for existing workloads

Scheduling model:

FDL is based on my draining buckets model which still needs a more detailed definition. However the core idea should be intuitive. The model was inspired by media streaming applications. It might be considered a type of deadline scheduling and/or equivalent to some other models. If a device receives an audio stream, processes it and plays it through a speaker, the rx buffer can overflow if the cpu is on something else for too long, then we get audio glitches. To avoid buffer overflows, the receiving thread has to get enough cpu cycles and there cannot be off-cpu gaps too large, thus the requirements are on both latency and cpu bandwidth. If we model every workload this way we get the draining buckets model. The scheduler's job is simply about preventing any bucket from overflowing. This is a continuous model with no event arrival intervals or quota replenishment periods, etc. The round robin deadline is simply the time to fill up an empty bucket.

The model was designed to be resilient, backward compatible and natively support overcommit. It prefers graceful degradation over admission control.

Interface:

Each cpu cgroup controller has 3 new parameters (per thread control is not supported at the moment).

cpu.deadline_rr: round robin latency in ns cpu.deadline_wakeup: optional wake up boost, latency in ns cpu.guaranteed_shares: cpu bandwidth allocation, 1024 == 1 cpu for first level cgroups, relative for lower cgroups

Implementation:

Backward compatibility is a major challenge to a generic latency aware scheduling policy. Many applications have adapted to various CFS behaviors over the years. Moving all of them to a new sched class without causing a few performance regressions is rather difficult. Moving only the latency sensitive applications to a new sched class does not make the problem much easier - two scheduling classes can easily create priority inversion problems. Existing high priority scheduling classes do have mechanisms to yield to low priority sched classes to prevent starvation, yet these mechanisms are difficult to tune and they can hurt the tail latency of high priority sched classes. The dilemma is new low latency applications can be much better supported if all threads are put in a new sched class, but old applications have a much better chance of still working if they are still in the old sched class.

This patch might be an unexpected take on the tradeoffs. It took a shortcut by directly modifying CFS to add latency support. Individual cgroups can be flipped to FDL and the remaining cgroups should see minimal disruption. ("Real-time containers" might sound like a joke but FDL is actually supporting them.) It also reuses the recursive mechanisms of fair group scheduling to support hierarchical scheduling. I also do not expect moving to a clean sheet design later will be made more difficult by FDL.

CFS is already similar to a deadline scheduler in that it picks the next task from a vruntime based rb tree. A deadline based rb tree is added in parallel to the vruntime tree to support latency based scheduling. The deadline tree is examined before the vruntime tree on pick next.

CFS is not a global scheduler so some compromises were made for multi-core scheduling. The deadline based pick next is cpu local but deadline awareness was added to the wake up load balancing path to even out the deadline pressure. A feedback loop is used to dynamically adjust the cgroup cpu shares and provide cpu bandwidth guarantee.

Compared to EEVDF:

I only have a shallow understanding of EEVDF scheduler so the comparison is also limited. They have both similarities and differences. The most prominent similarity might be that both are latency aware, generic sched classes taking the place of CFS. Some differences are: FDL tries to be as real time as possible, supporting configurable deadlines down to microseconds. FDL also aims to be non disruptive to user applications. The threads not configured to run under FDL should still see CFS behavior with minimal change, which is a reason for modifying CFS instead of creating a completely new sched class.

Example:

The script below launches 4 workloads in 4 cgroups and run them
concurrently: hackbench as the antagonist. 3 schbench with identical command line parameters but different cgroup configurations as workloads. One schbench instance runs under cfs and the other two instances run under fdl with different deadline parameters.

The schbench stats from one of the test runs (2 socket x 24 core / 96 hyperthread cascadelake):

==== cfs ====
warmup done, zeroing stats
Latency percentiles (usec) runtime 30 (s) (8496 total samples)

	50.0th: 417 (4248 samples)
	75.0th: 2268 (2129 samples)
	90.0th: 5512 (1270 samples)
	95.0th: 9168 (429 samples)
	*99.0th: 19936 (337 samples)
	99.5th: 25440 (42 samples)
	99.9th: 37952 (35 samples)
	min=7, max=59690

==== fdl loose ====
warmup done, zeroing stats
Latency percentiles (usec) runtime 30 (s) (8544 total samples)

	50.0th: 52 (4304 samples)
	75.0th: 68 (2167 samples)
	90.0th: 84 (1240 samples)
	95.0th: 97 (411 samples)
	*99.0th: 1378 (338 samples)
	99.5th: 2428 (44 samples)
	99.9th: 5608 (32 samples)
	min=6, max=23616

==== fdl ====
warmup done, zeroing stats
Latency percentiles (usec) runtime 30 (s) (8534 total samples)

	50.0th: 48 (4325 samples)
	75.0th: 63 (2210 samples)
	90.0th: 76 (1204 samples)
	95.0th: 85 (387 samples)
	*99.0th: 115 (323 samples)
	99.5th: 725 (43 samples)
	99.9th: 5400 (35 samples)
	min=1, max=12046

Data extracted from 3 test runs with antagonist and 3 test runs without antagonist

                           p50 latency        p99 latency
cfs with antagonist        300, 280, 417      18528, 20960, 19339
fdl-loose with antagonist  52, 51, 52         1722, 1942, 1378
fdl with antagonist        51, 49, 48         609, 234, 115
cfs no antagonist          38, 85, 69         123, 129, 124
fdl-loose no antagonist    85, 54, 84         128, 129, 124
fdl no antagonist          53, 52, 63         129, 118, 128

The test script:

antagonist=true

CR=<cgroup root>

killall hackbench

if $antagonist; then
mkdir -p $CR/antagonist
echo $$ > $CR/antagonist
hackbench -g 10 -f 10 -s 20000 --loops 1000000 > /dev/null& sleep 5
fi

mkdir -p $CR/cfs
echo $$ > $CR/cfs/tasks
echo 0 > $CR/cfs/cpu.deadline_rr
echo 0 > $CR/cfs/cpu.deadline_wakeup
echo 0 > $CR/cfs/cpu.guaranteed_shares
schbench -r 30 -i -1 &> log-cfs &

mkdir -p $CR/fdl-loose
echo $$ > $CR/fdl-loose/tasks
echo 5000000 > $CR/fdl-loose/cpu.deadline_rr
echo 2500000 > $CR/fdl-loose/cpu.deadline_wakeup
echo 7000 > $CR/fdl-loose/cpu.guaranteed_shares
schbench -r 30 -i -1 &> log-fdl-loose &

mkdir -p $CR/fdl
echo $$ > $CR/fdl/tasks
echo 200000 > $CR/fdl/cpu.deadline_rr
echo 100000 > $CR/fdl/cpu.deadline_wakeup
echo 7000 > $CR/fdl/cpu.guaranteed_shares
schbench -r 30 -i -1 &> log-fdl &

echo $$ > $CR/tasks

sleep 40

echo ==== cfs ====
cat log-cfs
echo
echo ==== fdl loose ====
cat log-fdl-loose
echo
echo ==== fdl ====
cat log-fdl
echo

killall hackbench

Xi Wang (1):
[RFC] sched: Morphing CFS into FDL, The Fair Deadline Scheduling Class

 include/linux/sched.h     |   7 +
 kernel/sched/Makefile     |   1 +
 kernel/sched/core.c       | 162 ++++++-
 kernel/sched/cpuacct.c    |   5 +
 kernel/sched/debug.c      |  10 +
 kernel/sched/fair.c       | 927 +++++++++++++++++++++++++++++++++++++-
 kernel/sched/features.h   |   2 +-
 kernel/sched/qos.c        | 305 +++++++++++++
 kernel/sched/qos.h        | 135 ++++++
 kernel/sched/qos_params.h |  30 ++
 kernel/sched/sched.h      |  60 +++
 kernel/sched/stats.h      |  10 +
 12 files changed, 1620 insertions(+), 34 deletions(-)
 create mode 100644 kernel/sched/qos.c
 create mode 100644 kernel/sched/qos.h
 create mode 100644 kernel/sched/qos_params.h
Signature · 1 line
2.40.0.348.gf938b09366-goog
author
#1 lore raw

RFC PATCH 1/1 sched: Morphing CFS into FDL, The Fair Deadline Scheduling Class

Modify the CFS sched class to add latency and cpu bandwidth guarantees. See cover letter for details.

Example:

mkdir -p $CR/fdl
echo $$ > $CR/fdl/tasks
echo 200000 > $CR/fdl/cpu.deadline_rr
echo 100000 > $CR/fdl/cpu.deadline_wakeup
echo 7000 > $CR/fdl/cpu.guaranteed_shares
schbench

---
 include/linux/sched.h     |   7 +
 kernel/sched/Makefile     |   1 +
 kernel/sched/core.c       | 162 ++++++-
 kernel/sched/cpuacct.c    |   5 +
 kernel/sched/debug.c      |  10 +
 kernel/sched/fair.c       | 927 +++++++++++++++++++++++++++++++++++++-
 kernel/sched/features.h   |   2 +-
 kernel/sched/qos.c        | 305 +++++++++++++
 kernel/sched/qos.h        | 135 ++++++
 kernel/sched/qos_params.h |  30 ++
 kernel/sched/sched.h      |  60 +++
 kernel/sched/stats.h      |  10 +
 12 files changed, 1620 insertions(+), 34 deletions(-)
 create mode 100644 kernel/sched/qos.c
 create mode 100644 kernel/sched/qos.h
 create mode 100644 kernel/sched/qos_params.h
include/linux/sched.h +7 -0
index ffb6eb55cd135..179cb93d1602b 100644
@@ -548,12 +548,19 @@ struct sched_entity {
 	/* For load-balancing: */
 	struct load_weight		load;
 	struct rb_node			run_node;
+#ifdef CONFIG_FAIR_GROUP_SCHED
+	struct rb_node			dl_node;
+	struct list_head		fdl_list_node;
+#endif
 	struct list_head		group_node;
 	unsigned int			on_rq;
 
 	u64				exec_start;
 	u64				sum_exec_runtime;
 	u64				vruntime;
+#ifdef CONFIG_FAIR_GROUP_SCHED
+	u64				dl;
+#endif
 	u64				prev_sum_exec_runtime;
 
 	u64				nr_migrations;
kernel/sched/Makefile +1 -0
index 976092b7bd452..8655a0d4f511e 100644
@@ -30,5 +30,6 @@ endif
 #
 obj-y += core.o
 obj-y += fair.o
+obj-$(CONFIG_FAIR_GROUP_SCHED) += qos.o
 obj-y += build_policy.o
 obj-y += build_utility.o
kernel/sched/core.c +151 -11

232 lines not on this page · raw message

kernel/sched/cpuacct.c +5 -0
index 0de9dda099496..287a1ea71592f 100644
@@ -188,6 +188,11 @@ static u64 cpuusage_read(struct cgroup_subsys_state *css, struct cftype *cft)
 	return __cpuusage_read(css, CPUACCT_STAT_NSTATS);
 }
 
+u64 qos_cpuusage_read(struct cgroup_subsys_state *css)
+{
+	return __cpuusage_read(css, CPUACCT_STAT_NSTATS);
+}
+
 static int cpuusage_write(struct cgroup_subsys_state *css, struct cftype *cft,
 			  u64 val)
 {
kernel/sched/debug.c +10 -0
index 1637b65ba07ac..09b1a6a1a08a7 100644
@@ -625,6 +625,7 @@ void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq)
 			cfs_rq->idle_nr_running);
 	SEQ_printf(m, "  .%-30s: %d\n", "idle_h_nr_running",
 			cfs_rq->idle_h_nr_running);
+	SEQ_printf(m, "  .%-30s: %d\n", "fdl_nr_running", cfs_rq->fdl_nr_running);
 	SEQ_printf(m, "  .%-30s: %ld\n", "load", cfs_rq->load.weight);
 #ifdef CONFIG_SMP
 	SEQ_printf(m, "  .%-30s: %lu\n", "load_avg",
@@ -743,6 +744,9 @@ do {									\
 	P(nr_switches);
 	P(nr_uninterruptible);
 	PN(next_balance);
+#ifdef CONFIG_FAIR_GROUP_SCHED
+	P(fdl_t_nr_running);
+#endif
 	SEQ_printf(m, "  .%-30s: %ld\n", "curr->pid", (long)(task_pid_nr(rq->curr)));
 	PN(clock);
 	PN(clock_task);
@@ -947,6 +951,7 @@ void proc_sched_show_task(struct task_struct *p, struct pid_namespace *ns,
 						  struct seq_file *m)
 {
 	unsigned long nr_switches;
+	struct sched_entity *se;
 
 	SEQ_printf(m, "%s (%d, #threads: %d)\n", p->comm, task_pid_nr_ns(p, ns),
 						get_nr_threads(p));
@@ -1047,6 +1052,11 @@ void proc_sched_show_task(struct task_struct *p, struct pid_namespace *ns,
 		P(dl.runtime);
 		P(dl.deadline);
 	}
+
+	for (se = &p->se; se; se = se->parent) {
+		__P(se->dl);
+	}
+
 #undef PN_SCHEDSTAT
 #undef P_SCHEDSTAT
 
kernel/sched/fair.c +905 -22

1,196 lines not on this page · raw message

kernel/sched/features.h +1 -1
index ee7f23c76bd33..0b0a8d37f0ce8 100644
@@ -37,7 +37,7 @@ SCHED_FEAT(CACHE_HOT_BUDDY, true)
  */
 SCHED_FEAT(WAKEUP_PREEMPTION, true)
 
-SCHED_FEAT(HRTICK, false)
+SCHED_FEAT(HRTICK, true)
 SCHED_FEAT(HRTICK_DL, false)
 SCHED_FEAT(DOUBLE_TICK, false)
 
kernel/sched/qos.c new file +305 -0

305 lines not on this page · raw message

kernel/sched/qos.h new file +135 -0

135 lines not on this page · raw message

kernel/sched/qos_params.h new file +30 -0
new file mode 100644
index 0000000000000..bb9ed8329b45e
@@ -0,0 +1,30 @@
+/* debug params */
+QOS_PARAM_S32(debug_bw, 0) /* Debug cpu bandwidth */
+QOS_PARAM_S32(debug_cpu, -1)
+QOS_PARAM_S64(debug_pid, 0)
+QOS_PARAM_S32(debug_nontask, 0) /* Messages for cgroups */
+QOS_PARAM_S32(dump_fdl_rq, 0)
+QOS_PARAM_S32(debug_hf, 1) /* On/off switch for high frequency messages */
+QOS_PARAM_S32(dump_debug, 0) /* Print everything */
+
+/* latency params */
+QOS_PARAM_U32(tick_margin, 970)
+QOS_PARAM_U32(dl_slack, 970)
+QOS_PARAM_U64(tick_skip, 80000) /* Min time to next tick after a tick miss, prevents consecutive misses */
+QOS_PARAM_U64(dl_skip, 50000) /* Min deadline extension after a deadline miss, prevents consecutive misses */
+QOS_PARAM_U64(max_tick_interval, 100000000)
+QOS_PARAM_U64(default_fair_dl, 5000000)
+QOS_PARAM_S32(wake_dl_scan, 1) /* Deadline based wake up load balancing search in addition to idle search */
+QOS_PARAM_U32(wake_dl_interval_shift, 0) /* Dl based wake lb every n wakeups */
+QOS_PARAM_U32(wake_dl_margin, 1500) /* Only consider wake lb to a cpu with a dl greater than task's dl scaled by this */
+QOS_PARAM_S32(wake_prefer_preempt_prev, 1) /* Don't check other cpus if the previous cpu can be preempted */
+QOS_PARAM_S32(wake_prefer_preempt_others, 0) /* Wake lb ends when a preemptible cpu is found, idle cpu not required */
+
+/* bandwidth params */
+QOS_PARAM_U32(target_wait_fraction, 100) /* Allow cpu shares increase only if wait time / on cpu time > this / 1024 */
+QOS_PARAM_U32(guaranteed_share_boost, 1)
+QOS_PARAM_U32(guaranteed_share_ratio, 800) /* Won't try to increase guaranteed cgroups cpu shares above this level */
+QOS_PARAM_U32(avg_usage_alpha, 10)
+QOS_PARAM_U32(avg_wait_alpha, 10)
+QOS_PARAM_U64(control_loop_interval, 10000000)
+QOS_PARAM_U32(max_share_boost, 10)
kernel/sched/sched.h +60 -0

110 lines not on this page · raw message

kernel/sched/stats.h +10 -0
index 84a188913cc9d..d151bf31a7808 100644
@@ -230,6 +230,8 @@ static inline void sched_info_dequeue(struct rq *rq, struct task_struct *t)
 	rq_sched_info_dequeue(rq, delta);
 }
 
+void qos_record_wait(struct task_group *tg, u64 delta);
+
 /*
  * Called when a task finally hits the CPU.  We can now calculate how
  * long it was waiting to run.  We also note when it began so that we
@@ -237,7 +239,10 @@ static inline void sched_info_dequeue(struct rq *rq, struct task_struct *t)
  */
 static void sched_info_arrive(struct rq *rq, struct task_struct *t)
 {
+	extern const struct sched_class fair_sched_class;
+
 	unsigned long long now, delta = 0;
+	struct cfs_rq *cfs_rq;
 
 	if (!t->sched_info.last_queued)
 		return;
@@ -250,6 +255,11 @@ static void sched_info_arrive(struct rq *rq, struct task_struct *t)
 	t->sched_info.pcount++;
 
 	rq_sched_info_arrive(rq, delta);
+
+	if (t->sched_class == &fair_sched_class) {
+		cfs_rq = cfs_rq_of(&t->se);
+		qos_record_wait(cfs_rq->tg, delta);
+	}
 }
 
 /*
Signature · 1 line
2.40.0.348.gf938b09366-goog