  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} <= 1I 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.1So 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 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 anas 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   