1 ========================== 1 ==========================
2 Real-Time group scheduling 2 Real-Time group scheduling
3 ========================== 3 ==========================
4 4
5 .. CONTENTS 5 .. CONTENTS
6 6
7 0. WARNING 7 0. WARNING
8 1. Overview 8 1. Overview
9 1.1 The problem 9 1.1 The problem
10 1.2 The solution 10 1.2 The solution
11 2. The interface 11 2. The interface
12 2.1 System-wide settings 12 2.1 System-wide settings
13 2.2 Default behaviour 13 2.2 Default behaviour
14 2.3 Basis for grouping tasks 14 2.3 Basis for grouping tasks
15 3. Future plans 15 3. Future plans
16 16
17 17
18 0. WARNING 18 0. WARNING
19 ========== 19 ==========
20 20
21 Fiddling with these settings can result in an 21 Fiddling with these settings can result in an unstable system, the knobs are
22 root only and assumes root knows what he is d 22 root only and assumes root knows what he is doing.
23 23
24 Most notable: 24 Most notable:
25 25
26 * very small values in sched_rt_period_us can 26 * very small values in sched_rt_period_us can result in an unstable
27 system when the period is smaller than eith 27 system when the period is smaller than either the available hrtimer
28 resolution, or the time it takes to handle 28 resolution, or the time it takes to handle the budget refresh itself.
29 29
30 * very small values in sched_rt_runtime_us ca 30 * very small values in sched_rt_runtime_us can result in an unstable
31 system when the runtime is so small the sys 31 system when the runtime is so small the system has difficulty making
32 forward progress (NOTE: the migration threa 32 forward progress (NOTE: the migration thread and kstopmachine both
33 are real-time processes). 33 are real-time processes).
34 34
35 1. Overview 35 1. Overview
36 =========== 36 ===========
37 37
38 38
39 1.1 The problem 39 1.1 The problem
40 --------------- 40 ---------------
41 41
42 Real-time scheduling is all about determinism, 42 Real-time scheduling is all about determinism, a group has to be able to rely on
43 the amount of bandwidth (eg. CPU time) being c 43 the amount of bandwidth (eg. CPU time) being constant. In order to schedule
44 multiple groups of real-time tasks, each group 44 multiple groups of real-time tasks, each group must be assigned a fixed portion
45 of the CPU time available. Without a minimum 45 of the CPU time available. Without a minimum guarantee a real-time group can
46 obviously fall short. A fuzzy upper limit is o 46 obviously fall short. A fuzzy upper limit is of no use since it cannot be
47 relied upon. Which leaves us with just the sin 47 relied upon. Which leaves us with just the single fixed portion.
48 48
49 1.2 The solution 49 1.2 The solution
50 ---------------- 50 ----------------
51 51
52 CPU time is divided by means of specifying how 52 CPU time is divided by means of specifying how much time can be spent running
53 in a given period. We allocate this "run time" 53 in a given period. We allocate this "run time" for each real-time group which
54 the other real-time groups will not be permitt 54 the other real-time groups will not be permitted to use.
55 55
56 Any time not allocated to a real-time group wi 56 Any time not allocated to a real-time group will be used to run normal priority
57 tasks (SCHED_OTHER). Any allocated run time no 57 tasks (SCHED_OTHER). Any allocated run time not used will also be picked up by
58 SCHED_OTHER. 58 SCHED_OTHER.
59 59
60 Let's consider an example: a frame fixed real- 60 Let's consider an example: a frame fixed real-time renderer must deliver 25
61 frames a second, which yields a period of 0.04 61 frames a second, which yields a period of 0.04s per frame. Now say it will also
62 have to play some music and respond to input, 62 have to play some music and respond to input, leaving it with around 80% CPU
63 time dedicated for the graphics. We can then g 63 time dedicated for the graphics. We can then give this group a run time of 0.8
64 * 0.04s = 0.032s. 64 * 0.04s = 0.032s.
65 65
66 This way the graphics group will have a 0.04s 66 This way the graphics group will have a 0.04s period with a 0.032s run time
67 limit. Now if the audio thread needs to refill 67 limit. Now if the audio thread needs to refill the DMA buffer every 0.005s, but
68 needs only about 3% CPU time to do so, it can 68 needs only about 3% CPU time to do so, it can do with a 0.03 * 0.005s =
69 0.00015s. So this group can be scheduled with 69 0.00015s. So this group can be scheduled with a period of 0.005s and a run time
70 of 0.00015s. 70 of 0.00015s.
71 71
72 The remaining CPU time will be used for user i 72 The remaining CPU time will be used for user input and other tasks. Because
73 real-time tasks have explicitly allocated the 73 real-time tasks have explicitly allocated the CPU time they need to perform
74 their tasks, buffer underruns in the graphics 74 their tasks, buffer underruns in the graphics or audio can be eliminated.
75 75
76 NOTE: the above example is not fully implement 76 NOTE: the above example is not fully implemented yet. We still
77 lack an EDF scheduler to make non-uniform peri 77 lack an EDF scheduler to make non-uniform periods usable.
78 78
79 79
80 2. The Interface 80 2. The Interface
81 ================ 81 ================
82 82
83 83
84 2.1 System wide settings 84 2.1 System wide settings
85 ------------------------ 85 ------------------------
86 86
87 The system wide settings are configured under 87 The system wide settings are configured under the /proc virtual file system:
88 88
89 /proc/sys/kernel/sched_rt_period_us: 89 /proc/sys/kernel/sched_rt_period_us:
90 The scheduling period that is equivalent to 90 The scheduling period that is equivalent to 100% CPU bandwidth.
91 91
92 /proc/sys/kernel/sched_rt_runtime_us: 92 /proc/sys/kernel/sched_rt_runtime_us:
93 A global limit on how much time real-time sc 93 A global limit on how much time real-time scheduling may use. This is always
94 less or equal to the period_us, as it denote 94 less or equal to the period_us, as it denotes the time allocated from the
95 period_us for the real-time tasks. Even with 95 period_us for the real-time tasks. Even without CONFIG_RT_GROUP_SCHED enabled,
96 this will limit time reserved to real-time p 96 this will limit time reserved to real-time processes. With
97 CONFIG_RT_GROUP_SCHED=y it signifies the tot 97 CONFIG_RT_GROUP_SCHED=y it signifies the total bandwidth available to all
98 real-time groups. 98 real-time groups.
99 99
100 * Time is specified in us because the interf 100 * Time is specified in us because the interface is s32. This gives an
101 operating range from 1us to about 35 minut 101 operating range from 1us to about 35 minutes.
102 * sched_rt_period_us takes values from 1 to 102 * sched_rt_period_us takes values from 1 to INT_MAX.
103 * sched_rt_runtime_us takes values from -1 t 103 * sched_rt_runtime_us takes values from -1 to sched_rt_period_us.
104 * A run time of -1 specifies runtime == peri 104 * A run time of -1 specifies runtime == period, ie. no limit.
105 105
106 106
107 2.2 Default behaviour 107 2.2 Default behaviour
108 --------------------- 108 ---------------------
109 109
110 The default values for sched_rt_period_us (100 110 The default values for sched_rt_period_us (1000000 or 1s) and
111 sched_rt_runtime_us (950000 or 0.95s). This g 111 sched_rt_runtime_us (950000 or 0.95s). This gives 0.05s to be used by
112 SCHED_OTHER (non-RT tasks). These defaults wer 112 SCHED_OTHER (non-RT tasks). These defaults were chosen so that a run-away
113 real-time tasks will not lock up the machine b 113 real-time tasks will not lock up the machine but leave a little time to recover
114 it. By setting runtime to -1 you'd get the ol 114 it. By setting runtime to -1 you'd get the old behaviour back.
115 115
116 By default all bandwidth is assigned to the ro 116 By default all bandwidth is assigned to the root group and new groups get the
117 period from /proc/sys/kernel/sched_rt_period_u 117 period from /proc/sys/kernel/sched_rt_period_us and a run time of 0. If you
118 want to assign bandwidth to another group, red 118 want to assign bandwidth to another group, reduce the root group's bandwidth
119 and assign some or all of the difference to an 119 and assign some or all of the difference to another group.
120 120
121 Real-time group scheduling means you have to a 121 Real-time group scheduling means you have to assign a portion of total CPU
122 bandwidth to the group before it will accept r 122 bandwidth to the group before it will accept real-time tasks. Therefore you will
123 not be able to run real-time tasks as any user 123 not be able to run real-time tasks as any user other than root until you have
124 done that, even if the user has the rights to 124 done that, even if the user has the rights to run processes with real-time
125 priority! 125 priority!
126 126
127 127
128 2.3 Basis for grouping tasks 128 2.3 Basis for grouping tasks
129 ---------------------------- 129 ----------------------------
130 130
131 Enabling CONFIG_RT_GROUP_SCHED lets you explic 131 Enabling CONFIG_RT_GROUP_SCHED lets you explicitly allocate real
132 CPU bandwidth to task groups. 132 CPU bandwidth to task groups.
133 133
134 This uses the cgroup virtual file system and " 134 This uses the cgroup virtual file system and "<cgroup>/cpu.rt_runtime_us"
135 to control the CPU time reserved for each cont 135 to control the CPU time reserved for each control group.
136 136
137 For more information on working with control g 137 For more information on working with control groups, you should read
138 Documentation/admin-guide/cgroup-v1/cgroups.rs 138 Documentation/admin-guide/cgroup-v1/cgroups.rst as well.
139 139
140 Group settings are checked against the followi 140 Group settings are checked against the following limits in order to keep the
141 configuration schedulable: 141 configuration schedulable:
142 142
143 \Sum_{i} runtime_{i} / global_period <= glo 143 \Sum_{i} runtime_{i} / global_period <= global_runtime / global_period
144 144
145 For now, this can be simplified to just the fo 145 For now, this can be simplified to just the following (but see Future plans):
146 146
147 \Sum_{i} runtime_{i} <= global_runtime 147 \Sum_{i} runtime_{i} <= global_runtime
148 148
149 149
150 3. Future plans 150 3. Future plans
151 =============== 151 ===============
152 152
153 There is work in progress to make the scheduli 153 There is work in progress to make the scheduling period for each group
154 ("<cgroup>/cpu.rt_period_us") configurable as 154 ("<cgroup>/cpu.rt_period_us") configurable as well.
155 155
156 The constraint on the period is that a subgrou 156 The constraint on the period is that a subgroup must have a smaller or
157 equal period to its parent. But realistically 157 equal period to its parent. But realistically its not very useful _yet_
158 as its prone to starvation without deadline sc 158 as its prone to starvation without deadline scheduling.
159 159
160 Consider two sibling groups A and B; both have 160 Consider two sibling groups A and B; both have 50% bandwidth, but A's
161 period is twice the length of B's. 161 period is twice the length of B's.
162 162
163 * group A: period=100000us, runtime=50000us 163 * group A: period=100000us, runtime=50000us
164 164
165 - this runs for 0.05s once every 0.1s 165 - this runs for 0.05s once every 0.1s
166 166
167 * group B: period= 50000us, runtime=25000us 167 * group B: period= 50000us, runtime=25000us
168 168
169 - this runs for 0.025s twice every 0.1 169 - this runs for 0.025s twice every 0.1s (or once every 0.05 sec).
170 170
171 This means that currently a while (1) loop in 171 This means that currently a while (1) loop in A will run for the full period of
172 B and can starve B's tasks (assuming they are 172 B and can starve B's tasks (assuming they are of lower priority) for a whole
173 period. 173 period.
174 174
175 The next project will be SCHED_EDF (Earliest D 175 The next project will be SCHED_EDF (Earliest Deadline First scheduling) to bring
176 full deadline scheduling to the linux kernel. 176 full deadline scheduling to the linux kernel. Deadline scheduling the above
177 groups and treating end of the period as a dea 177 groups and treating end of the period as a deadline will ensure that they both
178 get their allocated time. 178 get their allocated time.
179 179
180 Implementing SCHED_EDF might take a while to c 180 Implementing SCHED_EDF might take a while to complete. Priority Inheritance is
181 the biggest challenge as the current linux PI 181 the biggest challenge as the current linux PI infrastructure is geared towards
182 the limited static priority levels 0-99. With 182 the limited static priority levels 0-99. With deadline scheduling you need to
183 do deadline inheritance (since priority is inv 183 do deadline inheritance (since priority is inversely proportional to the
184 deadline delta (deadline - now)). 184 deadline delta (deadline - now)).
185 185
186 This means the whole PI machinery will have to 186 This means the whole PI machinery will have to be reworked - and that is one of
187 the most complex pieces of code we have. 187 the most complex pieces of code we have.
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.