[RFC 4/4] Documentation/scheduler/scheddeadline.txt: add some references
From: Luca Abeni
Date: Wed Apr 08 2015  08:01:23 EST
Add a description of the Dhall's effect, some discussion about
schedulability tests for global EDF, and references to realtime literature,

Documentation/scheduler/scheddeadline.txt  81 ++++++++++++++++++++++++
1 file changed, 71 insertions(+), 10 deletions()
diff git a/Documentation/scheduler/scheddeadline.txt b/Documentation/scheduler/scheddeadline.txt
index ffaf95f..da5a8d7 100644
 a/Documentation/scheduler/scheddeadline.txt
+++ b/Documentation/scheduler/scheddeadline.txt
@@ 160,7 +160,8 @@ CONTENTS
maximum tardiness of each task is smaller or equal than
((M â 1) Â WCET_max â WCET_min)/(M â (M â 2) Â U_max) + WCET_max
where WCET_max = max_i{WCET_i} is the maximum WCET, WCET_min=min_i{WCET_i}
 is the minimum WCET, and U_max = max_i{WCET_i/P_i} is the maximum utilisation.
+ is the minimum WCET, and U_max = max_i{WCET_i/P_i} is the maximum
+ utilisation[12].
If M=1 (uniprocessor system), or in case of partitioned scheduling (each
realtime task is statically assigned to one and only one CPU), it is
@@ 202,15 +203,52 @@ CONTENTS
On multiprocessor systems with global EDF scheduling (non partitioned
systems), a sufficient test for schedulability can not be based on the
 utilisations (it can be shown that task sets with utilisations slightly
 larger than 1 can miss deadlines regardless of the number of CPUs M).
 However, as previously stated, enforcing that the total utilisation is smaller
 than M is enough to guarantee that non realtime tasks are not starved and
 that the tardiness of realtime tasks has an upper bound.

 SCHED_DEADLINE can be used to schedule realtime tasks guaranteeing that
 the jobs' deadlines of a task are respected. In order to do this, a task
 must be scheduled by setting:
+ utilisations or densities: it can be shown that even if D_i = P_i task
+ sets with utilisations slightly larger than 1 can miss deadlines regardless
+ of the number of CPUs.
+ For example, consider a M tasks {Task_1,...Task_M} scheduled on M  1
+ CPUs, with the first M  1 tasks having a small worst case execution time
+ WCET_i=e and period equal to relative deadline P_i=D_i=P1. The last task
+ (Task_M) has period, relative deadline and worst case execution time
+ equal to P: P_M=D_M=WCET_M=P. If all the tasks activate at the
+ same time t, global EDF schedules the first M  1 tasks first (because
+ their absolute deadlines are equal to t + P  1, hence they are smaller
+ than the absolute deadline of Task_M, which is t + P). As a result, Task_M
+ can be scheduled only at time t + e, and will finish at time t + e + P,
+ after its absolute deadline t + P. The total utilisation of the task set
+ is (M  1) Â e / (P  1) + P / P = (M  1) Â e / (P  1) + 1, and for
+ small values of e this can become very close to 1. This is known as "Dhall's
+ effect"[7].
+ More complex schedulability tests for global EDF have been developed in
+ realtime literature[8,9], but they are not based on a simple comparison
+ between total utilisation (or density) and a fixed constant. If all tasks
+ have D_i = P_i, a sufficient schedulability condition can be expressed in
+ a simple way:
+ sum_i WCET_i / P_i <= M  (M  1) Â U_max
+ where U_max = max_i {WCET_i / P_i}[10]. Notice that for U_max = 1,
+ M  (M  1) Â U_max becomes M  M + 1 = 1 and this schedulability condition
+ just confirms the Dhall's effect. A more complete survey of the literature
+ about schedulability tests for multiprocessor realtime scheduling can be
+ found in [11].
+
+ As seen, enforcing that the total utilisation is smaller than M does not
+ guarantee that global EDF schedules the tasks without missing any deadline
+ (in other words, global EDF is not an optimal scheduling algorithm). However,
+ a total utilisation smaller than M is enough to guarantee that non realtime
+ tasks are not starved and that the tardiness of realtime tasks has an upper
+ bound[12] (as previously noticed). Different bounds on the maximum tardiness
+ experienced by realtime tasks have been developed in various papers[13,14],
+ but the theoretical result that is important for SCHED_DEADLINE is that if
+ the total utilisation is smaller or equal than M then the response times of
+ the tasks are limited.
+
+ Finally, it is important to understand the relationship between the
+ scheduling deadlines assigned by SCHED_DEADLINE and the tasks' deadlines
+ described above (which represent the real temporal constraints of the task).
+ If an admission test is used to guarantee that the scheduling deadlines are
+ respected, then SCHED_DEADLINE can be used to schedule realtime tasks
+ guaranteeing that the jobs' deadlines of a task are respected.
+ In order to do this, a task must be scheduled by setting:
 runtime >= WCET
 deadline = D
@@ 242,6 +280,29 @@ CONTENTS
Concerning the Preemptive Scheduling of Periodic RealTime tasks on
One Processor. RealTime Systems Journal, vol. 4, no. 2, pp 301324,
1990.
+ 7  S. J. Dhall and C. L. Liu. On a realtime scheduling problem. Operations
+ research, vol. 26, no. 1, pp 127140, 1978.
+ 8  T. Baker. Multiprocessor EDF and Deadline Monotonic Schedulability
+ Analysis. Proceedings of the 24th IEEE RealTime Systems Symposium, 2003.
+ 9  T. Baker. An Analysis of EDF Schedulability on a Multiprocessor.
+ IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 8,
+ pp 760768, 2005.
+ 10  J. Goossens, S. Funk and S. Baruah, PriorityDriven Scheduling of
+ Periodic Task Systems on Multiprocessors. RealTime Systems Journal,
+ vol. 25, no. 2â3, pp. 187â205, 2003.
+ 11  R. Davis and A. Burns. A Survey of Hard RealTime Scheduling for
+ Multiprocessor Systems. ACM Computing Surveys, vol. 43, no. 4, 2011.
+ http://wwwusers.cs.york.ac.uk/~robdavis/papers/MPSurveyv5.0.pdf
+ 12  U. C. Devi and J. H. Anderson. Tardiness Bounds under Global EDF
+ Scheduling on a Multiprocessor. RealTime Systems Journal, vol. 32,
+ no. 2, pp 133189, 2008.
+ 13  P. Valente and G. Lipari. An Upper Bound to the Lateness of Soft
+ RealTime Tasks Scheduled by EDF on Multiprocessors. Proceedings of
+ the 26th IEEE RealTime Systems Symposium, 2005.
+ 14  J. Erickson, U. Devi and S. Baruah. Improved tardiness bounds for
+ Global EDF. Proceedings of the 22nd Euromicro Conference on
+ RealTime Systems, 2010.
+
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/