Lines Matching +full:real +full:-
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 ------------------
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
91 remaining runtime are re-initialized as
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)
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
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
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
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
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
372 ----------------------------------------------------
375 real-time task is statically assigned to one and only one CPU), it 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
431 (because their absolute deadlines are equal to t + P - 1, hence they are
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
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!),
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
863 exit(-1);