aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorLuca Abeni <luca.abeni@unitn.it>2015-05-18 09:00:25 -0400
committerIngo Molnar <mingo@kernel.org>2015-05-19 02:39:19 -0400
commit3a3a58d4068382cf2e05f5c8fd3a0587836dacec (patch)
treeba17bb382d1f9257121e126e3eaf1a5381f95edd
parent3aed357ee499c71f589a2537af6ec7785029873f (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.txt32
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