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
206 - Maximum usable bandwidth (max_bw): This is the maximum bandwidth usable by
214 dq = -(max{ Ui, (Umax - Uinact - Uextra) } / Umax) dt
218 - Ui is the bandwidth of task Ti;
219 - Umax is the maximum reclaimable utilization (subjected to RT throttling
221 - Uinact is the (per runqueue) inactive utilization, computed as
222 (this_bq - running_bw);
223 - Uextra is the (per runqueue) extra reclaimable utilization
234 |-------- |----
236 |---|---|---|---|---|---|---|---|--------->t
244 | ------------------------|
246 |---|---|---|---|---|---|---|---|--------->t
252 1 ----------------- ------
254 0.5- -----------------
256 |---|---|---|---|---|---|---|---|--------->t
260 - Time t = 0:
264 Since there are no inactive tasks, its runtime is decreased as dq = -1 dt.
266 - Time t = 2:
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
274 - Time t = 4:
276 This is the 0-lag time for Task T1. Since it didn't woken up in the
280 dq = - 0.5 dt because Uinact = 0.5.
283 - Time t = 8:
289 2.3 Energy-aware scheduling
290 ---------------------------
293 GRUB-PA [19] algorithm, reducing the CPU operating frequency to the minimum
297 A particular care must be taken in case the time needed for changing frequency
302 3. Scheduling Real-Time Tasks
311 This section contains a (not-thorough) summary on classical deadline
322 suited for periodic or sporadic real-time tasks that need guarantees on their
326 ------------------------
328 A typical real-time task is composed of a repetition of computation phases
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
335 time max{c_j} is called "Worst Case Execution Time" (WCET) for the task.
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,
339 Summing up, a real-time task can be described as
343 The utilization of a real-time task is defined as the ratio between its
344 WCET and its period (or minimum inter-arrival time), and represents
345 the fraction of CPU time needed to execute the task.
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
355 non- real-time tasks by real-time tasks.
356 If, instead, the total utilization is smaller than M, then non real-time
361 between the finishing time of a job and its absolute deadline).
372 ----------------------------------------------------
375 real-time task is statically assigned to one and only one CPU), it is
392 (Task_1 is scheduled as soon as it is released, and finishes just in time
394 its response time cannot be larger than 50ms + 10ms = 60ms) even if
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
413 time-consuming to be performed on-line. Hence, as explained in Section
417 ------------------------------------------------------
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
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
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
439 lim_{e->0}U).
442 real-time literature[8,9], but they are not based on a simple comparison
447 sum(WCET_i / P_i) <= M - (M - 1) · U_max
450 M - (M - 1) · U_max becomes M - M + 1 = 1 and this schedulability condition
452 about schedulability tests for multi-processor real-time scheduling can be
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
461 experienced by real-time tasks have been developed in various papers[13,14],
467 -----------------------------------------------
471 deadline and period) and the real-time task parameters (WCET, D, P)
477 are respected, then SCHED_DEADLINE can be used to schedule real-time tasks
481 - runtime >= WCET
482 - deadline = D
483 - period <= P
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
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
501 Technical Report. http://disi.unitn.it/~abeni/tr-98-01.pdf
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,
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.
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,
522 11 - R. Davis and A. Burns. A Survey of Hard Real-Time Scheduling for
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
533 Real-Time Systems, 2010.
534 15 - G. Lipari, S. Baruah, Greedy reclamation of unused bandwidth in
535 constant-bandwidth servers, 12th IEEE Euromicro Conference on Real-Time
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),
540 17 - L. Abeni, G. Lipari, A. Parri, Y. Sun, Multicore CPU reclaiming: parallel
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
546 19 - C. Scordino, L. Abeni, J. Lelli, Energy-Aware Real-Time Scheduling in
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
557 of the available fractions of CPU time to the various tasks under control.
559 no guarantee can be given on the actual scheduling of the -deadline tasks.
562 correctly schedule a set of real-time tasks is that the total utilization
563 is smaller than M. When talking about -deadline tasks, this requires that
566 of a "traditional" real-time task, and is also often referred to as
569 to -deadline tasks is similar to the one already used for -rt
570 tasks with real-time group scheduling (a.k.a. RT-throttling - see
571 Documentation/scheduler/sched-rt-group.rst), and is based on readable/
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
578 A main difference between deadline bandwidth management and RT-throttling
579 is that -deadline tasks have bandwidth on their own (while -rt ones don't!),
582 only used at admission control time (i.e., when the user calls
586 interface we can put a cap on total utilization of -deadline tasks (i.e.,
590 ------------------------
594 For now the -rt knobs are used for -deadline admission control and the
595 -deadline runtime is accounted against the -rt runtime. We realize that this
598 run -rt tasks from a -deadline server; in which case the -rt bandwidth is a
601 This means that, for a root_domain comprising M CPUs, -deadline tasks
608 This is done by writing -1 in /proc/sys/kernel/sched_rt_runtime_us.
612 ------------------
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.
636 ---------------------
639 950000. With rt_period equal to 1000000, by default, it means that -deadline
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"
647 deterministically guarantee that -deadline tasks will receive their runtime
651 -deadline task cannot fork.
655 -----------------------------
663 This behavior of sched_yield() allows the task to wake-up exactly at
673 -deadline tasks cannot have an affinity mask smaller that the entire
675 through the cpuset facility (Documentation/admin-guide/cgroup-v1/cpusets.rst).
678 ------------------------------------
680 An example of a simple configuration (pin a -deadline task to CPU0)
681 follows (rt-app is used to create a -deadline task)::
684 mount -t cgroup -o cpuset cpuset /dev/cpuset
694 rt-app -t 100000:10000:d:0 -D5 # it is now actually superfluous to specify
702 - programmatic way to retrieve current runtime and absolute deadline
703 - refinements to deadline inheritance, especially regarding the possibility
704 of retaining bandwidth isolation among non-interacting tasks. This is
707 - (c)group based bandwidth management, and maybe scheduling;
708 - access control for non-root users (and related security concerns to
710 and how to prevent non-root users "cheat" the system?
722 available as a GitHub repository: https://github.com/scheduler-tools.
724 The first testing application is called rt-app and can be used to
725 start multiple threads with specific parameters. rt-app supports
727 parameters (e.g., niceness, priority, runtime/deadline/period). rt-app
729 workloads (maybe mimicking real use-cases) and evaluate how the scheduler
731 rt-app is available at: https://github.com/scheduler-tools/rt-app.
736 # rt-app -t 100000:10000:d -t 150000:20000:f:10 -D5
744 can be passed as input to rt-app with something like this::
746 # rt-app my_config.json
749 of the command line options. Please refer to rt-app documentation for more
750 details (`<rt-app-sources>/doc/*.json`).
757 # chrt -d -T 10000000 -D 100000000 0 ./my_cpuhog_app
764 # chrt -d -T 10000000 -D 100000000 -p 0 my_app_pid
769 We provide in what follows a simple (ugly) self-contained code snippet
770 showing how SCHED_DEADLINE reservations can be created by a real-time
778 #include <time.h>
863 exit(-1);