Re: [PATCH] sched/fair: Introduce priority load balance for CFS

From: Vincent Guittot
Date: Thu Nov 03 2022 - 05:24:17 EST

Next message: Marek Szyprowski: "Re: [PATCH 1/3] arm64: exynos: Add new compatible string for Exynos3250 SoC."
Previous message: Paolo Abeni: "Re: [PATCH v3 1/1] net: fec: add initial XDP support"
In reply to: Song Zhang: "Re: [PATCH] sched/fair: Introduce priority load balance for CFS"
Next in thread: Song Zhang: "Re: [PATCH] sched/fair: Introduce priority load balance for CFS"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

On Thu, 3 Nov 2022 at 10:20, Song Zhang <zhangsong34@xxxxxxxxxx> wrote:
>
>
>
> On 2022/11/3 16:33, Vincent Guittot wrote:
> > On Thu, 3 Nov 2022 at 04:01, Song Zhang <zhangsong34@xxxxxxxxxx> wrote:
> >>
> >> 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.
> >
> > What I mean is that migrating non idle tasks first is not a universal
> > win and not always what we want.
> >
>
> But migrating online tasks first is mostly a trade-off that
> non-idle(Latency Sensitive) tasks can obtain more CPU time and minimize
> the interference caused by IDLE tasks. I think this makes sense in most
> cases, or you can point out what else I need to think about it ?
>
> Best regards.
>
> >>
> >>>>
> >>>> 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:
> >
> > How can you care about latency when you start 10 workers on 8 vCPUs
> > with 5000 non idle threads ?
> >
>
> No no no... spawn 5000 idle(SCHED_IDLE) processes not 5000 non-idle
> threads, and with 10 non-idle schbench workers on 8 vCPUs.

yes spawn 5000 idle tasks but my point remains the same

>
> >>
> >> $ 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
> >>>>
> >>> .
> > .

Next message: Marek Szyprowski: "Re: [PATCH 1/3] arm64: exynos: Add new compatible string for Exynos3250 SoC."
Previous message: Paolo Abeni: "Re: [PATCH v3 1/1] net: fec: add initial XDP support"
In reply to: Song Zhang: "Re: [PATCH] sched/fair: Introduce priority load balance for CFS"
Next in thread: Song Zhang: "Re: [PATCH] sched/fair: Introduce priority load balance for CFS"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]