Lines Matching +full:real +full:- +full:time
12 3. Scheduling Real-Time Tasks
18 4.1 System-wide settings
33 system behavior. As for -rt (group) scheduling, it is assumed that root users
50 ------------------
54 "runtime" microseconds of execution time every "period" microseconds, and
57 every time the task wakes up, the scheduler computes a "scheduling deadline"
61 task actually receives "runtime" time units within "deadline" if a proper
70 with the "traditional" real-time task model (see Section 3) can effectively
76 - Each SCHED_DEADLINE task is characterized by the "runtime",
79 - The state of the task is described by a "scheduling deadline", and
82 - When a SCHED_DEADLINE task wakes up (becomes ready for execution),
86 ---------------------------------- > ---------
87 scheduling deadline - current time period
89 then, if the scheduling deadline is smaller than the current time, or
91 remaining runtime are re-initialized as
93 scheduling deadline = current time + deadline
99 - When a SCHED_DEADLINE task executes for an amount of time t, its
102 remaining runtime = remaining runtime - t
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)
110 time" for this task (see next item) is set to be equal to the current
113 - When the current time is equal to the replenishment time of a
126 ------------------------
134 ------------
136 ------------->| |
138 | ------------
140 ---------- | |
144 ---------- | |
146 | ------------
148 --------------| Non |
150 ------------
154 - ActiveContending: if it is ready for execution (or executing);
156 - ActiveNonContending: if it just blocked and has not yet surpassed the 0-lag
157 time;
159 - Inactive: if it is blocked and has surpassed the 0-lag time.
165 real-time guarantees. It therefore enters a transitional state called
167 the 0-lag time, when the task's bandwidth can be reclaimed without
168 breaking the real-time guarantees.
170 The 0-lag time for a task entering the ActiveNonContending state is
174 deadline - ---------------------
180 (b) If the task wakes up before the inactive timer fires, the task re-enters
200 - Active bandwidth (running_bw): this is the sum of the bandwidths of all
203 - Total bandwidth (this_bw): this is the sum of all tasks "belonging" to the
211 dq = -max{ Ui / Umax, (1 - Uinact - Uextra) } dt
215 - Ui is the bandwidth of task Ti;
216 - Umax is the maximum reclaimable utilization (subjected to RT throttling
218 - Uinact is the (per runqueue) inactive utilization, computed as
219 (this_bq - running_bw);
220 - Uextra is the (per runqueue) extra reclaimable utilization
231 |-------- |----
233 |---|---|---|---|---|---|---|---|--------->t
241 | ------------------------|
243 |---|---|---|---|---|---|---|---|--------->t
249 1 ----------------- ------
251 0.5- -----------------
253 |---|---|---|---|---|---|---|---|--------->t
257 - Time t = 0:
261 Since there are no inactive tasks, its runtime is decreased as dq = -1 dt.
263 - Time t = 2:
267 runtime is equal to 2, its 0-lag time is equal to t = 4.
268 Task T2 start execution, with runtime still decreased as dq = -1 dt since
271 - Time t = 4:
273 This is the 0-lag time for Task T1. Since it didn't woken up in the
277 dq = - 0.5 dt because Uinact = 0.5.
280 - Time t = 8:
286 2.3 Energy-aware scheduling
287 ---------------------------
290 GRUB-PA [19] algorithm, reducing the CPU operating frequency to the minimum
294 A particular care must be taken in case the time needed for changing frequency
299 3. Scheduling Real-Time Tasks
308 This section contains a (not-thorough) summary on classical deadline
319 suited for periodic or sporadic real-time tasks that need guarantees on their
323 ------------------------
325 A typical real-time task is composed of a repetition of computation phases
329 arrival time r_j (the time when the job starts), an amount of computation
330 time c_j needed to finish the job, and a job absolute deadline d_j, which
331 is the time within which the job should be finished. The maximum execution
332 time max{c_j} is called "Worst Case Execution Time" (WCET) for the task.
333 A real-time task can be periodic with period P if r_{j+1} = r_j + P, or
334 sporadic with minimum inter-arrival time P is r_{j+1} >= r_j + P. Finally,
336 Summing up, a real-time task can be described as
340 The utilization of a real-time task is defined as the ratio between its
341 WCET and its period (or minimum inter-arrival time), and represents
342 the fraction of CPU time needed to execute the task.
348 WCET_i/P_i over all the real-time tasks in the system. When considering
349 multiple real-time tasks, the parameters of the i-th task are indicated
352 non- real-time tasks by real-time tasks.
353 If, instead, the total utilization is smaller than M, then non real-time
358 between the finishing time of a job and its absolute deadline).
369 ----------------------------------------------------
372 real-time task is statically assigned to one and only one CPU), it is
389 (Task_1 is scheduled as soon as it is released, and finishes just in time
391 its response time cannot be larger than 50ms + 10ms = 60ms) even if
399 computing the total amount of CPU time h(t) needed by all the tasks to
400 respect all of their deadlines in a time interval of size t, and comparing
401 such a time with the interval size t. If h(t) is smaller than t (that is,
402 the amount of time needed by the tasks in a time interval of size t is
410 time-consuming to be performed on-line. Hence, as explained in Section
414 ------------------------------------------------------
424 and WCET equal to P. The remaining M tasks Task_i=(e,P-1,P-1) have an
425 arbitrarily small worst case execution time (indicated as "e" here) and a
427 activate at the same time t, global EDF schedules these M tasks first
428 (because their absolute deadlines are equal to t + P - 1, hence they are
430 result, Task_1 can be scheduled only at time t + e, and will finish at
431 time t + e + P, after its absolute deadline. The total utilization of the
432 task set is U = M · e / (P - 1) + P / P = M · e / (P - 1) + 1, and for small
436 lim_{e->0}U).
439 real-time literature[8,9], but they are not based on a simple comparison
444 sum(WCET_i / P_i) <= M - (M - 1) · U_max
447 M - (M - 1) · U_max becomes M - M + 1 = 1 and this schedulability condition
449 about schedulability tests for multi-processor real-time scheduling can be
455 a total utilization smaller than M is enough to guarantee that non real-time
456 tasks are not starved and that the tardiness of real-time tasks has an upper
458 experienced by real-time tasks have been developed in various papers[13,14],
464 -----------------------------------------------
468 deadline and period) and the real-time task parameters (WCET, D, P)
474 are respected, then SCHED_DEADLINE can be used to schedule real-time tasks
478 - runtime >= WCET
479 - deadline = D
480 - period <= P
491 1 - C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogram-
492 ming in a hard-real-time environment. Journal of the Association for
494 2 - L. Abeni , G. Buttazzo. Integrating Multimedia Applications in Hard
495 Real-Time Systems. Proceedings of the 19th IEEE Real-time Systems
496 Symposium, 1998. http://retis.sssup.it/~giorgio/paps/1998/rtss98-cbs.pdf
497 3 - L. Abeni. Server Mechanisms for Multimedia Applications. ReTiS Lab
498 Technical Report. http://disi.unitn.it/~abeni/tr-98-01.pdf
499 4 - J. Y. Leung and M.L. Merril. A Note on Preemptive Scheduling of
500 Periodic, Real-Time Tasks. Information Processing Letters, vol. 11,
501 no. 3, pp. 115-118, 1980.
502 5 - S. K. Baruah, A. K. Mok and L. E. Rosier. Preemptively Scheduling
503 Hard-Real-Time Sporadic Tasks on One Processor. Proceedings of the
504 11th IEEE Real-time Systems Symposium, 1990.
505 6 - S. K. Baruah, L. E. Rosier and R. R. Howell. Algorithms and Complexity
506 Concerning the Preemptive Scheduling of Periodic Real-Time tasks on
507 One Processor. Real-Time Systems Journal, vol. 4, no. 2, pp 301-324,
509 7 - S. J. Dhall and C. L. Liu. On a real-time scheduling problem. Operations
510 research, vol. 26, no. 1, pp 127-140, 1978.
511 8 - T. Baker. Multiprocessor EDF and Deadline Monotonic Schedulability
512 Analysis. Proceedings of the 24th IEEE Real-Time Systems Symposium, 2003.
513 9 - T. Baker. An Analysis of EDF Schedulability on a Multiprocessor.
515 pp 760-768, 2005.
516 10 - J. Goossens, S. Funk and S. Baruah, Priority-Driven Scheduling of
517 Periodic Task Systems on Multiprocessors. Real-Time Systems Journal,
519 11 - R. Davis and A. Burns. A Survey of Hard Real-Time Scheduling for
521 http://www-users.cs.york.ac.uk/~robdavis/papers/MPSurveyv5.0.pdf
522 12 - U. C. Devi and J. H. Anderson. Tardiness Bounds under Global EDF
523 Scheduling on a Multiprocessor. Real-Time Systems Journal, vol. 32,
524 no. 2, pp 133-189, 2008.
525 13 - P. Valente and G. Lipari. An Upper Bound to the Lateness of Soft
526 Real-Time Tasks Scheduled by EDF on Multiprocessors. Proceedings of
527 the 26th IEEE Real-Time Systems Symposium, 2005.
528 14 - J. Erickson, U. Devi and S. Baruah. Improved tardiness bounds for
530 Real-Time Systems, 2010.
531 15 - G. Lipari, S. Baruah, Greedy reclamation of unused bandwidth in
532 constant-bandwidth servers, 12th IEEE Euromicro Conference on Real-Time
534 16 - L. Abeni, J. Lelli, C. Scordino, L. Palopoli, Greedy CPU reclaiming for
535 SCHED DEADLINE. In Proceedings of the Real-Time Linux Workshop (RTLWS),
537 17 - L. Abeni, G. Lipari, A. Parri, Y. Sun, Multicore CPU reclaiming: parallel
540 18 - J. Lelli, C. Scordino, L. Abeni, D. Faggioli, Deadline scheduling in the
541 Linux kernel, Software: Practice and Experience, 46(6): 821-839, June
543 19 - C. Scordino, L. Abeni, J. Lelli, Energy-Aware Real-Time Scheduling in
551 As previously mentioned, in order for -deadline scheduling to be
552 effective and useful (that is, to be able to provide "runtime" time units
554 of the available fractions of CPU time to the various tasks under control.
556 no guarantee can be given on the actual scheduling of the -deadline tasks.
559 correctly schedule a set of real-time tasks is that the total utilization
560 is smaller than M. When talking about -deadline tasks, this requires that
563 of a "traditional" real-time task, and is also often referred to as
566 to -deadline tasks is similar to the one already used for -rt
567 tasks with real-time group scheduling (a.k.a. RT-throttling - see
568 Documentation/scheduler/sched-rt-group.rst), and is based on readable/
570 Notice that per-group settings (controlled through cgroupfs) are still not
571 defined for -deadline tasks, because more discussion is needed in order to
575 A main difference between deadline bandwidth management and RT-throttling
576 is that -deadline tasks have bandwidth on their own (while -rt ones don't!),
579 only used at admission control time (i.e., when the user calls
583 interface we can put a cap on total utilization of -deadline tasks (i.e.,
587 ------------------------
591 For now the -rt knobs are used for -deadline admission control and the
592 -deadline runtime is accounted against the -rt runtime. We realize that this
595 run -rt tasks from a -deadline server; in which case the -rt bandwidth is a
598 This means that, for a root_domain comprising M CPUs, -deadline tasks
605 This is done by writing -1 in /proc/sys/kernel/sched_rt_runtime_us.
609 ------------------
615 - a (maximum/typical) instance execution time,
616 - a minimum interval between consecutive instances,
617 - a time constraint by which each instance must be completed.
633 ---------------------
636 950000. With rt_period equal to 1000000, by default, it means that -deadline
639 This means that non -deadline tasks will receive at least 5% of the CPU time,
640 and that -deadline tasks will receive their runtime with a guaranteed
641 worst-case delay respect to the "deadline" parameter. If "deadline" = "period"
644 deterministically guarantee that -deadline tasks will receive their runtime
648 -deadline task cannot fork.
652 -----------------------------
660 This behavior of sched_yield() allows the task to wake-up exactly at
670 -deadline tasks cannot have an affinity mask smaller that the entire
672 through the cpuset facility (Documentation/admin-guide/cgroup-v1/cpusets.rst).
675 ------------------------------------
677 An example of a simple configuration (pin a -deadline task to CPU0)
678 follows (rt-app is used to create a -deadline task)::
681 mount -t cgroup -o cpuset cpuset /dev/cpuset
691 rt-app -t 100000:10000:d:0 -D5 # it is now actually superfluous to specify
699 - programmatic way to retrieve current runtime and absolute deadline
700 - refinements to deadline inheritance, especially regarding the possibility
701 of retaining bandwidth isolation among non-interacting tasks. This is
704 - (c)group based bandwidth management, and maybe scheduling;
705 - access control for non-root users (and related security concerns to
707 and how to prevent non-root users "cheat" the system?
719 available as a GitHub repository: https://github.com/scheduler-tools.
721 The first testing application is called rt-app and can be used to
722 start multiple threads with specific parameters. rt-app supports
724 parameters (e.g., niceness, priority, runtime/deadline/period). rt-app
726 workloads (maybe mimicking real use-cases) and evaluate how the scheduler
728 rt-app is available at: https://github.com/scheduler-tools/rt-app.
733 # rt-app -t 100000:10000:d -t 150000:20000:f:10 -D5
741 can be passed as input to rt-app with something like this::
743 # rt-app my_config.json
746 of the command line options. Please refer to rt-app documentation for more
747 details (`<rt-app-sources>/doc/*.json`).
750 schedtool-dl, which can be used to setup SCHED_DEADLINE parameters for a
751 certain pid/application. schedtool-dl is available at:
752 https://github.com/scheduler-tools/schedtool-dl.git.
756 # schedtool -E -t 10000000:100000000 -e ./my_cpuhog_app
763 # schedtool -E -t 10000000:100000000 my_app_pid
768 We provide in what follows a simple (ugly) self-contained code snippet
769 showing how SCHED_DEADLINE reservations can be created by a real-time
777 #include <time.h>
862 exit(-1);