Add micro quanta scheduling class
Subsystems (3)
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
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.
--- 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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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 == µq_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 == µq_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
@@ -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
@@ -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
@@ -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 != µq_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 = µq_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
@@ -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