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