[PATCH 0/8] SCHED_DEADLINE documentation update

[PATCH 0/8] SCHED_DEADLINE documentation update

[Luca Abeni]

Hi all,

here is an update for Documentation/scheduler/sched-deadline.txt.
Respect to the RFC I sent few days ago, I:
1) Split the patches in a better way, (so that, for example, Zhiqiang Zhang's
   authorship is preserved)
2) Tried to address all the comments I received on the RFC
3) Added another patch, to split Section 3 in various subsections.
   I think it is more readable in this way. Anyway, this is the last patch,
   so it can easily be skipped if people do not like it.

I also split in a separate patch the discussion about the relationship between
tasks' parameters and SCHED_DEADLINE parameters. This is (I think) the only
part of the patchset that has not been previously discussed; I decided to
isolate it in its own patch so that other patches can be applied anyway.


			Thanks,
				Luca


Luca Abeni (7):
  Documentation/scheduler/sched-deadline.txt: fix typos
  Documentation/scheduler/sched-deadline.txt: use consistent namings
  Documentation/scheduler/sched-deadline.txt: remove _i from sum, max
    and min
  Documentation/scheduler/sched-deadline.txt: Some notes on EDF
    schedulability
  Documentation/scheduler/sched-deadline.txt: add some references
  Documentation/scheduler/sched-deadline.txt: relationship between
    tasks' deadlines and scheduling deadlines
  Documentation/scheduler/sched-deadline.txt: Split Section 3

Zhiqiang Zhang (1):
  Documentation/scheduler/sched-deadline.txt: correct definition of
    density as C_i/min{D_i,P_i}

 Documentation/scheduler/sched-deadline.txt |  161 ++++++++++++++++++++++++----
 1 file changed, 142 insertions(+), 19 deletions(-)

-- 
1.7.9.5

[PATCH 1/8] Documentation/scheduler/sched-deadline.txt: correct definition of density as C_i/min{D_i,P_i}

[Luca Abeni]

From: Zhiqiang Zhang <zhangzhiqiang.zhang@huawei.com>

C_i/min{D_i,T_i},where T_i is not referred before, should be
substituted by C_i/min{D_i,P_i}.

----------------------------------------

Signed-off-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 21461a0..194664b 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 C_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 C_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

[PATCH 2/8] 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 194664b..01eaa66 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

[PATCH 3/8] Documentation/scheduler/sched-deadline.txt: use consistent namings

[Luca Abeni]

The name "C_i" was used (without previously defining it)
instead of "WCET_i".
---
 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 01eaa66..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,P_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,P_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

[PATCH 4/8] Documentation/scheduler/sched-deadline.txt: remove _i from sum, max and min

[Luca Abeni]

The "_i" index is used in this document to to denote a particular task,
so "sum_i", "max_i" and "min_i" might be confusing.
---
 Documentation/scheduler/sched-deadline.txt |   10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt
index 39341d9..c52e635 100644
--- a/Documentation/scheduler/sched-deadline.txt
+++ b/Documentation/scheduler/sched-deadline.txt
@@ -133,7 +133,7 @@ CONTENTS
  arrival time r_j (the time when the job starts), an amount of computation
  time c_j needed to finish the job, and a job absolute deadline d_j, which
  is the time within which the job should be finished. The maximum execution
- time max_j{c_j} is called "Worst Case Execution Time" (WCET) for the task.
+ time max{c_j} is called "Worst Case Execution Time" (WCET) for the task.
  A real-time task can be periodic with period P if r_{j+1} = r_j + P, or
  sporadic with minimum inter-arrival time P is r_{j+1} >= r_j + P. Finally,
  d_j = r_j + D, where D is the task's relative deadline.
@@ -141,7 +141,7 @@ CONTENTS
  WCET and its period (or minimum inter-arrival time), and represents
  the fraction of CPU time needed to execute the task.
 
