Re: [RFC 3/4] Documentation/scheduler/sched-deadline.txt: Some notes on EDF schedulability

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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-doc" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html




[Index of Archives]     [Kernel Newbies]     [Security]     [Netfilter]     [Bugtraq]     [Linux FS]     [Yosemite Forum]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Samba]     [Video 4 Linux]     [Device Mapper]     [Linux Resources]

  Powered by Linux