[PATCH 5/8] Documentation/scheduler/scheddeadline.txt: Some notes on EDF schedulability
From: Luca Abeni
Date: Fri Apr 10 2015  06:22:42 EST
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/scheddeadline.txt  46 +++++++++++++++++++++++++
1 file changed, 42 insertions(+), 4 deletions()
diff git a/Documentation/scheduler/scheddeadline.txt b/Documentation/scheduler/scheddeadline.txt
index c52e635..9663d53 100644
 a/Documentation/scheduler/scheddeadline.txt
+++ b/Documentation/scheduler/scheddeadline.txt
@@ 137,10 +137,12 @@ CONTENTS
A realtime task can be periodic with period P if r_{j+1} = r_j + P, or
sporadic with minimum interarrival time P is r_{j+1} >= r_j + P. Finally,
d_j = r_j + D, where D is the task's relative deadline.
+ Summing up, a realtime task can be described as
+ Task = (WCET, D, P)
+
The utilisation of a realtime task is defined as the ratio between its
WCET and its period (or minimum interarrival time), and represents
the fraction of CPU time needed to execute the task.

If the total utilisation U=sum(WCET_i/P_i) is larger than M (with M equal
to the number of CPUs), then the scheduler is unable to respect all the
deadlines.
@@ 170,9 +172,35 @@ CONTENTS
of the tasks running on such a CPU is smaller or equal than 1.
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(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).
+ of all the tasks running on a CPU if the sum of the densities of the tasks
+ running on such a CPU is smaller or equal than 1:
+ sum(WCET_i / min{D_i, P_i}) <= 1
+ 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=(50ms,50ms,100ms) and Task_2=(10ms,100ms,100ms).
+ 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 h(t) is smaller than t (that is,
+ the amount of time needed by the tasks in a time interval of size t is
+ smaller than the size of the interval) for all the possible values of t, then
+ 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 as well as too
+ timeconsuming to be performed online. 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 +234,16 @@ CONTENTS
Symposium, 1998. http://retis.sssup.it/~giorgio/paps/1998/rtss98cbs.pdf
3  L. Abeni. Server Mechanisms for Multimedia Applications. ReTiS Lab
Technical Report. http://disi.unitn.it/~abeni/tr9801.pdf
+ 4  J. Y. Leung and M.L. Merril. A Note on Preemptive Scheduling of
+ Periodic, RealTime Tasks. Information Processing Letters, vol. 11,
+ no. 3, pp. 115118, 1980.
+ 5  S. K. Baruah, A. K. Mok and L. E. Rosier. Preemptively Scheduling
+ HardRealTime Sporadic Tasks on One Processor. Proceedings of the
+ 11th IEEE Realtime Systems Symposium, 1990.
+ 6  S. K. Baruah, L. E. Rosier and R. R. Howell. Algorithms and Complexity
+ Concerning the Preemptive Scheduling of Periodic RealTime tasks on
+ One Processor. RealTime Systems Journal, vol. 4, no. 2, pp 301324,
+ 1990.
4. Bandwidth management
=======================

1.7.9.5

To unsubscribe from this list: send the line "unsubscribe linuxkernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomoinfo.html
Please read the FAQ at http://www.tux.org/lkml/