Skip to contentSkip to conversation

Add micro quanta scheduling class

PATCH New Xi Wang 1 participant 2 messages Sep 6, 2019

Subsystems (3)
lore
Share & tools
lore

Xi Wang

author
#0 lore raw

cover Add micro quanta scheduling class

This is a scheduling class that does one thing really well:
microsecond level scheduling granularity. There are many problems It doesn’t solve, e.g. there is minimal mutlicore support. Context switch and cache overheads are going to be higher but we found benefits outweigh drawbacks for certain applications.

It can be used in two different but related ways:

Provide softirq like scheduling latency for kernel and userspace threads. Somewhat safer and easier to use than both softirq and rt classes - microsecond level time slicing means a microq task can share a cpu with a cfs task and still maintain low scheduling latency. With rt classes users often have to choose between starving cfs tasks (rt bandwidht control not activated) and high rt tail latency (rt bandwidth control activated).

When busy polling is desired, we can run the busy polling thread under the microq class with less than 100% of allocated cpu bandwidth. The response latency would still be low and some cpu cycles are recovered from the busy polling loop - it is a middle ground between interrupt driven and busy polling.

Xi Wang (1):
sched: Add micro quanta scheduling class

 Documentation/scheduler/sched-microq.txt |  72 +++
 include/linux/sched.h                    |  12 +
 include/linux/sched/sysctl.h             |  12 +
 include/uapi/linux/sched.h               |   1 +
 init/Kconfig                             |  13 +
 kernel/sched/Makefile                    |   1 +
 kernel/sched/core.c                      | 138 ++++-
 kernel/sched/debug.c                     |  28 +
 kernel/sched/fair.c                      |   4 +-
 kernel/sched/microq.c                    | 750 +++++++++++++++++++++++
 kernel/sched/pelt.c                      |  30 +-
 kernel/sched/pelt.h                      |   6 +
 kernel/sched/rt.c                        |   6 +-
 kernel/sched/sched.h                     |  63 +-
 kernel/sysctl.c                          |  23 +
 15 files changed, 1135 insertions(+), 24 deletions(-)
 create mode 100644 Documentation/scheduler/sched-microq.txt
 create mode 100644 kernel/sched/microq.c
Signature · 1 line
2.23.0.187.g17f5b7556c-goog
author
#1 lore raw

PATCH 1/1 sched: Add micro quanta scheduling class

Micro quanta is a lightweight scheduling class designed for microsecond level scheduling intervals. It provides a more flexible way to share cores between highly latency sensitive tasks with other tasks - limiting the cpu share of latency sensitive tasks and maintaining low scheduling latency at the same time.

The scheduling policy is similar to real-time group scheduling period and runtime. There is no group support but more frequent context switching is possible. Tasks running with 2us scheduling period and 1us runtime has been demonstrated. The practical range of microq scheduling period is expected to be 10us ~ 1000us.

Cc Paul Turner <[email protected]>
Cc Ben Segall <[email protected]>'
---
 Documentation/scheduler/sched-microq.txt |  72 +++
 include/linux/sched.h                    |  12 +
 include/linux/sched/sysctl.h             |  12 +
 include/uapi/linux/sched.h               |   1 +
 init/Kconfig                             |  13 +
 kernel/sched/Makefile                    |   1 +
 kernel/sched/core.c                      | 138 ++++-
 kernel/sched/debug.c                     |  28 +
 kernel/sched/fair.c                      |   4 +-
 kernel/sched/microq.c                    | 750 +++++++++++++++++++++++
 kernel/sched/pelt.c                      |  30 +-
 kernel/sched/pelt.h                      |   6 +
 kernel/sched/rt.c                        |   6 +-
 kernel/sched/sched.h                     |  63 +-
 kernel/sysctl.c                          |  23 +
 15 files changed, 1135 insertions(+), 24 deletions(-)
 create mode 100644 Documentation/scheduler/sched-microq.txt
 create mode 100644 kernel/sched/microq.c