- If the total utilisation sum_i(WCET_i/P_i) is larger than M (with M equal
+ If the total utilisation U=sum(WCET_i/P_i) is larger than M (with M equal
  to the number of CPUs), then the scheduler is unable to respect all the
  deadlines.
  Note that total utilisation is defined as the sum of the utilisations
@@ -159,8 +159,8 @@ CONTENTS
  More precisely, it can be proven that using a global EDF scheduler the
  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.
+ where WCET_max = max{WCET_i} is the maximum WCET, WCET_min=min{WCET_i}
+ is the minimum WCET, and U_max = max{WCET_i/P_i} is the maximum utilisation.
 
  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
@@ -170,7 +170,7 @@ CONTENTS
  of the tasks running on such a CPU is smaller or equal than 1.
  If D_i != P_i for some task, then it is possible to define the density of
  a task as WCET_i/min{D_i,P_i}, and EDF is able to respect all the deadlines
- of all the tasks running on a CPU if the sum sum_i WCET_i/min{D_i,P_i} of the
+ of all the tasks running on a CPU if the sum sum(WCET_i/min{D_i,P_i}) of the
  densities of the tasks running on such a CPU is smaller or equal than 1
  (notice that this condition is only sufficient, and not necessary).
 
-- 
1.7.9.5

[PATCH 5/8] 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 |   46 +++++++++++++++++++++++++---
 1 file changed, 42 insertions(+), 4 deletions(-)

diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt
index c52e635..9663d53 100644
--- a/Documentation/scheduler/sched-deadline.txt
+++ b/Documentation/scheduler/sched-deadline.txt
@@ -137,10 +137,12 @@ CONTENTS
  A real-time task can be periodic with period P if r_{j+1} = r_j + P, or
  sporadic with minimum inter-arrival time P is r_{j+1} >= r_j + P. Finally,
  d_j = r_j + D, where D is the task's relative deadline.
+ Summing up, a real-time task can be described as
+	Task = (WCET, D, P) 
+
  The utilisation of a real-time task is defined as the ratio between its
  WCET and its period (or minimum inter-arrival time), and represents
  the fraction of CPU time needed to execute the task.
-
  If the total utilisation U=sum(WCET_i/P_i) is larger than M (with M equal
  to the number of CPUs), then the scheduler is unable to respect all the
  deadlines.
@@ -170,9 +172,35 @@ CONTENTS
  of the tasks running on such a CPU is smaller or equal than 1.
  If D_i != P_i for some task, then it is possible to define the density of
  a task as WCET_i/min{D_i,P_i}, and EDF is able to respect all the deadlines
- of all the tasks running on a CPU if the sum sum(WCET_i/min{D_i,P_i}) of the
- densities of the tasks running on such a CPU is smaller or equal than 1
- (notice that this condition is only sufficient, and not necessary).
+ of all the tasks running on a CPU if the sum of the densities of the tasks
+ running on such a CPU is smaller or equal than 1:
+	sum(WCET_i / min{D_i, P_i}) <= 1
+ It is important to notice that this condition is only sufficient, and not
+ necessary: there are task sets that are schedulable, but do not respect the
+ condition. For example, consider the task set {Task_1,Task_2} composed by
+ Task_1=(50ms,50ms,100ms) and Task_2=(10ms,100ms,100ms). 
+ EDF is clearly able to schedule the two tasks without missing any deadline
+ (Task_1 is scheduled as soon as it is released, and finishes just in time
+ to respect its deadline; Task_2 is scheduled immediately after Task_1, hence
+ its response time cannot be larger than 50ms + 10ms = 60ms) even if
+	50 / min{50,100} + 10 / min{100, 100} = 50 / 50 + 10 / 100 = 1.1
+ Of course it is possible to test the exact schedulability of tasks with
+ D_i != P_i (checking a condition that is both sufficient and necessary),
+ but this cannot be done by comparing the total utilisation or density with
+ a constant. Instead, the so called "processor demand" approach can be used,
+ computing the total amount of CPU time h(t) needed by all the tasks to
+ respect all of their deadlines in a time interval of size t, and comparing
+ such a time with the interval size t. If h(t) is smaller than t (that is,
+ the amount of time needed by the tasks in a time interval of size t is
+ smaller than the size of the interval) for all the possible values of t, then
+ EDF is able to schedule the tasks respecting all of their deadlines. Since
+ performing this check for all possible values of t is impossible, it has been
+ proven[4,5,6] that it is sufficient to perform the test for values of t
+ between 0 and a maximum value L. The cited papers contain all of the
+ mathematical details and explain how to compute h(t) and L.
+ In any case, this kind of analysis is too complex as well as too
+ time-consuming to be performed on-line. Hence, as explained in Section
+ 4 Linux uses an admission test based on the tasks' utilisations.
 
  On multiprocessor systems with global EDF scheduling (non partitioned
  systems), a sufficient test for schedulability can not be based on the
@@ -206,6 +234,16 @@ CONTENTS
       Symposium, 1998. http://retis.sssup.it/~giorgio/paps/1998/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

[PATCH 6/8] 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 |   73 +++++++++++++++++++++++++---
 1 file changed, 67 insertions(+), 6 deletions(-)

diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt
index 9663d53..8bec2f5 100644
--- a/Documentation/scheduler/sched-deadline.txt
+++ b/Documentation/scheduler/sched-deadline.txt
@@ -162,7 +162,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{WCET_i} is the maximum WCET, WCET_min=min{WCET_i}
- is the minimum WCET, and U_max = max{WCET_i/P_i} is the maximum utilisation.
+ is the minimum WCET, and U_max = max{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
@@ -204,11 +205,48 @@ 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.
+ 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.
+
+ Consider a set {Task_1,...Task_{M+1}} of M+1 tasks on a system with M 
+ CPUs, with the first task Task_1=(P,P,P) having period, relative deadline
+ and WCET equal to P. The remaining M tasks Task_i=(e,P-1,P-1) have an
+ arbitrarily small worst case execution time (indicated as "e" here) and a
+ period smaller than the one of the first task. Hence, if all the tasks
+ activate at the same time t, global EDF schedules these M tasks first
+ (because their absolute deadlines are equal to t + P - 1, hence they are
+ smaller than the absolute deadline of Task_1, which is t + P). As a
+ result, Task_1 can be scheduled only at time t + e, and will finish at
+ time t + e + P, after its absolute deadline. The total utilisation of the
+ task set is U = M · e / (P - 1) + P / P = M · 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]. Note: the example in the original paper by Dhall has been
+ slightly simplified here (for example, Dhall more correctly computed
+ lim_{e->0}U).
+
+ 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(WCET_i / P_i) <= M - (M - 1) · U_max
+ where U_max = max{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 noted). 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.
 
  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
@@ -244,6 +282,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

[PATCH 7/8] Documentation/scheduler/sched-deadline.txt: relationship between tasks' deadlines and scheduling deadlines

[Luca Abeni]

Clarify what is the relationship between tasks' parameters and scheduling
parameters, explaining how to set the scheduling parameters so that all the
absolute deadlines of a task are respected.
---
 Documentation/scheduler/sched-deadline.txt |   14 +++++++++++---
 1 file changed, 11 insertions(+), 3 deletions(-)

diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt
index 8bec2f5..e605d7f 100644
--- a/Documentation/scheduler/sched-deadline.txt
+++ b/Documentation/scheduler/sched-deadline.txt
@@ -248,9 +248,17 @@ CONTENTS
  the total utilisation is smaller or equal than M then the response times of
  the tasks are limited.
 
- 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:
+ Finally, it is important to understand the relationship between the
+ SCHED_DEADLINE scheduling parameters described in Section 2 (runtime,
+ deadline and period) and the real-time task parameters (WCET, D, P)
+ described in this section. Note that the tasks' temporal constraints are
+ represented by its absolute deadlines d_j = r_j + D described above, while
+ SCHED_DEADLINE schedules the tasks according to scheduling deadlines (see
+ Section 2).
+ 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 all the jobs' deadlines of a task are respected.
+ In order to do this, a task must be scheduled by setting:
 
   - runtime >= WCET
   - deadline = D
-- 
1.7.9.5

[PATCH 8/8] Documentation/scheduler/sched-deadline.txt: Split Section 3

[Luca Abeni]

Introduce 4 subsections to make Section 3 more readable.
---
 Documentation/scheduler/sched-deadline.txt |   16 ++++++++++++++++
 1 file changed, 16 insertions(+)

diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt
index e605d7f..ef7ed7d 100644
--- a/Documentation/scheduler/sched-deadline.txt
+++ b/Documentation/scheduler/sched-deadline.txt
@@ -8,6 +8,10 @@ CONTENTS
  1. Overview
  2. Scheduling algorithm
  3. Scheduling Real-Time Tasks
+   3.1 Definitions 
+   3.2 Schedulability Analysis for Uniprocessor Systems
+   3.3 Schedulability Analysis for Multiprocessor Systems
+   3.4 Relationship with SCHED_DEADLINE Parameters
  4. Bandwidth management
    4.1 System-wide settings
    4.2 Task interface
@@ -126,6 +130,9 @@ CONTENTS
  suited for periodic or sporadic real-time tasks that need guarantees on their
  timing behavior, e.g., multimedia, streaming, control applications, etc.
 
+3.1 Definitions 
+------------------------
+
  A typical real-time task is composed of a repetition of computation phases
  (task instances, or jobs) which are activated on a periodic or sporadic
  fashion.
@@ -165,6 +172,9 @@ CONTENTS
  is the minimum WCET, and U_max = max{WCET_i/P_i} is the maximum
  utilisation[12].
 
+3.2 Schedulability Analysis for Uniprocessor Systems
+------------------------
+
  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
  possible to formally check if all the deadlines are respected.
@@ -203,6 +213,9 @@ CONTENTS
  time-consuming to be performed on-line. Hence, as explained in Section
  4 Linux uses an admission test based on the tasks' utilisations.
 
+3.3 Schedulability Analysis for Multiprocessor Systems
+------------------------
+
  On multiprocessor systems with global EDF scheduling (non partitioned
  systems), a sufficient test for schedulability can not be based on the
  utilisations or densities: it can be shown that even if D_i = P_i task
@@ -248,6 +261,9 @@ CONTENTS
  the total utilisation is smaller or equal than M then the response times of
  the tasks are limited.
 
+3.4 Relationship with SCHED_DEADLINE Parameters
+------------------------
+
  Finally, it is important to understand the relationship between the
  SCHED_DEADLINE scheduling parameters described in Section 2 (runtime,
  deadline and period) and the real-time task parameters (WCET, D, P)
-- 
1.7.9.5

Re: [PATCH 0/8] SCHED_DEADLINE documentation update

[Henrik Austad]

On Fri, Apr 10, 2015 at 12:19:47PM +0200, Luca Abeni wrote:
> Hi all,

Hi Luca, nice work

> here is an update for Documentation/scheduler/sched-deadline.txt.
> Respect to the RFC I sent few days ago, I:
> 1) Split the patches in a better way, (so that, for example, Zhiqiang Zhang's
>    authorship is preserved)
> 2) Tried to address all the comments I received on the RFC
> 3) Added another patch, to split Section 3 in various subsections.
>    I think it is more readable in this way. Anyway, this is the last patch,
>    so it can easily be skipped if people do not like it.
> 
> I also split in a separate patch the discussion about the relationship between
> tasks' parameters and SCHED_DEADLINE parameters. This is (I think) the only
> part of the patchset that has not been previously discussed; I decided to
> isolate it in its own patch so that other patches can be applied anyway.

