Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S935255AbbDIKLL (ORCPT ); Thu, 9 Apr 2015 06:11:11 -0400 Received: from mail-lb0-f171.google.com ([209.85.217.171]:34045 "EHLO mail-lb0-f171.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S934467AbbDIKLE (ORCPT ); Thu, 9 Apr 2015 06:11:04 -0400 Date: Thu, 9 Apr 2015 12:10:58 +0200 From: Henrik Austad To: Luca Abeni Cc: Luca Abeni , peterz@infradead.org, juri.lelli@gmail.com, raistlin@linux.it, mingo@kernel.org, linux-kernel@vger.kernel.org, linux-doc@vger.kernel.org Subject: Re: [RFC 3/4] Documentation/scheduler/sched-deadline.txt: Some notes on EDF schedulability Message-ID: <20150409101058.GC10954@sisyphus.home.austad.us> References: <1428494380-1917-1-git-send-email-luca.abeni@unitn.it> <1428494380-1917-4-git-send-email-luca.abeni@unitn.it> <20150409090637.GA10954@sisyphus.home.austad.us> <552647AD.3040807@unitn.it> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <552647AD.3040807@unitn.it> User-Agent: Mutt/1.5.21 (2010-09-15) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 6527 Lines: 142 On Thu, Apr 09, 2015 at 11:34:37AM +0200, Luca Abeni wrote: > Hi Henrik, > > On 04/09/2015 11:06 AM, Henrik Austad wrote: > >On Wed, Apr 08, 2015 at 01:59:39PM +0200, Luca Abeni wrote: > [...] > >Also, density is equivalent > >to 'utilization', right? (which is referred to in sec 4.1 > No; the utilisation of task i (generally indicated as "U_i") is WCET_i / P_i (this > is explained earlier in the document); its density is WCET_i / min{P_i,D_i}. ah, yes, you're right of course. Don't mind my inane ramblings here then :) > >So you could rewrite this to something like this > > > > U_i = WCET_i ( min{D_i, P_i) > > U = sum U_i > > > >(or use \delta which is the normal symbol for density iirc) > Well, I already defined "total utilisation" earlier in the document, but without associating > a symbol like "U" to it. I can add "U = sum U_i" and "\delta = sum WCET_i / min{D_i, P_i)" and > use these symbols instead of repeating the sum. > > > >>+ It is important to notice that this condition is only sufficient, and not > >>+ necessary: there are task sets that are schedulable, but do not respect the > >>+ condition. For example, consider the task set {Task_1,Task_2} composed by > >>+ Task_1 with period P_1=100ms, relative deadline D_1=50ms and worst case > >>+ execution time WCET_1=50ms, and Task_2 with period P_2=100ms, relative > >>+ deadline D_2=100ms and worst case execution time WCET_2=10ms. > > > >We need a better way of describing a set of tasks in this text. > Yes, after re-reading the sentence I agree :) > > > >what about adding something like this to the start of Sec. 2? > > > >@@ -43,7 +43,13 @@ CONTENTS > > "deadline", to schedule tasks. A SCHED_DEADLINE task should receive > > "runtime" microseconds of execution time every "period" microseconds, and > > these "runtime" microseconds are available within "deadline" microseconds > >- from the beginning of the period. In order to implement this behaviour, > >+ from the beginning of the period. > >+ > >+ We can the describe a task in a concise manner: > >+ > >+ T_i = {period, WCET, deadline} > >+ > >+ In order to implement this behaviour, > Notice that these "period" and "runtime" are different things respect to the > task period and WCET described in Section 3 (the relationship between them is > explained at the end of Section 3: "Finally, it is important to understand the > relationship..."). Ok. I understood runtime as the dynamic value being managed by the scheduler and should never exceed WCET (or being set to WCET upon release and task preemption when runtime==0). I'll read through the entire thing carefully methinks > But at the beginning of Section 3, after defining WCET, P and D I can add a sentence > like the one you propose: > "A real-time task Task_i can be described concisely as > Task_i = (WCET_i, D_i, P_i) > " > (I used "Task_i" instead of "T_i" in order to avoid the "T_i <-> P_i" confusion > mentioned in previous emails) See! I'm not even consistent with my own naming. (aren't you glad you sent me these patches?) > >Then you can rewrite the task-description to be much more concise (and less > >verbose): > > > > T_1 = {100, 50, 50} > > T_2 = {100, 10, 100} > Agreed (only, I think in literature it is more common to use the WCET as a first > element of the triplet). Hmm, could be, I was sure it was period - as long as we're consistent I don't really care. I'd just like a more concise way of describing tasks. Use it the same order as in struct sched_dl_entity perhaps? (which is runtime, deadline, period)? > >>+ EDF is clearly able to schedule the two tasks without missing any deadline > >>+ (Task_1 is scheduled as soon as it is released, and finishes just in time > >>+ to respect its deadline; Task_2 is scheduled immediately after Task_1, hence > >>+ its response time cannot be larger than 50ms + 10ms = 60ms) even if > >>+ 50 / min{50,100} + 10 / min{100, 100} = 50 / 50 + 10 / 100 = 1.1 > >>+ Of course it is possible to test the exact schedulability of tasks with > >>+ D_i != P_i (checking a condition that is both sufficient and necessary), > >>+ but this cannot be done by comparing the total utilisation or density with > >>+ a constant. Instead, the so called "processor demand" approach can be used, > >>+ computing the total amount of CPU time h(t) needed by all the tasks to > >>+ respect all of their deadlines in a time interval of size t, and comparing > >>+ such a time with the interval size t. If for all values of t h(t) < t, then > > > > For all values of h(t'), t' < t ? > No, it is really "for all values of t, h(t) < t" (meaning that h(t) - the demanded > CPU time - should be smaller than t - the size of the time interval - for every > possible value of t). I realize the current text can be confusing and should > be reworded... Any suggestions? aaah, I read 't' as "a point in time", but 't' here is a _relative_ value, starting at offset X. *gah* this is getting messy. so, basically h(t) is defined as the length of the interval [0,t) (assuming we start at time 0..) Then I understand what you mean and then it makes more sense :) > >>+ EDF is able to schedule the tasks respecting all of their deadlines. Since > >>+ performing this check for all possible values of t is impossible, it has been > >>+ proven[4,5,6] that it is sufficient to perform the test for values of t > >>+ between 0 and a maximum value L. The cited papers contain all of the > >>+ mathematical details and explain how to compute h(t) and L. > >>+ In any case, this kind of analysis is too complex to be performed as an > > > >as well as too time-consuming to be perfomred on-line. > Ok. > > > >You could add a note stating that this can be computed offline for a small > >(and static) set of tasks, but I guess it doesn't really matter. Those with > >hard-rt requirements will (hopefully know what EDF is and is not capable > >of doing). > Well, my idea was that this text should be some kind of "quick introduction to > real-time scheduling" for people who do not know too much in advance... I'll > add a note about the fact that the admission test can be executed offline (for > static task sets). You're right, let's not add more text to this than absolutely needed. -- Henrik Austad -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/