Lines Matching +full:inactive +full:- +full:delay +full:- +full:ms
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 ---------- | |
142 | Inactive | |(b) | (a)
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.
163 (a) When a task blocks, it does not become immediately inactive since its
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.
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
181 the ActiveContending state and the "inactive timer" is canceled.
186 "inactive timer" is running on a different CPU, the "dl_non_contending"
189 "inactive timer" fires or when the task wakes up).
191 (c) When the "inactive timer" fires, the task enters the Inactive state and
194 (d) When an inactive task wakes up, it enters the ActiveContending state and
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
204 runqueue, including the tasks in Inactive state.
206 - Maximum usable bandwidth (max_bw): This is the maximum bandwidth usable by
210 The algorithm reclaims the bandwidth of the tasks in Inactive state.
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
272 there are no inactive tasks.
274 - Time t = 4:
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
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
390 Task_1=(50ms,50ms,100ms) and Task_2=(10ms,100ms,100ms).
394 its response time cannot be larger than 50ms + 10ms = 60ms) even if
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
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
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`).
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.
759 # schedtool -E -t 10000000:100000000 -e ./my_cpuhog_app
762 of 10ms every 100ms (note that parameters are expressed in microseconds).
766 # schedtool -E -t 10000000:100000000 my_app_pid
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
856 /* This creates a 10ms/30ms reservation */
865 exit(-1);