1 Deadline Task Scheduling
2 ------------------------
9 2. Scheduling algorithm
10 3. Scheduling Real-Time Tasks
11 4. Bandwidth management
12 4.1 System-wide settings
16 5.1 SCHED_DEADLINE and cpusets HOWTO
23 Fiddling with these settings can result in an unpredictable or even unstable
24 system behavior. As for -rt (group) scheduling, it is assumed that root users
25 know what they're doing.
31 The SCHED_DEADLINE policy contained inside the sched_dl scheduling class is
32 basically an implementation of the Earliest Deadline First (EDF) scheduling
33 algorithm, augmented with a mechanism (called Constant Bandwidth Server, CBS)
34 that makes it possible to isolate the behavior of tasks between each other.
37 2. Scheduling algorithm
40 SCHED_DEADLINE uses three parameters, named "runtime", "period", and
41 "deadline" to schedule tasks. A SCHED_DEADLINE task is guaranteed to receive
42 "runtime" microseconds of execution time every "period" microseconds, and
43 these "runtime" microseconds are available within "deadline" microseconds
44 from the beginning of the period. In order to implement this behaviour,
45 every time the task wakes up, the scheduler computes a "scheduling deadline"
46 consistent with the guarantee (using the CBS[2,3] algorithm). Tasks are then
47 scheduled using EDF[1] on these scheduling deadlines (the task with the
48 earliest scheduling deadline is selected for execution). Notice that this
49 guaranteed is respected if a proper "admission control" strategy (see Section
50 "4. Bandwidth management") is used.
52 Summing up, the CBS[2,3] algorithms assigns scheduling deadlines to tasks so
53 that each task runs for at most its runtime every period, avoiding any
54 interference between different tasks (bandwidth isolation), while the EDF[1]
55 algorithm selects the task with the earliest scheduling deadline as the one
56 to be executed next. Thanks to this feature, tasks that do not strictly comply
57 with the "traditional" real-time task model (see Section 3) can effectively
60 In more details, the CBS algorithm assigns scheduling deadlines to
61 tasks in the following way:
63 - Each SCHED_DEADLINE task is characterised by the "runtime",
64 "deadline", and "period" parameters;
66 - The state of the task is described by a "scheduling deadline", and
67 a "remaining runtime". These two parameters are initially set to 0;
69 - When a SCHED_DEADLINE task wakes up (becomes ready for execution),
70 the scheduler checks if
72 remaining runtime runtime
73 ---------------------------------- > ---------
74 scheduling deadline - current time period
76 then, if the scheduling deadline is smaller than the current time, or
77 this condition is verified, the scheduling deadline and the
78 remaining runtime are re-initialised as
80 scheduling deadline = current time + deadline
81 remaining runtime = runtime
83 otherwise, the scheduling deadline and the remaining runtime are
86 - When a SCHED_DEADLINE task executes for an amount of time t, its
87 remaining runtime is decreased as
89 remaining runtime = remaining runtime - t
91 (technically, the runtime is decreased at every tick, or when the
92 task is descheduled / preempted);
94 - When the remaining runtime becomes less or equal than 0, the task is
95 said to be "throttled" (also known as "depleted" in real-time literature)
96 and cannot be scheduled until its scheduling deadline. The "replenishment
97 time" for this task (see next item) is set to be equal to the current
98 value of the scheduling deadline;
100 - When the current time is equal to the replenishment time of a
101 throttled task, the scheduling deadline and the remaining runtime are
104 scheduling deadline = scheduling deadline + period
105 remaining runtime = remaining runtime + runtime
108 3. Scheduling Real-Time Tasks
109 =============================
111 * BIG FAT WARNING ******************************************************
113 * This section contains a (not-thorough) summary on classical deadline
114 * scheduling theory, and how it applies to SCHED_DEADLINE.
115 * The reader can "safely" skip to Section 4 if only interested in seeing
116 * how the scheduling policy can be used. Anyway, we strongly recommend
117 * to come back here and continue reading (once the urge for testing is
118 * satisfied :P) to be sure of fully understanding all technical details.
119 ************************************************************************
121 There are no limitations on what kind of task can exploit this new
122 scheduling discipline, even if it must be said that it is particularly
123 suited for periodic or sporadic real-time tasks that need guarantees on their
124 timing behavior, e.g., multimedia, streaming, control applications, etc.
126 A typical real-time task is composed of a repetition of computation phases
127 (task instances, or jobs) which are activated on a periodic or sporadic
129 Each job J_j (where J_j is the j^th job of the task) is characterised by an
130 arrival time r_j (the time when the job starts), an amount of computation
131 time c_j needed to finish the job, and a job absolute deadline d_j, which
132 is the time within which the job should be finished. The maximum execution
133 time max_j{c_j} is called "Worst Case Execution Time" (WCET) for the task.
134 A real-time task can be periodic with period P if r_{j+1} = r_j + P, or
135 sporadic with minimum inter-arrival time P is r_{j+1} >= r_j + P. Finally,
136 d_j = r_j + D, where D is the task's relative deadline.
138 SCHED_DEADLINE can be used to schedule real-time tasks guaranteeing that
139 the jobs' deadlines of a task are respected. In order to do this, a task
140 must be scheduled by setting:
146 IOW, if runtime >= WCET and if period is >= P, then the scheduling deadlines
147 and the absolute deadlines (d_j) coincide, so a proper admission control
148 allows to respect the jobs' absolute deadlines for this task (this is what is
149 called "hard schedulability property" and is an extension of Lemma 1 of [2]).
150 Notice that if runtime > deadline the admission control will surely reject
151 this task, as it is not possible to respect its temporal constraints.
154 1 - C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogram-
155 ming in a hard-real-time environment. Journal of the Association for
156 Computing Machinery, 20(1), 1973.
157 2 - L. Abeni , G. Buttazzo. Integrating Multimedia Applications in Hard
158 Real-Time Systems. Proceedings of the 19th IEEE Real-time Systems
159 Symposium, 1998. http://retis.sssup.it/~giorgio/paps/1998/rtss98-cbs.pdf
160 3 - L. Abeni. Server Mechanisms for Multimedia Applications. ReTiS Lab
161 Technical Report. http://disi.unitn.it/~abeni/tr-98-01.pdf
163 4. Bandwidth management
164 =======================
166 In order for the -deadline scheduling to be effective and useful, it is
167 important to have some method to keep the allocation of the available CPU
168 bandwidth to the tasks under control. This is usually called "admission
169 control" and if it is not performed at all, no guarantee can be given on
170 the actual scheduling of the -deadline tasks.
172 The interface used to control the fraction of CPU bandwidth that can be
173 allocated to -deadline tasks is similar to the one already used for -rt
174 tasks with real-time group scheduling (a.k.a. RT-throttling - see
175 Documentation/scheduler/sched-rt-group.txt), and is based on readable/
176 writable control files located in procfs (for system wide settings).
177 Notice that per-group settings (controlled through cgroupfs) are still not
178 defined for -deadline tasks, because more discussion is needed in order to
179 figure out how we want to manage SCHED_DEADLINE bandwidth at the task group
182 A main difference between deadline bandwidth management and RT-throttling
183 is that -deadline tasks have bandwidth on their own (while -rt ones don't!),
184 and thus we don't need a higher level throttling mechanism to enforce the
185 desired bandwidth. Therefore, using this simple interface we can put a cap
186 on total utilization of -deadline tasks (i.e., \Sum (runtime_i / period_i) <
187 global_dl_utilization_cap).
189 4.1 System wide settings
190 ------------------------
192 The system wide settings are configured under the /proc virtual file system.
194 For now the -rt knobs are used for -deadline admission control and the
195 -deadline runtime is accounted against the -rt runtime. We realise that this
196 isn't entirely desirable; however, it is better to have a small interface for
197 now, and be able to change it easily later. The ideal situation (see 5.) is to
198 run -rt tasks from a -deadline server; in which case the -rt bandwidth is a
199 direct subset of dl_bw.
201 This means that, for a root_domain comprising M CPUs, -deadline tasks
202 can be created while the sum of their bandwidths stays below:
204 M * (sched_rt_runtime_us / sched_rt_period_us)
206 It is also possible to disable this bandwidth management logic, and
207 be thus free of oversubscribing the system up to any arbitrary level.
208 This is done by writing -1 in /proc/sys/kernel/sched_rt_runtime_us.
214 Specifying a periodic/sporadic task that executes for a given amount of
215 runtime at each instance, and that is scheduled according to the urgency of
216 its own timing constraints needs, in general, a way of declaring:
217 - a (maximum/typical) instance execution time,
218 - a minimum interval between consecutive instances,
219 - a time constraint by which each instance must be completed.
222 * a new struct sched_attr, containing all the necessary fields is
224 * the new scheduling related syscalls that manipulate it, i.e.,
225 sched_setattr() and sched_getattr() are implemented.
229 ---------------------
231 The default value for SCHED_DEADLINE bandwidth is to have rt_runtime equal to
232 950000. With rt_period equal to 1000000, by default, it means that -deadline
233 tasks can use at most 95%, multiplied by the number of CPUs that compose the
234 root_domain, for each root_domain.
236 A -deadline task cannot fork.
238 5. Tasks CPU affinity
239 =====================
241 -deadline tasks cannot have an affinity mask smaller that the entire
242 root_domain they are created on. However, affinities can be specified
243 through the cpuset facility (Documentation/cgroups/cpusets.txt).
245 5.1 SCHED_DEADLINE and cpusets HOWTO
246 ------------------------------------
248 An example of a simple configuration (pin a -deadline task to CPU0)
249 follows (rt-app is used to create a -deadline task).
252 mount -t cgroup -o cpuset cpuset /dev/cpuset
255 echo 0 > cpu0/cpuset.cpus
256 echo 0 > cpu0/cpuset.mems
257 echo 1 > cpuset.cpu_exclusive
258 echo 0 > cpuset.sched_load_balance
259 echo 1 > cpu0/cpuset.cpu_exclusive
260 echo 1 > cpu0/cpuset.mem_exclusive
262 rt-app -t 100000:10000:d:0 -D5 (it is now actually superfluous to specify
270 - refinements to deadline inheritance, especially regarding the possibility
271 of retaining bandwidth isolation among non-interacting tasks. This is
272 being studied from both theoretical and practical points of view, and
273 hopefully we should be able to produce some demonstrative code soon;
274 - (c)group based bandwidth management, and maybe scheduling;
275 - access control for non-root users (and related security concerns to
276 address), which is the best way to allow unprivileged use of the mechanisms
277 and how to prevent non-root users "cheat" the system?
279 As already discussed, we are planning also to merge this work with the EDF
280 throttling patches [https://lkml.org/lkml/2010/2/23/239] but we still are in
281 the preliminary phases of the merge and we really seek feedback that would
282 help us decide on the direction it should take.