[RFC 0/4] SCHED_DEADLINE documentation update

[RFC 0/4] SCHED_DEADLINE documentation update

[Luca Abeni]

Hi all,

here is the promised update for Documentation/scheduler/sched-deadline.txt.
I send it as an RFC because of the following doubts:
1) I split the patches trying to isolate related changes. So,
   - the first patch fixes 2 typos that I noticed when updating the
     documentation
   - the second patch is based on Zhiqiang Zhang's patch and fixes some
     inconsistencies in the symbols used for period and execution times
   - the third patch adds a small discussion about admission tests for EDF on
     single processor systems
   - the fourth patch discusses the multi-processor case, adding some missing
     references
   I am not sure if this split is ok, or if I should do something different
   (should I put all of the changes in a single patch?)
2) The second patch is partly by me and partly by Zhiqiang Zhang. I do not
   know how to preserve Zhiqiang Zhang's authorship, so I added "Based on a
   patch by Zhiqiang Zhang" in the changelog. But I am not sure if this is
   the correct thing to do (maybe I should split this in 2 different patches?)
3) I re-read the added text multiple times, and it looks ok to me... But I am
   not a native speaker, so it might contain English errors or sentences that
   are not clear enough
4) I think I added all the needed references, and Section 3 now looks like a
   self-contained introduction to EDF scheduling... If someone thinks that
   some additional references are needed, let me know and I'll search and
   add them

			Thanks,
					Luca   

Luca Abeni (4):
  Documentation/scheduler/sched-deadline.txt: fix typos
  Documentation/scheduler/sched-deadline.txt: use consistent namings
  Documentation/scheduler/sched-deadline.txt: Some notes on EDF
    schedulability
  Documentation/scheduler/sched-deadline.txt: add some references

 Documentation/scheduler/sched-deadline.txt |  129 ++++++++++++++++++++++++----
 1 file changed, 113 insertions(+), 16 deletions(-)

-- 
1.7.9.5

[RFC 1/4] Documentation/scheduler/sched-deadline.txt: fix typos

[Luca Abeni]

---
 Documentation/scheduler/sched-deadline.txt |    4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt
index 21461a0..b29b16c 100644
--- a/Documentation/scheduler/sched-deadline.txt
+++ b/Documentation/scheduler/sched-deadline.txt
@@ -52,7 +52,7 @@ CONTENTS
  "admission control" strategy (see Section "4. Bandwidth management") is used
  (clearly, if the system is overloaded this guarantee cannot be respected).
 
- Summing up, the CBS[2,3] algorithms assigns scheduling deadlines to tasks so
+ Summing up, the CBS[2,3] algorithm assigns scheduling deadlines to tasks so
  that each task runs for at most its runtime every period, avoiding any
  interference between different tasks (bandwidth isolation), while the EDF[1]
  algorithm selects the task with the earliest scheduling deadline as the one
@@ -190,7 +190,7 @@ CONTENTS
   - deadline = D
   - period <= P
 
- IOW, if runtime >= WCET and if period is >= P, then the scheduling deadlines
+ IOW, if runtime >= WCET and if period is <= P, then the scheduling deadlines
  and the absolute deadlines (d_j) coincide, so a proper admission control
  allows to respect the jobs' absolute deadlines for this task (this is what is
  called "hard schedulability property" and is an extension of Lemma 1 of [2]).
-- 
1.7.9.5

[RFC 2/4] Documentation/scheduler/sched-deadline.txt: use consistent namings

[Luca Abeni]

The names "C_i" and "T_i" were used (without previously defining them)
instead of "WCET_i" and "P_i".
Based on a patch by Zhiqiang Zhang <zhangzhiqiang.zhang@huawei.com>
---
 Documentation/scheduler/sched-deadline.txt |    4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt
index b29b16c..39341d9 100644
--- a/Documentation/scheduler/sched-deadline.txt
+++ b/Documentation/scheduler/sched-deadline.txt
@@ -169,8 +169,8 @@ CONTENTS
  of all the tasks executing on a CPU if and only if the total utilisation
  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 C_i/min{D_i,T_i}, and EDF is able to respect all the deadlines
- of all the tasks running on a CPU if the sum sum_i C_i/min{D_i,T_i} of the
+ 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).
 
-- 
1.7.9.5

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

[Luca Abeni]

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

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

