From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754400AbdDLM3W (ORCPT ); Wed, 12 Apr 2017 08:29:22 -0400 Received: from mx1.redhat.com ([209.132.183.28]:41110 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752737AbdDLM3R (ORCPT ); Wed, 12 Apr 2017 08:29:17 -0400 DMARC-Filter: OpenDMARC Filter v1.3.2 mx1.redhat.com 11E387E9F2 Authentication-Results: ext-mx02.extmail.prod.ext.phx2.redhat.com; dmarc=none (p=none dis=none) header.from=redhat.com Authentication-Results: ext-mx02.extmail.prod.ext.phx2.redhat.com; spf=pass smtp.mailfrom=xpang@redhat.com DKIM-Filter: OpenDKIM Filter v2.11.0 mx1.redhat.com 11E387E9F2 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> <58EDBAC4.7020902@redhat.com> <20170412085544.6a54658f@luca> To: Luca Abeni Cc: Daniel Bristot de Oliveira , Xunlei Pang , linux-kernel@vger.kernel.org, Peter Zijlstra , Juri Lelli , Ingo Molnar , Steven Rostedt , Tommaso Cucinotta , =?UTF-8?Q?R=c3=b4mulo_Silva_de_Oliveira?= , Mathieu Poirier From: Xunlei Pang Message-ID: <58EE1DCC.80002@redhat.com> Date: Wed, 12 Apr 2017 20:30:04 +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: <20170412085544.6a54658f@luca> Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: 7bit X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.26]); Wed, 12 Apr 2017 12:29:12 +0000 (UTC) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 04/12/2017 at 02:55 PM, Luca Abeni wrote: > Hi, > > On Wed, 12 Apr 2017 13:27:32 +0800 > Xunlei Pang wrote: > [...] >> The more I read the code, the more I am confused why >> dl_entity_overflow() is needed, if the task is before its deadline, >> just let it run. > Sorry for jumping in this thread; I did not read all of the previous > emails, but I think I can answer this question :) > > dl_entity_overflow() is needed to check if a deadline task that is > waking up can use its current runtime and scheduling deadline without > breaking the guarantees for other deadline tasks. > > If the relative deadline of the tasks is equal to their period, this > check is mathematically correct (and its correctness has been formally > proved in some papers - see for example > http://disi.unitn.it/~abeni/tr-98-01.pdf). Will have a look, thanks for the pointer. > If the relative deadline is different from the period, then the check > is an approximation (and this is the big issue here). I am still not > sure about what is the best thing to do in this case. > >> E.g. For (runtime 2ms, deadline 4ms, period 8ms), >> for some reason was preempted after running a very short time 0.1ms, >> after 0.9ms it was scheduled back and immediately sleep 1ms, when it >> is awakened, remaining runtime is 1.9ms, remaining >> deadline(deadline-now) within this period is 2ms, but >> dl_entity_overflow() is true. However, clearly it can be correctly >> run 1.9ms before deadline comes wthin this period. > Sure, in this case the task can run for 1.9ms before the deadline... > But doing so, it might break the guarantees for other deadline tasks. > This is what the check is trying to avoid. Image this deadline task was preempted after running 0.1ms by another one with an earlier absolute deadline for 1.9ms, after scheduled back it will have the same status (1.9ms remaining runtime, 2ms remaining deadline) under the current implementation. I can hardly figure out the difference, why is wake-up(will check dl_entity_overflow()) so special? > >> We can add a condition in dl_runtime_exceeded(), if its deadline is >> passed, then zero its runtime if positive, and a new period begins. >> >> I did some tests with the following patch, seems it works well, >> please correct me if I am wrong. --- >> kernel/sched/deadline.c | 16 ++++++++++++---- >> 1 file changed, 12 insertions(+), 4 deletions(-) >> >> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c >> index a2ce590..600c530 100644 >> --- a/kernel/sched/deadline.c >> +++ b/kernel/sched/deadline.c >> @@ -498,8 +498,7 @@ 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); >> >> - if (dl_time_before(dl_se->deadline, rq_clock(rq)) || >> - dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) { >> + if (!dl_time_before(rq_clock(rq), dl_se->deadline)) { >> dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline; >> dl_se->runtime = pi_se->dl_runtime; >> } > I think this will break the guarantees for tasks with relative deadline > equal to period (think about a task with runtime 5ms, period 10ms and > relative deadline 10ms... What happens if the task executes for 4.9ms, > then blocks and immediately wakes up?) For your example, dl_se->deadline is after now, the if condition is false, update_dl_entity() actually does nothing, that is, after wake-up, it will carry (5ms-4.9ms)=0.1ms remaining runtime and (10ms-4.9ms)=5.1ms remaining deadline/period, continue within the current period. After running further 0.1ms, will be throttled by the timer in update_curr_dl(). It's actually the original logic, I just removed dl_entity_overflow() condition. Regards, Xunlei > > > Luca > >> @@ -722,13 +721,22 @@ static inline void >> dl_check_constrained_dl(struct sched_dl_entity *dl_se) >> dl_time_before(rq_clock(rq), dl_next_period(dl_se))) { if >> (unlikely(dl_se->dl_boosted || !start_dl_timer(p))) return; >> + >> + if (dl_se->runtime > 0) >> + dl_se->runtime = 0; >> + >> dl_se->dl_throttled = 1; >> } >> } >> >> static >> -int dl_runtime_exceeded(struct sched_dl_entity *dl_se) >> +int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se) >> { >> + if (!dl_time_before(rq_clock(rq), dl_se->deadline)) { >> + if (dl_se->runtime > 0) >> + dl_se->runtime = 0; >> + } >> + >> return (dl_se->runtime <= 0); >> } >> >> @@ -779,7 +787,7 @@ static void update_curr_dl(struct rq *rq) >> dl_se->runtime -= delta_exec; >> >> throttle: >> - if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) { >> + if (dl_runtime_exceeded(rq, dl_se) || dl_se->dl_yielded) { >> dl_se->dl_throttled = 1; >> __dequeue_task_dl(rq, curr, 0); >> if (unlikely(dl_se->dl_boosted || !start_dl_timer(curr)))