Documentation/scheduler/sched-microq.txt new file +72 -0
new file mode 100644
index 000000000000..b3deefdc265f
@@ -0,0 +1,72 @@
+Micro Quanta Scheduling
+
+Micro quanta (microq) is a lightweight scheduling class for microsecond level
+scheduling intervals. It can simultaneously provide low scheduling latency for
+real time tasks while causing no starvation or excessive latency for normal
+tasks. It is a safe (avoiding many of the priority inversion problems etc.) and
+high performance way to share a cpu.
+
+Main characteristics:
+
+ - A sample configuration is one microq task configured to run with 16us
+runtime and 20us period. Most of the time the microq task won’t wait for more
+than 20 - 16 = 4us. kworker and ksoftirqd tasks under cfs can still get 4us
+every 20us.
+
+ - The scheduling policy between microq class and cfs class is weighted fair
+queuing with latency guarantees for microq.
+
+ - No priority among microq tasks. Multiple microq tasks on the same cpu will
+round robin at tick interval.
+
+ - The microq class is work conserving. If no other task is running on a cpu, a
+microq task can take all cpu cycles regardless of runtime/period bandwidth
+allocation.
+
+ - Simple push load balancing only.
+
+ - No cgroup support.
+
+ - Driven by per cpu hrtimers.
+
+There are similarities between microq and rt group scheduling or between microq
+and SCHED_DEADLINE. Below is a quick comparison:
+
+ - rt group scheduling uses both tick and a global hrtimer for bandwidth
+control, which doesn’t work well for below tick interval. If rt tasks are
+throttled on many cpus the global hrtimer becomes a bottleneck. SCHED_DEADLINE
+appears to have similar behaviors. microq uses per cpu hrtimers.
+
+ - microq is based on fair queuing (or somewhat equivalent to SCHED_DEADLINE
+with period == deadline), not fixed scheduling intervals. A blocked task can
+accumulate credit similar to cfs or SCHED_DEADLINE, but different from fixed
+intervals of rt group scheduling.
+
+ - No priority among microq threads.
+
+ - microq is work conserving. rt group scheduling has fixed bandwidth
+allocation.
+
+ - Compared to SCHED_DEADLINE, microq is a lightweight scheduling class with a
+very limited feature set, but also with less restrictions, e.g. no admission
+control or cpu affinity requirements.
+
+
+Usage and expected behaviors:
+
+microq bandwidth can be controlled with either global or per task bandwidth
+parameters. If none of the microq tasks on a cpu specifies the bandwidth
+parameters, global parameters take effect.
+
+When there are multiple microq tasks on a run queue, the bandwidth parameters
+of the task with shortest period takes effect. (Note runtime in effect is not
+the sum of microq tasks, it is exactly the runtime requested by one microq
+task.)
+
+When there are multiple microq tasks on the same cpu, they will round-robin at
+tick interval. The microq scheduling period is likely shorter than the tick
+interval, thus the scheduler can switch between one microq task and a cfs task
+several times before switching to another microq task. The scheduling latency
+of a microq tasks is well shielded from cfs tasks but not from another microq
+task. Cooperative multitasking might be an option for some applications if
+multiple microq tasks on the same cpu is needed.
include/linux/sched.h +12 -0
index 8dc1811487f5..3c741225d057 100644
@@ -578,6 +578,15 @@ struct sched_dl_entity {
 	struct hrtimer inactive_timer;
 };
 
+#ifdef CONFIG_SCHED_CLASS_MICROQ
+struct sched_microq_entity {
+	struct list_head run_list;
+	int sched_period;
+	int sched_runtime;
+	unsigned int time_slice;
+};
+#endif
+
 #ifdef CONFIG_UCLAMP_TASK
 /* Number of utilization clamp buckets (shorter alias) */
 #define UCLAMP_BUCKETS CONFIG_UCLAMP_BUCKETS_COUNT