[Luca Abeni]

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
+ 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
+ (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
 =======================
-- 
1.7.9.5

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

[Peter Zijlstra]

On Wed, Apr 08, 2015 at 01:59:40PM +0200, Luca Abeni wrote:
> + 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

                             ^^^ noted?

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

Re: [RFC 0/4] SCHED_DEADLINE documentation update

[Peter Zijlstra]

On Wed, Apr 08, 2015 at 01:59:36PM +0200, Luca Abeni wrote:
> Hi all,
> 
> here is the promised update for Documentation/scheduler/sched-deadline.txt.
> I send it as an RFC because of the following doubts:
> 1) I split the patches trying to isolate related changes. So,
>    - the first patch fixes 2 typos that I noticed when updating the
>      documentation
>    - the second patch is based on Zhiqiang Zhang's patch and fixes some
>      inconsistencies in the symbols used for period and execution times
>    - the third patch adds a small discussion about admission tests for EDF on
>      single processor systems
>    - the fourth patch discusses the multi-processor case, adding some missing
>      references
>    I am not sure if this split is ok, or if I should do something different
>    (should I put all of the changes in a single patch?)

This is indeed the preferred way.

> 2) The second patch is partly by me and partly by Zhiqiang Zhang. I do not
>    know how to preserve Zhiqiang Zhang's authorship, so I added "Based on a
>    patch by Zhiqiang Zhang" in the changelog. But I am not sure if this is
>    the correct thing to do (maybe I should split this in 2 different patches?)

This is not uncommon practise and works for me.

> 3) I re-read the added text multiple times, and it looks ok to me... But I am
>    not a native speaker, so it might contain English errors or sentences that
>    are not clear enough

I send the one comment I had in reply to the relevant email.

Other than that it looked good to me so I've queued these patches.
Thanks!

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

[Juri Lelli]

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
>  =======================
> 

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

[Henrik Austad]

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}, but using 'sum_i' is confusing 
since we use this to denote a particular task Also, density is equivalent 
to 'utilization', right? (which is referred to in sec 4.1

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)

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

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,                                                                                                                                                                            
  every time the task wakes up, the scheduler computes a "scheduling deadline"                                                                                                                                     
  consistent with the guarantee (using the CBS[2,3] algorithm). Tasks are then                                                                                                                                     
  scheduled using EDF[1] on these scheduling deadlines (the task with the

@@..

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}

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


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

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

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

-- 
Henrik Austad

Re: [RFC 0/4] SCHED_DEADLINE documentation update

[Luca Abeni]

Hi Peter,

On 04/08/2015 04:44 PM, Peter Zijlstra wrote:
> On Wed, Apr 08, 2015 at 01:59:36PM +0200, Luca Abeni wrote:
>> Hi all,
>>
>> here is the promised update for Documentation/scheduler/sched-deadline.txt.
>> I send it as an RFC because of the following doubts:
>> 1) I split the patches trying to isolate related changes. So,
>>     - the first patch fixes 2 typos that I noticed when updating the
>>       documentation
>>     - the second patch is based on Zhiqiang Zhang's patch and fixes some
>>       inconsistencies in the symbols used for period and execution times
>>     - the third patch adds a small discussion about admission tests for EDF on
>>       single processor systems
>>     - the fourth patch discusses the multi-processor case, adding some missing
>>       references
>>     I am not sure if this split is ok, or if I should do something different
>>     (should I put all of the changes in a single patch?)
>
> This is indeed the preferred way.
>
>> 2) The second patch is partly by me and partly by Zhiqiang Zhang. I do not
>>     know how to preserve Zhiqiang Zhang's authorship, so I added "Based on a
>>     patch by Zhiqiang Zhang" in the changelog. But I am not sure if this is
>>     the correct thing to do (maybe I should split this in 2 different patches?)
>
> This is not uncommon practise and works for me.
>
>> 3) I re-read the added text multiple times, and it looks ok to me... But I am
>>     not a native speaker, so it might contain English errors or sentences that
>>     are not clear enough
>
> I send the one comment I had in reply to the relevant email.
>
> Other than that it looked good to me so I've queued these patches.
Ok; so how should I proceed? Should I address the various comments (by you, Juri
and Henrik) by sending incremental patches based on these ones (since I see you queued
these patches), or should I resend everything after addressing the various comments?


			Thanks,
				Luca

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

[Luca Abeni]

Hi Juri,

thanks for the review! I am fixing these issues locally.


			Thanks,
				Luca

