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:
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}
Yes
but using 'sum_i' is confusing
since we use this to denote a particular task
Sorry about that. I can use "sum" (without "_i") if this is more understandable (BTW,
"sum_i" is already used in other parts of the document; I'll change those "sum_i" too).
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}.
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...").
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)
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).
+ 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?
+ 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).
Thanks,
Luca
--
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
