linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Odin Ugedal <odin@uged.al>
To: Huaixin Chang <changhuaixin@linux.alibaba.com>
Cc: luca.abeni@santannapisa.it, anderson@cs.unc.edu,
	baruah@wustl.edu, Benjamin Segall <bsegall@google.com>,
	Dietmar Eggemann <dietmar.eggemann@arm.com>,
	dtcccc@linux.alibaba.com, Juri Lelli <juri.lelli@redhat.com>,
	khlebnikov@yandex-team.ru,
	open list <linux-kernel@vger.kernel.org>,
	Mel Gorman <mgorman@suse.de>, Ingo Molnar <mingo@redhat.com>,
	Odin Ugedal <odin@uged.al>,
	pauld@redhead.com, Peter Zijlstra <peterz@infradead.org>,
	Paul Turner <pjt@google.com>,
	Steven Rostedt <rostedt@goodmis.org>,
	Shanpei Chen <shanpeic@linux.alibaba.com>,
	Tejun Heo <tj@kernel.org>,
	tommaso.cucinotta@santannapisa.it,
	Vincent Guittot <vincent.guittot@linaro.org>,
	xiyou.wangcong@gmail.com
Subject: Re: [PATCH v6 1/3] sched/fair: Introduce the burstable CFS controller
Date: Tue, 22 Jun 2021 17:27:30 +0200	[thread overview]
Message-ID: <CAFpoUr1Q-DuvXhPtX=bNdjg6xVcyBF=Qm8kz+HG7pGtNtu9X4A@mail.gmail.com> (raw)
In-Reply-To: <20210621092800.23714-2-changhuaixin@linux.alibaba.com>

Hi,

Just some more thoughts.

man. 21. jun. 2021 kl. 11:28 skrev Huaixin Chang
<changhuaixin@linux.alibaba.com>:
>
> The CFS bandwidth controller limits CPU requests of a task group to
> quota during each period. However, parallel workloads might be bursty
> so that they get throttled even when their average utilization is under
> quota. And they are latency sensitive at the same time so that
> throttling them is undesired.
>
> We borrow time now against our future underrun, at the cost of increased
> interference against the other system users. All nicely bounded.
>
> Traditional (UP-EDF) bandwidth control is something like:
>
>   (U = \Sum u_i) <= 1
>
> This guaranteeds both that every deadline is met and that the system is
> stable. After all, if U were > 1, then for every second of walltime,
> we'd have to run more than a second of program time, and obviously miss
> our deadline, but the next deadline will be further out still, there is
> never time to catch up, unbounded fail.
>
> This work observes that a workload doesn't always executes the full
> quota; this enables one to describe u_i as a statistical distribution.
>
> For example, have u_i = {x,e}_i, where x is the p(95) and x+e p(100)
> (the traditional WCET). This effectively allows u to be smaller,
> increasing the efficiency (we can pack more tasks in the system), but at
> the cost of missing deadlines when all the odds line up. However, it
> does maintain stability, since every overrun must be paired with an
> underrun as long as our x is above the average.
>
> That is, suppose we have 2 tasks, both specify a p(95) value, then we
> have a p(95)*p(95) = 90.25% chance both tasks are within their quota and
> everything is good. At the same time we have a p(5)p(5) = 0.25% chance
> both tasks will exceed their quota at the same time (guaranteed deadline
> fail). Somewhere in between there's a threshold where one exceeds and
> the other doesn't underrun enough to compensate; this depends on the
> specific CDFs.
>
> At the same time, we can say that the worst case deadline miss, will be
> \Sum e_i; that is, there is a bounded tardiness (under the assumption
> that x+e is indeed WCET).
>
> The benefit of burst is seen when testing with schbench. Default value of
> kernel.sched_cfs_bandwidth_slice_us(5ms) and CONFIG_HZ(1000) is used.
>
>         mkdir /sys/fs/cgroup/cpu/test
>         echo $$ > /sys/fs/cgroup/cpu/test/cgroup.procs
>         echo 100000 > /sys/fs/cgroup/cpu/test/cpu.cfs_quota_us
>         echo 100000 > /sys/fs/cgroup/cpu/test/cpu.cfs_burst_us
>
>         ./schbench -m 1 -t 3 -r 20 -c 80000 -R 10
>
> The average CPU usage is at 80%. I run this for 10 times, and got long tail
> latency for 6 times and got throttled for 8 times.

I don't think this is the best example of the benefit given by burst.
If you double the period, to 200ms, all throttling is mitigated for this
example. Doubling the period is ~the same as having burst=quota (not 100%)
the same. It would be interesting to also see other workloads referred to here,
and how they behave with a double in period vs "100%" burst. (eg. 50% burst
is the ~the same as going from 100ms period to 150%).

The same way, using a 50ms period and 100% burst would cause throttling
here as well.

For certain workloads using about 100% of their quota constantly, then a short
burst over, would certainly benefit from this. However, those workloads should
then probably have a higher quota as well, also mitigating that problem, unless
we want it to be throttled.