On 04/09/2015 10:24 AM, Juri Lelli wrote:
> 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
>>   =======================
>>
>

Re: [RFC 0/4] SCHED_DEADLINE documentation update

[Peter Zijlstra]

On Thu, Apr 09, 2015 at 11:13:10AM +0200, Luca Abeni wrote:
> Ok; so how should I proceed? Should I address the various comments (by you, Juri
> and Henrik) by sending incremental patches based on these ones (since I see you queued
> these patches), or should I resend everything after addressing the various comments?

Whichever you prefer, if you'd like to just respin these patches that's
fine, I'll drop them -- but let me know before they end up in a git tree
;-)

Re: [RFC 0/4] SCHED_DEADLINE documentation update

[Luca Abeni]

On 04/09/2015 11:17 AM, Peter Zijlstra wrote:
> On Thu, Apr 09, 2015 at 11:13:10AM +0200, Luca Abeni wrote:
>> Ok; so how should I proceed? Should I address the various comments (by you, Juri
>> and Henrik) by sending incremental patches based on these ones (since I see you queued
>> these patches), or should I resend everything after addressing the various comments?
>
> Whichever you prefer, if you'd like to just respin these patches that's
> fine, I'll drop them -- but let me know before they end up in a git tree
> ;-)
Ok; given Henrik's comments, I suspect it is better to respin the patches.
I hope to resend everything in few days.


			Thanks,
				Luca

Re: [RFC 0/4] SCHED_DEADLINE documentation update

[Peter Zijlstra]

On Thu, Apr 09, 2015 at 11:19:16AM +0200, Luca Abeni wrote:
> On 04/09/2015 11:17 AM, Peter Zijlstra wrote:
> >On Thu, Apr 09, 2015 at 11:13:10AM +0200, Luca Abeni wrote:
> >>Ok; so how should I proceed? Should I address the various comments (by you, Juri
> >>and Henrik) by sending incremental patches based on these ones (since I see you queued
> >>these patches), or should I resend everything after addressing the various comments?
> >
> >Whichever you prefer, if you'd like to just respin these patches that's
> >fine, I'll drop them -- but let me know before they end up in a git tree
> >;-)
> Ok; given Henrik's comments, I suspect it is better to respin the patches.
> I hope to resend everything in few days.

OK, I'll await new and shiny patches :-) Thanks!

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

[Luca Abeni]

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

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

[Henrik Austad]

On Wed, Apr 08, 2015 at 01:59:40PM +0200, 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.

+ \newline (add som breathing space)

> + For example, consider a M tasks {Task_1,...Task_M} scheduled on M - 1

Please consider rewriting this to

"Consinder a set of M+1 tasks on a system with M CPUs [...]"

As 'M' is normally used to denote the number of cores available and it is 
much easier to grasp the context of "<some number> + 1" rather than "<some 
number - 1"-CPUs.

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

