188 lines · plain
1==========================2Real-Time group scheduling3==========================4 5.. CONTENTS6 7 0. WARNING8 1. Overview9 1.1 The problem10 1.2 The solution11 2. The interface12 2.1 System-wide settings13 2.2 Default behaviour14 2.3 Basis for grouping tasks15 3. Future plans16 17 180. WARNING19==========20 21 Fiddling with these settings can result in an unstable system, the knobs are22 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 unstable27 system when the period is smaller than either the available hrtimer28 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 unstable31 system when the runtime is so small the system has difficulty making32 forward progress (NOTE: the migration thread and kstopmachine both33 are real-time processes).34 351. Overview36===========37 38 391.1 The problem40---------------41 42Real-time scheduling is all about determinism, a group has to be able to rely on43the amount of bandwidth (eg. CPU time) being constant. In order to schedule44multiple groups of real-time tasks, each group must be assigned a fixed portion45of the CPU time available. Without a minimum guarantee a real-time group can46obviously fall short. A fuzzy upper limit is of no use since it cannot be47relied upon. Which leaves us with just the single fixed portion.48 491.2 The solution50----------------51 52CPU time is divided by means of specifying how much time can be spent running53in a given period. We allocate this "run time" for each real-time group which54the 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 priority57tasks (SCHED_OTHER). Any allocated run time not used will also be picked up by58SCHED_OTHER.59 60Let's consider an example: a frame fixed real-time renderer must deliver 2561frames a second, which yields a period of 0.04s per frame. Now say it will also62have to play some music and respond to input, leaving it with around 80% CPU63time dedicated for the graphics. We can then give this group a run time of 0.864* 0.04s = 0.032s.65 66This way the graphics group will have a 0.04s period with a 0.032s run time67limit. Now if the audio thread needs to refill the DMA buffer every 0.005s, but68needs 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 time70of 0.00015s.71 72The remaining CPU time will be used for user input and other tasks. Because73real-time tasks have explicitly allocated the CPU time they need to perform74their tasks, buffer underruns in the graphics or audio can be eliminated.75 76NOTE: the above example is not fully implemented yet. We still77lack an EDF scheduler to make non-uniform periods usable.78 79 802. The Interface81================82 83 842.1 System wide settings85------------------------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 always94 less or equal to the period_us, as it denotes the time allocated from the95 period_us for the real-time tasks. Even without CONFIG_RT_GROUP_SCHED enabled,96 this will limit time reserved to real-time processes. With97 CONFIG_RT_GROUP_SCHED=y it signifies the total bandwidth available to all98 real-time groups.99 100 * Time is specified in us because the interface is s32. This gives an101 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 106 1072.2 Default behaviour108---------------------109 110The default values for sched_rt_period_us (1000000 or 1s) and111sched_rt_runtime_us (950000 or 0.95s). This gives 0.05s to be used by112SCHED_OTHER (non-RT tasks). These defaults were chosen so that a run-away113real-time tasks will not lock up the machine but leave a little time to recover114it. By setting runtime to -1 you'd get the old behaviour back.115 116By default all bandwidth is assigned to the root group and new groups get the117period from /proc/sys/kernel/sched_rt_period_us and a run time of 0. If you118want to assign bandwidth to another group, reduce the root group's bandwidth119and assign some or all of the difference to another group.120 121Real-time group scheduling means you have to assign a portion of total CPU122bandwidth to the group before it will accept real-time tasks. Therefore you will123not be able to run real-time tasks as any user other than root until you have124done that, even if the user has the rights to run processes with real-time125priority!126 127 1282.3 Basis for grouping tasks129----------------------------130 131Enabling CONFIG_RT_GROUP_SCHED lets you explicitly allocate real132CPU bandwidth to task groups.133 134This uses the cgroup virtual file system and "<cgroup>/cpu.rt_runtime_us"135to control the CPU time reserved for each control group.136 137For more information on working with control groups, you should read138Documentation/admin-guide/cgroup-v1/cgroups.rst as well.139 140Group settings are checked against the following limits in order to keep the141configuration schedulable:142 143 \Sum_{i} runtime_{i} / global_period <= global_runtime / global_period144 145For now, this can be simplified to just the following (but see Future plans):146 147 \Sum_{i} runtime_{i} <= global_runtime148 149 1503. Future plans151===============152 153There is work in progress to make the scheduling period for each group154("<cgroup>/cpu.rt_period_us") configurable as well.155 156The constraint on the period is that a subgroup must have a smaller or157equal period to its parent. But realistically its not very useful _yet_158as its prone to starvation without deadline scheduling.159 160Consider two sibling groups A and B; both have 50% bandwidth, but A's161period is twice the length of B's.162 163* group A: period=100000us, runtime=50000us164 165 - this runs for 0.05s once every 0.1s166 167* group B: period= 50000us, runtime=25000us168 169 - this runs for 0.025s twice every 0.1s (or once every 0.05 sec).170 171This means that currently a while (1) loop in A will run for the full period of172B and can starve B's tasks (assuming they are of lower priority) for a whole173period.174 175The next project will be SCHED_EDF (Earliest Deadline First scheduling) to bring176full deadline scheduling to the linux kernel. Deadline scheduling the above177groups and treating end of the period as a deadline will ensure that they both178get their allocated time.179 180Implementing SCHED_EDF might take a while to complete. Priority Inheritance is181the biggest challenge as the current linux PI infrastructure is geared towards182the limited static priority levels 0-99. With deadline scheduling you need to183do deadline inheritance (since priority is inversely proportional to the184deadline delta (deadline - now)).185 186This means the whole PI machinery will have to be reworked - and that is one of187the most complex pieces of code we have.188