blob: 86eabe6c3419fd4f26aba47a090ecc1caff9a1fd [file] [log] [blame]
Viktor Radnaib9b158f2008-04-19 19:45:01 +02001 Real-Time group scheduling
2 --------------------------
3
4CONTENTS
5========
6
Peter Zijlstra60aa6052009-05-05 17:50:21 +020070. WARNING
Viktor Radnaib9b158f2008-04-19 19:45:01 +020081. Overview
9 1.1 The problem
10 1.2 The solution
112. The interface
12 2.1 System-wide settings
13 2.2 Default behaviour
14 2.3 Basis for grouping tasks
153. Future plans
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +010016
17
Peter Zijlstra60aa6052009-05-05 17:50:21 +0200180. WARNING
19==========
20
21 Fiddling with these settings can result in an unstable system, the knobs are
22 root only and assumes root knows what he is doing.
23
24Most notable:
25
26 * very small values in sched_rt_period_us can result in an unstable
27 system when the period is smaller than either the available hrtimer
28 resolution, or the time it takes to handle the budget refresh itself.
29
30 * very small values in sched_rt_runtime_us can result in an unstable
31 system when the runtime is so small the system has difficulty making
32 forward progress (NOTE: the migration thread and kstopmachine both
33 are real-time processes).
34
Viktor Radnaib9b158f2008-04-19 19:45:01 +0200351. Overview
36===========
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +010037
38
Viktor Radnaib9b158f2008-04-19 19:45:01 +0200391.1 The problem
40---------------
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +010041
Viktor Radnaib9b158f2008-04-19 19:45:01 +020042Realtime scheduling is all about determinism, a group has to be able to rely on
43the amount of bandwidth (eg. CPU time) being constant. In order to schedule
44multiple groups of realtime tasks, each group must be assigned a fixed portion
45of the CPU time available. Without a minimum guarantee a realtime group can
46obviously fall short. A fuzzy upper limit is of no use since it cannot be
47relied upon. Which leaves us with just the single fixed portion.
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +010048
Viktor Radnaib9b158f2008-04-19 19:45:01 +0200491.2 The solution
50----------------
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +010051
Viktor Radnaib9b158f2008-04-19 19:45:01 +020052CPU time is divided by means of specifying how much time can be spent running
53in a given period. We allocate this "run time" for each realtime group which
54the other realtime groups will not be permitted to use.
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +010055
Viktor Radnaib9b158f2008-04-19 19:45:01 +020056Any time not allocated to a realtime group will be used to run normal priority
57tasks (SCHED_OTHER). Any allocated run time not used will also be picked up by
58SCHED_OTHER.
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +010059
Viktor Radnaib9b158f2008-04-19 19:45:01 +020060Let's consider an example: a frame fixed realtime renderer must deliver 25
61frames a second, which yields a period of 0.04s per frame. Now say it will also
62have to play some music and respond to input, leaving it with around 80% CPU
63time dedicated for the graphics. We can then give this group a run time of 0.8
64* 0.04s = 0.032s.
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +010065
Viktor Radnaib9b158f2008-04-19 19:45:01 +020066This way the graphics group will have a 0.04s period with a 0.032s run time
67limit. Now if the audio thread needs to refill the DMA buffer every 0.005s, but
68needs only about 3% CPU time to do so, it can do with a 0.03 * 0.005s =
690.00015s. So this group can be scheduled with a period of 0.005s and a run time
70of 0.00015s.
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +010071
Hiroshi Shimamotof7d62362008-06-10 20:29:19 -070072The remaining CPU time will be used for user input and other tasks. Because
Viktor Radnaib9b158f2008-04-19 19:45:01 +020073realtime tasks have explicitly allocated the CPU time they need to perform
Hiroshi Shimamotof7d62362008-06-10 20:29:19 -070074their tasks, buffer underruns in the graphics or audio can be eliminated.
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +010075
Wolfram Sangd4ec36b2009-06-21 12:32:39 +020076NOTE: the above example is not fully implemented yet. We still
Viktor Radnaib9b158f2008-04-19 19:45:01 +020077lack an EDF scheduler to make non-uniform periods usable.
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +010078
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +010079
Viktor Radnaib9b158f2008-04-19 19:45:01 +0200802. The Interface
81================
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +010082
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +010083
Viktor Radnaib9b158f2008-04-19 19:45:01 +0200842.1 System wide settings
85------------------------
86
87The system wide settings are configured under the /proc virtual file system:
88
89/proc/sys/kernel/sched_rt_period_us:
90 The scheduling period that is equivalent to 100% CPU bandwidth
91
92/proc/sys/kernel/sched_rt_runtime_us:
93 A global limit on how much time realtime scheduling may use. Even without
94 CONFIG_RT_GROUP_SCHED enabled, this will limit time reserved to realtime
95 processes. With CONFIG_RT_GROUP_SCHED it signifies the total bandwidth
96 available to all realtime groups.
97
98 * Time is specified in us because the interface is s32. This gives an
99 operating range from 1us to about 35 minutes.
100 * sched_rt_period_us takes values from 1 to INT_MAX.
101 * sched_rt_runtime_us takes values from -1 to (INT_MAX - 1).
102 * A run time of -1 specifies runtime == period, ie. no limit.
103
104
1052.2 Default behaviour
106---------------------
107
108The default values for sched_rt_period_us (1000000 or 1s) and
109sched_rt_runtime_us (950000 or 0.95s). This gives 0.05s to be used by
110SCHED_OTHER (non-RT tasks). These defaults were chosen so that a run-away
111realtime tasks will not lock up the machine but leave a little time to recover
112it. By setting runtime to -1 you'd get the old behaviour back.
113
114By default all bandwidth is assigned to the root group and new groups get the
115period from /proc/sys/kernel/sched_rt_period_us and a run time of 0. If you
116want to assign bandwidth to another group, reduce the root group's bandwidth
117and assign some or all of the difference to another group.
118
119Realtime group scheduling means you have to assign a portion of total CPU
120bandwidth to the group before it will accept realtime tasks. Therefore you will
121not be able to run realtime tasks as any user other than root until you have
122done that, even if the user has the rights to run processes with realtime
123priority!
124
125
1262.3 Basis for grouping tasks
127----------------------------
128
129There are two compile-time settings for allocating CPU bandwidth. These are
130configured using the "Basis for grouping tasks" multiple choice menu under
131General setup > Group CPU Scheduler:
132
133a. CONFIG_USER_SCHED (aka "Basis for grouping tasks" = "user id")
134
135This lets you use the virtual files under
136"/sys/kernel/uids/<uid>/cpu_rt_runtime_us" to control he CPU time reserved for
137each user .
138
139The other option is:
140
141.o CONFIG_CGROUP_SCHED (aka "Basis for grouping tasks" = "Control groups")
142
Wolfram Sangd4ec36b2009-06-21 12:32:39 +0200143This uses the /cgroup virtual file system and
144"/cgroup/<cgroup>/cpu.rt_runtime_us" to control the CPU time reserved for each
145control group instead.
Viktor Radnaib9b158f2008-04-19 19:45:01 +0200146
147For more information on working with control groups, you should read
Thadeu Lima de Souza Cascardo21acb9c2009-02-04 10:12:08 +0100148Documentation/cgroups/cgroups.txt as well.
Viktor Radnaib9b158f2008-04-19 19:45:01 +0200149
Wolfram Sangd4ec36b2009-06-21 12:32:39 +0200150Group settings are checked against the following limits in order to keep the
151configuration schedulable:
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +0100152
153 \Sum_{i} runtime_{i} / global_period <= global_runtime / global_period
154
Viktor Radnaib9b158f2008-04-19 19:45:01 +0200155For now, this can be simplified to just the following (but see Future plans):
156
157 \Sum_{i} runtime_{i} <= global_runtime
158
159
1603. Future plans
161===============
162
163There is work in progress to make the scheduling period for each group
164("/sys/kernel/uids/<uid>/cpu_rt_period_us" or
165"/cgroup/<cgroup>/cpu.rt_period_us" respectively) configurable as well.
166
167The constraint on the period is that a subgroup must have a smaller or
168equal period to its parent. But realistically its not very useful _yet_
169as its prone to starvation without deadline scheduling.
170
171Consider two sibling groups A and B; both have 50% bandwidth, but A's
172period is twice the length of B's.
173
174* group A: period=100000us, runtime=10000us
175 - this runs for 0.01s once every 0.1s
176
177* group B: period= 50000us, runtime=10000us
178 - this runs for 0.01s twice every 0.1s (or once every 0.05 sec).
179
180This means that currently a while (1) loop in A will run for the full period of
181B and can starve B's tasks (assuming they are of lower priority) for a whole
182period.
183
184The next project will be SCHED_EDF (Earliest Deadline First scheduling) to bring
185full deadline scheduling to the linux kernel. Deadline scheduling the above
186groups and treating end of the period as a deadline will ensure that they both
187get their allocated time.
188
189Implementing SCHED_EDF might take a while to complete. Priority Inheritance is
190the biggest challenge as the current linux PI infrastructure is geared towards
GeunSik Limf04d82b2009-05-28 10:36:14 +0900191the limited static priority levels 0-99. With deadline scheduling you need to
Viktor Radnaib9b158f2008-04-19 19:45:01 +0200192do deadline inheritance (since priority is inversely proportional to the
Wolfram Sangd4ec36b2009-06-21 12:32:39 +0200193deadline delta (deadline - now)).
Viktor Radnaib9b158f2008-04-19 19:45:01 +0200194
195This means the whole PI machinery will have to be reworked - and that is one of
196the most complex pieces of code we have.