Normally, 'e' is used to denote an _arbitrarily_ small value, and I suspect 
that this is indeed the case here as well (you're going to describe 
Dhall's effect, right?). Perhaps make that point explicit?

     T_i = {P_i, e, P_i}

> + (Task_M) has period, relative deadline and worst case execution time
> + equal to P: P_M=D_M=WCET_M=P. 

      T_M = {P, P, 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
                                ^^^^^^
 Drop this, the text is full of equations as it is.

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

This gives the impression that 'e' must be constant, but all it really 
means is that e is an 'arbitrarily small value which can be *almost* 0' and 
that they will be picked _before_ the heavy task by EDF.

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

sum_i; as stated in another comment, just juse 'sum' (IMHO)

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

What about simething like

"
Finally, it is important to understand the relationship between the 
scheduling deadlines assigned by SCHED_DEADLINE and the tasks' deadlines
described above.

The task itself supplies a _relative_ deadline, i.e. an offset after the 
release of the task at which point it must be complete whereas 
SCHED_DEADLINE assigns an _absolute_ deadline (a specific point in time) on 
the form

     D_i = r_i + d_i
"
Or somesuch? I may be overdoing this.

> + 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
>  =======================
> -- 
> 1.7.9.5
> 

-- 
Henrik Austad

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

[Peter Zijlstra]

On Thu, Apr 09, 2015 at 11:39:08AM +0200, Henrik Austad wrote:
> > + 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
> 
> Normally, 'e' is used to denote an _arbitrarily_ small value, and I suspect 
> that this is indeed the case here as well (you're going to describe 
> Dhall's effect, right?). Perhaps make that point explicit?
> 
>      T_i = {P_i, e, P_i}

We're talking about \epsilon here, right? Is it customary to use a
regular 'e' in CS literature for that?

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

[Luca Abeni]

Hi Henrik,

On 04/09/2015 11:39 AM, Henrik Austad wrote:
[...]
>> - 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.
>
> + \newline (add som breathing space)
Ok

>
>> + For example, consider a M tasks {Task_1,...Task_M} scheduled on M - 1
>
> Please consider rewriting this to
>
> "Consinder a set of M+1 tasks on a system with M CPUs [...]"
>
> As 'M' is normally used to denote the number of cores available and it is
> much easier to grasp the context of "<some number> + 1" rather than "<some
> number - 1"-CPUs.
Yes, this is what I originally wrote (and is the example I teach to students:
http://disi.unitn.it/~abeni/RTOS/multiprocessor.pdf, slide 7). But then I
re-read the original paper, and I see Dhall used m tasks (and n CPUs, just to
confuse people :). So I rewrote the example in this way... Also because in this
way the last task is Task_M, instead of Task_{M+1} which would make the notation
more complex (because of the _{M+1}). But I can rewrite using M+1 tasks and M CPUs.


>> + 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
>
> Normally, 'e' is used to denote an _arbitrarily_ small value, and I suspect
> that this is indeed the case here as well
Right. This was a \epsilon in the original paper (actually, Dhall used  2\epsilon
and I decided to simplify things a little bit).

> (you're going to describe
> Dhall's effect, right?). Perhaps make that point explicit?
>
>       T_i = {P_i, e, P_i}
>
>> + (Task_M) has period, relative deadline and worst case execution time
>> + equal to P: P_M=D_M=WCET_M=P.
>
>        T_M = {P, P, P}
Ok


>> + 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
>                                  ^^^^^^
>   Drop this, the text is full of equations as it is.
Ok

>
>> + 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].
>
> This gives the impression that 'e' must be constant, but all it really
> means is that e is an 'arbitrarily small value which can be *almost* 0'
Right. The original paper uses "\lim_{\epsilon -> 0} ...", but I decided to
simplify the description (maybe I oversimplified?). A constant and small e
should be ok to give an intuition of Dhall's effect: if e becomes very small,
the utilisation becomes very near to 1. But if you think this confuses the reader,
I can add a note about \lim_{e -> 0}

> and that they will be picked _before_ the heavy task by EDF.
Right. This is because these tasks have period (and relative deadline) equal to P-1.


>> + 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
>
> sum_i; as stated in another comment, just juse 'sum' (IMHO)
Ok; if other people agree, I'll add a patch to the patchset to convert all the
"sum_" into "sum".


>> + 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).
>
> What about simething like
>
> "
> Finally, it is important to understand the relationship between the
> scheduling deadlines assigned by SCHED_DEADLINE and the tasks' deadlines
> described above.
>
> The task itself supplies a _relative_ deadline, i.e. an offset after the
> release of the task at which point it must be complete whereas
> SCHED_DEADLINE assigns an _absolute_ deadline (a specific point in time) on
> the form
>
>       D_i = r_i + d_i
> "
> Or somesuch? I may be overdoing this.
This is not the point I wanted to make... Absolute deadlines (equal to r + D)
have been previously defined in the document for real-time tasks too.
The difference between SCHED_DEADLINE's deadlines and tasks' deadlines is not
"absolute vs relative". The difference is that SCHED_DEADLINE cannot know the
"real" tasks' deadlines, so it uses "scheduling deadlines" that are generated
according to the CBS rules (described in Section 2).
Now, if a task is developed according to the Liu&Layland model (does not block
before the end of the job) and the SCHED_DEADLINE parameters are properly assigned
(runtime >= WCET, period <= P) then the task's absolute deadlines and the scheduling
deadlines coincides, so it is possible to guarantee the respect of the task's temporal
constraints.
This is the tricky (and confusing :) thing about SCHED_DEADLINE.
I'll see if I can reword this paragraph to make it more clear.


			Thanks,
				Luca

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

[Luca Abeni]

On 04/09/2015 11:44 AM, Peter Zijlstra wrote:
> On Thu, Apr 09, 2015 at 11:39:08AM +0200, Henrik Austad wrote:
>>> + 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
>>
>> Normally, 'e' is used to denote an _arbitrarily_ small value, and I suspect
>> that this is indeed the case here as well (you're going to describe
>> Dhall's effect, right?). Perhaps make that point explicit?
>>
>>       T_i = {P_i, e, P_i}
>
> We're talking about \epsilon here, right?
Right. I used "e" to make the thing more readable in a simple text document.

> Is it customary to use a regular 'e' in CS literature for that?
I do not know... I just wanted to use one single character, and to avoid the "\"
(which only makes sense to people using latex :)

But if you want I can use "epsilon" or "\epsilon"... Let me know


			Thanks,
				Luca

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

[Henrik Austad]

On Thu, Apr 09, 2015 at 11:34:37AM +0200, Luca Abeni wrote:
> 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:
>  [...]
> >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}.

ah, yes, you're right of course. Don't mind my inane ramblings here then :)


> >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...").

Ok. I understood runtime as the dynamic value being managed by the 
scheduler and should never exceed WCET (or being set to WCET upon release 
and task preemption when runtime==0).

I'll read through the entire thing carefully methinks

> 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)

See! I'm not even consistent with my own naming. (aren't you glad you sent 
me these patches?)

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

