Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752290AbdDLCHi (ORCPT ); Tue, 11 Apr 2017 22:07:38 -0400 Received: from mx1.redhat.com ([209.132.183.28]:36790 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751848AbdDLCHf (ORCPT ); Tue, 11 Apr 2017 22:07:35 -0400 DMARC-Filter: OpenDMARC Filter v1.3.2 mx1.redhat.com 76231C04B948 Authentication-Results: ext-mx07.extmail.prod.ext.phx2.redhat.com; dmarc=none (p=none dis=none) header.from=redhat.com Authentication-Results: ext-mx07.extmail.prod.ext.phx2.redhat.com; spf=pass smtp.mailfrom=xpang@redhat.com DKIM-Filter: OpenDKIM Filter v2.11.0 mx1.redhat.com 76231C04B948 Reply-To: xlpang@redhat.com Subject: Re: [PATCH] sched/deadline: Throttle a constrained task activated if overflow References: <1491816131-20268-1-git-send-email-xlpang@redhat.com> <4d24b94c-1e57-b82c-ff0f-099157ba5526@redhat.com> <58EC6F63.4070708@redhat.com> <58EC8065.6030806@redhat.com> <541883c2-a8bb-0b03-0987-292ee8b2b25e@redhat.com> To: Daniel Bristot de Oliveira , xlpang@redhat.com, linux-kernel@vger.kernel.org Cc: Peter Zijlstra , Juri Lelli , Ingo Molnar , Luca Abeni , Steven Rostedt , Tommaso Cucinotta , =?UTF-8?Q?R=c3=b4mulo_Silva_de_Oliveira?= , Mathieu Poirier From: Xunlei Pang Message-ID: <58ED8C1D.9080402@redhat.com> Date: Wed, 12 Apr 2017 10:08:29 +0800 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.2.0 MIME-Version: 1.0 In-Reply-To: <541883c2-a8bb-0b03-0987-292ee8b2b25e@redhat.com> Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.31]); Wed, 12 Apr 2017 02:07:35 +0000 (UTC) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 6437 Lines: 137 On 04/11/2017 at 05:24 PM, Daniel Bristot de Oliveira wrote: > On 04/11/2017 09:06 AM, Xunlei Pang wrote: >> On 04/11/2017 at 01:53 PM, Xunlei Pang wrote: >>> On 04/11/2017 at 04:47 AM, Daniel Bristot de Oliveira wrote: >>>> On 04/10/2017 11:22 AM, Xunlei Pang wrote: >>>>> I was testing Daniel's changes with his test case in the commit >>>>> df8eac8cafce ("sched/deadline: Throttle a constrained deadline >>>>> task activated after the deadline"), and tweaked it a little. >>>>> >>>>> Instead of having the runtime equal to the deadline, I tweaked >>>>> runtime, deadline and sleep value to ensure every time it calls >>>>> dl_check_constrained_dl() with "dl_se->deadline > rq_clock(rq)" >>>>> as well as true dl_entity_overflow(), so it does replenishing >>>>> every wake up in update_dl_entity(), and break its bandwidth. >>>>> >>>>> Daniel's test case had: >>>>> attr.sched_runtime = 2 * 1000 * 1000; /* 2 ms */ >>>>> attr.sched_deadline = 2 * 1000 * 1000; /* 2 ms*/ >>>>> attr.sched_period = 2 * 1000 * 1000 * 1000; /* 2 s */ >>>>> ts.tv_sec = 0; >>>>> ts.tv_nsec = 2000 * 1000; /* 2 ms */ >>>>> >>>>> I changed it to: >>>>> attr.sched_runtime = 5 * 1000 * 1000; /* 5 ms */ >>>>> attr.sched_deadline = 7 * 1000 * 1000; /* 7 ms */ >>>>> attr.sched_period = 1 * 1000 * 1000 * 1000; /* 1 s */ >>>>> ts.tv_sec = 0; >>>>> ts.tv_nsec = 1000 * 1000; /* 1 ms */ >>>>> >>>>> The change above can result in over 25% of the CPU on my machine. >>>>> >>>>> In order to avoid the beakage, we improve dl_check_constrained_dl() >>>>> to prevent dl tasks from being activated until the next period if it >>>>> runs out of bandwidth of the current period. >>>> The problem now is that, with your patch, we will throttle the task >>>> with some possible runtime. Moreover, the task did not brake any >>>> rule, like being awakened after the deadline - the user-space is not >>>> misbehaving. >>>> >>>> That is +- what the reproducer is doing when using your patch, >>>> (I put some trace_printk when noticing the overflow in the wakeup). >>>> >>>> -0 [007] d.h. 1505.066439: enqueue_task_dl: my current runtime is 3657361 and the deadline is 4613027 from now >>>> -0 [007] d.h. 1505.066439: enqueue_task_dl: my dl_runtime is 5000000 >>>> >>>> and so the task will be throttled with 3657361 ns runtime available. >>>> >>>> As we can see, it is really breaking the density: >>>> >>>> 5ms / 7ms (.714285) < 3657361 / 4613027 (.792833) >>>> >>>> Well, it is not breaking that much. Trying to be less pessimist, we can >>>> compute a new runtime with following equation: >>>> >>>> runtime = (dl_runtime / dl_deadline) * (deadline - now) >>>> >>>> That is, a runtime which fits in the task's density. >>> This is a good point, to make the best use of remaining deadline, let me think more. >> I don't know if this will make things more complicated, we can see in update_dl_entity(): >> if (dl_time_before(dl_se->deadline, rq_clock(rq)) || >> dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) { >> dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline; >> dl_se->runtime = pi_se->dl_runtime; >> } >> >> Looks like we have similar issue for non-constrained tasks in case of true dl_entity_overflow(), although >> its deadline is promoted(BTW, I think when overflow it should be dl_se->deadline += pi_se->dl_deadline?), >> the previous runtime is discarded, we may need to apply the same runtime truncating logic on it as well >> if we want to truncate runtime. > For implicit deadline, the density is equals to the utilization. > So things here are less pessimistic, and we are using the same > rule for overflow and admission. > > If you push "dl_se->deadline += pi_se->dl_deadline", you will give > > runtime / (deadline - now) + period. > > runtime. > > As the deadline is in the future, (the !dl_time_before(dl_se->deadline, > rq_clock(rq)), then (deadline - now) + period > period. Therefore, the > next period will receive less than runtime / period & the task will > receive a lower priority - a farther deadline. Yes, I think I got your meaning, thanks for the detailed explanation. This is indeed an issue, that's why I suggested to do truncate here as well. But in the current implementation, promote deadline to "clock + pi_se->dl_deadline", will cause overlapping between periods, kind of like [ period n ] [ period n+1 ] the overlapped time window is (deadline -now), is this a problem? > > Well, we could not to truncate the runtime, but than we would carry > things from the past. If the task self-suspended for a long > period, the sum of the residual runtime + runtime could give > a higher utilization than Q/P. > > Moreover, the current rule provides a guarantee that Tommaso likes. > The CBS self-adjusts the period in the case of a timing drift of the > external "event" that activates the task, without breaking Q/P. > > (He can explain more about it....) Anyway implicit deadline has the same issue, image in update_dl_entity() when "deadline > rq_clock" and true dl_entity_overflow(), it can run part of dl_se->runtime within (dl_se->deadline - rq_clock), no? what do you think we truncate runtime in the common update_dl_entity()? Like: diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c index a2ce590..e92aad6 100644 --- a/kernel/sched/deadline.c +++ b/kernel/sched/deadline.c @@ -497,11 +497,21 @@ static void update_dl_entity(struct sched_dl_entity *dl_se, { struct dl_rq *dl_rq = dl_rq_of_se(dl_se); struct rq *rq = rq_of_dl_rq(dl_rq); + u64 clock = rq_clock(rq); - if (dl_time_before(dl_se->deadline, rq_clock(rq)) || - dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) { - dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline; + if (!dl_time_before(clock, dl_se->deadline)) { + dl_se->deadline = clock + pi_se->dl_deadline; dl_se->runtime = pi_se->dl_runtime; + return; + } + + /* Truncate the runtime to fit the density in the current period after overflow. */ + if (dl_entity_overflow(dl_se, pi_se, clock)) { + unsigned long ratio; + + /* TODO: save the quotient in a variable like dl_se->dl_bw */ + ratio = to_ratio(pi_se->dl_deadline, pi_se->dl_runtime); + dl_se->runtime = (ratio * (dl_se->deadline - clock)) >> 20; } }