aboutsummaryrefslogtreecommitdiffstats
path: root/Documentation/scheduler
diff options
context:
space:
mode:
authorViktor Radnai <viktor.radnai@gmail.com>2008-04-19 13:45:01 -0400
committerIngo Molnar <mingo@elte.hu>2008-04-19 13:45:01 -0400
commitb9b158fe1ca2c166ff918de30cb098eafcae487a (patch)
tree4320cfc00f7910444061479f652d0f94787b7c31 /Documentation/scheduler
parentc24b7c524421f9ea9d9ebab55f80cfb1f3fb77a3 (diff)
sched: better rt-group documentation
Viktor was nice enough to enhance the document based on my replies to his questions on the subject. Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl> Signed-off-by: Ingo Molnar <mingo@elte.hu>
Diffstat (limited to 'Documentation/scheduler')
-rw-r--r--Documentation/scheduler/sched-rt-group.txt188
1 files changed, 153 insertions, 35 deletions
diff --git a/Documentation/scheduler/sched-rt-group.txt b/Documentation/scheduler/sched-rt-group.txt
index 1c6332f4543c..14f901f639ee 100644
--- a/Documentation/scheduler/sched-rt-group.txt
+++ b/Documentation/scheduler/sched-rt-group.txt
@@ -1,59 +1,177 @@
1 Real-Time group scheduling
2 --------------------------
1 3
4CONTENTS
5========
2 6
3Real-Time group scheduling. 71. Overview
8 1.1 The problem
9 1.2 The solution
102. The interface
11 2.1 System-wide settings
12 2.2 Default behaviour
13 2.3 Basis for grouping tasks
143. Future plans
4 15
5The problem space:
6 16
7In order to schedule multiple groups of realtime tasks each group must 171. Overview
8be assigned a fixed portion of the CPU time available. Without a minimum 18===========
9guarantee a realtime group can obviously fall short. A fuzzy upper limit
10is of no use since it cannot be relied upon. Which leaves us with just
11the single fixed portion.
12 19
13CPU time is divided by means of specifying how much time can be spent
14running in a given period. Say a frame fixed realtime renderer must
15deliver 25 frames a second, which yields a period of 0.04s. Now say
16it will also have to play some music and respond to input, leaving it
17with around 80% for the graphics. We can then give this group a runtime
18of 0.8 * 0.04s = 0.032s.
19 20
20This way the graphics group will have a 0.04s period with a 0.032s runtime 211.1 The problem
21limit. 22---------------
22 23
23Now if the audio thread needs to refill the DMA buffer every 0.005s, but 24Realtime scheduling is all about determinism, a group has to be able to rely on
24needs only about 3% CPU time to do so, it can do with a 0.03 * 0.005s 25the amount of bandwidth (eg. CPU time) being constant. In order to schedule
25= 0.00015s. 26multiple groups of realtime tasks, each group must be assigned a fixed portion
27of the CPU time available. Without a minimum guarantee a realtime group can
28obviously fall short. A fuzzy upper limit is of no use since it cannot be
29relied upon. Which leaves us with just the single fixed portion.
26 30
311.2 The solution
32----------------
27 33
28The Interface: 34CPU time is divided by means of specifying how much time can be spent running
35in a given period. We allocate this "run time" for each realtime group which
36the other realtime groups will not be permitted to use.
29 37
30system wide: 38Any time not allocated to a realtime group will be used to run normal priority
39tasks (SCHED_OTHER). Any allocated run time not used will also be picked up by
40SCHED_OTHER.
31 41
32/proc/sys/kernel/sched_rt_period_ms 42Let's consider an example: a frame fixed realtime renderer must deliver 25
33/proc/sys/kernel/sched_rt_runtime_us 43frames a second, which yields a period of 0.04s per frame. Now say it will also
44have to play some music and respond to input, leaving it with around 80% CPU
45time dedicated for the graphics. We can then give this group a run time of 0.8
46* 0.04s = 0.032s.
34 47
35CONFIG_FAIR_USER_SCHED 48This way the graphics group will have a 0.04s period with a 0.032s run time
49limit. Now if the audio thread needs to refill the DMA buffer every 0.005s, but
50needs only about 3% CPU time to do so, it can do with a 0.03 * 0.005s =
510.00015s. So this group can be scheduled with a period of 0.005s and a run time
52of 0.00015s.
36 53
37/sys/kernel/uids/<uid>/cpu_rt_runtime_us 54The remaining CPU time will be used for user input and other tass. Because
55realtime tasks have explicitly allocated the CPU time they need to perform
56their tasks, buffer underruns in the graphocs or audio can be eliminated.
38 57
39or 58NOTE: the above example is not fully implemented as of yet (2.6.25). We still
59lack an EDF scheduler to make non-uniform periods usable.
40 60
41CONFIG_FAIR_CGROUP_SCHED
42 61
43/cgroup/<cgroup>/cpu.rt_runtime_us 622. The Interface
63================
44 64
45[ time is specified in us because the interface is s32; this gives an
46 operating range of ~35m to 1us ]
47 65
48The period takes values in [ 1, INT_MAX ], runtime in [ -1, INT_MAX - 1 ]. 662.1 System wide settings
67------------------------
49 68
50A runtime of -1 specifies runtime == period, ie. no limit. 69The system wide settings are configured under the /proc virtual file system:
51 70
52New groups get the period from /proc/sys/kernel/sched_rt_period_us and 71/proc/sys/kernel/sched_rt_period_us:
53a runtime of 0. 72 The scheduling period that is equivalent to 100% CPU bandwidth
54 73
55Settings are constrained to: 74/proc/sys/kernel/sched_rt_runtime_us:
75 A global limit on how much time realtime scheduling may use. Even without
76 CONFIG_RT_GROUP_SCHED enabled, this will limit time reserved to realtime
77 processes. With CONFIG_RT_GROUP_SCHED it signifies the total bandwidth
78 available to all realtime groups.
79
80 * Time is specified in us because the interface is s32. This gives an
81 operating range from 1us to about 35 minutes.
82 * sched_rt_period_us takes values from 1 to INT_MAX.
83 * sched_rt_runtime_us takes values from -1 to (INT_MAX - 1).
84 * A run time of -1 specifies runtime == period, ie. no limit.
85
86
872.2 Default behaviour
88---------------------
89
90The default values for sched_rt_period_us (1000000 or 1s) and
91sched_rt_runtime_us (950000 or 0.95s). This gives 0.05s to be used by
92SCHED_OTHER (non-RT tasks). These defaults were chosen so that a run-away
93realtime tasks will not lock up the machine but leave a little time to recover
94it. By setting runtime to -1 you'd get the old behaviour back.
95
96By default all bandwidth is assigned to the root group and new groups get the
97period from /proc/sys/kernel/sched_rt_period_us and a run time of 0. If you
98want to assign bandwidth to another group, reduce the root group's bandwidth
99and assign some or all of the difference to another group.
100
101Realtime group scheduling means you have to assign a portion of total CPU
102bandwidth to the group before it will accept realtime tasks. Therefore you will
103not be able to run realtime tasks as any user other than root until you have
104done that, even if the user has the rights to run processes with realtime
105priority!
106
107
1082.3 Basis for grouping tasks
109----------------------------
110
111There are two compile-time settings for allocating CPU bandwidth. These are
112configured using the "Basis for grouping tasks" multiple choice menu under
113General setup > Group CPU Scheduler:
114
115a. CONFIG_USER_SCHED (aka "Basis for grouping tasks" = "user id")
116
117This lets you use the virtual files under
118"/sys/kernel/uids/<uid>/cpu_rt_runtime_us" to control he CPU time reserved for
119each user .
120
121The other option is:
122
123.o CONFIG_CGROUP_SCHED (aka "Basis for grouping tasks" = "Control groups")
124
125This uses the /cgroup virtual file system and "/cgroup/<cgroup>/cpu.rt_runtime_us"
126to control the CPU time reserved for each control group instead.
127
128For more information on working with control groups, you should read
129Documentation/cgroups.txt as well.
130
131Group settings are checked against the following limits in order to keep the configuration
132schedulable:
56 133
57 \Sum_{i} runtime_{i} / global_period <= global_runtime / global_period 134 \Sum_{i} runtime_{i} / global_period <= global_runtime / global_period
58 135
59in order to keep the configuration schedulable. 136For now, this can be simplified to just the following (but see Future plans):
137
138 \Sum_{i} runtime_{i} <= global_runtime
139
140
1413. Future plans
142===============
143
144There is work in progress to make the scheduling period for each group
145("/sys/kernel/uids/<uid>/cpu_rt_period_us" or
146"/cgroup/<cgroup>/cpu.rt_period_us" respectively) configurable as well.
147
148The constraint on the period is that a subgroup must have a smaller or
149equal period to its parent. But realistically its not very useful _yet_
150as its prone to starvation without deadline scheduling.
151
152Consider two sibling groups A and B; both have 50% bandwidth, but A's
153period is twice the length of B's.
154
155* group A: period=100000us, runtime=10000us
156 - this runs for 0.01s once every 0.1s
157
158* group B: period= 50000us, runtime=10000us
159 - this runs for 0.01s twice every 0.1s (or once every 0.05 sec).
160
161This means that currently a while (1) loop in A will run for the full period of
162B and can starve B's tasks (assuming they are of lower priority) for a whole
163period.
164
165The next project will be SCHED_EDF (Earliest Deadline First scheduling) to bring
166full deadline scheduling to the linux kernel. Deadline scheduling the above
167groups and treating end of the period as a deadline will ensure that they both
168get their allocated time.
169
170Implementing SCHED_EDF might take a while to complete. Priority Inheritance is
171the biggest challenge as the current linux PI infrastructure is geared towards
172the limited static priority levels 0-139. With deadline scheduling you need to
173do deadline inheritance (since priority is inversely proportional to the
174deadline delta (deadline - now).
175
176This means the whole PI machinery will have to be reworked - and that is one of
177the most complex pieces of code we have.