Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S934024AbbDIJGx (ORCPT ); Thu, 9 Apr 2015 05:06:53 -0400 Received: from mail-la0-f47.google.com ([209.85.215.47]:35936 "EHLO mail-la0-f47.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S932926AbbDIJGo (ORCPT ); Thu, 9 Apr 2015 05:06:44 -0400 Date: Thu, 9 Apr 2015 11:06:38 +0200 From: Henrik Austad To: Luca Abeni Cc: peterz@infradead.org, juri.lelli@gmail.com, raistlin@linux.it, mingo@kernel.org, linux-kernel@vger.kernel.org, linux-doc@vger.kernel.org, Luca Abeni Subject: Re: [RFC 3/4] Documentation/scheduler/sched-deadline.txt: Some notes on EDF schedulability Message-ID: <20150409090637.GA10954@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> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1428494380-1917-4-git-send-email-luca.abeni@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: 8693 Lines: 133 On Wed, Apr 08, 2015 at 01:59:39PM +0200, Luca Abeni wrote: > Add a short discussion about sufficient and necessary schedulability tests, > and a simple example showing that if D_i != P_i then density based tests > are only sufficient. > Also add some references to scientific papers on schedulability tests for > EDF that are both necessary and sufficient, and on their computational > complexity. > --- > Documentation/scheduler/sched-deadline.txt | 40 ++++++++++++++++++++++++++-- > 1 file changed, 38 insertions(+), 2 deletions(-) > > diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt > index 39341d9..ffaf95f 100644 > --- a/Documentation/scheduler/sched-deadline.txt > +++ b/Documentation/scheduler/sched-deadline.txt > @@ -171,8 +171,34 @@ CONTENTS > If D_i != P_i for some task, then it is possible to define the density of > a task as WCET_i/min{D_i,P_i}, and EDF is able to respect all the deadlines > of all the tasks running on a CPU if the sum sum_i WCET_i/min{D_i,P_i} of the > - densities of the tasks running on such a CPU is smaller or equal than 1 > - (notice that this condition is only sufficient, and not necessary). > + densities of the tasks running on such a CPU is smaller or equal than 1: > + sum_i WCET_i / min{D_i, P_i} <= 1 I assume you mean sum {forall i in the set}, but using 'sum_i' is confusing since we use this to denote a particular task Also, density is equivalent to 'utilization', right? (which is referred to in sec 4.1 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) > + 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. 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, every time the task wakes up, the scheduler computes a "scheduling deadline" consistent with the guarantee (using the CBS[2,3] algorithm). Tasks are then scheduled using EDF[1] on these scheduling deadlines (the task with the @@.. 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} > + 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 ? > + 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. 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). > + admission test in the kernel (hence, as explained in Section 4 Linux uses > + an admission test based on the tasks' utilisations). > > On multiprocessor systems with global EDF scheduling (non partitioned > systems), a sufficient test for schedulability can not be based on the > @@ -206,6 +232,16 @@ CONTENTS > Symposium, 1998. http://retis.sssup.it/~giorgio/paps/1998/rtss98-cbs.pdf > 3 - L. Abeni. Server Mechanisms for Multimedia Applications. ReTiS Lab > Technical Report. http://disi.unitn.it/~abeni/tr-98-01.pdf > + 4 - J. Y. Leung and M.L. Merril. A Note on Preemptive Scheduling of > + Periodic, Real-Time Tasks. Information Processing Letters, vol. 11, > + no. 3, pp. 115-118, 1980. > + 5 - S. K. Baruah, A. K. Mok and L. E. Rosier. Preemptively Scheduling > + Hard-Real-Time Sporadic Tasks on One Processor. Proceedings of the > + 11th IEEE Real-time Systems Symposium, 1990. > + 6 - S. K. Baruah, L. E. Rosier and R. R. Howell. Algorithms and Complexity > + Concerning the Preemptive Scheduling of Periodic Real-Time tasks on > + One Processor. Real-Time Systems Journal, vol. 4, no. 2, pp 301-324, > + 1990. > > 4. Bandwidth management > ======================= > -- > 1.7.9.5 > -- 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/