1========================== 2Real-Time group scheduling 3========================== 4 5.. CONTENTS 6 7 0. WARNING 8 1. Overview 9 1.1 The problem 10 1.2 The solution 11 2. The interface 12 2.1 System-wide settings 13 2.2 Default behaviour 14 2.3 Basis for grouping tasks 15 3. Future plans 16 17 180. 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 351. Overview 36=========== 37 38 391.1 The problem 40--------------- 41 42Real-time 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 real-time tasks, each group must be assigned a fixed portion 45of the CPU time available. Without a minimum guarantee a real-time 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. 48 491.2 The solution 50---------------- 51 52CPU 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 real-time group which 54the other real-time groups will not be permitted to use. 55 56Any time not allocated to a real-time 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. 59 60Let's consider an example: a frame fixed real-time 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. 65 66This 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. 71 72The remaining CPU time will be used for user input and other tasks. Because 73real-time tasks have explicitly allocated the CPU time they need to perform 74their tasks, buffer underruns in the graphics or audio can be eliminated. 75 76NOTE: the above example is not fully implemented yet. We still 77lack an EDF scheduler to make non-uniform periods usable. 78 79 802. The Interface 81================ 82 83 842.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 real-time scheduling may use. This is always 94 less or equal to the period_us, as it denotes the time allocated from the 95 period_us for the real-time tasks. Without CONFIG_RT_GROUP_SCHED enabled, 96 this only serves for admission control of deadline tasks. With 97 CONFIG_RT_GROUP_SCHED=y it also signifies the total bandwidth available to 98 all real-time groups. 99 100 * Time is specified in us because the interface is s32. This gives an 101 operating range from 1us to about 35 minutes. 102 * sched_rt_period_us takes values from 1 to INT_MAX. 103 * sched_rt_runtime_us takes values from -1 to sched_rt_period_us. 104 * A run time of -1 specifies runtime == period, ie. no limit. 105 * sched_rt_runtime_us/sched_rt_period_us > 0.05 inorder to preserve 106 bandwidth for fair dl_server. For accurate value check average of 107 runtime/period in /sys/kernel/debug/sched/fair_server/cpuX/ 108 109 1102.2 Default behaviour 111--------------------- 112 113The default values for sched_rt_period_us (1000000 or 1s) and 114sched_rt_runtime_us (950000 or 0.95s). This gives 0.05s to be used by 115SCHED_OTHER (non-RT tasks). These defaults were chosen so that a run-away 116real-time tasks will not lock up the machine but leave a little time to recover 117it. By setting runtime to -1 you'd get the old behaviour back. 118 119By default all bandwidth is assigned to the root group and new groups get the 120period from /proc/sys/kernel/sched_rt_period_us and a run time of 0. If you 121want to assign bandwidth to another group, reduce the root group's bandwidth 122and assign some or all of the difference to another group. 123 124Real-time group scheduling means you have to assign a portion of total CPU 125bandwidth to the group before it will accept real-time tasks. Therefore you will 126not be able to run real-time tasks as any user other than root until you have 127done that, even if the user has the rights to run processes with real-time 128priority! 129 130 1312.3 Basis for grouping tasks 132---------------------------- 133 134Enabling CONFIG_RT_GROUP_SCHED lets you explicitly allocate real 135CPU bandwidth to task groups. 136 137This uses the cgroup virtual file system and "<cgroup>/cpu.rt_runtime_us" 138to control the CPU time reserved for each control group. 139 140For more information on working with control groups, you should read 141Documentation/admin-guide/cgroup-v1/cgroups.rst as well. 142 143Group settings are checked against the following limits in order to keep the 144configuration schedulable: 145 146 \Sum_{i} runtime_{i} / global_period <= global_runtime / global_period 147 148For now, this can be simplified to just the following (but see Future plans): 149 150 \Sum_{i} runtime_{i} <= global_runtime 151 152 1533. Future plans 154=============== 155 156There is work in progress to make the scheduling period for each group 157("<cgroup>/cpu.rt_period_us") configurable as well. 158 159The constraint on the period is that a subgroup must have a smaller or 160equal period to its parent. But realistically its not very useful _yet_ 161as its prone to starvation without deadline scheduling. 162 163Consider two sibling groups A and B; both have 50% bandwidth, but A's 164period is twice the length of B's. 165 166* group A: period=100000us, runtime=50000us 167 168 - this runs for 0.05s once every 0.1s 169 170* group B: period= 50000us, runtime=25000us 171 172 - this runs for 0.025s twice every 0.1s (or once every 0.05 sec). 173 174This means that currently a while (1) loop in A will run for the full period of 175B and can starve B's tasks (assuming they are of lower priority) for a whole 176period. 177 178The next project will be SCHED_EDF (Earliest Deadline First scheduling) to bring 179full deadline scheduling to the linux kernel. Deadline scheduling the above 180groups and treating end of the period as a deadline will ensure that they both 181get their allocated time. 182 183Implementing SCHED_EDF might take a while to complete. Priority Inheritance is 184the biggest challenge as the current linux PI infrastructure is geared towards 185the limited static priority levels 0-99. With deadline scheduling you need to 186do deadline inheritance (since priority is inversely proportional to the 187deadline delta (deadline - now)). 188 189This means the whole PI machinery will have to be reworked - and that is one of 190the most complex pieces of code we have. 191