diff options
author | Luca Abeni <luca.abeni@unitn.it> | 2015-05-18 09:00:25 -0400 |
---|---|---|
committer | Ingo Molnar <mingo@kernel.org> | 2015-05-19 02:39:19 -0400 |
commit | 3a3a58d4068382cf2e05f5c8fd3a0587836dacec (patch) | |
tree | ba17bb382d1f9257121e126e3eaf1a5381f95edd | |
parent | 3aed357ee499c71f589a2537af6ec7785029873f (diff) |
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 <luca.abeni@unitn.it>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: henrik@austad.us
Cc: juri.lelli@gmail.com
Cc: raistlin@linux.it
Link: http://lkml.kernel.org/r/1431954032-16473-3-git-send-email-luca.abeni@unitn.it
Signed-off-by: Ingo Molnar <mingo@kernel.org>
-rw-r--r-- | Documentation/scheduler/sched-deadline.txt | 32 |
1 files changed, 16 insertions, 16 deletions
diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt index 194664bb8bbf..af40d6cc776b 100644 --- a/Documentation/scheduler/sched-deadline.txt +++ b/Documentation/scheduler/sched-deadline.txt | |||
@@ -43,7 +43,7 @@ CONTENTS | |||
43 | "deadline", to schedule tasks. A SCHED_DEADLINE task should receive | 43 | "deadline", to schedule tasks. A SCHED_DEADLINE task should receive |
44 | "runtime" microseconds of execution time every "period" microseconds, and | 44 | "runtime" microseconds of execution time every "period" microseconds, and |
45 | these "runtime" microseconds are available within "deadline" microseconds | 45 | these "runtime" microseconds are available within "deadline" microseconds |
46 | from the beginning of the period. In order to implement this behaviour, | 46 | from the beginning of the period. In order to implement this behavior, |
47 | every time the task wakes up, the scheduler computes a "scheduling deadline" | 47 | every time the task wakes up, the scheduler computes a "scheduling deadline" |
48 | consistent with the guarantee (using the CBS[2,3] algorithm). Tasks are then | 48 | consistent with the guarantee (using the CBS[2,3] algorithm). Tasks are then |
49 | scheduled using EDF[1] on these scheduling deadlines (the task with the | 49 | scheduled using EDF[1] on these scheduling deadlines (the task with the |
@@ -63,7 +63,7 @@ CONTENTS | |||
63 | In more details, the CBS algorithm assigns scheduling deadlines to | 63 | In more details, the CBS algorithm assigns scheduling deadlines to |
64 | tasks in the following way: | 64 | tasks in the following way: |
65 | 65 | ||
66 | - Each SCHED_DEADLINE task is characterised by the "runtime", | 66 | - Each SCHED_DEADLINE task is characterized by the "runtime", |
67 | "deadline", and "period" parameters; | 67 | "deadline", and "period" parameters; |
68 | 68 | ||
69 | - The state of the task is described by a "scheduling deadline", and | 69 | - The state of the task is described by a "scheduling deadline", and |
@@ -78,7 +78,7 @@ CONTENTS | |||
78 | 78 | ||
79 | then, if the scheduling deadline is smaller than the current time, or | 79 | then, if the scheduling deadline is smaller than the current time, or |
80 | this condition is verified, the scheduling deadline and the | 80 | this condition is verified, the scheduling deadline and the |
81 | remaining runtime are re-initialised as | 81 | remaining runtime are re-initialized as |
82 | 82 | ||
83 | scheduling deadline = current time + deadline | 83 | scheduling deadline = current time + deadline |
84 | remaining runtime = runtime | 84 | remaining runtime = runtime |
@@ -129,7 +129,7 @@ CONTENTS | |||
129 | A typical real-time task is composed of a repetition of computation phases | 129 | A typical real-time task is composed of a repetition of computation phases |
130 | (task instances, or jobs) which are activated on a periodic or sporadic | 130 | (task instances, or jobs) which are activated on a periodic or sporadic |
131 | fashion. | 131 | fashion. |
132 | Each job J_j (where J_j is the j^th job of the task) is characterised by an | 132 | Each job J_j (where J_j is the j^th job of the task) is characterized by an |
133 | arrival time r_j (the time when the job starts), an amount of computation | 133 | arrival time r_j (the time when the job starts), an amount of computation |
134 | time c_j needed to finish the job, and a job absolute deadline d_j, which | 134 | time c_j needed to finish the job, and a job absolute deadline d_j, which |
135 | is the time within which the job should be finished. The maximum execution | 135 | is the time within which the job should be finished. The maximum execution |
@@ -137,20 +137,20 @@ CONTENTS | |||
137 | A real-time task can be periodic with period P if r_{j+1} = r_j + P, or | 137 | A real-time task can be periodic with period P if r_{j+1} = r_j + P, or |
138 | sporadic with minimum inter-arrival time P is r_{j+1} >= r_j + P. Finally, | 138 | sporadic with minimum inter-arrival time P is r_{j+1} >= r_j + P. Finally, |
139 | d_j = r_j + D, where D is the task's relative deadline. | 139 | d_j = r_j + D, where D is the task's relative deadline. |
140 | The utilisation of a real-time task is defined as the ratio between its | 140 | The utilization of a real-time task is defined as the ratio between its |
141 | WCET and its period (or minimum inter-arrival time), and represents | 141 | WCET and its period (or minimum inter-arrival time), and represents |
142 | the fraction of CPU time needed to execute the task. | 142 | the fraction of CPU time needed to execute the task. |
143 | 143 | ||
144 | If the total utilisation sum_i(WCET_i/P_i) is larger than M (with M equal | 144 | If the total utilization sum_i(WCET_i/P_i) is larger than M (with M equal |
145 | to the number of CPUs), then the scheduler is unable to respect all the | 145 | to the number of CPUs), then the scheduler is unable to respect all the |
146 | deadlines. | 146 | deadlines. |
147 | Note that total utilisation is defined as the sum of the utilisations | 147 | Note that total utilization is defined as the sum of the utilizations |
148 | WCET_i/P_i over all the real-time tasks in the system. When considering | 148 | WCET_i/P_i over all the real-time tasks in the system. When considering |
149 | multiple real-time tasks, the parameters of the i-th task are indicated | 149 | multiple real-time tasks, the parameters of the i-th task are indicated |
150 | with the "_i" suffix. | 150 | with the "_i" suffix. |
151 | Moreover, if the total utilisation is larger than M, then we risk starving | 151 | Moreover, if the total utilization is larger than M, then we risk starving |
152 | non- real-time tasks by real-time tasks. | 152 | non- real-time tasks by real-time tasks. |
153 | If, instead, the total utilisation is smaller than M, then non real-time | 153 | If, instead, the total utilization is smaller than M, then non real-time |
154 | tasks will not be starved and the system might be able to respect all the | 154 | tasks will not be starved and the system might be able to respect all the |
155 | deadlines. | 155 | deadlines. |
156 | As a matter of fact, in this case it is possible to provide an upper bound | 156 | As a matter of fact, in this case it is possible to provide an upper bound |
@@ -160,13 +160,13 @@ CONTENTS | |||
160 | maximum tardiness of each task is smaller or equal than | 160 | maximum tardiness of each task is smaller or equal than |
161 | ((M − 1) · WCET_max − WCET_min)/(M − (M − 2) · U_max) + WCET_max | 161 | ((M − 1) · WCET_max − WCET_min)/(M − (M − 2) · U_max) + WCET_max |
162 | where WCET_max = max_i{WCET_i} is the maximum WCET, WCET_min=min_i{WCET_i} | 162 | where WCET_max = max_i{WCET_i} is the maximum WCET, WCET_min=min_i{WCET_i} |
163 | is the minimum WCET, and U_max = max_i{WCET_i/P_i} is the maximum utilisation. | 163 | is the minimum WCET, and U_max = max_i{WCET_i/P_i} is the maximum utilization. |
164 | 164 | ||
165 | If M=1 (uniprocessor system), or in case of partitioned scheduling (each | 165 | If M=1 (uniprocessor system), or in case of partitioned scheduling (each |
166 | real-time task is statically assigned to one and only one CPU), it is | 166 | real-time task is statically assigned to one and only one CPU), it is |
167 | possible to formally check if all the deadlines are respected. | 167 | possible to formally check if all the deadlines are respected. |
168 | If D_i = P_i for all tasks, then EDF is able to respect all the deadlines | 168 | If D_i = P_i for all tasks, then EDF is able to respect all the deadlines |
169 | of all the tasks executing on a CPU if and only if the total utilisation | 169 | of all the tasks executing on a CPU if and only if the total utilization |
170 | of the tasks running on such a CPU is smaller or equal than 1. | 170 | of the tasks running on such a CPU is smaller or equal than 1. |
171 | If D_i != P_i for some task, then it is possible to define the density of | 171 | If D_i != P_i for some task, then it is possible to define the density of |
172 | a task as C_i/min{D_i,P_i}, and EDF is able to respect all the deadlines | 172 | a task as C_i/min{D_i,P_i}, and EDF is able to respect all the deadlines |
@@ -176,9 +176,9 @@ CONTENTS | |||
176 | 176 | ||
177 | On multiprocessor systems with global EDF scheduling (non partitioned | 177 | On multiprocessor systems with global EDF scheduling (non partitioned |
178 | systems), a sufficient test for schedulability can not be based on the | 178 | systems), a sufficient test for schedulability can not be based on the |
179 | utilisations (it can be shown that task sets with utilisations slightly | 179 | utilizations (it can be shown that task sets with utilizations slightly |
180 | larger than 1 can miss deadlines regardless of the number of CPUs M). | 180 | larger than 1 can miss deadlines regardless of the number of CPUs M). |
181 | However, as previously stated, enforcing that the total utilisation is smaller | 181 | However, as previously stated, enforcing that the total utilization is smaller |
182 | than M is enough to guarantee that non real-time tasks are not starved and | 182 | than M is enough to guarantee that non real-time tasks are not starved and |
183 | that the tardiness of real-time tasks has an upper bound. | 183 | that the tardiness of real-time tasks has an upper bound. |
184 | 184 | ||
@@ -218,10 +218,10 @@ CONTENTS | |||
218 | no guarantee can be given on the actual scheduling of the -deadline tasks. | 218 | no guarantee can be given on the actual scheduling of the -deadline tasks. |
219 | 219 | ||
220 | As already stated in Section 3, a necessary condition to be respected to | 220 | As already stated in Section 3, a necessary condition to be respected to |
221 | correctly schedule a set of real-time tasks is that the total utilisation | 221 | correctly schedule a set of real-time tasks is that the total utilization |
222 | is smaller than M. When talking about -deadline tasks, this requires that | 222 | is smaller than M. When talking about -deadline tasks, this requires that |
223 | the sum of the ratio between runtime and period for all tasks is smaller | 223 | the sum of the ratio between runtime and period for all tasks is smaller |
224 | than M. Notice that the ratio runtime/period is equivalent to the utilisation | 224 | than M. Notice that the ratio runtime/period is equivalent to the utilization |
225 | of a "traditional" real-time task, and is also often referred to as | 225 | of a "traditional" real-time task, and is also often referred to as |
226 | "bandwidth". | 226 | "bandwidth". |
227 | The interface used to control the CPU bandwidth that can be allocated | 227 | The interface used to control the CPU bandwidth that can be allocated |
@@ -251,7 +251,7 @@ CONTENTS | |||
251 | The system wide settings are configured under the /proc virtual file system. | 251 | The system wide settings are configured under the /proc virtual file system. |
252 | 252 | ||
253 | For now the -rt knobs are used for -deadline admission control and the | 253 | For now the -rt knobs are used for -deadline admission control and the |
254 | -deadline runtime is accounted against the -rt runtime. We realise that this | 254 | -deadline runtime is accounted against the -rt runtime. We realize that this |
255 | isn't entirely desirable; however, it is better to have a small interface for | 255 | isn't entirely desirable; however, it is better to have a small interface for |
256 | now, and be able to change it easily later. The ideal situation (see 5.) is to | 256 | now, and be able to change it easily later. The ideal situation (see 5.) is to |
257 | run -rt tasks from a -deadline server; in which case the -rt bandwidth is a | 257 | run -rt tasks from a -deadline server; in which case the -rt bandwidth is a |