Hmm, could be, I was sure it was period - as long as we're consistent I 
don't really care. I'd just like a more concise way of describing tasks.

Use it the same order as in struct sched_dl_entity perhaps? (which is 
runtime, deadline, period)?

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

aaah, I read 't' as "a point in time", but 't' here is a _relative_ value, 
starting at offset X. *gah* this is getting messy.

so, basically h(t) is defined as the length of the interval [0,t) (assuming 
we start at time 0..)

Then I understand what you mean and then it makes more sense :)

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

You're right, let's not add more text to this than absolutely needed.

-- 
Henrik Austad

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

[Peter Zijlstra]

On Thu, Apr 09, 2015 at 12:08:36PM +0200, Luca Abeni wrote:
> On 04/09/2015 11:44 AM, Peter Zijlstra wrote:
> >On Thu, Apr 09, 2015 at 11:39:08AM +0200, Henrik Austad wrote:
> >>>+ 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
> >>
> >>Normally, 'e' is used to denote an _arbitrarily_ small value, and I suspect
> >>that this is indeed the case here as well (you're going to describe
> >>Dhall's effect, right?). Perhaps make that point explicit?
> >>
> >>      T_i = {P_i, e, P_i}
> >
> >We're talking about \epsilon here, right?
> Right. I used "e" to make the thing more readable in a simple text document.
> 
> >Is it customary to use a regular 'e' in CS literature for that?
> I do not know... I just wanted to use one single character, and to avoid the "\"
> (which only makes sense to people using latex :)
> 
> But if you want I can use "epsilon" or "\epsilon"... Let me know

I'm fine either way, its just my math/physics brain piping up.

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

[Henrik Austad]

On Thu, Apr 09, 2015 at 12:11:25PM +0200, Peter Zijlstra wrote:
> On Thu, Apr 09, 2015 at 12:08:36PM +0200, Luca Abeni wrote:
> > On 04/09/2015 11:44 AM, Peter Zijlstra wrote:
> > >On Thu, Apr 09, 2015 at 11:39:08AM +0200, Henrik Austad wrote:
> > >>>+ 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
> > >>
> > >>Normally, 'e' is used to denote an _arbitrarily_ small value, and I suspect
> > >>that this is indeed the case here as well (you're going to describe
> > >>Dhall's effect, right?). Perhaps make that point explicit?
> > >>
> > >>      T_i = {P_i, e, P_i}
> > >
> > >We're talking about \epsilon here, right?
> > Right. I used "e" to make the thing more readable in a simple text document.
> > 
> > >Is it customary to use a regular 'e' in CS literature for that?
> > I do not know... I just wanted to use one single character, and to avoid the "\"
> > (which only makes sense to people using latex :)
> > 
> > But if you want I can use "epsilon" or "\epsilon"... Let me know
> 
> I'm fine either way, its just my math/physics brain piping up.

I'd vote for 'e' then (just to mess with peterz' brain and avoid some 
confusing \'s).

-- 
Henrik Austad

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

[Henrik Austad]

On Thu, Apr 09, 2015 at 12:05:54PM +0200, Luca Abeni wrote:
> Hi Henrik,

> [..]
> >>+ 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).
> >
> >What about simething like
> >
> >"
> >Finally, it is important to understand the relationship between the
> >scheduling deadlines assigned by SCHED_DEADLINE and the tasks' deadlines
> >described above.
> >
> >The task itself supplies a _relative_ deadline, i.e. an offset after the
> >release of the task at which point it must be complete whereas
> >SCHED_DEADLINE assigns an _absolute_ deadline (a specific point in time) on
> >the form
> >
> >      D_i = r_i + d_i
> >"
> >Or somesuch? I may be overdoing this.
> This is not the point I wanted to make... Absolute deadlines (equal to r + D)
> have been previously defined in the document for real-time tasks too.
> The difference between SCHED_DEADLINE's deadlines and tasks' deadlines is not
> "absolute vs relative". The difference is that SCHED_DEADLINE cannot know the
> "real" tasks' deadlines, so it uses "scheduling deadlines" that are generated
> according to the CBS rules (described in Section 2).

Ah, fair point, I was indeed too hasty. Thanks for clearing that up though!

> Now, if a task is developed according to the Liu&Layland model (does not block
> before the end of the job) and the SCHED_DEADLINE parameters are properly assigned
> (runtime >= WCET, period <= P) then the task's absolute deadlines and the scheduling
> deadlines coincides, so it is possible to guarantee the respect of the task's temporal
> constraints.
> This is the tricky (and confusing :) thing about SCHED_DEADLINE.
> I'll see if I can reword this paragraph to make it more clear.

Right! Assuming a spherical cow in vacuum etc etc. You're right of course, 
disregard my ramblings.

-- 
Henrik Austad

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

[Luca Abeni]

On 04/09/2015 12:10 PM, Henrik Austad wrote:
[...]
>>> @@ -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...").
>
> Ok. I understood runtime as the dynamic value being managed by the
> scheduler and should never exceed WCET (or being set to WCET upon release
> and task preemption when runtime==0).
Uh... That's yet another thing (called "remaining runtime" in the document).

This is the situation:
1) A task is characterised by 3 parameters: WCET, D, and P. These only depend on the
    application's code (how much time the application takes to do its work, how often
    it activate, and how fast it should finish in order to respect its temporal
    constraints).
    Section 3 tries to introduce and describe these parameters (which come from real-time
    literature).
