Hi all,
here is an update for Documentation/scheduler/sched-deadline.txt.
Respect to the previous version I sent some time ago, I:
1) Signed-off all my patches (I hope I did it properly, this time :)
2) Added a patch to switch to American English before adding other
changes to the file
3) Converted my changes to American English
Thanks,
Luca
Luca Abeni (8):
Documentation/scheduler/sched-deadline.txt: switch to American
English
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 | 184 +++++++++++++++++++++++-----
1 file changed, 154 insertions(+), 30 deletions(-)
--
1.7.9.5
From: Zhiqiang Zhang <[email protected]>
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 <[email protected]>
---
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
This file previously mixed American and British English; switch to American
for consistency.
Signed-off-by: Luca Abeni <[email protected]>
---
Documentation/scheduler/sched-deadline.txt | 32 ++++++++++++++--------------
1 file changed, 16 insertions(+), 16 deletions(-)
diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt
index 194664b..af40d6c 100644
--- a/Documentation/scheduler/sched-deadline.txt
+++ b/Documentation/scheduler/sched-deadline.txt
@@ -43,7 +43,7 @@ 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. In order to implement this behavior,
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
@@ -63,7 +63,7 @@ CONTENTS
In more details, the CBS algorithm assigns scheduling deadlines to
tasks in the following way:
- - Each SCHED_DEADLINE task is characterised by the "runtime",
+ - Each SCHED_DEADLINE task is characterized by the "runtime",
"deadline", and "period" parameters;
- The state of the task is described by a "scheduling deadline", and
@@ -78,7 +78,7 @@ CONTENTS
then, if the scheduling deadline is smaller than the current time, or
this condition is verified, the scheduling deadline and the
- remaining runtime are re-initialised as
+ remaining runtime are re-initialized as
scheduling deadline = current time + deadline
remaining runtime = runtime
@@ -129,7 +129,7 @@ CONTENTS
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.
- Each job J_j (where J_j is the j^th job of the task) is characterised by an
+ Each job J_j (where J_j is the j^th job of the task) is characterized by an
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
@@ -137,20 +137,20 @@ 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.
- The utilisation of a real-time task is defined as the ratio between its
+ The utilization 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 sum_i(WCET_i/P_i) is larger than M (with M equal
+ If the total utilization sum_i(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
+ Note that total utilization is defined as the sum of the utilizations
WCET_i/P_i over all the real-time tasks in the system. When considering
multiple real-time tasks, the parameters of the i-th task are indicated
with the "_i" suffix.
- Moreover, if the total utilisation is larger than M, then we risk starving
+ Moreover, if the total utilization is larger than M, then we risk starving
non- real-time tasks by real-time tasks.
- If, instead, the total utilisation is smaller than M, then non real-time
+ If, instead, the total utilization is smaller than M, then non real-time
tasks will not be starved and the system might be able to respect all the
deadlines.
As a matter of fact, in this case it is possible to provide an upper bound
@@ -160,13 +160,13 @@ 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 utilization.
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.
If D_i = P_i for all tasks, then EDF is able to respect all the deadlines
- of all the tasks executing on a CPU if and only if the total utilisation
+ of all the tasks executing on a CPU if and only if the total utilization
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
@@ -176,9 +176,9 @@ 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
+ utilizations (it can be shown that task sets with utilizations 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
+ However, as previously stated, enforcing that the total utilization 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.
@@ -218,10 +218,10 @@ CONTENTS
no guarantee can be given on the actual scheduling of the -deadline tasks.
As already stated in Section 3, a necessary condition to be respected to
- correctly schedule a set of real-time tasks is that the total utilisation
+ correctly schedule a set of real-time tasks is that the total utilization
is smaller than M. When talking about -deadline tasks, this requires that
the sum of the ratio between runtime and period for all tasks is smaller
- than M. Notice that the ratio runtime/period is equivalent to the utilisation
+ than M. Notice that the ratio runtime/period is equivalent to the utilization
of a "traditional" real-time task, and is also often referred to as
"bandwidth".
The interface used to control the CPU bandwidth that can be allocated
@@ -251,7 +251,7 @@ CONTENTS
The system wide settings are configured under the /proc virtual file system.
For now the -rt knobs are used for -deadline admission control and the
- -deadline runtime is accounted against the -rt runtime. We realise that this
+ -deadline runtime is accounted against the -rt runtime. We realize that this
isn't entirely desirable; however, it is better to have a small interface for
now, and be able to change it easily later. The ideal situation (see 5.) is to
run -rt tasks from a -deadline server; in which case the -rt bandwidth is a
--
1.7.9.5
Signed-off-by: Luca Abeni <[email protected]>
---
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 af40d6c..0f51a1a 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
The name "C_i" was used (without previously defining it)
instead of "WCET_i".
Signed-off-by: Luca Abeni <[email protected]>
---
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 0f51a1a..73ef489 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 utilization
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
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.
Signed-off-by: Luca Abeni <[email protected]>
---
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 73ef489..c794ebf 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 utilization sum_i(WCET_i/P_i) is larger than M (with M equal
+ If the total utilization 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 utilization is defined as the sum of the utilizations
@@ -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 utilization.
+ 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 utilization.
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
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.
Signed-off-by: Luca Abeni <[email protected]>
---
Documentation/scheduler/sched-deadline.txt | 45 ++++++++++++++++++++++++++--
1 file changed, 42 insertions(+), 3 deletions(-)
diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt
index c794ebf..4df4665 100644
--- a/Documentation/scheduler/sched-deadline.txt
+++ b/Documentation/scheduler/sched-deadline.txt
@@ -137,6 +137,9 @@ 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 utilization 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.
@@ -170,9 +173,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 utilization 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' utilizations.
On multiprocessor systems with global EDF scheduling (non partitioned
systems), a sufficient test for schedulability can not be based on the
@@ -206,6 +235,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
Add a description of the Dhall's effect, some discussion about
schedulability tests for global EDF, and references to real-time literature,
Signed-off-by: Luca Abeni <[email protected]>
---
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 4df4665..bd9ce00 100644
--- a/Documentation/scheduler/sched-deadline.txt
+++ b/Documentation/scheduler/sched-deadline.txt
@@ -163,7 +163,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 utilization.
+ is the minimum WCET, and U_max = max{WCET_i/P_i} is the maximum
+ utilization[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
@@ -205,11 +206,48 @@ CONTENTS
On multiprocessor systems with global EDF scheduling (non partitioned
systems), a sufficient test for schedulability can not be based on the
- utilizations (it can be shown that task sets with utilizations slightly
- larger than 1 can miss deadlines regardless of the number of CPUs M).
- However, as previously stated, enforcing that the total utilization 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.
+ utilizations or densities: it can be shown that even if D_i = P_i task
+ sets with utilizations 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 utilization 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 utilization (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 utilization 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 utilization 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 utilization 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
@@ -245,6 +283,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
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.
Signed-off-by: Luca Abeni <[email protected]>
---
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 bd9ce00..ead13bcc 100644
--- a/Documentation/scheduler/sched-deadline.txt
+++ b/Documentation/scheduler/sched-deadline.txt
@@ -249,9 +249,17 @@ CONTENTS
the total utilization 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
Introduce 4 subsections to make Section 3 more readable.
Signed-off-by: Luca Abeni <[email protected]>
---
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 ead13bcc..163675c 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.
@@ -166,6 +173,9 @@ CONTENTS
is the minimum WCET, and U_max = max{WCET_i/P_i} is the maximum
utilization[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.
@@ -204,6 +214,9 @@ CONTENTS
time-consuming to be performed on-line. Hence, as explained in Section
4 Linux uses an admission test based on the tasks' utilizations.
+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
utilizations or densities: it can be shown that even if D_i = P_i task
@@ -249,6 +262,9 @@ CONTENTS
the total utilization 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
Commit-ID: 3aed357ee499c71f589a2537af6ec7785029873f
Gitweb: http://git.kernel.org/tip/3aed357ee499c71f589a2537af6ec7785029873f
Author: Zhiqiang Zhang <[email protected]>
AuthorDate: Mon, 18 May 2015 15:00:24 +0200
Committer: Ingo Molnar <[email protected]>
CommitDate: Tue, 19 May 2015 08:39:19 +0200
sched/dl/Documentation: Correct the definition of density as C_i/min{D_i,P_i}
C_i/min{D_i,T_i}, where T_i is not referred before, should be
substituted with C_i/min{D_i,P_i}.
Signed-off-by: Zhiqiang Zhang <[email protected]>
Signed-off-by: Peter Zijlstra (Intel) <[email protected]>
Cc: Linus Torvalds <[email protected]>
Cc: Peter Zijlstra <[email protected]>
Cc: Thomas Gleixner <[email protected]>
Cc: [email protected]
Cc: [email protected]
Cc: [email protected]
Link: http://lkml.kernel.org/r/[email protected]
Signed-off-by: Ingo Molnar <[email protected]>
---
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).
Commit-ID: 3a3a58d4068382cf2e05f5c8fd3a0587836dacec
Gitweb: http://git.kernel.org/tip/3a3a58d4068382cf2e05f5c8fd3a0587836dacec
Author: Luca Abeni <[email protected]>
AuthorDate: Mon, 18 May 2015 15:00:25 +0200
Committer: Ingo Molnar <[email protected]>
CommitDate: Tue, 19 May 2015 08:39:19 +0200
sched/dl/Documentation: Switch to American English
This file previously mixed American and British English; switch to American
for consistency.
Signed-off-by: Luca Abeni <[email protected]>
Signed-off-by: Peter Zijlstra (Intel) <[email protected]>
Cc: Linus Torvalds <[email protected]>
Cc: Peter Zijlstra <[email protected]>
Cc: Thomas Gleixner <[email protected]>
Cc: [email protected]
Cc: [email protected]
Cc: [email protected]
Link: http://lkml.kernel.org/r/[email protected]
Signed-off-by: Ingo Molnar <[email protected]>
---
Documentation/scheduler/sched-deadline.txt | 32 +++++++++++++++---------------
1 file changed, 16 insertions(+), 16 deletions(-)
diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt
index 194664b..af40d6c 100644
--- a/Documentation/scheduler/sched-deadline.txt
+++ b/Documentation/scheduler/sched-deadline.txt
@@ -43,7 +43,7 @@ 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. In order to implement this behavior,
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
@@ -63,7 +63,7 @@ CONTENTS
In more details, the CBS algorithm assigns scheduling deadlines to
tasks in the following way:
- - Each SCHED_DEADLINE task is characterised by the "runtime",
+ - Each SCHED_DEADLINE task is characterized by the "runtime",
"deadline", and "period" parameters;
- The state of the task is described by a "scheduling deadline", and
@@ -78,7 +78,7 @@ CONTENTS
then, if the scheduling deadline is smaller than the current time, or
this condition is verified, the scheduling deadline and the
- remaining runtime are re-initialised as
+ remaining runtime are re-initialized as
scheduling deadline = current time + deadline
remaining runtime = runtime
@@ -129,7 +129,7 @@ CONTENTS
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.
- Each job J_j (where J_j is the j^th job of the task) is characterised by an
+ Each job J_j (where J_j is the j^th job of the task) is characterized by an
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
@@ -137,20 +137,20 @@ 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.
- The utilisation of a real-time task is defined as the ratio between its
+ The utilization 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 sum_i(WCET_i/P_i) is larger than M (with M equal
+ If the total utilization sum_i(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
+ Note that total utilization is defined as the sum of the utilizations
WCET_i/P_i over all the real-time tasks in the system. When considering
multiple real-time tasks, the parameters of the i-th task are indicated
with the "_i" suffix.
- Moreover, if the total utilisation is larger than M, then we risk starving
+ Moreover, if the total utilization is larger than M, then we risk starving
non- real-time tasks by real-time tasks.
- If, instead, the total utilisation is smaller than M, then non real-time
+ If, instead, the total utilization is smaller than M, then non real-time
tasks will not be starved and the system might be able to respect all the
deadlines.
As a matter of fact, in this case it is possible to provide an upper bound
@@ -160,13 +160,13 @@ 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 utilization.
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.
If D_i = P_i for all tasks, then EDF is able to respect all the deadlines
- of all the tasks executing on a CPU if and only if the total utilisation
+ of all the tasks executing on a CPU if and only if the total utilization
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
@@ -176,9 +176,9 @@ 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
+ utilizations (it can be shown that task sets with utilizations 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
+ However, as previously stated, enforcing that the total utilization 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.
@@ -218,10 +218,10 @@ CONTENTS
no guarantee can be given on the actual scheduling of the -deadline tasks.
As already stated in Section 3, a necessary condition to be respected to
- correctly schedule a set of real-time tasks is that the total utilisation
+ correctly schedule a set of real-time tasks is that the total utilization
is smaller than M. When talking about -deadline tasks, this requires that
the sum of the ratio between runtime and period for all tasks is smaller
- than M. Notice that the ratio runtime/period is equivalent to the utilisation
+ than M. Notice that the ratio runtime/period is equivalent to the utilization
of a "traditional" real-time task, and is also often referred to as
"bandwidth".
The interface used to control the CPU bandwidth that can be allocated
@@ -251,7 +251,7 @@ CONTENTS
The system wide settings are configured under the /proc virtual file system.
For now the -rt knobs are used for -deadline admission control and the
- -deadline runtime is accounted against the -rt runtime. We realise that this
+ -deadline runtime is accounted against the -rt runtime. We realize that this
isn't entirely desirable; however, it is better to have a small interface for
now, and be able to change it easily later. The ideal situation (see 5.) is to
run -rt tasks from a -deadline server; in which case the -rt bandwidth is a
Commit-ID: 3aa2dbe27f76528660e18b21f88a2c78ea8996ba
Gitweb: http://git.kernel.org/tip/3aa2dbe27f76528660e18b21f88a2c78ea8996ba
Author: Luca Abeni <[email protected]>
AuthorDate: Mon, 18 May 2015 15:00:26 +0200
Committer: Ingo Molnar <[email protected]>
CommitDate: Tue, 19 May 2015 08:39:19 +0200
sched/dl/Documentation: Fix typos
Signed-off-by: Luca Abeni <[email protected]>
Signed-off-by: Peter Zijlstra (Intel) <[email protected]>
Cc: Linus Torvalds <[email protected]>
Cc: Peter Zijlstra <[email protected]>
Cc: Thomas Gleixner <[email protected]>
Cc: [email protected]
Cc: [email protected]
Cc: [email protected]
Link: http://lkml.kernel.org/r/[email protected]
Signed-off-by: Ingo Molnar <[email protected]>
---
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 af40d6c..0f51a1a 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]).
Commit-ID: 48355c4775741ee15b66bad7d09b263d93ce86f8
Gitweb: http://git.kernel.org/tip/48355c4775741ee15b66bad7d09b263d93ce86f8
Author: Luca Abeni <[email protected]>
AuthorDate: Mon, 18 May 2015 15:00:27 +0200
Committer: Ingo Molnar <[email protected]>
CommitDate: Tue, 19 May 2015 08:39:20 +0200
sched/dl/Documentation: Use consistent naming
The name "C_i" was used (without previously defining it)
instead of "WCET_i".
Signed-off-by: Luca Abeni <[email protected]>
Signed-off-by: Peter Zijlstra (Intel) <[email protected]>
Cc: Linus Torvalds <[email protected]>
Cc: Peter Zijlstra <[email protected]>
Cc: Thomas Gleixner <[email protected]>
Cc: [email protected]
Cc: [email protected]
Cc: [email protected]
Link: http://lkml.kernel.org/r/[email protected]
Signed-off-by: Ingo Molnar <[email protected]>
---
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 0f51a1a..73ef489 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 utilization
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).
Commit-ID: c2a684930fce07f19d1a52d7bbe7474fe64fde31
Gitweb: http://git.kernel.org/tip/c2a684930fce07f19d1a52d7bbe7474fe64fde31
Author: Luca Abeni <[email protected]>
AuthorDate: Mon, 18 May 2015 15:00:28 +0200
Committer: Ingo Molnar <[email protected]>
CommitDate: Tue, 19 May 2015 08:39:20 +0200
sched/dl/Documentation: Clarify indexing notation
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.
Signed-off-by: Luca Abeni <[email protected]>
Signed-off-by: Peter Zijlstra (Intel) <[email protected]>
Cc: Linus Torvalds <[email protected]>
Cc: Peter Zijlstra <[email protected]>
Cc: Thomas Gleixner <[email protected]>
Cc: [email protected]
Cc: [email protected]
Cc: [email protected]
Link: http://lkml.kernel.org/r/[email protected]
Signed-off-by: Ingo Molnar <[email protected]>
---
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 73ef489..c794ebf 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 utilization sum_i(WCET_i/P_i) is larger than M (with M equal
+ If the total utilization 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 utilization is defined as the sum of the utilizations
@@ -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 utilization.
+ 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 utilization.
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).
Commit-ID: e0deda8142a60e4a39d5ba2ea47294a851b4309a
Gitweb: http://git.kernel.org/tip/e0deda8142a60e4a39d5ba2ea47294a851b4309a
Author: Luca Abeni <[email protected]>
AuthorDate: Mon, 18 May 2015 15:00:29 +0200
Committer: Ingo Molnar <[email protected]>
CommitDate: Tue, 19 May 2015 08:39:20 +0200
sched/dl/Documentation: Add some notes on EDF schedulability
Add a short discussion about sufficient and necessary schedulability tests,
and add 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.
Signed-off-by: Luca Abeni <[email protected]>
Signed-off-by: Peter Zijlstra (Intel) <[email protected]>
Cc: Linus Torvalds <[email protected]>
Cc: Peter Zijlstra <[email protected]>
Cc: Thomas Gleixner <[email protected]>
Cc: [email protected]
Cc: [email protected]
Cc: [email protected]
Link: http://lkml.kernel.org/r/[email protected]
Signed-off-by: Ingo Molnar <[email protected]>
---
Documentation/scheduler/sched-deadline.txt | 45 ++++++++++++++++++++++++++++--
1 file changed, 42 insertions(+), 3 deletions(-)
diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt
index c794ebf..bd4123b 100644
--- a/Documentation/scheduler/sched-deadline.txt
+++ b/Documentation/scheduler/sched-deadline.txt
@@ -137,6 +137,9 @@ 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 utilization 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.
@@ -170,9 +173,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 utilization 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' utilizations.
On multiprocessor systems with global EDF scheduling (non partitioned
systems), a sufficient test for schedulability can not be based on the
@@ -206,6 +235,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
=======================
Commit-ID: 134136c4b730c1a4830a8b74e2717d858291361b
Gitweb: http://git.kernel.org/tip/134136c4b730c1a4830a8b74e2717d858291361b
Author: Luca Abeni <[email protected]>
AuthorDate: Mon, 18 May 2015 15:00:30 +0200
Committer: Ingo Molnar <[email protected]>
CommitDate: Tue, 19 May 2015 08:39:21 +0200
sched/dl/Documentation: Add some references
Add a description of the Dhall's effect, some discussion about
schedulability tests for global EDF, and references to real-time
literature.
Signed-off-by: Luca Abeni <[email protected]>
Signed-off-by: Peter Zijlstra (Intel) <[email protected]>
Cc: Linus Torvalds <[email protected]>
Cc: Peter Zijlstra <[email protected]>
Cc: Thomas Gleixner <[email protected]>
Cc: [email protected]
Cc: [email protected]
Cc: [email protected]
Link: http://lkml.kernel.org/r/[email protected]
Signed-off-by: Ingo Molnar <[email protected]>
---
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 bd4123b..984a01d 100644
--- a/Documentation/scheduler/sched-deadline.txt
+++ b/Documentation/scheduler/sched-deadline.txt
@@ -163,7 +163,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 utilization.
+ is the minimum WCET, and U_max = max{WCET_i/P_i} is the maximum
+ utilization[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
@@ -205,11 +206,48 @@ CONTENTS
On multiprocessor systems with global EDF scheduling (non partitioned
systems), a sufficient test for schedulability can not be based on the
- utilizations (it can be shown that task sets with utilizations slightly
- larger than 1 can miss deadlines regardless of the number of CPUs M).
- However, as previously stated, enforcing that the total utilization 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.
+ utilizations or densities: it can be shown that even if D_i = P_i task
+ sets with utilizations 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 utilization 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 utilization (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 utilization 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 utilization 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 utilization 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
@@ -245,6 +283,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
=======================
Commit-ID: 78740858903460d4b926b9a90c705fcb6103da54
Gitweb: http://git.kernel.org/tip/78740858903460d4b926b9a90c705fcb6103da54
Author: Luca Abeni <[email protected]>
AuthorDate: Mon, 18 May 2015 15:00:31 +0200
Committer: Ingo Molnar <[email protected]>
CommitDate: Tue, 19 May 2015 08:39:21 +0200
sched/dl/Documentation: Clarify the relationship between tasks' deadlines and absolute scheduling deadlines
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.
Signed-off-by: Luca Abeni <[email protected]>
Signed-off-by: Peter Zijlstra (Intel) <[email protected]>
Cc: Linus Torvalds <[email protected]>
Cc: Peter Zijlstra <[email protected]>
Cc: Thomas Gleixner <[email protected]>
Cc: [email protected]
Cc: [email protected]
Cc: [email protected]
Link: http://lkml.kernel.org/r/[email protected]
Signed-off-by: Ingo Molnar <[email protected]>
---
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 984a01d..2a924e1 100644
--- a/Documentation/scheduler/sched-deadline.txt
+++ b/Documentation/scheduler/sched-deadline.txt
@@ -249,9 +249,17 @@ CONTENTS
the total utilization 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
Commit-ID: 6aaa10254dfe61c8c5e87c26e21be0664782a5b4
Gitweb: http://git.kernel.org/tip/6aaa10254dfe61c8c5e87c26e21be0664782a5b4
Author: Luca Abeni <[email protected]>
AuthorDate: Mon, 18 May 2015 15:00:32 +0200
Committer: Ingo Molnar <[email protected]>
CommitDate: Tue, 19 May 2015 08:39:21 +0200
sched/dl/Documentation: Split Section 3
Introduce 4 subsections to make Section 3 more readable.
Signed-off-by: Luca Abeni <[email protected]>
Signed-off-by: Peter Zijlstra (Intel) <[email protected]>
Cc: Linus Torvalds <[email protected]>
Cc: Peter Zijlstra <[email protected]>
Cc: Thomas Gleixner <[email protected]>
Cc: [email protected]
Cc: [email protected]
Cc: [email protected]
Link: http://lkml.kernel.org/r/[email protected]
Signed-off-by: Ingo Molnar <[email protected]>
---
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 2a924e1..e114513 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.
@@ -166,6 +173,9 @@ CONTENTS
is the minimum WCET, and U_max = max{WCET_i/P_i} is the maximum
utilization[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.
@@ -204,6 +214,9 @@ CONTENTS
time-consuming to be performed on-line. Hence, as explained in Section
4 Linux uses an admission test based on the tasks' utilizations.
+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
utilizations or densities: it can be shown that even if D_i = P_i task
@@ -249,6 +262,9 @@ CONTENTS
the total utilization 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)
On Mon, May 18, 2015 at 03:00:23PM +0200, Luca Abeni wrote:
> Hi all,
Hi Luca, from my point of view, it looks good! (I still think the M+1
describing Dhall's effect is confusing, but that's probably more about me
than the text itself :)
To the series;
Reviewed-by: Henrik Austad <[email protected]>
> here is an update for Documentation/scheduler/sched-deadline.txt.
> Respect to the previous version I sent some time ago, I:
> 1) Signed-off all my patches (I hope I did it properly, this time :)
> 2) Added a patch to switch to American English before adding other
> changes to the file
> 3) Converted my changes to American English
>
>
>
> Thanks,
> Luca
>
>
> Luca Abeni (8):
> Documentation/scheduler/sched-deadline.txt: switch to American
> English
> 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 | 184 +++++++++++++++++++++++-----
> 1 file changed, 154 insertions(+), 30 deletions(-)
>
> --
> 1.7.9.5
>
--
Henrik Austad