Apart from a slight nitpick (I didn't bother adding it the thread for patch 
6) that the patch adds more than just references, it also describes Dhall's
effect, perhaps that should be reflected in the patch's subject.

Please consider adding

   Reviewed-by: Henrik Austad <henrik@austad.us>

> 
> 			Thanks,
> 				Luca
> 
> 
> Luca Abeni (7):
>   Documentation/scheduler/sched-deadline.txt: fix typos
>   Documentation/scheduler/sched-deadline.txt: use consistent namings
>   Documentation/scheduler/sched-deadline.txt: remove _i from sum, max
>     and min
>   Documentation/scheduler/sched-deadline.txt: Some notes on EDF
>     schedulability
>   Documentation/scheduler/sched-deadline.txt: add some references
>   Documentation/scheduler/sched-deadline.txt: relationship between
>     tasks' deadlines and scheduling deadlines
>   Documentation/scheduler/sched-deadline.txt: Split Section 3
> 
> Zhiqiang Zhang (1):
>   Documentation/scheduler/sched-deadline.txt: correct definition of
>     density as C_i/min{D_i,P_i}
> 
>  Documentation/scheduler/sched-deadline.txt |  161 ++++++++++++++++++++++++----
>  1 file changed, 142 insertions(+), 19 deletions(-)
> 
> -- 
> 1.7.9.5
> 