2) The SCHED_DEADLINE scheduler accepts 3 scheduling parameters (as arguments of the
    sched_setattr() system call): runtime, deadline and period. These are used by the
    scheduler to assign a dynamic priority to the tasks. Described in Section 2.
3) Internally, the scheduler maintains some dynamic values (remaining budget and
    scheduling deadline). The "remaining budget" starts from the "budget" value and
    decreases when a task executes. When it arrives to 0 the task is throttled, etc...

The problem is that the scheduling parameters (runtime deadline and period, item 2
and Section 3) and the task's parameters (WCET D and P, item 1 and Section 2) are
conceptually two different things... And of course the task's temporal constraints
are respected only if the scheduling parameters are set in an appropriate way.


					Luca

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

[Ingo Molnar]

* Henrik Austad <henrik@austad.us> wrote:

> On Thu, Apr 09, 2015 at 12:11:25PM +0200, Peter Zijlstra wrote:
> > On Thu, Apr 09, 2015 at 12:08:36PM +0200, Luca Abeni wrote:
> > > On 04/09/2015 11:44 AM, Peter Zijlstra wrote:
> > > >On Thu, Apr 09, 2015 at 11:39:08AM +0200, Henrik Austad wrote:
> > > >>>+ 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
> > > >>
> > > >>Normally, 'e' is used to denote an _arbitrarily_ small value, and I suspect
> > > >>that this is indeed the case here as well (you're going to describe
> > > >>Dhall's effect, right?). Perhaps make that point explicit?
> > > >>
> > > >>      T_i = {P_i, e, P_i}
> > > >
> > > >We're talking about \epsilon here, right?
> > > Right. I used "e" to make the thing more readable in a simple text document.
> > > 
> > > >Is it customary to use a regular 'e' in CS literature for that?
> > > I do not know... I just wanted to use one single character, and to avoid the "\"
> > > (which only makes sense to people using latex :)
> > > 
> > > But if you want I can use "epsilon" or "\epsilon"... Let me know
> > 
> > I'm fine either way, its just my math/physics brain piping up.
> 
> I'd vote for 'e' then (just to mess with peterz' brain and avoid some 
> confusing \'s).

Just make sure you explain the nomenclature in the document!

Thanks,

	Ingo