443 lines · plain
1=========================2Capacity Aware Scheduling3=========================4 51. CPU Capacity6===============7 81.1 Introduction9----------------10 11Conventional, homogeneous SMP platforms are composed of purely identical12CPUs. Heterogeneous platforms on the other hand are composed of CPUs with13different performance characteristics - on such platforms, not all CPUs can be14considered equal.15 16CPU capacity is a measure of the performance a CPU can reach, normalized against17the most performant CPU in the system. Heterogeneous systems are also called18asymmetric CPU capacity systems, as they contain CPUs of different capacities.19 20Disparity in maximum attainable performance (IOW in maximum CPU capacity) stems21from two factors:22 23- not all CPUs may have the same microarchitecture (µarch).24- with Dynamic Voltage and Frequency Scaling (DVFS), not all CPUs may be25 physically able to attain the higher Operating Performance Points (OPP).26 27Arm big.LITTLE systems are an example of both. The big CPUs are more28performance-oriented than the LITTLE ones (more pipeline stages, bigger caches,29smarter predictors, etc), and can usually reach higher OPPs than the LITTLE ones30can.31 32CPU performance is usually expressed in Millions of Instructions Per Second33(MIPS), which can also be expressed as a given amount of instructions attainable34per Hz, leading to::35 36 capacity(cpu) = work_per_hz(cpu) * max_freq(cpu)37 381.2 Scheduler terms39-------------------40 41Two different capacity values are used within the scheduler. A CPU's42``original capacity`` is its maximum attainable capacity, i.e. its maximum43attainable performance level. This original capacity is returned by44the function arch_scale_cpu_capacity(). A CPU's ``capacity`` is its ``original45capacity`` to which some loss of available performance (e.g. time spent46handling IRQs) is subtracted.47 48Note that a CPU's ``capacity`` is solely intended to be used by the CFS class,49while ``original capacity`` is class-agnostic. The rest of this document will use50the term ``capacity`` interchangeably with ``original capacity`` for the sake of51brevity.52 531.3 Platform examples54---------------------55 561.3.1 Identical OPPs57~~~~~~~~~~~~~~~~~~~~58 59Consider an hypothetical dual-core asymmetric CPU capacity system where60 61- work_per_hz(CPU0) = W62- work_per_hz(CPU1) = W/263- all CPUs are running at the same fixed frequency64 65By the above definition of capacity:66 67- capacity(CPU0) = C68- capacity(CPU1) = C/269 70To draw the parallel with Arm big.LITTLE, CPU0 would be a big while CPU1 would71be a LITTLE.72 73With a workload that periodically does a fixed amount of work, you will get an74execution trace like so::75 76 CPU0 work ^77 | ____ ____ ____78 | | | | | | |79 +----+----+----+----+----+----+----+----+----+----+-> time80 81 CPU1 work ^82 | _________ _________ ____83 | | | | | |84 +----+----+----+----+----+----+----+----+----+----+-> time85 86CPU0 has the highest capacity in the system (C), and completes a fixed amount of87work W in T units of time. On the other hand, CPU1 has half the capacity of88CPU0, and thus only completes W/2 in T.89 901.3.2 Different max OPPs91~~~~~~~~~~~~~~~~~~~~~~~~92 93Usually, CPUs of different capacity values also have different maximum94OPPs. Consider the same CPUs as above (i.e. same work_per_hz()) with:95 96- max_freq(CPU0) = F97- max_freq(CPU1) = 2/3 * F98 99This yields:100 101- capacity(CPU0) = C102- capacity(CPU1) = C/3103 104Executing the same workload as described in 1.3.1, which each CPU running at its105maximum frequency results in::106 107 CPU0 work ^108 | ____ ____ ____109 | | | | | | |110 +----+----+----+----+----+----+----+----+----+----+-> time111 112 workload on CPU1113 CPU1 work ^114 | ______________ ______________ ____115 | | | | | |116 +----+----+----+----+----+----+----+----+----+----+-> time117 1181.4 Representation caveat119-------------------------120 121It should be noted that having a *single* value to represent differences in CPU122performance is somewhat of a contentious point. The relative performance123difference between two different µarchs could be X% on integer operations, Y% on124floating point operations, Z% on branches, and so on. Still, results using this125simple approach have been satisfactory for now.126 1272. Task utilization128===================129 1302.1 Introduction131----------------132 133Capacity aware scheduling requires an expression of a task's requirements with134regards to CPU capacity. Each scheduler class can express this differently, and135while task utilization is specific to CFS, it is convenient to describe it here136in order to introduce more generic concepts.137 138Task utilization is a percentage meant to represent the throughput requirements139of a task. A simple approximation of it is the task's duty cycle, i.e.::140 141 task_util(p) = duty_cycle(p)142 143On an SMP system with fixed frequencies, 100% utilization suggests the task is a144busy loop. Conversely, 10% utilization hints it is a small periodic task that145spends more time sleeping than executing. Variable CPU frequencies and146asymmetric CPU capacities complexify this somewhat; the following sections will147expand on these.148 1492.2 Frequency invariance150------------------------151 152One issue that needs to be taken into account is that a workload's duty cycle is153directly impacted by the current OPP the CPU is running at. Consider running a154periodic workload at a given frequency F::155 156 CPU work ^157 | ____ ____ ____158 | | | | | | |159 +----+----+----+----+----+----+----+----+----+----+-> time160 161This yields duty_cycle(p) == 25%.162 163Now, consider running the *same* workload at frequency F/2::164 165 CPU work ^166 | _________ _________ ____167 | | | | | |168 +----+----+----+----+----+----+----+----+----+----+-> time169 170This yields duty_cycle(p) == 50%, despite the task having the exact same171behaviour (i.e. executing the same amount of work) in both executions.172 173The task utilization signal can be made frequency invariant using the following174formula::175 176 task_util_freq_inv(p) = duty_cycle(p) * (curr_frequency(cpu) / max_frequency(cpu))177 178Applying this formula to the two examples above yields a frequency invariant179task utilization of 25%.180 1812.3 CPU invariance182------------------183 184CPU capacity has a similar effect on task utilization in that running an185identical workload on CPUs of different capacity values will yield different186duty cycles.187 188Consider the system described in 1.3.2., i.e.::189 190- capacity(CPU0) = C191- capacity(CPU1) = C/3192 193Executing a given periodic workload on each CPU at their maximum frequency would194result in::195 196 CPU0 work ^197 | ____ ____ ____198 | | | | | | |199 +----+----+----+----+----+----+----+----+----+----+-> time200 201 CPU1 work ^202 | ______________ ______________ ____203 | | | | | |204 +----+----+----+----+----+----+----+----+----+----+-> time205 206IOW,207 208- duty_cycle(p) == 25% if p runs on CPU0 at its maximum frequency209- duty_cycle(p) == 75% if p runs on CPU1 at its maximum frequency210 211The task utilization signal can be made CPU invariant using the following212formula::213 214 task_util_cpu_inv(p) = duty_cycle(p) * (capacity(cpu) / max_capacity)215 216with ``max_capacity`` being the highest CPU capacity value in the217system. Applying this formula to the above example above yields a CPU218invariant task utilization of 25%.219 2202.4 Invariant task utilization221------------------------------222 223Both frequency and CPU invariance need to be applied to task utilization in224order to obtain a truly invariant signal. The pseudo-formula for a task225utilization that is both CPU and frequency invariant is thus, for a given226task p::227 228 curr_frequency(cpu) capacity(cpu)229 task_util_inv(p) = duty_cycle(p) * ------------------- * -------------230 max_frequency(cpu) max_capacity231 232In other words, invariant task utilization describes the behaviour of a task as233if it were running on the highest-capacity CPU in the system, running at its234maximum frequency.235 236Any mention of task utilization in the following sections will imply its237invariant form.238 2392.5 Utilization estimation240--------------------------241 242Without a crystal ball, task behaviour (and thus task utilization) cannot243accurately be predicted the moment a task first becomes runnable. The CFS class244maintains a handful of CPU and task signals based on the Per-Entity Load245Tracking (PELT) mechanism, one of those yielding an *average* utilization (as246opposed to instantaneous).247 248This means that while the capacity aware scheduling criteria will be written249considering a "true" task utilization (using a crystal ball), the implementation250will only ever be able to use an estimator thereof.251 2523. Capacity aware scheduling requirements253=========================================254 2553.1 CPU capacity256----------------257 258Linux cannot currently figure out CPU capacity on its own, this information thus259needs to be handed to it. Architectures must define arch_scale_cpu_capacity()260for that purpose.261 262The arm, arm64, and RISC-V architectures directly map this to the arch_topology driver263CPU scaling data, which is derived from the capacity-dmips-mhz CPU binding; see264Documentation/devicetree/bindings/cpu/cpu-capacity.txt.265 2663.2 Frequency invariance267------------------------268 269As stated in 2.2, capacity-aware scheduling requires a frequency-invariant task270utilization. Architectures must define arch_scale_freq_capacity(cpu) for that271purpose.272 273Implementing this function requires figuring out at which frequency each CPU274have been running at. One way to implement this is to leverage hardware counters275whose increment rate scale with a CPU's current frequency (APERF/MPERF on x86,276AMU on arm64). Another is to directly hook into cpufreq frequency transitions,277when the kernel is aware of the switched-to frequency (also employed by278arm/arm64).279 2804. Scheduler topology281=====================282 283During the construction of the sched domains, the scheduler will figure out284whether the system exhibits asymmetric CPU capacities. Should that be the285case:286 287- The sched_asym_cpucapacity static key will be enabled.288- The SD_ASYM_CPUCAPACITY_FULL flag will be set at the lowest sched_domain289 level that spans all unique CPU capacity values.290- The SD_ASYM_CPUCAPACITY flag will be set for any sched_domain that spans291 CPUs with any range of asymmetry.292 293The sched_asym_cpucapacity static key is intended to guard sections of code that294cater to asymmetric CPU capacity systems. Do note however that said key is295*system-wide*. Imagine the following setup using cpusets::296 297 capacity C/2 C298 ________ ________299 / \ / \300 CPUs 0 1 2 3 4 5 6 7301 \__/ \______________/302 cpusets cs0 cs1303 304Which could be created via:305 306.. code-block:: sh307 308 mkdir /sys/fs/cgroup/cpuset/cs0309 echo 0-1 > /sys/fs/cgroup/cpuset/cs0/cpuset.cpus310 echo 0 > /sys/fs/cgroup/cpuset/cs0/cpuset.mems311 312 mkdir /sys/fs/cgroup/cpuset/cs1313 echo 2-7 > /sys/fs/cgroup/cpuset/cs1/cpuset.cpus314 echo 0 > /sys/fs/cgroup/cpuset/cs1/cpuset.mems315 316 echo 0 > /sys/fs/cgroup/cpuset/cpuset.sched_load_balance317 318Since there *is* CPU capacity asymmetry in the system, the319sched_asym_cpucapacity static key will be enabled. However, the sched_domain320hierarchy of CPUs 0-1 spans a single capacity value: SD_ASYM_CPUCAPACITY isn't321set in that hierarchy, it describes an SMP island and should be treated as such.322 323Therefore, the 'canonical' pattern for protecting codepaths that cater to324asymmetric CPU capacities is to:325 326- Check the sched_asym_cpucapacity static key327- If it is enabled, then also check for the presence of SD_ASYM_CPUCAPACITY in328 the sched_domain hierarchy (if relevant, i.e. the codepath targets a specific329 CPU or group thereof)330 3315. Capacity aware scheduling implementation332===========================================333 3345.1 CFS335-------336 3375.1.1 Capacity fitness338~~~~~~~~~~~~~~~~~~~~~~339 340The main capacity scheduling criterion of CFS is::341 342 task_util(p) < capacity(task_cpu(p))343 344This is commonly called the capacity fitness criterion, i.e. CFS must ensure a345task "fits" on its CPU. If it is violated, the task will need to achieve more346work than what its CPU can provide: it will be CPU-bound.347 348Furthermore, uclamp lets userspace specify a minimum and a maximum utilization349value for a task, either via sched_setattr() or via the cgroup interface (see350Documentation/admin-guide/cgroup-v2.rst). As its name imply, this can be used to351clamp task_util() in the previous criterion.352 3535.1.2 Wakeup CPU selection354~~~~~~~~~~~~~~~~~~~~~~~~~~355 356CFS task wakeup CPU selection follows the capacity fitness criterion described357above. On top of that, uclamp is used to clamp the task utilization values,358which lets userspace have more leverage over the CPU selection of CFS359tasks. IOW, CFS wakeup CPU selection searches for a CPU that satisfies::360 361 clamp(task_util(p), task_uclamp_min(p), task_uclamp_max(p)) < capacity(cpu)362 363By using uclamp, userspace can e.g. allow a busy loop (100% utilization) to run364on any CPU by giving it a low uclamp.max value. Conversely, it can force a small365periodic task (e.g. 10% utilization) to run on the highest-performance CPUs by366giving it a high uclamp.min value.367 368.. note::369 370 Wakeup CPU selection in CFS can be eclipsed by Energy Aware Scheduling371 (EAS), which is described in Documentation/scheduler/sched-energy.rst.372 3735.1.3 Load balancing374~~~~~~~~~~~~~~~~~~~~375 376A pathological case in the wakeup CPU selection occurs when a task rarely377sleeps, if at all - it thus rarely wakes up, if at all. Consider::378 379 w == wakeup event380 381 capacity(CPU0) = C382 capacity(CPU1) = C / 3383 384 workload on CPU0385 CPU work ^386 | _________ _________ ____387 | | | | | |388 +----+----+----+----+----+----+----+----+----+----+-> time389 w w w390 391 workload on CPU1392 CPU work ^393 | ____________________________________________394 | |395 +----+----+----+----+----+----+----+----+----+----+->396 w397 398This workload should run on CPU0, but if the task either:399 400- was improperly scheduled from the start (inaccurate initial401 utilization estimation)402- was properly scheduled from the start, but suddenly needs more403 processing power404 405then it might become CPU-bound, IOW ``task_util(p) > capacity(task_cpu(p))``;406the CPU capacity scheduling criterion is violated, and there may not be any more407wakeup event to fix this up via wakeup CPU selection.408 409Tasks that are in this situation are dubbed "misfit" tasks, and the mechanism410put in place to handle this shares the same name. Misfit task migration411leverages the CFS load balancer, more specifically the active load balance part412(which caters to migrating currently running tasks). When load balance happens,413a misfit active load balance will be triggered if a misfit task can be migrated414to a CPU with more capacity than its current one.415 4165.2 RT417------418 4195.2.1 Wakeup CPU selection420~~~~~~~~~~~~~~~~~~~~~~~~~~421 422RT task wakeup CPU selection searches for a CPU that satisfies::423 424 task_uclamp_min(p) <= capacity(task_cpu(cpu))425 426while still following the usual priority constraints. If none of the candidate427CPUs can satisfy this capacity criterion, then strict priority based scheduling428is followed and CPU capacities are ignored.429 4305.3 DL431------432 4335.3.1 Wakeup CPU selection434~~~~~~~~~~~~~~~~~~~~~~~~~~435 436DL task wakeup CPU selection searches for a CPU that satisfies::437 438 task_bandwidth(p) < capacity(task_cpu(p))439 440while still respecting the usual bandwidth and deadline constraints. If441none of the candidate CPUs can satisfy this capacity criterion, then the442task will remain on its current CPU.443