From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751312AbdBOHkQ (ORCPT ); Wed, 15 Feb 2017 02:40:16 -0500 Received: from mail.santannapisa.it ([193.205.80.99]:33683 "EHLO mail.santannapisa.it" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750760AbdBOHkP (ORCPT ); Wed, 15 Feb 2017 02:40:15 -0500 Date: Wed, 15 Feb 2017 08:40:03 +0100 From: Luca Abeni To: Steven Rostedt Cc: linux-kernel@vger.kernel.org, Ingo Molnar , Peter Zijlstra , Daniel Bristot de Oliveira , Juri Lelli , Tommaso Cucinotta , Mike Galbraith , Romulo Silva de Oliveira Subject: Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow Message-ID: <20170215084003.4d123e5b@luca> In-Reply-To: <20170214191417.4dd96145@gandalf.local.home> References: <20170214142848.4e62a91f@gandalf.local.home> <20170214234926.6b415428@sweethome> <20170214191417.4dd96145@gandalf.local.home> 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 Hi Steven, On Tue, 14 Feb 2017 19:14:17 -0500 Steven Rostedt wrote: [...] > > I am not sure about the correct fix (wouldn't > > "runtime / (deadline - t) > dl_runtime / dl_deadline" allow the > > task to use a fraction of CPU time equal to dl_runtime / > > dl_deadline?) > > > > The current code is clearly wrong (as shown by Daniel), but I do not > > understand how the current check can allow the task to consume more > > than dl_runtime / dl_period... I need some more time to think about > > this issue. > > > > This is in dl_entity_overflow() which is called by update_dl_entity() > which has this: > > 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; > } > > > The comments in this code state: > > * The policy here is that we update the deadline of the entity only > if: > * - the current deadline is in the past, > * - using the remaining runtime with the current deadline would make > * the entity exceed its bandwidth. > > That second comment is saying that when this task woke up, if the > percentage left to run will exceed its bandwidth with the rest of the > system then reset its deadline and its runtime. Right; this is the problem. When the relative deadline is different from the period, the term "bandwidth" is ambiguous... We can consider the utilisation (maximum runtime / period), or the density (maximum runtime / relative deadline). In some sense, the two approaches are both correct (if we use density, we are more pessimistic but we try to respect deadlines in a hard way; if we use utilisation, we allow more tasks to be admitted but we can only provide bounded tardiness). What the current code is doing is to mix the two approaches (resulting in a wrong runtime/deadline assignment). > What happens in the current logic, is that overflow() check says, when > the deadline is much smaller than the period, "yeah, we're going to > exceed our percentage!" so give us more, even though it wont exceed > its percentage if we compared runtime with deadline. > > The relative-runtime / relative-period is a tiny percentage, which > does not reflect the percentage that the task is allowed to have > before the deadline is hit. The tasks bandwidth should be calculated > by the relative-runtime / relative-deadline, as runtime <= deadline > <= period, and the runtime should happen within the deadline. > > When the task wakes up, it currently looks at how much time is left > absolute-deadline - t, and compares it to the amount of runtime left. > The percentage allowed should still be compared with the percentage > between relative-runtime and relative-deadline. The relative-period or > even absolute-period, should have no influence in this decision. Ok, thanks; I think I can now see why this can result in a task consuming more than the reserved utilisation. I still need some time to convince me that "runtime / (deadline - t) > dl_runtime / dl_deadline" is the correct check to use (in this case, shouldn't we also change the admission test to use densities instead of utilisations?) Thanks, Luca