@@ -688,6 +697,9 @@ struct task_struct {
 	const struct sched_class	*sched_class;
 	struct sched_entity		se;
 	struct sched_rt_entity		rt;
+#ifdef CONFIG_SCHED_CLASS_MICROQ
+	struct sched_microq_entity microq;
+#endif
 #ifdef CONFIG_CGROUP_SCHED
 	struct task_group		*sched_task_group;
 #endif
include/linux/sched/sysctl.h +12 -0
index d4f6215ee03f..f1b8a0a23504 100644
@@ -56,6 +56,13 @@ int sched_proc_update_handler(struct ctl_table *table, int write,
 extern unsigned int sysctl_sched_rt_period;
 extern int sysctl_sched_rt_runtime;
 
+#ifdef CONFIG_SCHED_CLASS_MICROQ
+/* micro quanta period and runtime */
+extern int sysctl_sched_microq_period;
+extern int sysctl_sched_microq_runtime;
+extern int sched_microq_timeslice;
+#endif
+
 #ifdef CONFIG_UCLAMP_TASK
 extern unsigned int sysctl_sched_uclamp_util_min;
 extern unsigned int sysctl_sched_uclamp_util_max;
@@ -101,4 +108,9 @@ extern int sched_energy_aware_handler(struct ctl_table *table, int write,
 				 loff_t *ppos);
 #endif
 
+#ifdef CONFIG_SCHED_CLASS_MICROQ
+extern int sched_microq_proc_handler(struct ctl_table *table, int write,
+		void __user *buffer, size_t *lenp, loff_t *ppos);
+#endif
+
 #endif /* _LINUX_SCHED_SYSCTL_H */
include/uapi/linux/sched.h +1 -0
index b3105ac1381a..71b4af023f17 100644
@@ -57,6 +57,7 @@ struct clone_args {
 /* SCHED_ISO: reserved but not implemented yet */
 #define SCHED_IDLE		5
 #define SCHED_DEADLINE		6
+#define SCHED_MICROQ		7
 
 /* Can be ORed in to make sure the process is reverted back to SCHED_NORMAL on fork */
 #define SCHED_RESET_ON_FORK     0x40000000
init/Kconfig +13 -0
index d3ad48272924..f544c2d6ded9 100644
@@ -2126,6 +2126,19 @@ config PADATA
 	depends on SMP
 	bool
 
+config SCHED_CLASS_MICROQ
+	bool "Micro Quanta scheduling class"
+	default y
+	help
+	  Micro quanta is a lightweight scheduling class designed for
+	  microsecond level scheduling intervals. It provides a more flexible
+	  way to share cores between highly latency sensitive tasks with other
+	  tasks - limiting the cpu share of latency sensitive tasks and
+	  maintaining low scheduling latency at the same time. The scheduling
+	  policy is similar to real-time group scheduling period and runtime.
+	  There is no group support but more frequent context switching
+	  is possible.
+
 config ASN1
 	tristate
 	help
kernel/sched/Makefile +1 -0
index 21fb5a5662b5..76255ef8636c 100644
@@ -30,3 +30,4 @@ obj-$(CONFIG_CPU_FREQ_GOV_SCHEDUTIL) += cpufreq_schedutil.o
 obj-$(CONFIG_MEMBARRIER) += membarrier.o
 obj-$(CONFIG_CPU_ISOLATION) += isolation.o
 obj-$(CONFIG_PSI) += psi.o
+obj-$(CONFIG_SCHED_CLASS_MICROQ) += microq.o
kernel/sched/core.c +121 -17

225 lines not on this page · raw message

kernel/sched/debug.c +28 -0
index f7e4579e746c..9bfd4b106b7e 100644
@@ -611,6 +611,31 @@ void print_dl_rq(struct seq_file *m, int cpu, struct dl_rq *dl_rq)
 #undef PU
 }
 
+#ifdef CONFIG_SCHED_CLASS_MICROQ
+void print_microq_rq(struct seq_file *m, int cpu, struct microq_rq *microq_rq)
+{
+	SEQ_printf(m, "\nmicroq_rq[%d]:\n", cpu);
+
+#define P(x) \
+	SEQ_printf(m, "  .%-30s: %Ld\n", #x, (long long)(microq_rq->x))
+#define PN(x) \
+	SEQ_printf(m, "  .%-30s: %Ld.%06ld\n", #x, SPLIT_NS(microq_rq->x))
+
+	P(microq_nr_running);
+	P(microq_throttled);
+	PN(microq_time);
+	PN(microq_target_time);
+	P(microq_runtime);
+	P(microq_period);
+	P(last_push_failed);
+	PN(quanta_start);
+	P(delta_exec_uncharged);
+
+#undef PN
+#undef P
+}
+#endif
+
 static void print_cpu(struct seq_file *m, int cpu)
 {
 	struct rq *rq = cpu_rq(cpu);
@@ -670,6 +695,9 @@ do {									\
 	print_cfs_stats(m, cpu);
 	print_rt_stats(m, cpu);
 	print_dl_stats(m, cpu);
+#ifdef CONFIG_SCHED_CLASS_MICROQ
+	print_microq_stats(m, cpu);
+#endif
 
 	print_rq(m, rq, cpu);
 	spin_unlock_irqrestore(&sched_debug_lock, flags);
kernel/sched/fair.c +2 -2
index 036be95a87e9..31f3f058cec1 100644
@@ -7556,7 +7556,7 @@ static void update_blocked_averages(int cpu)
 	}
 
 	curr_class = rq->curr->sched_class;
-	update_rt_rq_load_avg(rq_clock_pelt(rq), rq, curr_class == &rt_sched_class);
+	update_rt_rq_load_avg(rq_clock_pelt(rq), rq, curr_class == &rt_sched_class || curr_class == &microq_sched_class);
 	update_dl_rq_load_avg(rq_clock_pelt(rq), rq, curr_class == &dl_sched_class);
 	update_irq_load_avg(rq, 0);
 	/* Don't need periodic decay once load/util_avg are null */
@@ -7626,7 +7626,7 @@ static inline void update_blocked_averages(int cpu)
 	update_cfs_rq_load_avg(cfs_rq_clock_pelt(cfs_rq), cfs_rq);
 
 	curr_class = rq->curr->sched_class;
-	update_rt_rq_load_avg(rq_clock_pelt(rq), rq, curr_class == &rt_sched_class);
+	update_rt_rq_load_avg(rq_clock_pelt(rq), rq, curr_class == &rt_sched_class || curr_class == &microq_sched_class);
 	update_dl_rq_load_avg(rq_clock_pelt(rq), rq, curr_class == &dl_sched_class);
 	update_irq_load_avg(rq, 0);
 	update_blocked_load_status(rq, cfs_rq_has_blocked(cfs_rq) || others_have_blocked(rq));
kernel/sched/microq.c new file +750 -0

750 lines not on this page · raw message

kernel/sched/pelt.c +27 -3
index a96db50d40e0..486bf7e6ee31 100644
@@ -107,7 +107,7 @@ static u32 __accumulate_pelt_segments(u64 periods, u32 d1, u32 d3)
  *                     n=1
  */
 static __always_inline u32
-accumulate_sum(u64 delta, struct sched_avg *sa,
+accumulate_sum(u64 delta, u64 contrib_ratio, struct sched_avg *sa,
 	       unsigned long load, unsigned long runnable, int running)
 {
 	u32 contrib = (u32)delta; /* p == 0 -> delta < 1024 */
@@ -134,6 +134,7 @@ accumulate_sum(u64 delta, struct sched_avg *sa,
 	}
 	sa->period_contrib = delta;
 
+	contrib = contrib * contrib_ratio / SCHED_FIXEDPOINT_SCALE;
 	if (load)
 		sa->load_sum += load * contrib;
 	if (runnable)
@@ -173,7 +174,7 @@ accumulate_sum(u64 delta, struct sched_avg *sa,
  *            = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
  */
 static __always_inline int
-___update_load_sum(u64 now, struct sched_avg *sa,
+___update_load_sum_ratio(u64 now, u64 contrib_ratio, struct sched_avg *sa,
 		  unsigned long load, unsigned long runnable, int running)
 {
 	u64 delta;
@@ -217,12 +218,20 @@ ___update_load_sum(u64 now, struct sched_avg *sa,
 	 * Step 1: accumulate *_sum since last_update_time. If we haven't
 	 * crossed period boundaries, finish.
 	 */
-	if (!accumulate_sum(delta, sa, load, runnable, running))
+	if (!accumulate_sum(delta, contrib_ratio, sa, load, runnable, running))
 		return 0;
 
 	return 1;
 }
 
+static __always_inline int
+___update_load_sum(u64 now, struct sched_avg *sa,
+		  unsigned long load, unsigned long runnable, int running)
+{
+	return ___update_load_sum_ratio(now, SCHED_FIXEDPOINT_SCALE, sa, load, runnable, running);
+}
+
+
 static __always_inline void
 ___update_load_avg(struct sched_avg *sa, unsigned long load, unsigned long runnable)
 {
@@ -329,6 +338,21 @@ int update_rt_rq_load_avg(u64 now, struct rq *rq, int running)
 	return 0;
 }
 
+int update_rt_rq_load_avg_ratio(u64 now, u64 contrib_ratio, struct rq *rq, int running)
+{
+	if (___update_load_sum_ratio(now, contrib_ratio, &rq->avg_rt,
+				running,
+				running,
+				running)) {
+
+		___update_load_avg(&rq->avg_rt, 1, 1);
+		trace_pelt_rt_tp(rq);
+		return 1;
+	}
+
+	return 0;
+}
+
 /*
  * dl_rq:
  *
kernel/sched/pelt.h +6 -0
index afff644da065..52840dbb02ab 100644
@@ -5,6 +5,7 @@ int __update_load_avg_blocked_se(u64 now, struct sched_entity *se);
 int __update_load_avg_se(u64 now, struct cfs_rq *cfs_rq, struct sched_entity *se);
 int __update_load_avg_cfs_rq(u64 now, struct cfs_rq *cfs_rq);
 int update_rt_rq_load_avg(u64 now, struct rq *rq, int running);
+int update_rt_rq_load_avg_ratio(u64 now, u64 contrib_ratio, struct rq *rq, int running);
 int update_dl_rq_load_avg(u64 now, struct rq *rq, int running);
 
 #ifdef CONFIG_HAVE_SCHED_AVG_IRQ
@@ -152,6 +153,11 @@ update_rt_rq_load_avg(u64 now, struct rq *rq, int running)
 	return 0;
 }
 
+int update_rt_rq_load_avg_ratio(u64 now, u64 contrib_ratio, struct rq *rq, int running)
+{
+	return 0;
+}
+
 static inline int
 update_dl_rq_load_avg(u64 now, struct rq *rq, int running)
 {
kernel/sched/rt.c +5 -1
index a532558a5176..a50afb692ce1 100644
@@ -1586,7 +1586,7 @@ pick_next_task_rt(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 	 * utilization. We only care of the case where we start to schedule a
 	 * rt task
 	 */
-	if (rq->curr->sched_class != &rt_sched_class)
+	if (rq->curr->sched_class != &rt_sched_class && rq->curr->sched_class != &microq_sched_class)
 		update_rt_rq_load_avg(rq_clock_pelt(rq), rq, 0);
 
 	return p;
@@ -2371,7 +2371,11 @@ static unsigned int get_rr_interval_rt(struct rq *rq, struct task_struct *task)
 }
 
 const struct sched_class rt_sched_class = {
+#ifdef CONFIG_SCHED_CLASS_MICROQ
+	.next			= &microq_sched_class,
+#else
 	.next			= &fair_sched_class,
+#endif
 	.enqueue_task		= enqueue_task_rt,
 	.dequeue_task		= dequeue_task_rt,
 	.yield_task		= yield_task_rt,
kernel/sched/sched.h +62 -1

99 lines not on this page · raw message

kernel/sysctl.c +23 -0
index 1c1ad1e14f21..aba857c78c2d 100644
@@ -452,6 +452,29 @@ static struct ctl_table kern_table[] = {
 		.mode		= 0644,
 		.proc_handler	= sched_rr_handler,
 	},
+#ifdef CONFIG_SCHED_CLASS_MICROQ
+	{
+		.procname	= "sched_microq_period_ns",
+		.data		= &sysctl_sched_microq_period,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= sched_microq_proc_handler,
+	},
+	{
+		.procname	= "sched_microq_runtime_ns",
+		.data		= &sysctl_sched_microq_runtime,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= sched_microq_proc_handler,
+	},
+	{
+		.procname	= "sched_microq_timeslice",
+		.data		= &sched_microq_timeslice,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= proc_dointvec,
+	},
+#endif
 #ifdef CONFIG_UCLAMP_TASK
 	{
 		.procname	= "sched_util_clamp_min",
Signature · 1 line
2.23.0.187.g17f5b7556c-goog