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

[Song Zhang <zhangsong34@xxxxxxxxxx>]

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