Re: [PATCH] sched/fair: Introduce priority load balance for CFS
From: Song Zhang
Date: Wed Nov 02 2022 - 23:02:22 EST
Thanks for your reply!
On 2022/11/3 2:01, Vincent Guittot wrote:
On Wed, 2 Nov 2022 at 04:54, Song Zhang <zhangsong34@xxxxxxxxxx> wrote:
This really looks like a v3 of
https://lore.kernel.org/all/20220810015636.3865248-1-zhangsong34@xxxxxxxxxx/
Please keep versioning.
Add a new sysctl interface:
/proc/sys/kernel/sched_prio_load_balance_enabled
We don't want to add more sysctl knobs for the scheduler, we even
removed some. Knob usually means that you want to fix your use case
but the solution doesn't make sense for all cases.
OK, I will remove this knobs later.
0: default behavior
1: enable priority load balance for CFS
For co-location with idle and non-idle tasks, when CFS do load balance,
it is reasonable to prefer migrating non-idle tasks and migrating idle
tasks lastly. This will reduce the interference by SCHED_IDLE tasks
as much as possible.
I don't agree that it's always the best choice to migrate a non-idle task 1st.
CPU0 has 1 non idle task and CPU1 has 1 non idle task and hundreds of
idle task and there is an imbalance between the 2 CPUS: migrating the
non idle task from CPU1 to CPU0 is not the best choice
If the non idle task on CPU1 is running or cache hot, it cannot be
migrated and idle tasks can also be migrated from CPU1 to CPU0. So I
think it does not matter.
Testcase:
- Spawn large number of idle(SCHED_IDLE) tasks occupy CPUs
What do you mean by a large number ?
- Let non-idle tasks compete with idle tasks for CPU time.
Using schbench to test non-idle tasks latency:
$ ./schbench -m 1 -t 10 -r 30 -R 200
How many CPUs do you have ?
OK, some details may not be mentioned.
My virtual machine has 8 CPUs running with a schbench process and 5000
idle tasks. The idle task is a while dead loop process below:
$ cat idle_process.c
int main()
{
int i = 0;
while(1) {
usleep(500);
for(i = 0; i < 1000000; i++);
}
}
You can compile and spawn 5000 idle(SCHED_IDLE) tasks occupying 8 CPUs
and execute schbench command to test it.
Test result:
1.Default behavior
Latency percentiles (usec) runtime 30 (s) (4562 total samples)
50.0th: 62528 (2281 samples)
75.0th: 623616 (1141 samples)
90.0th: 764928 (687 samples)
95.0th: 824320 (225 samples)
*99.0th: 920576 (183 samples)
99.5th: 953344 (23 samples)
99.9th: 1008640 (18 samples)
min=9, max=1074466
2.Enable priority load balance
Latency percentiles (usec) runtime 30 (s) (4391 total samples)
50.0th: 22624 (2204 samples)
75.0th: 48832 (1092 samples)
90.0th: 85376 (657 samples)
95.0th: 113280 (220 samples)
*99.0th: 182528 (175 samples)
99.5th: 206592 (22 samples)
99.9th: 290304 (17 samples)
min=6, max=351815
From percentile details, we see the benefit of priority load balance
that 95% of non-idle tasks latencies stays no more than 113ms, while
But even 113ms seems quite a large number if there is anything else
but 10 schbench workers and a bunch of idle threads that are running.
non-idle tasks latencies has got almost 50% over 600ms if priority
load balance not enabled.
Als have you considered enabling sched_feature LB_MIN ?
I have tried to echo LB_MIN > /sys/kernel/debug/sched/features, but this
feature seems make no sense.
Signed-off-by: Song Zhang <zhangsong34@xxxxxxxxxx>
---
include/linux/sched/sysctl.h | 4 +++
init/Kconfig | 10 ++++++
kernel/sched/core.c | 3 ++
kernel/sched/fair.c | 61 +++++++++++++++++++++++++++++++++++-
kernel/sched/sched.h | 3 ++
kernel/sysctl.c | 11 +++++++
6 files changed, 91 insertions(+), 1 deletion(-)
diff --git a/include/linux/sched/sysctl.h b/include/linux/sched/sysctl.h
index 303ee7dd0c7e..9b3673269ecc 100644
--- a/include/linux/sched/sysctl.h
+++ b/include/linux/sched/sysctl.h
@@ -32,6 +32,10 @@ extern unsigned int sysctl_numa_balancing_promote_rate_limit;
#define sysctl_numa_balancing_mode 0
#endif
+#ifdef CONFIG_SCHED_PRIO_LB
+extern unsigned int sysctl_sched_prio_load_balance_enabled;
+#endif
+
int sysctl_numa_balancing(struct ctl_table *table, int write, void *buffer,
size_t *lenp, loff_t *ppos);
diff --git a/init/Kconfig b/init/Kconfig
index 694f7c160c9c..b0dfe6701218 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -1026,6 +1026,16 @@ config CFS_BANDWIDTH
restriction.
See Documentation/scheduler/sched-bwc.rst for more information.
+config SCHED_PRIO_LB
+ bool "Priority load balance for CFS"
+ depends on SMP
+ default n
+ help
+ This feature enable CFS priority load balance to reduce
+ non-idle tasks latency interferenced by SCHED_IDLE tasks.
+ It prefer migrating non-idle tasks firstly and
+ migrating SCHED_IDLE tasks lastly.
+
config RT_GROUP_SCHED
bool "Group scheduling for SCHED_RR/FIFO"
depends on CGROUP_SCHED
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 5800b0623ff3..9be35431fdd5 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -9731,6 +9731,9 @@ void __init sched_init(void)
rq->max_idle_balance_cost = sysctl_sched_migration_cost;
INIT_LIST_HEAD(&rq->cfs_tasks);
+#ifdef CONFIG_SCHED_PRIO_LB
+ INIT_LIST_HEAD(&rq->cfs_idle_tasks);
+#endif
rq_attach_root(rq, &def_root_domain);
#ifdef CONFIG_NO_HZ_COMMON
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index e4a0b8bd941c..bdeb04324f0c 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -139,6 +139,10 @@ static int __init setup_sched_thermal_decay_shift(char *str)
}
__setup("sched_thermal_decay_shift=", setup_sched_thermal_decay_shift);
+#ifdef CONFIG_SCHED_PRIO_LB
+unsigned int sysctl_sched_prio_load_balance_enabled;
+#endif
+
#ifdef CONFIG_SMP
/*
* For asym packing, by default the lower numbered CPU has higher priority.
@@ -3199,6 +3203,21 @@ static inline void update_scan_period(struct task_struct *p, int new_cpu)
#endif /* CONFIG_NUMA_BALANCING */
+#ifdef CONFIG_SCHED_PRIO_LB
+static void
+adjust_rq_cfs_tasks(
+ void (*list_op)(struct list_head *, struct list_head *),
+ struct rq *rq,
+ struct sched_entity *se)
+{
+ if (sysctl_sched_prio_load_balance_enabled &&
+ task_has_idle_policy(task_of(se)))
+ (*list_op)(&se->group_node, &rq->cfs_idle_tasks);
+ else
+ (*list_op)(&se->group_node, &rq->cfs_tasks);
+}
+#endif
+
static void
account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
@@ -3208,7 +3227,11 @@ account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
struct rq *rq = rq_of(cfs_rq);
account_numa_enqueue(rq, task_of(se));
+#ifdef CONFIG_SCHED_PRIO_LB
+ adjust_rq_cfs_tasks(list_add, rq, se);
+#else
list_add(&se->group_node, &rq->cfs_tasks);
+#endif
}
#endif
cfs_rq->nr_running++;
@@ -7631,7 +7654,11 @@ done: __maybe_unused;
* the list, so our cfs_tasks list becomes MRU
* one.
*/
+#ifdef CONFIG_SCHED_PRIO_LB
+ adjust_rq_cfs_tasks(list_move, rq, &p->se);
+#else
list_move(&p->se.group_node, &rq->cfs_tasks);
+#endif
#endif
if (hrtick_enabled_fair(rq))
@@ -8156,11 +8183,18 @@ static void detach_task(struct task_struct *p, struct lb_env *env)
static struct task_struct *detach_one_task(struct lb_env *env)
{
struct task_struct *p;
+ struct list_head *tasks = &env->src_rq->cfs_tasks;
+#ifdef CONFIG_SCHED_PRIO_LB
+ bool has_detach_idle_tasks = false;
+#endif
lockdep_assert_rq_held(env->src_rq);
+#ifdef CONFIG_SCHED_PRIO_LB
+again:
+#endif
list_for_each_entry_reverse(p,
- &env->src_rq->cfs_tasks, se.group_node) {
+ tasks, se.group_node) {
if (!can_migrate_task(p, env))
continue;
@@ -8175,6 +8209,13 @@ static struct task_struct *detach_one_task(struct lb_env *env)
schedstat_inc(env->sd->lb_gained[env->idle]);
return p;
}
+#ifdef CONFIG_SCHED_PRIO_LB
+ if (sysctl_sched_prio_load_balance_enabled && !has_detach_idle_tasks) {
+ has_detach_idle_tasks = true;
+ tasks = &env->src_rq->cfs_idle_tasks;
+ goto again;
+ }
+#endif
return NULL;
}
@@ -8190,6 +8231,9 @@ static int detach_tasks(struct lb_env *env)
unsigned long util, load;
struct task_struct *p;
int detached = 0;
+#ifdef CONFIG_SCHED_PRIO_LB
+ bool has_detach_idle_tasks = false;
+#endif
lockdep_assert_rq_held(env->src_rq);
@@ -8205,6 +8249,9 @@ static int detach_tasks(struct lb_env *env)
if (env->imbalance <= 0)
return 0;
+#ifdef CONFIG_SCHED_PRIO_LB
+again:
+#endif
while (!list_empty(tasks)) {
/*
* We don't want to steal all, otherwise we may be treated likewise,
@@ -8310,6 +8357,14 @@ static int detach_tasks(struct lb_env *env)
list_move(&p->se.group_node, tasks);
}
+#ifdef CONFIG_SCHED_PRIO_LB
+ if (sysctl_sched_prio_load_balance_enabled &&
+ !has_detach_idle_tasks && env->imbalance > 0) {
+ has_detach_idle_tasks = true;
+ tasks = &env->src_rq->cfs_idle_tasks;
+ goto again;
+ }
+#endif
/*
* Right now, this is one of only two places we collect this stat
* so we can safely collect detach_one_task() stats here rather
@@ -11814,7 +11869,11 @@ static void set_next_task_fair(struct rq *rq, struct task_struct *p, bool first)
* Move the next running task to the front of the list, so our
* cfs_tasks list becomes MRU one.
*/
+#ifdef CONFIG_SCHED_PRIO_LB
+ adjust_rq_cfs_tasks(list_move, rq, se);
+#else
list_move(&se->group_node, &rq->cfs_tasks);
+#endif
}
#endif
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 1644242ecd11..1b831c05ba30 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -1053,6 +1053,9 @@ struct rq {
int online;
struct list_head cfs_tasks;
+#ifdef CONFIG_SCHED_PRIO_LB
+ struct list_head cfs_idle_tasks;
+#endif
struct sched_avg avg_rt;
struct sched_avg avg_dl;
diff --git a/kernel/sysctl.c b/kernel/sysctl.c
index 188c305aeb8b..5fc0f9ffb675 100644
--- a/kernel/sysctl.c
+++ b/kernel/sysctl.c
@@ -2090,6 +2090,17 @@ static struct ctl_table kern_table[] = {
.extra1 = SYSCTL_ONE,
.extra2 = SYSCTL_INT_MAX,
},
+#endif
+#ifdef CONFIG_SCHED_PRIO_LB
+ {
+ .procname = "sched_prio_load_balance_enabled",
+ .data = &sysctl_sched_prio_load_balance_enabled,
+ .maxlen = sizeof(unsigned int),
+ .mode = 0644,
+ .proc_handler = proc_dointvec_minmax,
+ .extra1 = SYSCTL_ZERO,
+ .extra2 = SYSCTL_ONE,
+ },
#endif
{ }
};
--
2.27.0
.