lkml.org 
[lkml]   [2022]   [Sep]   [29]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
Date
SubjectRe: [RFC PATCH] sched/fair: Choose the CPU where short task is running during wake up
On Thu, 15 Sept 2022 at 18:54, Chen Yu <yu.c.chen@intel.com> wrote:
>
> [Background]
> At LPC 2022 Real-time and Scheduling Micro Conference we presented
> the cross CPU wakeup issue. This patch is a text version of the
> talk, and hopefully we can clarify the problem and appreciate for any
> feedback.
>
> [re-send due to the previous one did not reach LKML, sorry
> for any inconvenience.]
>
> [Problem Statement]
> For a workload that is doing frequent context switches, the throughput
> scales well until the number of instances reaches a peak point. After
> that peak point, the throughput drops significantly if the number of
> instances continues to increase.
>
> The will-it-scale context_switch1 test case exposes the issue. The
> test platform has 112 CPUs per LLC domain. The will-it-scale launches
> 1, 8, 16 ... 112 instances respectively. Each instance is composed
> of 2 tasks, and each pair of tasks would do ping-pong scheduling via
> pipe_read() and pipe_write(). No task is bound to any CPU.
> We found that, once the number of instances is higher than
> 56(112 tasks in total, every CPU has 1 task), the throughput
> drops accordingly if the instance number continues to increase:
>
> ^
> throughput|
> | X
> | X X X
> | X X X
> | X X
> | X X
> | X
> | X
> | X
> | X
> |
> +-----------------.------------------->
> 56
> number of instances
>
> [Symptom analysis]
> Both perf profile and lockstat have shown that, the bottleneck
> is the runqueue spinlock. Take perf profile for example:
>
> nr_instance rq lock percentage
> 1 1.22%
> 8 1.17%
> 16 1.20%
> 24 1.22%
> 32 1.46%
> 40 1.61%
> 48 1.63%
> 56 1.65%
> --------------------------
> 64 3.77% |
> 72 5.90% | increase
> 80 7.95% |
> 88 9.98% v
> 96 11.81%
> 104 13.54%
> 112 15.13%
>
> And the rq lock bottleneck is composed of two paths(perf profile):
>
> (path1):
> raw_spin_rq_lock_nested.constprop.0;
> try_to_wake_up;
> default_wake_function;
> autoremove_wake_function;
> __wake_up_common;
> __wake_up_common_lock;
> __wake_up_sync_key;
> pipe_write;
> new_sync_write;
> vfs_write;
> ksys_write;
> __x64_sys_write;
> do_syscall_64;
> entry_SYSCALL_64_after_hwframe;write
>
> (path2):
> raw_spin_rq_lock_nested.constprop.0;
> __sched_text_start;
> schedule_idle;
> do_idle;
> cpu_startup_entry;
> start_secondary;
> secondary_startup_64_no_verify
>
> The idle percentage is around 30% when there are 112 instances:
> %Cpu0 : 2.7 us, 66.7 sy, 0.0 ni, 30.7 id
>
> As a comparison, if we set CPU affinity to these workloads,
> which stops them from migrating among CPUs, the idle percentage
> drops to nearly 0%, and the throughput increases by about 300%.
> This indicates that there is room for optimization.
>
> A possible scenario to describe the lock contention:
> task A tries to wakeup task B on CPU1, then task A grabs the
> runqueue lock of CPU1. If CPU1 is about to quit idle, it needs
> to grab its own lock which has been taken by someone else. Then
> CPU1 takes more time to quit which hurts the performance.
>
> TTWU_QUEUE could mitigate the cross CPU runqueue lock contention.
> Since commit f3dd3f674555 ("sched: Remove the limitation of WF_ON_CPU
> on wakelist if wakee cpu is idle"), TTWU_QUEUE offloads the work from
> the waker and leverages the idle CPU to queue the wakee. However, a long
> idle duration is still observed. The idle task spends quite some time
> on sched_ttwu_pending() before it switches out. This long idle
> duration would mislead SIS_UTIL, then SIS_UTIL suggests the waker scan
> for more CPUs. The time spent searching for an idle CPU would make
> wakee waiting for more time, which in turn leads to more idle time.
> The NEWLY_IDLE balance fails to pull tasks to the idle CPU, which
> might be caused by no runnable wakee being found.
>
> [Proposal]
> If a system is busy, and if the workloads are doing frequent context
> switches, it might not be a good idea to spread the wakee on different
> CPUs. Instead, consider the task running time and enhance wake affine
> might be applicable.
>
> This idea has been suggested by Rik at LPC 2019 when discussing
> the latency nice. He asked the following question: if P1 is a small-time
> slice task on CPU, can we put the waking task P2 on the CPU and wait for
> P1 to release the CPU, without wasting time to search for an idle CPU?
> At LPC 2021 Vincent Guittot has proposed:
> 1. If the wakee is a long-running task, should we skip the short idle CPU?
> 2. If the wakee is a short-running task, can we put it onto a lightly loaded
> local CPU?

When I said that, I had in mind to use the task utilization (util_avg
or util_est) which reflects the recent behavior of the task but not to
compute an average duration

>
> Current proposal is a variant of 2:
> If the target CPU is running a short-time slice task, and the wakee
> is also a short-time slice task, the target CPU could be chosen as the
> candidate when the system is busy.
>
> The definition of a short-time slice task is: The average running time
> of the task during each run is no more than sysctl_sched_min_granularity.
> If a task switches in and then voluntarily relinquishes the CPU
> quickly, it is regarded as a short-running task. Choosing
> sysctl_sched_min_granularity because it is the minimal slice if there
> are too many runnable tasks.
>
> Reuse the nr_idle_scan of SIS_UTIL to decide if the system is busy.
> If yes, then a compromised "idle" CPU might be acceptable.
>
> The reason is that, if the waker is a short running task, it might
> relinquish the CPU soon, the wakee has the chance to be scheduled.
> On the other hand, if the wakee is also a short-running task, the
> impact it brings to the target CPU is small. If the system is
> already busy, maybe we could lower the bar to find an idle CPU.
> The effect is, the wake affine is enhanced.
>
> [Benchmark results]
> The baseline is 6.0-rc4.
>
> The throughput of will-it-scale.context_switch1 has been increased by
> 331.13% with this patch applied.
>
> netperf
> =======
> case load baseline(std%) compare%( std%)
> TCP_RR 28 threads 1.00 ( 0.57) +0.29 ( 0.59)
> TCP_RR 56 threads 1.00 ( 0.49) +0.43 ( 0.43)
> TCP_RR 84 threads 1.00 ( 0.34) +0.24 ( 0.34)
> TCP_RR 112 threads 1.00 ( 0.26) +1.57 ( 0.20)
> TCP_RR 140 threads 1.00 ( 0.20) +178.05 ( 8.83)
> TCP_RR 168 threads 1.00 ( 10.14) +0.87 ( 10.03)
> TCP_RR 196 threads 1.00 ( 13.51) +0.90 ( 11.84)
> TCP_RR 224 threads 1.00 ( 7.12) +0.66 ( 8.28)
> UDP_RR 28 threads 1.00 ( 0.96) -0.10 ( 0.97)
> UDP_RR 56 threads 1.00 ( 10.93) +0.24 ( 0.82)
> UDP_RR 84 threads 1.00 ( 8.99) +0.40 ( 0.71)
> UDP_RR 112 threads 1.00 ( 0.15) +0.72 ( 7.77)
> UDP_RR 140 threads 1.00 ( 11.11) +135.81 ( 13.86)
> UDP_RR 168 threads 1.00 ( 12.58) +147.63 ( 12.72)
> UDP_RR 196 threads 1.00 ( 19.47) -0.34 ( 16.14)
> UDP_RR 224 threads 1.00 ( 12.88) -0.35 ( 12.73)
>
> hackbench
> =========
> case load baseline(std%) compare%( std%)
> process-pipe 1 group 1.00 ( 1.02) +0.14 ( 0.62)
> process-pipe 2 groups 1.00 ( 0.73) +0.29 ( 0.51)
> process-pipe 4 groups 1.00 ( 0.16) +0.24 ( 0.31)
> process-pipe 8 groups 1.00 ( 0.06) +11.56 ( 0.11)
> process-sockets 1 group 1.00 ( 1.59) +0.06 ( 0.77)
> process-sockets 2 groups 1.00 ( 1.13) -1.86 ( 1.31)
> process-sockets 4 groups 1.00 ( 0.14) +1.76 ( 0.29)
> process-sockets 8 groups 1.00 ( 0.27) +2.73 ( 0.10)
> threads-pipe 1 group 1.00 ( 0.43) +0.83 ( 2.20)
> threads-pipe 2 groups 1.00 ( 0.52) +1.03 ( 0.55)
> threads-pipe 4 groups 1.00 ( 0.44) -0.08 ( 0.31)
> threads-pipe 8 groups 1.00 ( 0.04) +11.86 ( 0.05)
> threads-sockets 1 groups 1.00 ( 1.89) +3.51 ( 0.57)
> threads-sockets 2 groups 1.00 ( 0.04) -1.12 ( 0.69)
> threads-sockets 4 groups 1.00 ( 0.14) +1.77 ( 0.18)
> threads-sockets 8 groups 1.00 ( 0.03) +2.75 ( 0.03)
>
> tbench
> ======
> case load baseline(std%) compare%( std%)
> loopback 28 threads 1.00 ( 0.08) +0.51 ( 0.25)
> loopback 56 threads 1.00 ( 0.15) -0.89 ( 0.16)
> loopback 84 threads 1.00 ( 0.03) +0.35 ( 0.07)
> loopback 112 threads 1.00 ( 0.06) +2.84 ( 0.01)
> loopback 140 threads 1.00 ( 0.07) +0.69 ( 0.11)
> loopback 168 threads 1.00 ( 0.09) +0.14 ( 0.18)
> loopback 196 threads 1.00 ( 0.04) -0.18 ( 0.20)
> loopback 224 threads 1.00 ( 0.25) -0.37 ( 0.03)
>
> Other benchmarks are under testing.
>
> This patch is more about enhancing the wake affine, rather than improving
> the SIS efficiency, so Mel's SIS statistic patch was not deployed for now.
>
> [Limitations]
> When the number of CPUs suggested by SIS_UTIL is lower than 60% of the LLC
> CPUs, the LLC domain is regarded as relatively busy. However, the 60% is
> somewhat hacky, because it indicates that the util_avg% is around 50%,
> a half busy LLC. I don't have other lightweight/accurate method in mind to
> check if the LLC domain is busy or not.
>
> [Misc]
> At LPC we received useful suggestions. The first one is that we should look at
> the time from the task is woken up, to the time the task goes back to sleep.
> I assume this is aligned with what is proposed here - we consider the average
> running time, rather than the total running time. The second one is that we
> should consider the long-running task. And this is under investigation.
>
> Besides, Prateek has mentioned that the SIS_UTIL is unable to deal with
> burst workload. Because there is a delay to reflect the instantaneous
> utilization and SIS_UTIL expects the workload to be stable. If the system
> is idle most of the time, but suddenly the workloads burst, the SIS_UTIL
> overscans. The current patch might mitigate this symptom somehow, as burst
> workload is usually regarded as a short-running task.
>
> Suggested-by: Tim Chen <tim.c.chen@intel.com>
> Signed-off-by: Chen Yu <yu.c.chen@intel.com>
> ---
> kernel/sched/fair.c | 31 ++++++++++++++++++++++++++++++-
> 1 file changed, 30 insertions(+), 1 deletion(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 914096c5b1ae..7519ab5b911c 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -6020,6 +6020,19 @@ static int wake_wide(struct task_struct *p)
> return 1;
> }
>
> +/*
> + * If a task switches in and then voluntarily relinquishes the
> + * CPU quickly, it is regarded as a short running task.
> + * sysctl_sched_min_granularity is chosen as the threshold,
> + * as this value is the minimal slice if there are too many
> + * runnable tasks, see __sched_period().
> + */
> +static int is_short_task(struct task_struct *p)
> +{
> + return (p->se.sum_exec_runtime <=
> + (p->nvcsw * sysctl_sched_min_granularity));

you assume that the task behavior will never change during is whole life time

> +}
> +
> /*
> * The purpose of wake_affine() is to quickly determine on which CPU we can run
> * soonest. For the purpose of speed we only consider the waking and previous
> @@ -6050,7 +6063,8 @@ wake_affine_idle(int this_cpu, int prev_cpu, int sync)
> if (available_idle_cpu(this_cpu) && cpus_share_cache(this_cpu, prev_cpu))
> return available_idle_cpu(prev_cpu) ? prev_cpu : this_cpu;
>
> - if (sync && cpu_rq(this_cpu)->nr_running == 1)
> + if ((sync && cpu_rq(this_cpu)->nr_running == 1) ||
> + is_short_task(cpu_curr(this_cpu)))
> return this_cpu;
>
> if (available_idle_cpu(prev_cpu))
> @@ -6434,6 +6448,21 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, bool
> /* overloaded LLC is unlikely to have idle cpu/core */
> if (nr == 1)
> return -1;
> +
> + /*
> + * If nr is smaller than 60% of llc_weight, it
> + * indicates that the util_avg% is higher than 50%.
> + * This is calculated by SIS_UTIL in
> + * update_idle_cpu_scan(). The 50% util_avg indicates
> + * a half-busy LLC domain. System busier than this
> + * level could lower its bar to choose a compromised
> + * "idle" CPU. If the waker on target CPU is a short
> + * task and the wakee is also a short task, pick
> + * target directly.
> + */
> + if (!has_idle_core && (5 * nr < 3 * sd->span_weight) &&
> + is_short_task(p) && is_short_task(cpu_curr(target)))
> + return target;
> }
> }
>
> --
> 2.25.1
>

\
 
 \ /
  Last update: 2022-09-29 10:04    [W:0.154 / U:0.444 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site