1 Real-Time group scheduling 2 -------------------------- 3 4CONTENTS 5======== 6 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 15 16 171. Overview 18=========== 19 20 211.1 The problem 22--------------- 23 24Realtime scheduling is all about determinism, a group has to be able to rely on 25the amount of bandwidth (eg. CPU time) being constant. In order to schedule 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. 30 311.2 The solution 32---------------- 33 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. 37 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. 41 42Let's consider an example: a frame fixed realtime renderer must deliver 25 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. 47 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. 53 54The remaining CPU time will be used for user input and other tasks. Because 55realtime tasks have explicitly allocated the CPU time they need to perform 56their tasks, buffer underruns in the graphics or audio can be eliminated. 57 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. 60 61 622. The Interface 63================ 64 65 662.1 System wide settings 67------------------------ 68 69The system wide settings are configured under the /proc virtual file system: 70 71/proc/sys/kernel/sched_rt_period_us: 72 The scheduling period that is equivalent to 100% CPU bandwidth 73 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: 133 134 \Sum_{i} runtime_{i} / global_period <= global_runtime / global_period 135 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. 178