Timing issues for refilling the cfs_b can also cause some throttling, and
naturally giving more runtime will "fix" those issues, but I think there
are better ways of solving it than adding new APIs.


Overall, my biggest issue with this approach is that it would be hard for users
to reason about what burst is, and what it "fixes", especially compared to
the period length. I think a lot of people would benefit from using longer
periods than 100ms when they have way more processes than the ratio between
the quota and the period. I therefore think it would be best to use examples
for when to use burst where a period change would not fix the issue.


> Tail latencies are shown below, and it wasn't the worst case.
>
>         Latency percentiles (usec)
>                 50.0000th: 19872
>                 75.0000th: 21344
>                 90.0000th: 22176
>                 95.0000th: 22496
>                 *99.0000th: 22752
>                 99.5000th: 22752
>                 99.9000th: 22752
>                 min=0, max=22727
>         rps: 9.90 p95 (usec) 22496 p99 (usec) 22752 p95/cputime 28.12% p99/cputime 28.44%
>
> The interferenece when using burst is valued by the possibilities for
> missing the deadline and the average WCET. Test results showed that when
> there many cgroups or CPU is under utilized, the interference is
> limited. More details are shown in:
> https://lore.kernel.org/lkml/5371BD36-55AE-4F71-B9D7-B86DC32E3D2B@linux.alibaba.com/
>
> Co-developed-by: Shanpei Chen <shanpeic@linux.alibaba.com>
> Signed-off-by: Shanpei Chen <shanpeic@linux.alibaba.com>
> Co-developed-by: Tianchen Ding <dtcccc@linux.alibaba.com>
> Signed-off-by: Tianchen Ding <dtcccc@linux.alibaba.com>
> Signed-off-by: Huaixin Chang <changhuaixin@linux.alibaba.com>
> ---

Anyways, this should also probably scale burst together with period and quota
when the period is too short. Something like the diff below, as well as
updating the message.


Thanks
Odin


diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index bfaa6e1f6067..ab809bd11785 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -5277,6 +5277,7 @@ static enum hrtimer_restart
sched_cfs_period_timer(struct hrtimer *timer)
                        if (new < max_cfs_quota_period) {
                                cfs_b->period = ns_to_ktime(new);
                                cfs_b->quota *= 2;
+                               cfs_b->burst *= 2;

                                pr_warn_ratelimited(
        "cfs_period_timer[cpu%d]: period too short, scaling up (new
cfs_period_us = %lld, cfs_quota_us = %lld)\n",

  parent reply	other threads:[~2021-06-22 15:28 UTC|newest]

Thread overview: 17+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-06-21  9:27 [PATCH v6 0/3] sched/fair: Burstable CFS bandwidth controller Huaixin Chang
2021-06-21  9:27 ` [PATCH v6 1/3] sched/fair: Introduce the burstable CFS controller Huaixin Chang
2021-06-22 13:19   ` Peter Zijlstra
2021-06-22 18:57     ` Benjamin Segall
2021-06-24  8:48     ` changhuaixin
2021-06-24  9:28       ` Peter Zijlstra
2021-06-22 15:27   ` Odin Ugedal [this message]
2021-06-23  8:47     ` Peter Zijlstra
2021-06-24  8:45     ` changhuaixin
2021-06-24  7:39   ` [tip: sched/core] " tip-bot2 for Huaixin Chang
2021-06-21  9:27 ` [PATCH v6 2/3] sched/fair: Add cfs bandwidth burst statistics Huaixin Chang
2021-06-28 15:00   ` Peter Zijlstra
2021-06-28 15:12     ` Peter Zijlstra
2021-07-02 11:31     ` changhuaixin
2021-06-21  9:28 ` [PATCH v6 3/3] sched/fair: Add document for burstable CFS bandwidth Huaixin Chang
2021-06-22 15:26   ` Odin Ugedal
2021-06-22 14:25 ` [PATCH v6 0/3] sched/fair: Burstable CFS bandwidth controller Tejun Heo

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='CAFpoUr1Q-DuvXhPtX=bNdjg6xVcyBF=Qm8kz+HG7pGtNtu9X4A@mail.gmail.com' \
    --to=odin@uged.al \
    --cc=anderson@cs.unc.edu \
    --cc=baruah@wustl.edu \
    --cc=bsegall@google.com \
    --cc=changhuaixin@linux.alibaba.com \
    --cc=dietmar.eggemann@arm.com \
    --cc=dtcccc@linux.alibaba.com \
    --cc=juri.lelli@redhat.com \
    --cc=khlebnikov@yandex-team.ru \
    --cc=linux-kernel@vger.kernel.org \
    --cc=luca.abeni@santannapisa.it \
    --cc=mgorman@suse.de \
    --cc=mingo@redhat.com \
    --cc=pauld@redhead.com \
    --cc=peterz@infradead.org \
    --cc=pjt@google.com \
    --cc=rostedt@goodmis.org \
    --cc=shanpeic@linux.alibaba.com \
    --cc=tj@kernel.org \
    --cc=tommaso.cucinotta@santannapisa.it \
    --cc=vincent.guittot@linaro.org \
    --cc=xiyou.wangcong@gmail.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).