Lines Matching +full:timer +full:- +full:cannot +full:- +full:wake +full:- +full:cpu
12 3. Scheduling Real-Time Tasks
18 4.1 System-wide settings
22 5. Tasks CPU affinity
33 system behavior. As for -rt (group) scheduling, it is assumed that root users
50 ------------------
63 (clearly, if the system is overloaded this guarantee cannot be respected).
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)
109 and cannot be scheduled until its scheduling deadline. The "replenishment
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.
164 bandwidth cannot be immediately reclaimed without breaking the
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
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
299 setting a fixed CPU frequency results in a lower amount of deadline misses.
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
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
372 ----------------------------------------------------
375 real-time task is statically assigned to one and only one CPU), it is
378 of all the tasks executing on a CPU if and only if the total utilization
379 of the tasks running on such a CPU is smaller or equal than 1.
382 of all the tasks running on a CPU if the sum of the densities of the tasks
383 running on such a CPU is smaller or equal than 1:
394 its response time cannot be larger than 50ms + 10ms = 60ms) even if
400 but this cannot be done by comparing the total utilization or density with
402 computing the total amount of CPU time h(t) needed by all the tasks to
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
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
568 The interface used to control the CPU bandwidth that can be allocated
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!),
584 parameters, so that CPU bandwidth is allocated to SCHED_DEADLINE tasks
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
670 5. Tasks CPU affinity
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);