Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753348AbdDLNKW (ORCPT ); Wed, 12 Apr 2017 09:10:22 -0400 Received: from mail.santannapisa.it ([193.205.80.98]:51772 "EHLO mail.santannapisa.it" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752961AbdDLNKV (ORCPT ); Wed, 12 Apr 2017 09:10:21 -0400 Date: Wed, 12 Apr 2017 15:10:13 +0200 From: luca abeni To: Xunlei Pang Cc: Daniel Bristot de Oliveira , Xunlei Pang , linux-kernel@vger.kernel.org, Peter Zijlstra , Juri Lelli , Ingo Molnar , Steven Rostedt , Tommaso Cucinotta , =?UTF-8?B?UsO0bXVsbw==?= Silva de Oliveira , Mathieu Poirier Subject: Re: [PATCH] sched/deadline: Throttle a constrained task activated if overflow Message-ID: <20170412151013.2afad8a1@nowhere> In-Reply-To: <58EE1DCC.80002@redhat.com> References: <1491816131-20268-1-git-send-email-xlpang@redhat.com> <4d24b94c-1e57-b82c-ff0f-099157ba5526@redhat.com> <58EDBAC4.7020902@redhat.com> <20170412085544.6a54658f@luca> <58EE1DCC.80002@redhat.com> Organization: Scuola Superiore S.Anna X-Mailer: Claws Mail 3.13.2 (GTK+ 2.24.30; x86_64-pc-linux-gnu) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 5429 Lines: 130 On Wed, 12 Apr 2017 20:30:04 +0800 Xunlei Pang wrote: [...] > > 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. The big difference is that in your first example the task blocks for some time while being the earliest-deadline task (so, the scheduling algorithm would give some execution time to the task, but the task does not use it... So, when the task wakes up, it has to check if now it is too late for using its reserved execution time). On the other hand, in this second example the task is preempted by an earlier-deadline (higher priority) task, so there is no risk to have execution time reserved to the task that the task does not use (if I understand well your examples). > >> 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(). Ok, sorry; I saw you inverted rq_clock(rq) and dl_se->deadline), but I did not notice you added a "!". My fault. In this case, with this change the task cannot consume more than runtime every period (which is good), but it still risks to cause unexpected missed deadlines. (if relative deadline == period, on uni-processor the current algorithm guarantees that the runtime will always be consumed before the scheduling deadline; on multi-processor it guarantees that the runtime will be consumed before a maximum delay from the deadline; with this change, it is not possible to provide this guarantee anymore). Luca > > 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))) >