Documentation/scheduler/sched-deadline.rst

12     3. Scheduling Real-Time Tasks
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
87         scheduling deadline - current time           period
89     then, if the scheduling deadline is smaller than the current time, or
93          scheduling deadline = current time + deadline
99   - When a SCHED_DEADLINE task executes for an amount of time t, its
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
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
260   - Time t = 0:
266   - Time t = 2:
270     runtime is equal to 2, its 0-lag time is equal to t = 4.
274   - Time t = 4:
276     This is the 0-lag time for Task T1. Since it didn't woken up in the
283   - Time t = 8:
297  A particular care must be taken in case the time needed for changing frequency
302 3. Scheduling Real-Time Tasks
322  suited for periodic or sporadic real-time tasks that need guarantees on their
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).
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
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
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
442  real-time literature[8,9], but they are not based on a simple comparison
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],
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
495       ming in a hard-real-time environment. Journal of the Association for
498       Real-Time Systems. Proceedings of the 19th IEEE Real-time Systems
503       Periodic, Real-Time Tasks. Information Processing Letters, vol. 11,
506       Hard-Real-Time Sporadic Tasks on One Processor. Proceedings of the
507       11th IEEE Real-time Systems Symposium, 1990.
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
515       Analysis. Proceedings of the 24th IEEE Real-Time Systems Symposium, 2003.
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
526        Scheduling on a Multiprocessor. Real-Time Systems Journal, vol. 32,
529        Real-Time Tasks Scheduled by EDF on Multiprocessors. Proceedings of
530        the 26th IEEE Real-Time Systems Symposium, 2005.
533        Real-Time Systems, 2010.
535        constant-bandwidth servers, 12th IEEE Euromicro Conference on Real-Time
538        SCHED DEADLINE. In Proceedings of the Real-Time Linux Workshop (RTLWS),
546   19 - C. Scordino, L. Abeni, J. Lelli, Energy-Aware Real-Time Scheduling in
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.
562  correctly schedule a set of real-time tasks is that the total utilization
566  of a "traditional" real-time task, and is also often referred to as
570  tasks with real-time group scheduling (a.k.a. RT-throttling - see
582  only used at admission control time (i.e., when the user calls
618   - a (maximum/typical) instance execution time,
620   - a time constraint by which each instance must be completed.
642  This means that non -deadline tasks will receive at least 5% of the CPU time,
770  showing how SCHED_DEADLINE reservations can be created by a real-time
778    #include <time.h>