-- 
Henrik Austad

Re: [PATCH 0/8] SCHED_DEADLINE documentation update

[Ingo Molnar]

* Luca Abeni <luca.abeni@unitn.it> wrote:

> Hi all,
> 
> here is an update for Documentation/scheduler/sched-deadline.txt.
> Respect to the RFC I sent few days ago, I:
> 1) Split the patches in a better way, (so that, for example, Zhiqiang Zhang's
>    authorship is preserved)
> 2) Tried to address all the comments I received on the RFC
> 3) Added another patch, to split Section 3 in various subsections.
>    I think it is more readable in this way. Anyway, this is the last patch,
>    so it can easily be skipped if people do not like it.
> 
> I also split in a separate patch the discussion about the relationship between
> tasks' parameters and SCHED_DEADLINE parameters. This is (I think) the only
> part of the patchset that has not been previously discussed; I decided to
> isolate it in its own patch so that other patches can be applied anyway.

Note that your Signed-off-by lines are missing.

I also noticed the following inconsistency: 'utilization' (and 
variants) is spelled in two variants in the text: 'utilization' and 
'utilisation'.

I'd strongly suggest using 'utilization' et al (american spelling), 
because that's how it's spelled in most of the kernel source.

Thanks,

	Ingo

Re: [PATCH 0/8] SCHED_DEADLINE documentation update

