Documentation/scheduler/sched-capacity.rst

2 Capacity Aware Scheduling
5 1. CPU Capacity
9 ----------------
13 different performance characteristics - on such platforms, not all CPUs can be
16 CPU capacity is a measure of the performance a CPU can reach, normalized against
18 asymmetric CPU capacity systems, as they contain CPUs of different capacities.
20 Disparity in maximum attainable performance (IOW in maximum CPU capacity) stems
23 - not all CPUs may have the same microarchitecture (µarch).
24 - with Dynamic Voltage and Frequency Scaling (DVFS), not all CPUs may be
28 performance-oriented than the LITTLE ones (more pipeline stages, bigger caches,
36   capacity(cpu) = work_per_hz(cpu) * max_freq(cpu)
39 -------------------
41 Two different capacity values are used within the scheduler. A CPU's
42 ``capacity_orig`` is its maximum attainable capacity, i.e. its maximum
43 attainable performance level. A CPU's ``capacity`` is its ``capacity_orig`` to
47 Note that a CPU's ``capacity`` is solely intended to be used by the CFS class,
48 while ``capacity_orig`` is class-agnostic. The rest of this document will use
49 the term ``capacity`` interchangeably with ``capacity_orig`` for the sake of
53 ---------------------
58 Consider an hypothetical dual-core asymmetric CPU capacity system where
60 - work_per_hz(CPU0) = W
61 - work_per_hz(CPU1) = W/2
62 - all CPUs are running at the same fixed frequency
64 By the above definition of capacity:
66 - capacity(CPU0) = C
67 - capacity(CPU1) = C/2
78            +----+----+----+----+----+----+----+----+----+----+-> time
83            +----+----+----+----+----+----+----+----+----+----+-> time
85 CPU0 has the highest capacity in the system (C), and completes a fixed amount of
86 work W in T units of time. On the other hand, CPU1 has half the capacity of
92 Usually, CPUs of different capacity values also have different maximum
95 - max_freq(CPU0) = F
96 - max_freq(CPU1) = 2/3 * F
100 - capacity(CPU0) = C
101 - capacity(CPU1) = C/3
109            +----+----+----+----+----+----+----+----+----+----+-> time
115            +----+----+----+----+----+----+----+----+----+----+-> time
118 -------------------------
130 ----------------
132 Capacity aware scheduling requires an expression of a task's requirements with
133 regards to CPU capacity. Each scheduler class can express this differently, and
149 ------------------------
158            +----+----+----+----+----+----+----+----+----+----+-> time
167            +----+----+----+----+----+----+----+----+----+----+-> time
181 ------------------
183 CPU capacity has a similar effect on task utilization in that running an
184 identical workload on CPUs of different capacity values will yield different
189 - capacity(CPU0) = C
190 - capacity(CPU1) = C/3
198            +----+----+----+----+----+----+----+----+----+----+-> time
203            +----+----+----+----+----+----+----+----+----+----+-> time
207 - duty_cycle(p) == 25% if p runs on CPU0 at its maximum frequency
208 - duty_cycle(p) == 75% if p runs on CPU1 at its maximum frequency
213   task_util_cpu_inv(p) = duty_cycle(p) * (capacity(cpu) / max_capacity)
215 with ``max_capacity`` being the highest CPU capacity value in the
220 ------------------------------
223 order to obtain a truly invariant signal. The pseudo-formula for a task
227                                      curr_frequency(cpu)   capacity(cpu)
228   task_util_inv(p) = duty_cycle(p) * ------------------- * -------------
232 if it were running on the highest-capacity CPU in the system, running at its
239 --------------------------
243 maintains a handful of CPU and task signals based on the Per-Entity Load
247 This means that while the capacity aware scheduling criteria will be written
251 3. Capacity aware scheduling requirements
254 3.1 CPU capacity
255 ----------------
257 Linux cannot currently figure out CPU capacity on its own, this information thus
262 CPU scaling data, which is derived from the capacity-dmips-mhz CPU binding; see
263 Documentation/devicetree/bindings/arm/cpu-capacity.txt.
266 ------------------------
268 As stated in 2.2, capacity-aware scheduling requires a frequency-invariant task
276 when the kernel is aware of the switched-to frequency (also employed by
286 - The sched_asym_cpucapacity static key will be enabled.
287 - The SD_ASYM_CPUCAPACITY flag will be set at the lowest sched_domain level that
288   spans all unique CPU capacity values.
291 cater to asymmetric CPU capacity systems. Do note however that said key is
292 *system-wide*. Imagine the following setup using cpusets::
294   capacity    C/2          C
303 .. code-block:: sh
306   echo 0-1 > /sys/fs/cgroup/cpuset/cs0/cpuset.cpus
310   echo 2-7 > /sys/fs/cgroup/cpuset/cs1/cpuset.cpus
315 Since there *is* CPU capacity asymmetry in the system, the
317 hierarchy of CPUs 0-1 spans a single capacity value: SD_ASYM_CPUCAPACITY isn't
323 - Check the sched_asym_cpucapacity static key
324 - If it is enabled, then also check for the presence of SD_ASYM_CPUCAPACITY in
328 5. Capacity aware scheduling implementation
332 -------
334 5.1.1 Capacity fitness
337 The main capacity scheduling criterion of CFS is::
339   task_util(p) < capacity(task_cpu(p))
341 This is commonly called the capacity fitness criterion, i.e. CFS must ensure a
343 work than what its CPU can provide: it will be CPU-bound.
347 Documentation/admin-guide/cgroup-v2.rst). As its name imply, this can be used to
353 CFS task wakeup CPU selection follows the capacity fitness criterion described
358   clamp(task_util(p), task_uclamp_min(p), task_uclamp_max(p)) < capacity(cpu)
362 periodic task (e.g. 10% utilization) to run on the highest-performance CPUs by
368   (EAS), which is described in Documentation/scheduler/sched-energy.rst.
374 sleeps, if at all - it thus rarely wakes up, if at all. Consider::
378   capacity(CPU0) = C
379   capacity(CPU1) = C / 3
385            +----+----+----+----+----+----+----+----+----+----+-> time
392            +----+----+----+----+----+----+----+----+----+----+->
397 - was improperly scheduled from the start (inaccurate initial
399 - was properly scheduled from the start, but suddenly needs more
402 then it might become CPU-bound, IOW ``task_util(p) > capacity(task_cpu(p))``;
403 the CPU capacity scheduling criterion is violated, and there may not be any more
411 to a CPU with more capacity than its current one.
414 ------
421   task_uclamp_min(p) <= capacity(task_cpu(cpu))
424 CPUs can satisfy this capacity criterion, then strict priority based scheduling
428 ------
435   task_bandwidth(p) < capacity(task_cpu(p))
438 none of the candidate CPUs can satisfy this capacity criterion, then the