요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.
1. 요약·해설
원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.
Task utilization과 PELT
sched-capacity.rst:127-251Task utilization은 runnable·running history를 PELT로 감쇠 누적한 값입니다. 현재 CPU에서 관찰한 raw runtime을 그대로 쓰면 frequency가 낮거나 작은 CPU에서 같은 task가 더 오래 실행되어 util이 부풀 수 있습니다.
Frequency invariance는 현재 주파수 대비 최대 주파수 비율을, CPU invariance는 현재 CPU 대비 기준 CPU capacity 비율을 반영해 task work demand를 platform 독립 scale로 만듭니다. 두 보정이 있어야 migration 전후 util을 같은 척도로 비교할 수 있습니다.
최대 주파수 F에서 한 주기 네 칸 중 한 칸만 실행하면 raw duty cycle은 25%입니다. 이 경우 현재 주파수와 최대 주파수가 같으므로 보정 뒤 utilization도 25%입니다.
Task의 알고리즘과 처리한 work는 그대로인데 주파수가 절반이면 실행 시간이 두 배가 되어 raw duty cycle이 50%로 보입니다. 이를 task demand 증가로 해석하면 잘못된 CPU placement와 DVFS feedback이 생깁니다. 현재/최대 주파수 비율을 곱하면 원래 demand 25%로 돌아옵니다.
작은 CPU에서 오래 실행됐다는 사실을 task가 더 무거워졌다고 해석하지 않기 위해 현재 CPU capacity와 기준 max capacity의 비율을 곱합니다. 같은 work라면 migration 전 CPU0에서 측정한 값과 migration 후 CPU1에서 측정한 값이 같은 scale로 수렴해야 합니다.
util_est는 sleep 후 곧 다시 실행될 task의 demand를 PELT가 천천히 따라가는 문제를 줄이기 위해 최근 activation의 utilization estimate를 제공합니다. Fast ramp-up workload placement와 DVFS 결정에 사용됩니다.
Scheduler topology에 capacity를 제공한다
sched-capacity.rst:252-330Architecture는 CPU scale과 frequency invariance source를 scheduler에 제공하고 asymmetric capacity CPU가 같은 sched domain에서 비교되도록 topology flag를 구성합니다. Firmware capacity 정보가 실제 hardware와 맞지 않으면 wakeup placement 전체가 왜곡됩니다.
Capacity 정보는 Energy Aware Scheduling과 같지 않습니다. Capacity fitness는 task가 CPU에 맞는지 판단하고 energy model은 fit 후보 중 예상 energy를 비교합니다.
CFS wakeup과 load balance
sched-capacity.rst:331-415Fair scheduler는 task utilization이 CPU available capacity 안에 드는지 capacity fitness를 계산합니다. Wakeup path는 affinity, cache locality, idle state와 capacity를 함께 고려해 fit CPU를 찾고, periodic balance는 misfit task를 더 큰 CPU로 이동시킵니다.
큰 task를 작은 CPU에 둔 상태를 misfit이라고 하지만 affinity와 cpuset이 큰 CPU를 허용하지 않으면 scheduler가 해결할 수 없습니다. uclamp_min/max도 effective utilization과 fit 판단에 영향을 줍니다.
Wakeup CPU selection은 task가 잠에서 깨어날 때만 다시 선택할 기회를 얻습니다. 작은 CPU에서 task가 CPU-bound가 되면 다음 sleep과 wakeup 자체가 사라질 수 있으므로 잘못된 배치가 계속됩니다. 이때 periodic load balancer가 task_util > capacity 조건을 보고 더 큰 CPU로 active migration해야 합니다.
RT와 deadline task placement
sched-capacity.rst:416-442RT wakeup은 priority와 현재 runqueue 상태에 capacity fitness를 결합해 high-capacity CPU가 필요한 task를 작은 CPU에 고정하지 않도록 합니다. Deadline class도 affinity와 admission 조건 안에서 capacity가 deadline 보장에 충분한 CPU를 선택해야 합니다.
2. 영어 원문 전체
번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.
원문 전체 펼치기
=========================
Capacity Aware Scheduling
=========================
1. CPU Capacity
===============
1.1 Introduction
----------------
Conventional, homogeneous SMP platforms are composed of purely identical
CPUs. Heterogeneous platforms on the other hand are composed of CPUs with
different performance characteristics - on such platforms, not all CPUs can be
considered equal.
CPU capacity is a measure of the performance a CPU can reach, normalized against
the most performant CPU in the system. Heterogeneous systems are also called
asymmetric CPU capacity systems, as they contain CPUs of different capacities.
Disparity in maximum attainable performance (IOW in maximum CPU capacity) stems
from two factors:
- not all CPUs may have the same microarchitecture (µarch).
- with Dynamic Voltage and Frequency Scaling (DVFS), not all CPUs may be
physically able to attain the higher Operating Performance Points (OPP).
Arm big.LITTLE systems are an example of both. The big CPUs are more
performance-oriented than the LITTLE ones (more pipeline stages, bigger caches,
smarter predictors, etc), and can usually reach higher OPPs than the LITTLE ones
can.
CPU performance is usually expressed in Millions of Instructions Per Second
(MIPS), which can also be expressed as a given amount of instructions attainable
per Hz, leading to::
capacity(cpu) = work_per_hz(cpu) * max_freq(cpu)
1.2 Scheduler terms
-------------------
Two different capacity values are used within the scheduler. A CPU's
``original capacity`` is its maximum attainable capacity, i.e. its maximum
attainable performance level. This original capacity is returned by
the function arch_scale_cpu_capacity(). A CPU's ``capacity`` is its ``original
capacity`` to which some loss of available performance (e.g. time spent
handling IRQs) is subtracted.
Note that a CPU's ``capacity`` is solely intended to be used by the CFS class,
while ``original capacity`` is class-agnostic. The rest of this document will use
the term ``capacity`` interchangeably with ``original capacity`` for the sake of
brevity.
1.3 Platform examples
---------------------
1.3.1 Identical OPPs
~~~~~~~~~~~~~~~~~~~~
Consider an hypothetical dual-core asymmetric CPU capacity system where
- work_per_hz(CPU0) = W
- work_per_hz(CPU1) = W/2
- all CPUs are running at the same fixed frequency
By the above definition of capacity:
- capacity(CPU0) = C
- capacity(CPU1) = C/2
To draw the parallel with Arm big.LITTLE, CPU0 would be a big while CPU1 would
be a LITTLE.
With a workload that periodically does a fixed amount of work, you will get an
execution trace like so::
CPU0 work ^
| ____ ____ ____
| | | | | | |
+----+----+----+----+----+----+----+----+----+----+-> time
CPU1 work ^
| _________ _________ ____
| | | | | |
+----+----+----+----+----+----+----+----+----+----+-> time
CPU0 has the highest capacity in the system (C), and completes a fixed amount of
work W in T units of time. On the other hand, CPU1 has half the capacity of
CPU0, and thus only completes W/2 in T.
1.3.2 Different max OPPs
~~~~~~~~~~~~~~~~~~~~~~~~
Usually, CPUs of different capacity values also have different maximum
OPPs. Consider the same CPUs as above (i.e. same work_per_hz()) with:
- max_freq(CPU0) = F
- max_freq(CPU1) = 2/3 * F
This yields:
- capacity(CPU0) = C
- capacity(CPU1) = C/3
Executing the same workload as described in 1.3.1, which each CPU running at its
maximum frequency results in::
CPU0 work ^
| ____ ____ ____
| | | | | | |
+----+----+----+----+----+----+----+----+----+----+-> time
workload on CPU1
CPU1 work ^
| ______________ ______________ ____
| | | | | |
+----+----+----+----+----+----+----+----+----+----+-> time
1.4 Representation caveat
-------------------------
It should be noted that having a *single* value to represent differences in CPU
performance is somewhat of a contentious point. The relative performance
difference between two different µarchs could be X% on integer operations, Y% on
floating point operations, Z% on branches, and so on. Still, results using this
simple approach have been satisfactory for now.
2. Task utilization
===================
2.1 Introduction
----------------
Capacity aware scheduling requires an expression of a task's requirements with
regards to CPU capacity. Each scheduler class can express this differently, and
while task utilization is specific to CFS, it is convenient to describe it here
in order to introduce more generic concepts.
Task utilization is a percentage meant to represent the throughput requirements
of a task. A simple approximation of it is the task's duty cycle, i.e.::
task_util(p) = duty_cycle(p)
On an SMP system with fixed frequencies, 100% utilization suggests the task is a
busy loop. Conversely, 10% utilization hints it is a small periodic task that
spends more time sleeping than executing. Variable CPU frequencies and
asymmetric CPU capacities complexify this somewhat; the following sections will
expand on these.
2.2 Frequency invariance
------------------------
One issue that needs to be taken into account is that a workload's duty cycle is
directly impacted by the current OPP the CPU is running at. Consider running a
periodic workload at a given frequency F::
CPU work ^
| ____ ____ ____
| | | | | | |
+----+----+----+----+----+----+----+----+----+----+-> time
This yields duty_cycle(p) == 25%.
Now, consider running the *same* workload at frequency F/2::
CPU work ^
| _________ _________ ____
| | | | | |
+----+----+----+----+----+----+----+----+----+----+-> time
This yields duty_cycle(p) == 50%, despite the task having the exact same
behaviour (i.e. executing the same amount of work) in both executions.
The task utilization signal can be made frequency invariant using the following
formula::
task_util_freq_inv(p) = duty_cycle(p) * (curr_frequency(cpu) / max_frequency(cpu))
Applying this formula to the two examples above yields a frequency invariant
task utilization of 25%.
2.3 CPU invariance
------------------
CPU capacity has a similar effect on task utilization in that running an
identical workload on CPUs of different capacity values will yield different
duty cycles.
Consider the system described in 1.3.2., i.e.::
- capacity(CPU0) = C
- capacity(CPU1) = C/3
Executing a given periodic workload on each CPU at their maximum frequency would
result in::
CPU0 work ^
| ____ ____ ____
| | | | | | |
+----+----+----+----+----+----+----+----+----+----+-> time
CPU1 work ^
| ______________ ______________ ____
| | | | | |
+----+----+----+----+----+----+----+----+----+----+-> time
IOW,
- duty_cycle(p) == 25% if p runs on CPU0 at its maximum frequency
- duty_cycle(p) == 75% if p runs on CPU1 at its maximum frequency
The task utilization signal can be made CPU invariant using the following
formula::
task_util_cpu_inv(p) = duty_cycle(p) * (capacity(cpu) / max_capacity)
with ``max_capacity`` being the highest CPU capacity value in the
system. Applying this formula to the above example above yields a CPU
invariant task utilization of 25%.
2.4 Invariant task utilization
------------------------------
Both frequency and CPU invariance need to be applied to task utilization in
order to obtain a truly invariant signal. The pseudo-formula for a task
utilization that is both CPU and frequency invariant is thus, for a given
task p::
curr_frequency(cpu) capacity(cpu)
task_util_inv(p) = duty_cycle(p) * ------------------- * -------------
max_frequency(cpu) max_capacity
In other words, invariant task utilization describes the behaviour of a task as
if it were running on the highest-capacity CPU in the system, running at its
maximum frequency.
Any mention of task utilization in the following sections will imply its
invariant form.
2.5 Utilization estimation
--------------------------
Without a crystal ball, task behaviour (and thus task utilization) cannot
accurately be predicted the moment a task first becomes runnable. The CFS class
maintains a handful of CPU and task signals based on the Per-Entity Load
Tracking (PELT) mechanism, one of those yielding an *average* utilization (as
opposed to instantaneous).
This means that while the capacity aware scheduling criteria will be written
considering a "true" task utilization (using a crystal ball), the implementation
will only ever be able to use an estimator thereof.
3. Capacity aware scheduling requirements
=========================================
3.1 CPU capacity
----------------
Linux cannot currently figure out CPU capacity on its own, this information thus
needs to be handed to it. Architectures must define arch_scale_cpu_capacity()
for that purpose.
The arm, arm64, and RISC-V architectures directly map this to the arch_topology driver
CPU scaling data, which is derived from the capacity-dmips-mhz CPU binding; see
Documentation/devicetree/bindings/cpu/cpu-capacity.txt.
3.2 Frequency invariance
------------------------
As stated in 2.2, capacity-aware scheduling requires a frequency-invariant task
utilization. Architectures must define arch_scale_freq_capacity(cpu) for that
purpose.
Implementing this function requires figuring out at which frequency each CPU
have been running at. One way to implement this is to leverage hardware counters
whose increment rate scale with a CPU's current frequency (APERF/MPERF on x86,
AMU on arm64). Another is to directly hook into cpufreq frequency transitions,
when the kernel is aware of the switched-to frequency (also employed by
arm/arm64).
4. Scheduler topology
=====================
During the construction of the sched domains, the scheduler will figure out
whether the system exhibits asymmetric CPU capacities. Should that be the
case:
- The sched_asym_cpucapacity static key will be enabled.
- The SD_ASYM_CPUCAPACITY_FULL flag will be set at the lowest sched_domain
level that spans all unique CPU capacity values.
- The SD_ASYM_CPUCAPACITY flag will be set for any sched_domain that spans
CPUs with any range of asymmetry.
The sched_asym_cpucapacity static key is intended to guard sections of code that
cater to asymmetric CPU capacity systems. Do note however that said key is
*system-wide*. Imagine the following setup using cpusets::
capacity C/2 C
________ ________
/ \ / \
CPUs 0 1 2 3 4 5 6 7
\__/ \______________/
cpusets cs0 cs1
Which could be created via:
.. code-block:: sh
mkdir /sys/fs/cgroup/cpuset/cs0
echo 0-1 > /sys/fs/cgroup/cpuset/cs0/cpuset.cpus
echo 0 > /sys/fs/cgroup/cpuset/cs0/cpuset.mems
mkdir /sys/fs/cgroup/cpuset/cs1
echo 2-7 > /sys/fs/cgroup/cpuset/cs1/cpuset.cpus
echo 0 > /sys/fs/cgroup/cpuset/cs1/cpuset.mems
echo 0 > /sys/fs/cgroup/cpuset/cpuset.sched_load_balance
Since there *is* CPU capacity asymmetry in the system, the
sched_asym_cpucapacity static key will be enabled. However, the sched_domain
hierarchy of CPUs 0-1 spans a single capacity value: SD_ASYM_CPUCAPACITY isn't
set in that hierarchy, it describes an SMP island and should be treated as such.
Therefore, the 'canonical' pattern for protecting codepaths that cater to
asymmetric CPU capacities is to:
- Check the sched_asym_cpucapacity static key
- If it is enabled, then also check for the presence of SD_ASYM_CPUCAPACITY in
the sched_domain hierarchy (if relevant, i.e. the codepath targets a specific
CPU or group thereof)
5. Capacity aware scheduling implementation
===========================================
5.1 CFS
-------
5.1.1 Capacity fitness
~~~~~~~~~~~~~~~~~~~~~~
The main capacity scheduling criterion of CFS is::
task_util(p) < capacity(task_cpu(p))
This is commonly called the capacity fitness criterion, i.e. CFS must ensure a
task "fits" on its CPU. If it is violated, the task will need to achieve more
work than what its CPU can provide: it will be CPU-bound.
Furthermore, uclamp lets userspace specify a minimum and a maximum utilization
value for a task, either via sched_setattr() or via the cgroup interface (see
Documentation/admin-guide/cgroup-v2.rst). As its name imply, this can be used to
clamp task_util() in the previous criterion.
5.1.2 Wakeup CPU selection
~~~~~~~~~~~~~~~~~~~~~~~~~~
CFS task wakeup CPU selection follows the capacity fitness criterion described
above. On top of that, uclamp is used to clamp the task utilization values,
which lets userspace have more leverage over the CPU selection of CFS
tasks. IOW, CFS wakeup CPU selection searches for a CPU that satisfies::
clamp(task_util(p), task_uclamp_min(p), task_uclamp_max(p)) < capacity(cpu)
By using uclamp, userspace can e.g. allow a busy loop (100% utilization) to run
on any CPU by giving it a low uclamp.max value. Conversely, it can force a small
periodic task (e.g. 10% utilization) to run on the highest-performance CPUs by
giving it a high uclamp.min value.
.. note::
Wakeup CPU selection in CFS can be eclipsed by Energy Aware Scheduling
(EAS), which is described in Documentation/scheduler/sched-energy.rst.
5.1.3 Load balancing
~~~~~~~~~~~~~~~~~~~~
A pathological case in the wakeup CPU selection occurs when a task rarely
sleeps, if at all - it thus rarely wakes up, if at all. Consider::
w == wakeup event
capacity(CPU0) = C
capacity(CPU1) = C / 3
workload on CPU0
CPU work ^
| _________ _________ ____
| | | | | |
+----+----+----+----+----+----+----+----+----+----+-> time
w w w
workload on CPU1
CPU work ^
| ____________________________________________
| |
+----+----+----+----+----+----+----+----+----+----+->
w
This workload should run on CPU0, but if the task either:
- was improperly scheduled from the start (inaccurate initial
utilization estimation)
- was properly scheduled from the start, but suddenly needs more
processing power
then it might become CPU-bound, IOW ``task_util(p) > capacity(task_cpu(p))``;
the CPU capacity scheduling criterion is violated, and there may not be any more
wakeup event to fix this up via wakeup CPU selection.
Tasks that are in this situation are dubbed "misfit" tasks, and the mechanism
put in place to handle this shares the same name. Misfit task migration
leverages the CFS load balancer, more specifically the active load balance part
(which caters to migrating currently running tasks). When load balance happens,
a misfit active load balance will be triggered if a misfit task can be migrated
to a CPU with more capacity than its current one.
5.2 RT
------
5.2.1 Wakeup CPU selection
~~~~~~~~~~~~~~~~~~~~~~~~~~
RT task wakeup CPU selection searches for a CPU that satisfies::
task_uclamp_min(p) <= capacity(task_cpu(cpu))
while still following the usual priority constraints. If none of the candidate
CPUs can satisfy this capacity criterion, then strict priority based scheduling
is followed and CPU capacities are ignored.
5.3 DL
------
5.3.1 Wakeup CPU selection
~~~~~~~~~~~~~~~~~~~~~~~~~~
DL task wakeup CPU selection searches for a CPU that satisfies::
task_bandwidth(p) < capacity(task_cpu(p))
while still respecting the usual bandwidth and deadline constraints. If
none of the candidate CPUs can satisfy this capacity criterion, then the
task will remain on its current CPU.
3. 한국어 전문 번역
영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.
CPU capacity의 정의
1-37전통적인 homogeneous SMP platform은 성능 특성이 완전히 동일한 CPU로 구성된다. 반면 heterogeneous platform에는 서로 다른 성능 특성을 가진 CPU가 들어 있으므로 모든 CPU를 동등하게 취급할 수 없다.
CPU capacity는 한 CPU가 도달할 수 있는 performance를 system에서 가장 빠른 CPU에 대해 normalize한 값이다. 서로 다른 capacity의 CPU를 포함한 heterogeneous system을 asymmetric CPU capacity system이라고도 부른다.
최대로 달성 가능한 performance, 즉 maximum CPU capacity가 달라지는 원인은 두 가지다. 첫째, 모든 CPU가 같은 microarchitecture(µarch)를 사용하지 않을 수 있다. 둘째, Dynamic Voltage and Frequency Scaling(DVFS)을 사용하더라도 모든 CPU가 물리적으로 가장 높은 Operating Performance Point(OPP)에 도달할 수 있는 것은 아니다.
Arm big.LITTLE system은 두 원인이 함께 나타나는 예다. Big CPU는 LITTLE CPU보다 pipeline stage가 많고 cache가 크며 predictor가 정교한 등 performance 중심으로 설계되어 있고, 일반적으로 LITTLE CPU가 도달할 수 있는 것보다 높은 OPP까지 올라간다.
CPU performance는 보통 Millions of Instructions Per Second(MIPS)로 표현한다. 이를 Hz당 처리할 수 있는 instruction 양과 maximum frequency의 곱으로 쓰면 다음 관계가 된다.
capacity(cpu) = work_per_hz(cpu) * max_freq(cpu)Scheduler가 구분하는 original capacity와 capacity
38-51Scheduler 내부에서는 서로 다른 두 capacity 값을 사용한다. CPU의 original capacity는 그 CPU가 달성할 수 있는 최대 capacity, 즉 최대 performance level이다. arch_scale_cpu_capacity()가 이 값을 반환한다.
CPU의 capacity는 original capacity에서 현재 사용할 수 없는 performance를 뺀 값이다. 예를 들어 IRQ 처리에 소비한 시간은 task 실행에 사용할 수 없으므로 available capacity를 감소시킨다.
| 용어 | 의미 | 사용 범위 |
|---|---|---|
| original capacity | CPU가 최대로 달성 가능한 normalized performance | scheduler class에 독립적 |
| capacity | original capacity에서 IRQ 등 현재 performance 손실을 뺀 값 | CFS class 전용 |
이 문서의 나머지 부분은 간결하게 쓰기 위해 capacity라는 말로 original capacity까지 함께 가리킨다.
동일 OPP와 서로 다른 maximum OPP 예제
53-117동일한 OPP에서 microarchitecture만 다른 경우
가상의 dual-core asymmetric system에서 CPU0의 work_per_hz를 W, CPU1의 값을 W/2라고 하고 두 CPU가 같은 fixed frequency로 실행된다고 하자. 정의에 따라 capacity(CPU0)=C, capacity(CPU1)=C/2가 된다. Arm big.LITTLE에 대응시키면 CPU0가 big, CPU1이 LITTLE이다.
동일한 양의 periodic work는 CPU0에서 한 시간 칸, CPU1에서 두 시간 칸을 차지한다. CPU1은 T 동안 CPU0 작업량의 절반만 처리한다.
CPU0는 system에서 가장 높은 capacity C를 가지며 T 시간 동안 고정된 작업량 W를 끝낸다. CPU1의 capacity는 절반이므로 같은 T 동안 W/2만 끝낼 수 있다.
Maximum OPP까지 다른 경우
실제 system에서는 capacity가 다른 CPU가 서로 다른 maximum OPP를 갖는 경우가 많다. 앞의 work_per_hz 관계를 그대로 두고 max_freq(CPU0)=F, max_freq(CPU1)=2/3×F라고 하자. 그러면 capacity(CPU0)=C, capacity(CPU1)=C/3이 된다.
각 CPU를 자신의 maximum frequency로 구동해도 CPU1은 microarchitecture와 maximum OPP의 차이가 겹쳐 같은 workload를 처리하는 시간이 CPU0의 세 배가 된다.
하나의 scalar로 performance를 나타낼 때의 한계
118-125CPU performance 차이를 하나의 값으로 표현하는 방식에는 논쟁의 여지가 있다. 서로 다른 두 microarchitecture의 상대 성능 차이는 integer operation에서 X%, floating-point operation에서 Y%, branch에서 Z%처럼 workload 특성마다 달라질 수 있다. 그럼에도 현재까지는 이 단순한 접근으로 얻은 결과가 만족스러웠다.
Task utilization과 duty cycle
127-147Capacity-aware scheduling을 하려면 task가 요구하는 CPU capacity를 수치로 표현해야 한다. Scheduler class마다 다른 방식으로 표현할 수 있으며 task utilization은 CFS에 고유한 개념이지만, 더 일반적인 개념을 소개하기 편리하므로 여기에서 설명한다.
Task utilization은 task가 요구하는 throughput을 나타내는 percentage다. 간단하게는 task의 duty cycle, 즉 전체 관찰 시간 중 실제 실행한 시간의 비율로 근사할 수 있다.
task_util(p) = duty_cycle(p)Fixed frequency SMP system에서 utilization 100%는 task가 busy loop일 가능성을 나타낸다. 반대로 10%는 실행 시간보다 sleep 시간이 긴 작은 periodic task임을 시사한다. CPU frequency가 바뀌거나 CPU capacity가 비대칭이면 이 해석이 더 복잡해진다.
Frequency invariant utilization
149-179Workload의 raw duty cycle은 CPU가 현재 실행 중인 OPP의 영향을 직접 받는다. Frequency F에서 일정한 periodic workload를 실행해 duty cycle이 25%라고 하자.
한 period를 네 칸으로 보았을 때 한 칸 실행하고 세 칸 쉬므로 raw duty cycle은 25%다.
동일한 task가 정확히 같은 양의 일을 하더라도 frequency를 F/2로 내리면 작업을 끝내는 데 두 배 시간이 걸려 duty cycle은 50%가 된다.
Task의 논리적 동작은 같지만 CPU 속도가 절반이므로 각 period에서 실행 시간이 두 칸으로 늘어난다. Raw duty cycle만 보면 workload 요구량이 커진 것처럼 보인다.
Current frequency와 maximum frequency의 비율을 곱하면 task utilization을 frequency invariant하게 만들 수 있다.
task_util_freq_inv(p) = duty_cycle(p) *
(curr_frequency(cpu) / max_frequency(cpu))첫 번째 예제는 25%×F/F=25%이고 두 번째는 50%×(F/2)/F=25%다. Frequency가 달라도 같은 workload 요구량은 동일한 25% utilization으로 표현된다.
CPU invariant utilization
181-218CPU capacity 차이도 utilization에 같은 문제를 만든다. 동일한 workload를 capacity가 다른 CPU에서 실행하면 서로 다른 duty cycle이 관찰된다. 앞의 system처럼 capacity(CPU0)=C, capacity(CPU1)=C/3이고 각 CPU를 maximum frequency에서 실행한다고 하자.
같은 periodic workload가 CPU0에서는 period의 25%, CPU1에서는 75%를 점유한다. Task가 요구하는 실제 처리량은 같고 CPU의 처리 능력만 다르다.
Task utilization에 해당 CPU capacity와 system maximum capacity의 비율을 곱하면 CPU invariant signal을 얻을 수 있다.
task_util_cpu_inv(p) = duty_cycle(p) *
(capacity(cpu) / max_capacity)max_capacity는 system에서 가장 높은 CPU capacity다. CPU0에서는 25%×C/C=25%, CPU1에서는 75%×(C/3)/C=25%가 되어 동일 workload가 같은 값으로 normalize된다.
완전한 invariant signal과 PELT estimator
220-250진정한 invariant task utilization을 얻으려면 frequency invariance와 CPU invariance를 모두 적용해야 한다. Task p에 대한 pseudo-formula는 다음과 같다.
curr_frequency(cpu) capacity(cpu)
task_util_inv(p) = duty_cycle(p) * ------------------- * -------------
max_frequency(cpu) max_capacityInvariant task utilization은 해당 task가 system에서 capacity가 가장 큰 CPU 위에서 maximum frequency로 실행되었다고 가정했을 때의 동작을 표현한다. 이후 절에서 별도 수식어 없이 task utilization이라고 하면 이 invariant form을 뜻한다.
Task가 처음 runnable이 되는 순간에는 미래 동작을 알 수 없으므로 utilization을 정확히 예측할 수 없다. CFS는 Per-Entity Load Tracking(PELT)을 기반으로 여러 CPU·task signal을 유지하며, 그중 하나가 instantaneous 값이 아닌 average utilization을 제공한다.
따라서 capacity-aware scheduling 기준은 미래를 안다고 가정한 true task utilization으로 설명할 수 있지만, 실제 구현은 언제나 그 값의 estimator만 사용할 수 있다. 초기 estimate 오류가 뒤의 misfit migration이 필요한 이유가 된다.
Architecture가 제공해야 하는 capacity와 frequency scale
252-278현재 Linux는 CPU capacity를 스스로 알아낼 수 없으므로 platform이 정보를 제공해야 한다. 이를 위해 architecture는 arch_scale_cpu_capacity()를 정의해야 한다.
arm, arm64, RISC-V architecture는 이 값을 arch_topology driver의 CPU scaling data에 직접 연결한다. Scaling data는 capacity-dmips-mhz CPU binding에서 유도되며 관련 binding은 Documentation/devicetree/bindings/cpu/cpu-capacity.txt에 있다.
Capacity-aware scheduling에는 frequency-invariant task utilization도 필요하므로 architecture는 arch_scale_freq_capacity(cpu)를 정의해야 한다. 이 함수를 구현하려면 각 CPU가 실제로 어떤 frequency에서 실행되었는지 알아내야 한다.
- Current frequency에 비례하는 속도로 증가하는 hardware counter를 사용한다. x86의 APERF/MPERF와 arm64의 AMU가 예다.
- Kernel이 전환된 frequency를 알고 있는 cpufreq frequency transition 경로에 직접 hook한다. arm과 arm64도 이 방식을 사용한다.
Scheduler topology와 asymmetric capacity flag
280-330Sched domain을 구성할 때 scheduler는 system에 asymmetric CPU capacity가 있는지 판별한다. 비대칭이 발견되면 다음 state를 설정한다.
- sched_asym_cpucapacity static key를 enable한다.
- 모든 고유 CPU capacity 값을 포함하는 가장 낮은 sched_domain level에 SD_ASYM_CPUCAPACITY_FULL flag를 설정한다.
- 어떤 범위든 capacity asymmetry가 있는 CPU들을 포함하는 sched_domain마다 SD_ASYM_CPUCAPACITY flag를 설정한다.
sched_asym_cpucapacity static key는 asymmetric CPU capacity system 전용 code path를 보호한다. 다만 이 key는 system-wide다. 다음 cpuset 구성을 생각해 보자.
| CPU | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| capacity | C/2 | C/2 | C/2 | C/2 | C | C | C | C |
| cpuset | cs0 | cs0 | cs1 | cs1 | cs1 | cs1 | cs1 | cs1 |
mkdir /sys/fs/cgroup/cpuset/cs0
echo 0-1 > /sys/fs/cgroup/cpuset/cs0/cpuset.cpus
echo 0 > /sys/fs/cgroup/cpuset/cs0/cpuset.mems
mkdir /sys/fs/cgroup/cpuset/cs1
echo 2-7 > /sys/fs/cgroup/cpuset/cs1/cpuset.cpus
echo 0 > /sys/fs/cgroup/cpuset/cs1/cpuset.mems
echo 0 > /sys/fs/cgroup/cpuset/cpuset.sched_load_balanceSystem 전체에는 C/2와 C가 함께 있으므로 sched_asym_cpucapacity static key가 enable된다. 하지만 CPU 0-1의 sched_domain hierarchy는 C/2라는 단일 capacity 값만 포함하므로 SD_ASYM_CPUCAPACITY가 설정되지 않는다. 이 영역은 SMP island이며 그렇게 취급해야 한다.
따라서 asymmetric capacity 전용 code path를 보호하는 표준 pattern은 먼저 system-wide sched_asym_cpucapacity static key를 검사하고, key가 enable된 경우 특정 CPU나 group을 대상으로 하는 경로라면 해당 sched_domain hierarchy에 SD_ASYM_CPUCAPACITY가 실제로 있는지도 함께 검사하는 것이다.
CFS capacity fitness와 uclamp
331-371CFS의 핵심 capacity scheduling 기준은 task utilization이 현재 CPU capacity보다 작은지 확인하는 것이다.
task_util(p) < capacity(task_cpu(p))이를 capacity fitness criterion이라고 한다. CFS는 task가 자신의 CPU에 fit하도록 보장해야 한다. 조건을 위반하면 task가 CPU가 제공할 수 있는 것보다 많은 work를 요구하므로 CPU-bound 상태가 된다.
Uclamp를 사용하면 user space가 sched_setattr() 또는 cgroup interface를 통해 task의 minimum·maximum utilization 값을 지정할 수 있다. 자세한 cgroup interface는 Documentation/admin-guide/cgroup-v2.rst에 있다. 이름 그대로 uclamp는 앞의 기준에 들어가는 task_util()을 제한한다.
CFS wakeup CPU selection은 capacity fitness를 따르고 uclamp로 task utilization을 clamp한다. 따라서 후보 CPU는 다음 조건을 만족해야 한다.
clamp(task_util(p), task_uclamp_min(p), task_uclamp_max(p))
< capacity(cpu)User space는 100% utilization의 busy loop에 낮은 uclamp.max를 주어 어떤 CPU에서도 실행할 수 있게 할 수 있다. 반대로 utilization 10%의 작은 periodic task에 높은 uclamp.min을 주어 가장 빠른 CPU에서 실행되도록 유도할 수 있다.
CFS의 wakeup CPU selection은 Energy Aware Scheduling(EAS)의 선택에 의해 가려질 수 있다. EAS는 Documentation/scheduler/sched-energy.rst에서 설명한다.
Wakeup이 드문 task와 misfit migration
373-415Task가 거의 또는 전혀 sleep하지 않으면 wakeup CPU selection에 병적인 사각지대가 생긴다. Wakeup event 자체가 거의 없기 때문이다. Capacity(CPU0)=C, capacity(CPU1)=C/3인 system에서 CPU0라면 periodic하게 sleep할 workload가 CPU1에서는 끝없이 실행되는 상황을 생각할 수 있다.
CPU0에서는 작업을 끝내고 sleep한 뒤 다음 wakeup마다 배치 기회가 생긴다. CPU1에서는 capacity가 부족해 첫 wakeup 뒤 계속 runnable 상태로 남으므로 wakeup CPU selection이 잘못된 배치를 고칠 기회가 없다.
이 workload는 CPU0에서 실행해야 한다. 그러나 initial utilization estimate가 부정확해 처음부터 잘못 배치되었거나, 처음에는 올바르게 배치되었지만 갑자기 더 많은 processing power가 필요해지면 CPU-bound가 될 수 있다. 이때 task_util(p)>capacity(task_cpu(p))가 되어 capacity criterion을 위반하지만, 추가 wakeup이 없어 wakeup CPU selection으로 바로잡지 못할 수 있다.
이 상태의 task를 misfit task라고 하며 이를 처리하는 mechanism도 misfit task migration이라고 부른다. Misfit migration은 CFS load balancer, 그중에서도 현재 실행 중인 task를 이동시키는 active load balance를 이용한다. Load balance 시점에 misfit task를 현재 CPU보다 capacity가 큰 CPU로 옮길 수 있다면 misfit active load balance를 trigger한다.
RT와 DL class의 capacity 기준
416-442RT wakeup CPU selection
RT task의 wakeup CPU selection은 기존 priority constraint를 지키면서 다음 capacity 조건을 만족하는 CPU를 찾는다.
task_uclamp_min(p) <= capacity(task_cpu(cpu))후보 CPU 중 어느 것도 capacity 기준을 만족하지 못하면 CPU capacity를 무시하고 strict priority 기반 scheduling을 따른다.
DL wakeup CPU selection
DL task의 wakeup CPU selection은 기존 bandwidth와 deadline constraint를 지키면서 다음 조건을 만족하는 CPU를 찾는다.
task_bandwidth(p) < capacity(task_cpu(p))후보 CPU 중 capacity 기준을 만족하는 CPU가 하나도 없다면 DL task는 현재 CPU에 그대로 남는다.
CPU capacity는 단위 시간당 처리 능력
sched-capacity.rst:5-126CPU capacity는 동일한 시간 동안 CPU가 수행할 수 있는 work의 상대량입니다. Microarchitecture가 다르거나 최대 OPP가 다르면 같은 utilization task도 CPU마다 completion time과 energy가 달라집니다.
Scheduler는 최고 capacity CPU를 SCHED_CAPACITY_SCALE 기준으로 정규화하고 작은 CPU를 비율로 표현합니다. 값은 절대 instruction 수가 아니라 scheduler placement에 쓰는 상대 척도이며 thermal pressure와 frequency state로 available capacity가 줄 수 있습니다.
두 CPU가 같은 clock으로 동작해도 CPU1이 cycle당 절반의 work만 처리하면 같은 W를 끝내는 데 두 배의 시간이 필요합니다. Scheduler capacity는 이 차이를 C와 C/2 같은 상대값으로 표현합니다. Utilization이 같다는 사실만으로 두 CPU에서 completion time이 같다고 볼 수 없는 이유입니다.
CPU1은 cycle당 work가 절반인 데다 최고 주파수도 CPU0의 2/3이므로 최대 처리량은 1/3입니다. Capacity 값에는 microarchitecture와 maximum OPP의 효과가 함께 들어갑니다. 현재 frequency 저하는 별도의 frequency invariance와 available-capacity 계산에서 반영합니다.