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

[Luca Abeni <lucabe72@gmail.com>]

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
+ 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.
+ 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
+ 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
+ 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