# Re: [RFC 4/4] Documentation/scheduler/sched-deadline.txt: add some references

**From: **Juri Lelli

**Date: ** Thu Apr 09 2015 - 04:23:39 EST

On 08/04/15 12:59, Luca Abeni wrote:

>* Add a description of the Dhall's effect, some discussion about*

>* schedulability tests for global EDF, and references to real-time literature,*

>* ---*

>* Documentation/scheduler/sched-deadline.txt | 81 ++++++++++++++++++++++++----*

>* 1 file changed, 71 insertions(+), 10 deletions(-)*

>* *

>* diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt*

>* index ffaf95f..da5a8d7 100644*

>* --- a/Documentation/scheduler/sched-deadline.txt*

>* +++ b/Documentation/scheduler/sched-deadline.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*

>* real-time 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 real-time tasks are not starved and*

>* - that the tardiness of real-time tasks has an upper bound.*

>* -*

>* - SCHED_DEADLINE can be used to schedule real-time 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*

^

s/a//

>* + 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=P-1. The last task*

^

and equal to P-1:

It seemed confusing to me as it is right now.

>* + (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*

>* + real-time 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 multi-processor real-time 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 real-time*

>* + tasks are not starved and that the tardiness of real-time tasks has an upper*

>* + bound[12] (as previously noticed). Different bounds on the maximum tardiness*

>* + experienced by real-time 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 real-time 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 Real-Time tasks on*

>* One Processor. Real-Time Systems Journal, vol. 4, no. 2, pp 301-324,*

>* 1990.*

>* + 7 - S. J. Dhall and C. L. Liu. On a real-time scheduling problem. Operations*

>* + research, vol. 26, no. 1, pp 127-140, 1978.*

>* + 8 - T. Baker. Multiprocessor EDF and Deadline Monotonic Schedulability*

>* + Analysis. Proceedings of the 24th IEEE Real-Time 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 760-768, 2005.*

>* + 10 - J. Goossens, S. Funk and S. Baruah, Priority-Driven Scheduling of*

>* + Periodic Task Systems on Multiprocessors. Real-Time Systems Journal,*

>* + vol. 25, no. 2â3, pp. 187â205, 2003.*

>* + 11 - R. Davis and A. Burns. A Survey of Hard Real-Time Scheduling for*

>* + Multiprocessor Systems. ACM Computing Surveys, vol. 43, no. 4, 2011.*

>* + http://www-users.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. Real-Time Systems Journal, vol. 32,*

>* + no. 2, pp 133-189, 2008.*

>* + 13 - P. Valente and G. Lipari. An Upper Bound to the Lateness of Soft*

>* + Real-Time Tasks Scheduled by EDF on Multiprocessors. Proceedings of*

>* + the 26th IEEE Real-Time Systems Symposium, 2005.*

>* + 14 - J. Erickson, U. Devi and S. Baruah. Improved tardiness bounds for*

>* + Global EDF. Proceedings of the 22nd Euromicro Conference on*

>* + Real-Time Systems, 2010.*

>* +*

>* *

>* 4. Bandwidth management*

>* =======================*

>* *

--

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/