Commit | Line | Data |
---|---|---|
d6a3b247 MCC |
1 | ======================== |
2 | Deadline Task Scheduling | |
3 | ======================== | |
4 | ||
5 | .. CONTENTS | |
6 | ||
7 | 0. WARNING | |
8 | 1. Overview | |
9 | 2. Scheduling algorithm | |
10 | 2.1 Main algorithm | |
11 | 2.2 Bandwidth reclaiming | |
12 | 3. Scheduling Real-Time Tasks | |
13 | 3.1 Definitions | |
14 | 3.2 Schedulability Analysis for Uniprocessor Systems | |
15 | 3.3 Schedulability Analysis for Multiprocessor Systems | |
16 | 3.4 Relationship with SCHED_DEADLINE Parameters | |
17 | 4. Bandwidth management | |
18 | 4.1 System-wide settings | |
19 | 4.2 Task interface | |
20 | 4.3 Default behavior | |
21 | 4.4 Behavior of sched_yield() | |
22 | 5. Tasks CPU affinity | |
23 | 5.1 SCHED_DEADLINE and cpusets HOWTO | |
24 | 6. Future plans | |
25 | A. Test suite | |
26 | B. Minimal main() | |
712e5e34 DF |
27 | |
28 | ||
29 | 0. WARNING | |
30 | ========== | |
31 | ||
32 | Fiddling with these settings can result in an unpredictable or even unstable | |
33 | system behavior. As for -rt (group) scheduling, it is assumed that root users | |
34 | know what they're doing. | |
35 | ||
36 | ||
37 | 1. Overview | |
38 | =========== | |
39 | ||
40 | The SCHED_DEADLINE policy contained inside the sched_dl scheduling class is | |
41 | basically an implementation of the Earliest Deadline First (EDF) scheduling | |
42 | algorithm, augmented with a mechanism (called Constant Bandwidth Server, CBS) | |
43 | that makes it possible to isolate the behavior of tasks between each other. | |
44 | ||
45 | ||
46 | 2. Scheduling algorithm | |
d6a3b247 | 47 | ======================= |
712e5e34 | 48 | |
ccc9d651 CS |
49 | 2.1 Main algorithm |
50 | ------------------ | |
51 | ||
bb4e30a4 | 52 | SCHED_DEADLINE [18] uses three parameters, named "runtime", "period", and |
b56bfc6c | 53 | "deadline", to schedule tasks. A SCHED_DEADLINE task should receive |
712e5e34 DF |
54 | "runtime" microseconds of execution time every "period" microseconds, and |
55 | these "runtime" microseconds are available within "deadline" microseconds | |
3a3a58d4 | 56 | from the beginning of the period. In order to implement this behavior, |
712e5e34 DF |
57 | every time the task wakes up, the scheduler computes a "scheduling deadline" |
58 | consistent with the guarantee (using the CBS[2,3] algorithm). Tasks are then | |
59 | scheduled using EDF[1] on these scheduling deadlines (the task with the | |
b56bfc6c LA |
60 | earliest scheduling deadline is selected for execution). Notice that the |
61 | task actually receives "runtime" time units within "deadline" if a proper | |
62 | "admission control" strategy (see Section "4. Bandwidth management") is used | |
63 | (clearly, if the system is overloaded this guarantee cannot be respected). | |
712e5e34 | 64 | |
3aa2dbe2 | 65 | Summing up, the CBS[2,3] algorithm assigns scheduling deadlines to tasks so |
712e5e34 DF |
66 | that each task runs for at most its runtime every period, avoiding any |
67 | interference between different tasks (bandwidth isolation), while the EDF[1] | |
ad67dc31 LA |
68 | algorithm selects the task with the earliest scheduling deadline as the one |
69 | to be executed next. Thanks to this feature, tasks that do not strictly comply | |
70 | with the "traditional" real-time task model (see Section 3) can effectively | |
71 | use the new policy. | |
712e5e34 DF |
72 | |
73 | In more details, the CBS algorithm assigns scheduling deadlines to | |
74 | tasks in the following way: | |
75 | ||
3a3a58d4 | 76 | - Each SCHED_DEADLINE task is characterized by the "runtime", |
712e5e34 DF |
77 | "deadline", and "period" parameters; |
78 | ||
79 | - The state of the task is described by a "scheduling deadline", and | |
ad67dc31 | 80 | a "remaining runtime". These two parameters are initially set to 0; |
712e5e34 DF |
81 | |
82 | - When a SCHED_DEADLINE task wakes up (becomes ready for execution), | |
d6a3b247 | 83 | the scheduler checks if:: |
712e5e34 | 84 | |
ad67dc31 LA |
85 | remaining runtime runtime |
86 | ---------------------------------- > --------- | |
87 | scheduling deadline - current time period | |
712e5e34 DF |
88 | |
89 | then, if the scheduling deadline is smaller than the current time, or | |
90 | this condition is verified, the scheduling deadline and the | |
3a3a58d4 | 91 | remaining runtime are re-initialized as |
712e5e34 DF |
92 | |
93 | scheduling deadline = current time + deadline | |
ad67dc31 | 94 | remaining runtime = runtime |
712e5e34 | 95 | |
ad67dc31 | 96 | otherwise, the scheduling deadline and the remaining runtime are |
712e5e34 DF |
97 | left unchanged; |
98 | ||
99 | - When a SCHED_DEADLINE task executes for an amount of time t, its | |
d6a3b247 | 100 | remaining runtime is decreased as:: |
712e5e34 | 101 | |
ad67dc31 | 102 | remaining runtime = remaining runtime - t |
712e5e34 DF |
103 | |
104 | (technically, the runtime is decreased at every tick, or when the | |
105 | task is descheduled / preempted); | |
106 | ||
ad67dc31 | 107 | - When the remaining runtime becomes less or equal than 0, the task is |
712e5e34 DF |
108 | said to be "throttled" (also known as "depleted" in real-time literature) |
109 | and cannot be scheduled until its scheduling deadline. The "replenishment | |
110 | time" for this task (see next item) is set to be equal to the current | |
111 | value of the scheduling deadline; | |
112 | ||
113 | - When the current time is equal to the replenishment time of a | |
ad67dc31 | 114 | throttled task, the scheduling deadline and the remaining runtime are |
d6a3b247 | 115 | updated as:: |
712e5e34 DF |
116 | |
117 | scheduling deadline = scheduling deadline + period | |
ad67dc31 | 118 | remaining runtime = remaining runtime + runtime |
712e5e34 | 119 | |
bb4e30a4 CS |
120 | The SCHED_FLAG_DL_OVERRUN flag in sched_attr's sched_flags field allows a task |
121 | to get informed about runtime overruns through the delivery of SIGXCPU | |
122 | signals. | |
123 | ||
712e5e34 | 124 | |
ccc9d651 CS |
125 | 2.2 Bandwidth reclaiming |
126 | ------------------------ | |
127 | ||
128 | Bandwidth reclaiming for deadline tasks is based on the GRUB (Greedy | |
129 | Reclamation of Unused Bandwidth) algorithm [15, 16, 17] and it is enabled | |
130 | when flag SCHED_FLAG_RECLAIM is set. | |
131 | ||
d6a3b247 | 132 | The following diagram illustrates the state names for tasks handled by GRUB:: |
ccc9d651 CS |
133 | |
134 | ------------ | |
135 | (d) | Active | | |
136 | ------------->| | | |
137 | | | Contending | | |
138 | | ------------ | |
139 | | A | | |
140 | ---------- | | | |
141 | | | | | | |
142 | | Inactive | |(b) | (a) | |
143 | | | | | | |
144 | ---------- | | | |
145 | A | V | |
146 | | ------------ | |
147 | | | Active | | |
148 | --------------| Non | | |
149 | (c) | Contending | | |
150 | ------------ | |
151 | ||
152 | A task can be in one of the following states: | |
153 | ||
154 | - ActiveContending: if it is ready for execution (or executing); | |
155 | ||
156 | - ActiveNonContending: if it just blocked and has not yet surpassed the 0-lag | |
157 | time; | |
158 | ||
159 | - Inactive: if it is blocked and has surpassed the 0-lag time. | |
160 | ||
161 | State transitions: | |
162 | ||
163 | (a) When a task blocks, it does not become immediately inactive since its | |
164 | bandwidth cannot be immediately reclaimed without breaking the | |
165 | real-time guarantees. It therefore enters a transitional state called | |
166 | ActiveNonContending. The scheduler arms the "inactive timer" to fire at | |
167 | the 0-lag time, when the task's bandwidth can be reclaimed without | |
168 | breaking the real-time guarantees. | |
169 | ||
170 | The 0-lag time for a task entering the ActiveNonContending state is | |
d6a3b247 | 171 | computed as:: |
ccc9d651 CS |
172 | |
173 | (runtime * dl_period) | |
174 | deadline - --------------------- | |
175 | dl_runtime | |
176 | ||
177 | where runtime is the remaining runtime, while dl_runtime and dl_period | |
178 | are the reservation parameters. | |
179 | ||
180 | (b) If the task wakes up before the inactive timer fires, the task re-enters | |
181 | the ActiveContending state and the "inactive timer" is canceled. | |
182 | In addition, if the task wakes up on a different runqueue, then | |
183 | the task's utilization must be removed from the previous runqueue's active | |
184 | utilization and must be added to the new runqueue's active utilization. | |
185 | In order to avoid races between a task waking up on a runqueue while the | |
d6a3b247 | 186 | "inactive timer" is running on a different CPU, the "dl_non_contending" |
ccc9d651 CS |
187 | flag is used to indicate that a task is not on a runqueue but is active |
188 | (so, the flag is set when the task blocks and is cleared when the | |
189 | "inactive timer" fires or when the task wakes up). | |
190 | ||
191 | (c) When the "inactive timer" fires, the task enters the Inactive state and | |
192 | its utilization is removed from the runqueue's active utilization. | |
193 | ||
194 | (d) When an inactive task wakes up, it enters the ActiveContending state and | |
195 | its utilization is added to the active utilization of the runqueue where | |
196 | it has been enqueued. | |
197 | ||
198 | For each runqueue, the algorithm GRUB keeps track of two different bandwidths: | |
199 | ||
200 | - Active bandwidth (running_bw): this is the sum of the bandwidths of all | |
201 | tasks in active state (i.e., ActiveContending or ActiveNonContending); | |
202 | ||
203 | - Total bandwidth (this_bw): this is the sum of all tasks "belonging" to the | |
204 | runqueue, including the tasks in Inactive state. | |
205 | ||
e20f204c VP |
206 | - Maximum usable bandwidth (max_bw): This is the maximum bandwidth usable by |
207 | deadline tasks and is currently set to the RT capacity. | |
208 | ||
ccc9d651 CS |
209 | |
210 | The algorithm reclaims the bandwidth of the tasks in Inactive state. | |
211 | It does so by decrementing the runtime of the executing task Ti at a pace equal | |
212 | to | |
213 | ||
e20f204c | 214 | dq = -(max{ Ui, (Umax - Uinact - Uextra) } / Umax) dt |
ccc9d651 | 215 | |
5c0342ca CS |
216 | where: |
217 | ||
218 | - Ui is the bandwidth of task Ti; | |
219 | - Umax is the maximum reclaimable utilization (subjected to RT throttling | |
220 | limits); | |
221 | - Uinact is the (per runqueue) inactive utilization, computed as | |
222 | (this_bq - running_bw); | |
223 | - Uextra is the (per runqueue) extra reclaimable utilization | |
224 | (subjected to RT throttling limits). | |
ccc9d651 CS |
225 | |
226 | ||
227 | Let's now see a trivial example of two deadline tasks with runtime equal | |
d6a3b247 MCC |
228 | to 4 and period equal to 8 (i.e., bandwidth equal to 0.5):: |
229 | ||
230 | A Task T1 | |
231 | | | |
232 | | | | |
233 | | | | |
234 | |-------- |---- | |
235 | | | V | |
236 | |---|---|---|---|---|---|---|---|--------->t | |
237 | 0 1 2 3 4 5 6 7 8 | |
238 | ||
239 | ||
240 | A Task T2 | |
241 | | | |
242 | | | | |
243 | | | | |
244 | | ------------------------| | |
245 | | | V | |
246 | |---|---|---|---|---|---|---|---|--------->t | |
247 | 0 1 2 3 4 5 6 7 8 | |
248 | ||
249 | ||
250 | A running_bw | |
251 | | | |
252 | 1 ----------------- ------ | |
253 | | | | | |
254 | 0.5- ----------------- | |
255 | | | | |
256 | |---|---|---|---|---|---|---|---|--------->t | |
257 | 0 1 2 3 4 5 6 7 8 | |
ccc9d651 CS |
258 | |
259 | ||
260 | - Time t = 0: | |
261 | ||
262 | Both tasks are ready for execution and therefore in ActiveContending state. | |
263 | Suppose Task T1 is the first task to start execution. | |
264 | Since there are no inactive tasks, its runtime is decreased as dq = -1 dt. | |
265 | ||
266 | - Time t = 2: | |
267 | ||
268 | Suppose that task T1 blocks | |
269 | Task T1 therefore enters the ActiveNonContending state. Since its remaining | |
270 | runtime is equal to 2, its 0-lag time is equal to t = 4. | |
271 | Task T2 start execution, with runtime still decreased as dq = -1 dt since | |
272 | there are no inactive tasks. | |
273 | ||
274 | - Time t = 4: | |
275 | ||
276 | This is the 0-lag time for Task T1. Since it didn't woken up in the | |
277 | meantime, it enters the Inactive state. Its bandwidth is removed from | |
278 | running_bw. | |
279 | Task T2 continues its execution. However, its runtime is now decreased as | |
280 | dq = - 0.5 dt because Uinact = 0.5. | |
281 | Task T2 therefore reclaims the bandwidth unused by Task T1. | |
282 | ||
283 | - Time t = 8: | |
284 | ||
285 | Task T1 wakes up. It enters the ActiveContending state again, and the | |
286 | running_bw is incremented. | |
287 | ||
288 | ||
bb4e30a4 | 289 | 2.3 Energy-aware scheduling |
d6a3b247 | 290 | --------------------------- |
bb4e30a4 CS |
291 | |
292 | When cpufreq's schedutil governor is selected, SCHED_DEADLINE implements the | |
293 | GRUB-PA [19] algorithm, reducing the CPU operating frequency to the minimum | |
294 | value that still allows to meet the deadlines. This behavior is currently | |
295 | implemented only for ARM architectures. | |
296 | ||
297 | A particular care must be taken in case the time needed for changing frequency | |
298 | is of the same order of magnitude of the reservation period. In such cases, | |
299 | setting a fixed CPU frequency results in a lower amount of deadline misses. | |
300 | ||
301 | ||
712e5e34 DF |
302 | 3. Scheduling Real-Time Tasks |
303 | ============================= | |
304 | ||
d6a3b247 MCC |
305 | |
306 | ||
307 | .. BIG FAT WARNING ****************************************************** | |
308 | ||
309 | .. warning:: | |
310 | ||
311 | This section contains a (not-thorough) summary on classical deadline | |
312 | scheduling theory, and how it applies to SCHED_DEADLINE. | |
313 | The reader can "safely" skip to Section 4 if only interested in seeing | |
314 | how the scheduling policy can be used. Anyway, we strongly recommend | |
315 | to come back here and continue reading (once the urge for testing is | |
316 | satisfied :P) to be sure of fully understanding all technical details. | |
317 | ||
318 | .. ************************************************************************ | |
712e5e34 DF |
319 | |
320 | There are no limitations on what kind of task can exploit this new | |
321 | scheduling discipline, even if it must be said that it is particularly | |
322 | suited for periodic or sporadic real-time tasks that need guarantees on their | |
323 | timing behavior, e.g., multimedia, streaming, control applications, etc. | |
324 | ||
6aaa1025 LA |
325 | 3.1 Definitions |
326 | ------------------------ | |
327 | ||
712e5e34 DF |
328 | A typical real-time task is composed of a repetition of computation phases |
329 | (task instances, or jobs) which are activated on a periodic or sporadic | |
330 | fashion. | |
3a3a58d4 | 331 | Each job J_j (where J_j is the j^th job of the task) is characterized by an |
712e5e34 DF |
332 | arrival time r_j (the time when the job starts), an amount of computation |
333 | time c_j needed to finish the job, and a job absolute deadline d_j, which | |
334 | is the time within which the job should be finished. The maximum execution | |
c2a68493 | 335 | time max{c_j} is called "Worst Case Execution Time" (WCET) for the task. |
712e5e34 DF |
336 | A real-time task can be periodic with period P if r_{j+1} = r_j + P, or |
337 | sporadic with minimum inter-arrival time P is r_{j+1} >= r_j + P. Finally, | |
338 | d_j = r_j + D, where D is the task's relative deadline. | |
e0deda81 | 339 | Summing up, a real-time task can be described as |
d6a3b247 | 340 | |
e0deda81 LA |
341 | Task = (WCET, D, P) |
342 | ||
3a3a58d4 | 343 | The utilization of a real-time task is defined as the ratio between its |
b56bfc6c LA |
344 | WCET and its period (or minimum inter-arrival time), and represents |
345 | the fraction of CPU time needed to execute the task. | |
346 | ||
c2a68493 | 347 | If the total utilization U=sum(WCET_i/P_i) is larger than M (with M equal |
b56bfc6c LA |
348 | to the number of CPUs), then the scheduler is unable to respect all the |
349 | deadlines. | |
3a3a58d4 | 350 | Note that total utilization is defined as the sum of the utilizations |
b56bfc6c LA |
351 | WCET_i/P_i over all the real-time tasks in the system. When considering |
352 | multiple real-time tasks, the parameters of the i-th task are indicated | |
353 | with the "_i" suffix. | |
3a3a58d4 | 354 | Moreover, if the total utilization is larger than M, then we risk starving |
b56bfc6c | 355 | non- real-time tasks by real-time tasks. |
3a3a58d4 | 356 | If, instead, the total utilization is smaller than M, then non real-time |
b56bfc6c LA |
357 | tasks will not be starved and the system might be able to respect all the |
358 | deadlines. | |
359 | As a matter of fact, in this case it is possible to provide an upper bound | |
360 | for tardiness (defined as the maximum between 0 and the difference | |
361 | between the finishing time of a job and its absolute deadline). | |
362 | More precisely, it can be proven that using a global EDF scheduler the | |
363 | maximum tardiness of each task is smaller or equal than | |
d6a3b247 | 364 | |
b56bfc6c | 365 | ((M − 1) · WCET_max − WCET_min)/(M − (M − 2) · U_max) + WCET_max |
d6a3b247 | 366 | |
c2a68493 | 367 | where WCET_max = max{WCET_i} is the maximum WCET, WCET_min=min{WCET_i} |
134136c4 LA |
368 | is the minimum WCET, and U_max = max{WCET_i/P_i} is the maximum |
369 | utilization[12]. | |
b56bfc6c | 370 | |
6aaa1025 | 371 | 3.2 Schedulability Analysis for Uniprocessor Systems |
d6a3b247 | 372 | ---------------------------------------------------- |
6aaa1025 | 373 | |
b56bfc6c LA |
374 | If M=1 (uniprocessor system), or in case of partitioned scheduling (each |
375 | real-time task is statically assigned to one and only one CPU), it is | |
376 | possible to formally check if all the deadlines are respected. | |
377 | If D_i = P_i for all tasks, then EDF is able to respect all the deadlines | |
3a3a58d4 | 378 | of all the tasks executing on a CPU if and only if the total utilization |
b56bfc6c LA |
379 | of the tasks running on such a CPU is smaller or equal than 1. |
380 | If D_i != P_i for some task, then it is possible to define the density of | |
48355c47 | 381 | a task as WCET_i/min{D_i,P_i}, and EDF is able to respect all the deadlines |
e0deda81 LA |
382 | of all the tasks running on a CPU if the sum of the densities of the tasks |
383 | running on such a CPU is smaller or equal than 1: | |
d6a3b247 | 384 | |
e0deda81 | 385 | sum(WCET_i / min{D_i, P_i}) <= 1 |
d6a3b247 | 386 | |
e0deda81 LA |
387 | It is important to notice that this condition is only sufficient, and not |
388 | necessary: there are task sets that are schedulable, but do not respect the | |
389 | condition. For example, consider the task set {Task_1,Task_2} composed by | |
390 | Task_1=(50ms,50ms,100ms) and Task_2=(10ms,100ms,100ms). | |
391 | EDF is clearly able to schedule the two tasks without missing any deadline | |
392 | (Task_1 is scheduled as soon as it is released, and finishes just in time | |
393 | to respect its deadline; Task_2 is scheduled immediately after Task_1, hence | |
394 | its response time cannot be larger than 50ms + 10ms = 60ms) even if | |
d6a3b247 | 395 | |
e0deda81 | 396 | 50 / min{50,100} + 10 / min{100, 100} = 50 / 50 + 10 / 100 = 1.1 |
d6a3b247 | 397 | |
e0deda81 LA |
398 | Of course it is possible to test the exact schedulability of tasks with |
399 | D_i != P_i (checking a condition that is both sufficient and necessary), | |
400 | but this cannot be done by comparing the total utilization or density with | |
401 | a constant. Instead, the so called "processor demand" approach can be used, | |
402 | computing the total amount of CPU time h(t) needed by all the tasks to | |
403 | respect all of their deadlines in a time interval of size t, and comparing | |
404 | such a time with the interval size t. If h(t) is smaller than t (that is, | |
405 | the amount of time needed by the tasks in a time interval of size t is | |
406 | smaller than the size of the interval) for all the possible values of t, then | |
407 | EDF is able to schedule the tasks respecting all of their deadlines. Since | |
408 | performing this check for all possible values of t is impossible, it has been | |
409 | proven[4,5,6] that it is sufficient to perform the test for values of t | |
410 | between 0 and a maximum value L. The cited papers contain all of the | |
411 | mathematical details and explain how to compute h(t) and L. | |
412 | In any case, this kind of analysis is too complex as well as too | |
413 | time-consuming to be performed on-line. Hence, as explained in Section | |
414 | 4 Linux uses an admission test based on the tasks' utilizations. | |
b56bfc6c | 415 | |
6aaa1025 | 416 | 3.3 Schedulability Analysis for Multiprocessor Systems |
d6a3b247 | 417 | ------------------------------------------------------ |
6aaa1025 | 418 | |
b56bfc6c LA |
419 | On multiprocessor systems with global EDF scheduling (non partitioned |
420 | systems), a sufficient test for schedulability can not be based on the | |
134136c4 LA |
421 | utilizations or densities: it can be shown that even if D_i = P_i task |
422 | sets with utilizations slightly larger than 1 can miss deadlines regardless | |
423 | of the number of CPUs. | |
424 | ||
425 | Consider a set {Task_1,...Task_{M+1}} of M+1 tasks on a system with M | |
426 | CPUs, with the first task Task_1=(P,P,P) having period, relative deadline | |
427 | and WCET equal to P. The remaining M tasks Task_i=(e,P-1,P-1) have an | |
428 | arbitrarily small worst case execution time (indicated as "e" here) and a | |
429 | period smaller than the one of the first task. Hence, if all the tasks | |
430 | activate at the same time t, global EDF schedules these M tasks first | |
431 | (because their absolute deadlines are equal to t + P - 1, hence they are | |
432 | smaller than the absolute deadline of Task_1, which is t + P). As a | |
433 | result, Task_1 can be scheduled only at time t + e, and will finish at | |
434 | time t + e + P, after its absolute deadline. The total utilization of the | |
435 | task set is U = M · e / (P - 1) + P / P = M · e / (P - 1) + 1, and for small | |
436 | values of e this can become very close to 1. This is known as "Dhall's | |
437 | effect"[7]. Note: the example in the original paper by Dhall has been | |
438 | slightly simplified here (for example, Dhall more correctly computed | |
439 | lim_{e->0}U). | |
440 | ||
441 | More complex schedulability tests for global EDF have been developed in | |
442 | real-time literature[8,9], but they are not based on a simple comparison | |
443 | between total utilization (or density) and a fixed constant. If all tasks | |
444 | have D_i = P_i, a sufficient schedulability condition can be expressed in | |
445 | a simple way: | |
d6a3b247 | 446 | |
134136c4 | 447 | sum(WCET_i / P_i) <= M - (M - 1) · U_max |
d6a3b247 | 448 | |
134136c4 LA |
449 | where U_max = max{WCET_i / P_i}[10]. Notice that for U_max = 1, |
450 | M - (M - 1) · U_max becomes M - M + 1 = 1 and this schedulability condition | |
451 | just confirms the Dhall's effect. A more complete survey of the literature | |
452 | about schedulability tests for multi-processor real-time scheduling can be | |
453 | found in [11]. | |
454 | ||
455 | As seen, enforcing that the total utilization is smaller than M does not | |
456 | guarantee that global EDF schedules the tasks without missing any deadline | |
457 | (in other words, global EDF is not an optimal scheduling algorithm). However, | |
458 | a total utilization smaller than M is enough to guarantee that non real-time | |
459 | tasks are not starved and that the tardiness of real-time tasks has an upper | |
460 | bound[12] (as previously noted). Different bounds on the maximum tardiness | |
461 | experienced by real-time tasks have been developed in various papers[13,14], | |
462 | but the theoretical result that is important for SCHED_DEADLINE is that if | |
463 | the total utilization is smaller or equal than M then the response times of | |
464 | the tasks are limited. | |
712e5e34 | 465 | |
6aaa1025 | 466 | 3.4 Relationship with SCHED_DEADLINE Parameters |
d6a3b247 | 467 | ----------------------------------------------- |
6aaa1025 | 468 | |
78740858 LA |
469 | Finally, it is important to understand the relationship between the |
470 | SCHED_DEADLINE scheduling parameters described in Section 2 (runtime, | |
471 | deadline and period) and the real-time task parameters (WCET, D, P) | |
472 | described in this section. Note that the tasks' temporal constraints are | |
473 | represented by its absolute deadlines d_j = r_j + D described above, while | |
474 | SCHED_DEADLINE schedules the tasks according to scheduling deadlines (see | |
475 | Section 2). | |
476 | If an admission test is used to guarantee that the scheduling deadlines | |
477 | are respected, then SCHED_DEADLINE can be used to schedule real-time tasks | |
478 | guaranteeing that all the jobs' deadlines of a task are respected. | |
479 | In order to do this, a task must be scheduled by setting: | |
712e5e34 DF |
480 | |
481 | - runtime >= WCET | |
482 | - deadline = D | |
483 | - period <= P | |
484 | ||
3aa2dbe2 | 485 | IOW, if runtime >= WCET and if period is <= P, then the scheduling deadlines |
712e5e34 DF |
486 | and the absolute deadlines (d_j) coincide, so a proper admission control |
487 | allows to respect the jobs' absolute deadlines for this task (this is what is | |
488 | called "hard schedulability property" and is an extension of Lemma 1 of [2]). | |
ad67dc31 LA |
489 | Notice that if runtime > deadline the admission control will surely reject |
490 | this task, as it is not possible to respect its temporal constraints. | |
712e5e34 DF |
491 | |
492 | References: | |
d6a3b247 | 493 | |
712e5e34 DF |
494 | 1 - C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogram- |
495 | ming in a hard-real-time environment. Journal of the Association for | |
496 | Computing Machinery, 20(1), 1973. | |
497 | 2 - L. Abeni , G. Buttazzo. Integrating Multimedia Applications in Hard | |
498 | Real-Time Systems. Proceedings of the 19th IEEE Real-time Systems | |
499 | Symposium, 1998. http://retis.sssup.it/~giorgio/paps/1998/rtss98-cbs.pdf | |
500 | 3 - L. Abeni. Server Mechanisms for Multimedia Applications. ReTiS Lab | |
ad67dc31 | 501 | Technical Report. http://disi.unitn.it/~abeni/tr-98-01.pdf |
e0deda81 LA |
502 | 4 - J. Y. Leung and M.L. Merril. A Note on Preemptive Scheduling of |
503 | Periodic, Real-Time Tasks. Information Processing Letters, vol. 11, | |
504 | no. 3, pp. 115-118, 1980. | |
505 | 5 - S. K. Baruah, A. K. Mok and L. E. Rosier. Preemptively Scheduling | |
506 | Hard-Real-Time Sporadic Tasks on One Processor. Proceedings of the | |
507 | 11th IEEE Real-time Systems Symposium, 1990. | |
508 | 6 - S. K. Baruah, L. E. Rosier and R. R. Howell. Algorithms and Complexity | |
509 | Concerning the Preemptive Scheduling of Periodic Real-Time tasks on | |
510 | One Processor. Real-Time Systems Journal, vol. 4, no. 2, pp 301-324, | |
511 | 1990. | |
134136c4 LA |
512 | 7 - S. J. Dhall and C. L. Liu. On a real-time scheduling problem. Operations |
513 | research, vol. 26, no. 1, pp 127-140, 1978. | |
514 | 8 - T. Baker. Multiprocessor EDF and Deadline Monotonic Schedulability | |
515 | Analysis. Proceedings of the 24th IEEE Real-Time Systems Symposium, 2003. | |
516 | 9 - T. Baker. An Analysis of EDF Schedulability on a Multiprocessor. | |
517 | IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 8, | |
518 | pp 760-768, 2005. | |
519 | 10 - J. Goossens, S. Funk and S. Baruah, Priority-Driven Scheduling of | |
520 | Periodic Task Systems on Multiprocessors. Real-Time Systems Journal, | |
521 | vol. 25, no. 2–3, pp. 187–205, 2003. | |
522 | 11 - R. Davis and A. Burns. A Survey of Hard Real-Time Scheduling for | |
523 | Multiprocessor Systems. ACM Computing Surveys, vol. 43, no. 4, 2011. | |
524 | http://www-users.cs.york.ac.uk/~robdavis/papers/MPSurveyv5.0.pdf | |
525 | 12 - U. C. Devi and J. H. Anderson. Tardiness Bounds under Global EDF | |
526 | Scheduling on a Multiprocessor. Real-Time Systems Journal, vol. 32, | |
527 | no. 2, pp 133-189, 2008. | |
528 | 13 - P. Valente and G. Lipari. An Upper Bound to the Lateness of Soft | |
529 | Real-Time Tasks Scheduled by EDF on Multiprocessors. Proceedings of | |
530 | the 26th IEEE Real-Time Systems Symposium, 2005. | |
531 | 14 - J. Erickson, U. Devi and S. Baruah. Improved tardiness bounds for | |
532 | Global EDF. Proceedings of the 22nd Euromicro Conference on | |
533 | Real-Time Systems, 2010. | |
ccc9d651 CS |
534 | 15 - G. Lipari, S. Baruah, Greedy reclamation of unused bandwidth in |
535 | constant-bandwidth servers, 12th IEEE Euromicro Conference on Real-Time | |
536 | Systems, 2000. | |
537 | 16 - L. Abeni, J. Lelli, C. Scordino, L. Palopoli, Greedy CPU reclaiming for | |
538 | SCHED DEADLINE. In Proceedings of the Real-Time Linux Workshop (RTLWS), | |
539 | Dusseldorf, Germany, 2014. | |
540 | 17 - L. Abeni, G. Lipari, A. Parri, Y. Sun, Multicore CPU reclaiming: parallel | |
541 | or sequential?. In Proceedings of the 31st Annual ACM Symposium on Applied | |
542 | Computing, 2016. | |
bb4e30a4 CS |
543 | 18 - J. Lelli, C. Scordino, L. Abeni, D. Faggioli, Deadline scheduling in the |
544 | Linux kernel, Software: Practice and Experience, 46(6): 821-839, June | |
545 | 2016. | |
546 | 19 - C. Scordino, L. Abeni, J. Lelli, Energy-Aware Real-Time Scheduling in | |
547 | the Linux Kernel, 33rd ACM/SIGAPP Symposium On Applied Computing (SAC | |
548 | 2018), Pau, France, April 2018. | |
134136c4 | 549 | |
712e5e34 DF |
550 | |
551 | 4. Bandwidth management | |
552 | ======================= | |
553 | ||
b56bfc6c LA |
554 | As previously mentioned, in order for -deadline scheduling to be |
555 | effective and useful (that is, to be able to provide "runtime" time units | |
556 | within "deadline"), it is important to have some method to keep the allocation | |
557 | of the available fractions of CPU time to the various tasks under control. | |
558 | This is usually called "admission control" and if it is not performed, then | |
559 | no guarantee can be given on the actual scheduling of the -deadline tasks. | |
560 | ||
561 | As already stated in Section 3, a necessary condition to be respected to | |
3a3a58d4 | 562 | correctly schedule a set of real-time tasks is that the total utilization |
b56bfc6c LA |
563 | is smaller than M. When talking about -deadline tasks, this requires that |
564 | the sum of the ratio between runtime and period for all tasks is smaller | |
3a3a58d4 | 565 | than M. Notice that the ratio runtime/period is equivalent to the utilization |
b56bfc6c LA |
566 | of a "traditional" real-time task, and is also often referred to as |
567 | "bandwidth". | |
568 | The interface used to control the CPU bandwidth that can be allocated | |
569 | to -deadline tasks is similar to the one already used for -rt | |
0d9ba8b0 | 570 | tasks with real-time group scheduling (a.k.a. RT-throttling - see |
d6a3b247 | 571 | Documentation/scheduler/sched-rt-group.rst), and is based on readable/ |
0d9ba8b0 JL |
572 | writable control files located in procfs (for system wide settings). |
573 | Notice that per-group settings (controlled through cgroupfs) are still not | |
574 | defined for -deadline tasks, because more discussion is needed in order to | |
575 | figure out how we want to manage SCHED_DEADLINE bandwidth at the task group | |
576 | level. | |
577 | ||
578 | A main difference between deadline bandwidth management and RT-throttling | |
712e5e34 | 579 | is that -deadline tasks have bandwidth on their own (while -rt ones don't!), |
0d9ba8b0 | 580 | and thus we don't need a higher level throttling mechanism to enforce the |
b56bfc6c LA |
581 | desired bandwidth. In other words, this means that interface parameters are |
582 | only used at admission control time (i.e., when the user calls | |
583 | sched_setattr()). Scheduling is then performed considering actual tasks' | |
584 | parameters, so that CPU bandwidth is allocated to SCHED_DEADLINE tasks | |
585 | respecting their needs in terms of granularity. Therefore, using this simple | |
586 | interface we can put a cap on total utilization of -deadline tasks (i.e., | |
587 | \Sum (runtime_i / period_i) < global_dl_utilization_cap). | |
712e5e34 DF |
588 | |
589 | 4.1 System wide settings | |
590 | ------------------------ | |
591 | ||
592 | The system wide settings are configured under the /proc virtual file system. | |
593 | ||
0d9ba8b0 | 594 | For now the -rt knobs are used for -deadline admission control and the |
3a3a58d4 | 595 | -deadline runtime is accounted against the -rt runtime. We realize that this |
0d9ba8b0 JL |
596 | isn't entirely desirable; however, it is better to have a small interface for |
597 | now, and be able to change it easily later. The ideal situation (see 5.) is to | |
598 | run -rt tasks from a -deadline server; in which case the -rt bandwidth is a | |
599 | direct subset of dl_bw. | |
712e5e34 DF |
600 | |
601 | This means that, for a root_domain comprising M CPUs, -deadline tasks | |
602 | can be created while the sum of their bandwidths stays below: | |
603 | ||
604 | M * (sched_rt_runtime_us / sched_rt_period_us) | |
605 | ||
606 | It is also possible to disable this bandwidth management logic, and | |
607 | be thus free of oversubscribing the system up to any arbitrary level. | |
608 | This is done by writing -1 in /proc/sys/kernel/sched_rt_runtime_us. | |
609 | ||
610 | ||
611 | 4.2 Task interface | |
612 | ------------------ | |
613 | ||
614 | Specifying a periodic/sporadic task that executes for a given amount of | |
615 | runtime at each instance, and that is scheduled according to the urgency of | |
616 | its own timing constraints needs, in general, a way of declaring: | |
d6a3b247 | 617 | |
712e5e34 DF |
618 | - a (maximum/typical) instance execution time, |
619 | - a minimum interval between consecutive instances, | |
620 | - a time constraint by which each instance must be completed. | |
621 | ||
622 | Therefore: | |
d6a3b247 | 623 | |
712e5e34 DF |
624 | * a new struct sched_attr, containing all the necessary fields is |
625 | provided; | |
626 | * the new scheduling related syscalls that manipulate it, i.e., | |
627 | sched_setattr() and sched_getattr() are implemented. | |
628 | ||
59f8c298 TC |
629 | For debugging purposes, the leftover runtime and absolute deadline of a |
630 | SCHED_DEADLINE task can be retrieved through /proc/<pid>/sched (entries | |
631 | dl.runtime and dl.deadline, both values in ns). A programmatic way to | |
632 | retrieve these values from production code is under discussion. | |
633 | ||
712e5e34 DF |
634 | |
635 | 4.3 Default behavior | |
636 | --------------------- | |
637 | ||
638 | The default value for SCHED_DEADLINE bandwidth is to have rt_runtime equal to | |
639 | 950000. With rt_period equal to 1000000, by default, it means that -deadline | |
640 | tasks can use at most 95%, multiplied by the number of CPUs that compose the | |
641 | root_domain, for each root_domain. | |
b56bfc6c LA |
642 | This means that non -deadline tasks will receive at least 5% of the CPU time, |
643 | and that -deadline tasks will receive their runtime with a guaranteed | |
644 | worst-case delay respect to the "deadline" parameter. If "deadline" = "period" | |
645 | and the cpuset mechanism is used to implement partitioned scheduling (see | |
646 | Section 5), then this simple setting of the bandwidth management is able to | |
647 | deterministically guarantee that -deadline tasks will receive their runtime | |
648 | in a period. | |
649 | ||
650 | Finally, notice that in order not to jeopardize the admission control a | |
651 | -deadline task cannot fork. | |
712e5e34 | 652 | |
b95202a3 TC |
653 | |
654 | 4.4 Behavior of sched_yield() | |
655 | ----------------------------- | |
656 | ||
657 | When a SCHED_DEADLINE task calls sched_yield(), it gives up its | |
658 | remaining runtime and is immediately throttled, until the next | |
659 | period, when its runtime will be replenished (a special flag | |
660 | dl_yielded is set and used to handle correctly throttling and runtime | |
661 | replenishment after a call to sched_yield()). | |
662 | ||
663 | This behavior of sched_yield() allows the task to wake-up exactly at | |
664 | the beginning of the next period. Also, this may be useful in the | |
665 | future with bandwidth reclaiming mechanisms, where sched_yield() will | |
666 | make the leftoever runtime available for reclamation by other | |
667 | SCHED_DEADLINE tasks. | |
668 | ||
669 | ||
712e5e34 DF |
670 | 5. Tasks CPU affinity |
671 | ===================== | |
672 | ||
673 | -deadline tasks cannot have an affinity mask smaller that the entire | |
674 | root_domain they are created on. However, affinities can be specified | |
da82c92f | 675 | through the cpuset facility (Documentation/admin-guide/cgroup-v1/cpusets.rst). |
712e5e34 DF |
676 | |
677 | 5.1 SCHED_DEADLINE and cpusets HOWTO | |
678 | ------------------------------------ | |
679 | ||
680 | An example of a simple configuration (pin a -deadline task to CPU0) | |
d6a3b247 MCC |
681 | follows (rt-app is used to create a -deadline task):: |
682 | ||
683 | mkdir /dev/cpuset | |
684 | mount -t cgroup -o cpuset cpuset /dev/cpuset | |
685 | cd /dev/cpuset | |
686 | mkdir cpu0 | |
687 | echo 0 > cpu0/cpuset.cpus | |
688 | echo 0 > cpu0/cpuset.mems | |
689 | echo 1 > cpuset.cpu_exclusive | |
690 | echo 0 > cpuset.sched_load_balance | |
691 | echo 1 > cpu0/cpuset.cpu_exclusive | |
692 | echo 1 > cpu0/cpuset.mem_exclusive | |
693 | echo $$ > cpu0/tasks | |
694 | rt-app -t 100000:10000:d:0 -D5 # it is now actually superfluous to specify | |
695 | # task affinity | |
712e5e34 DF |
696 | |
697 | 6. Future plans | |
698 | =============== | |
699 | ||
700 | Still missing: | |
701 | ||
59f8c298 | 702 | - programmatic way to retrieve current runtime and absolute deadline |
712e5e34 DF |
703 | - refinements to deadline inheritance, especially regarding the possibility |
704 | of retaining bandwidth isolation among non-interacting tasks. This is | |
705 | being studied from both theoretical and practical points of view, and | |
706 | hopefully we should be able to produce some demonstrative code soon; | |
707 | - (c)group based bandwidth management, and maybe scheduling; | |
708 | - access control for non-root users (and related security concerns to | |
709 | address), which is the best way to allow unprivileged use of the mechanisms | |
710 | and how to prevent non-root users "cheat" the system? | |
711 | ||
712 | As already discussed, we are planning also to merge this work with the EDF | |
05a5f51c | 713 | throttling patches [https://lore.kernel.org/r/cover.1266931410.git.fabio@helm.retis] but we still are in |
712e5e34 DF |
714 | the preliminary phases of the merge and we really seek feedback that would |
715 | help us decide on the direction it should take. | |
f5801933 JL |
716 | |
717 | Appendix A. Test suite | |
718 | ====================== | |
719 | ||
720 | The SCHED_DEADLINE policy can be easily tested using two applications that | |
721 | are part of a wider Linux Scheduler validation suite. The suite is | |
722 | available as a GitHub repository: https://github.com/scheduler-tools. | |
723 | ||
724 | The first testing application is called rt-app and can be used to | |
725 | start multiple threads with specific parameters. rt-app supports | |
726 | SCHED_{OTHER,FIFO,RR,DEADLINE} scheduling policies and their related | |
727 | parameters (e.g., niceness, priority, runtime/deadline/period). rt-app | |
728 | is a valuable tool, as it can be used to synthetically recreate certain | |
729 | workloads (maybe mimicking real use-cases) and evaluate how the scheduler | |
730 | behaves under such workloads. In this way, results are easily reproducible. | |
731 | rt-app is available at: https://github.com/scheduler-tools/rt-app. | |
732 | ||
733 | Thread parameters can be specified from the command line, with something like | |
d6a3b247 | 734 | this:: |
f5801933 JL |
735 | |
736 | # rt-app -t 100000:10000:d -t 150000:20000:f:10 -D5 | |
737 | ||
738 | The above creates 2 threads. The first one, scheduled by SCHED_DEADLINE, | |
739 | executes for 10ms every 100ms. The second one, scheduled at SCHED_FIFO | |
740 | priority 10, executes for 20ms every 150ms. The test will run for a total | |
741 | of 5 seconds. | |
742 | ||
743 | More interestingly, configurations can be described with a json file that | |
d6a3b247 | 744 | can be passed as input to rt-app with something like this:: |
f5801933 JL |
745 | |
746 | # rt-app my_config.json | |
747 | ||
748 | The parameters that can be specified with the second method are a superset | |
749 | of the command line options. Please refer to rt-app documentation for more | |
d6a3b247 | 750 | details (`<rt-app-sources>/doc/*.json`). |
f5801933 JL |
751 | |
752 | The second testing application is a modification of schedtool, called | |
753 | schedtool-dl, which can be used to setup SCHED_DEADLINE parameters for a | |
754 | certain pid/application. schedtool-dl is available at: | |
755 | https://github.com/scheduler-tools/schedtool-dl.git. | |
756 | ||
d6a3b247 | 757 | The usage is straightforward:: |
f5801933 JL |
758 | |
759 | # schedtool -E -t 10000000:100000000 -e ./my_cpuhog_app | |
760 | ||
761 | With this, my_cpuhog_app is put to run inside a SCHED_DEADLINE reservation | |
762 | of 10ms every 100ms (note that parameters are expressed in microseconds). | |
763 | You can also use schedtool to create a reservation for an already running | |
d6a3b247 | 764 | application, given that you know its pid:: |
f5801933 JL |
765 | |
766 | # schedtool -E -t 10000000:100000000 my_app_pid | |
13924d2a JL |
767 | |
768 | Appendix B. Minimal main() | |
769 | ========================== | |
770 | ||
771 | We provide in what follows a simple (ugly) self-contained code snippet | |
772 | showing how SCHED_DEADLINE reservations can be created by a real-time | |
d6a3b247 MCC |
773 | application developer:: |
774 | ||
775 | #define _GNU_SOURCE | |
776 | #include <unistd.h> | |
777 | #include <stdio.h> | |
778 | #include <stdlib.h> | |
779 | #include <string.h> | |
780 | #include <time.h> | |
781 | #include <linux/unistd.h> | |
782 | #include <linux/kernel.h> | |
783 | #include <linux/types.h> | |
784 | #include <sys/syscall.h> | |
785 | #include <pthread.h> | |
786 | ||
787 | #define gettid() syscall(__NR_gettid) | |
788 | ||
789 | #define SCHED_DEADLINE 6 | |
790 | ||
791 | /* XXX use the proper syscall numbers */ | |
792 | #ifdef __x86_64__ | |
793 | #define __NR_sched_setattr 314 | |
794 | #define __NR_sched_getattr 315 | |
795 | #endif | |
796 | ||
797 | #ifdef __i386__ | |
798 | #define __NR_sched_setattr 351 | |
799 | #define __NR_sched_getattr 352 | |
800 | #endif | |
801 | ||
802 | #ifdef __arm__ | |
803 | #define __NR_sched_setattr 380 | |
804 | #define __NR_sched_getattr 381 | |
805 | #endif | |
806 | ||
807 | static volatile int done; | |
808 | ||
809 | struct sched_attr { | |
13924d2a JL |
810 | __u32 size; |
811 | ||
812 | __u32 sched_policy; | |
813 | __u64 sched_flags; | |
814 | ||
815 | /* SCHED_NORMAL, SCHED_BATCH */ | |
816 | __s32 sched_nice; | |
817 | ||
818 | /* SCHED_FIFO, SCHED_RR */ | |
819 | __u32 sched_priority; | |
820 | ||
821 | /* SCHED_DEADLINE (nsec) */ | |
822 | __u64 sched_runtime; | |
823 | __u64 sched_deadline; | |
824 | __u64 sched_period; | |
d6a3b247 | 825 | }; |
13924d2a | 826 | |
d6a3b247 | 827 | int sched_setattr(pid_t pid, |
13924d2a JL |
828 | const struct sched_attr *attr, |
829 | unsigned int flags) | |
d6a3b247 | 830 | { |
13924d2a | 831 | return syscall(__NR_sched_setattr, pid, attr, flags); |
d6a3b247 | 832 | } |
13924d2a | 833 | |
d6a3b247 | 834 | int sched_getattr(pid_t pid, |
13924d2a JL |
835 | struct sched_attr *attr, |
836 | unsigned int size, | |
837 | unsigned int flags) | |
d6a3b247 | 838 | { |
13924d2a | 839 | return syscall(__NR_sched_getattr, pid, attr, size, flags); |
d6a3b247 | 840 | } |
13924d2a | 841 | |
d6a3b247 MCC |
842 | void *run_deadline(void *data) |
843 | { | |
13924d2a JL |
844 | struct sched_attr attr; |
845 | int x = 0; | |
846 | int ret; | |
847 | unsigned int flags = 0; | |
848 | ||
849 | printf("deadline thread started [%ld]\n", gettid()); | |
850 | ||
851 | attr.size = sizeof(attr); | |
852 | attr.sched_flags = 0; | |
853 | attr.sched_nice = 0; | |
854 | attr.sched_priority = 0; | |
855 | ||
856 | /* This creates a 10ms/30ms reservation */ | |
857 | attr.sched_policy = SCHED_DEADLINE; | |
858 | attr.sched_runtime = 10 * 1000 * 1000; | |
859 | attr.sched_period = attr.sched_deadline = 30 * 1000 * 1000; | |
860 | ||
861 | ret = sched_setattr(0, &attr, flags); | |
862 | if (ret < 0) { | |
863 | done = 0; | |
864 | perror("sched_setattr"); | |
865 | exit(-1); | |
866 | } | |
867 | ||
868 | while (!done) { | |
869 | x++; | |
870 | } | |
871 | ||
872 | printf("deadline thread dies [%ld]\n", gettid()); | |
873 | return NULL; | |
d6a3b247 | 874 | } |
13924d2a | 875 | |
d6a3b247 MCC |
876 | int main (int argc, char **argv) |
877 | { | |
13924d2a JL |
878 | pthread_t thread; |
879 | ||
880 | printf("main thread [%ld]\n", gettid()); | |
881 | ||
882 | pthread_create(&thread, NULL, run_deadline, NULL); | |
883 | ||
884 | sleep(10); | |
885 | ||
886 | done = 1; | |
887 | pthread_join(thread, NULL); | |
888 | ||
889 | printf("main dies [%ld]\n", gettid()); | |
890 | return 0; | |
d6a3b247 | 891 | } |