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

From: Henrik Austad
Date: Thu Apr 09 2015 - 05:06:59 EST

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@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/