[Luca Abeni]

Hi,

On 04/12/2015 11:47 AM, Ingo Molnar wrote:
>
> * Luca Abeni <luca.abeni@unitn.it> wrote:
>
>> Hi all,
>>
>> here is an update for Documentation/scheduler/sched-deadline.txt.
>> Respect to the RFC I sent few days ago, I:
>> 1) Split the patches in a better way, (so that, for example, Zhiqiang Zhang's
>>     authorship is preserved)
>> 2) Tried to address all the comments I received on the RFC
>> 3) Added another patch, to split Section 3 in various subsections.
>>     I think it is more readable in this way. Anyway, this is the last patch,
>>     so it can easily be skipped if people do not like it.
>>
>> I also split in a separate patch the discussion about the relationship between
>> tasks' parameters and SCHED_DEADLINE parameters. This is (I think) the only
>> part of the patchset that has not been previously discussed; I decided to
>> isolate it in its own patch so that other patches can be applied anyway.
>
> Note that your Signed-off-by lines are missing.
Ops... I knew I was doing something wrong...


> I also noticed the following inconsistency: 'utilization' (and
> variants) is spelled in two variants in the text: 'utilization' and
> 'utilisation'.
>
> I'd strongly suggest using 'utilization' et al (american spelling),
> because that's how it's spelled in most of the kernel source.
Sorry about that... I have ispell configured to use the british dictionary
as a default.
I think this inconsistency already existed before my patches... So, what should
I do? Should I resend the patchset, adding a patch to convert from british to
american spelling before my new changes? Or can the patches be committed as they
are now, and then I send a follow-up patch to convert the spelling?

In any case, I'll send the new version of the patchset or the follow-up patch
(depending on what is the preferred thing) later this week, on Thursday or on
Friday (right now I am overloaded with work-related stuff).


			Thanks,
				Luca