요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.
1. 요약·해설
원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.
Frequency와 CPU invariance
schedutil.rst:45-92같은 wall time을 실행해도 낮은 주파수 CPU가 처리한 실제 일은 적습니다. frequency invariance는 현재 주파수 대비 최대 성능으로 실행 기여도를 보정하고, CPU invariance는 서로 다른 micro-architecture의 최대 capacity 차이를 보정합니다.
UTIL_EST와 UCLAMP
schedutil.rst:93-119UTIL_EST는 sleep 뒤 다시 깨어난 task의 utilization이 PELT로 천천히 올라가는 문제를 줄이기 위해 최근 실행 구간의 추정치를 제공합니다. 그 결과에 uclamp_min/max를 적용해 정책상 최소·최대 성능 범위를 반영합니다.
Scheduler event에서 DVFS 요청까지
schedutil.rst:120-173scheduler가 갱신한 utilization을 governor가 capacity 대비 비율로 바꾸고 rate limit을 거쳐 cpufreq driver에 목표 주파수를 전달합니다.
schedutil은 enqueue, dequeue, tick과 migration 등 scheduler utilization이 바뀌는 지점에서 update hook을 받습니다. fast-switch를 지원하면 scheduler context에서 빠르게 주파수를 바꾸고, 그렇지 않으면 irq_work와 kthread 경로로 느린 driver 호출을 넘깁니다.
관찰할 때는 governor 계산값만 보지 말고 policy가 묶는 CPU 집합, transition latency, up/down rate limit과 thermal cooling 상태를 함께 확인해야 합니다. 목표값과 실제 clock 사이의 차이는 scheduler가 아니라 cpufreq driver 또는 firmware 제약에서 생길 수 있습니다.
2. 영어 원문 전체
번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.
원문 전체 펼치기
=========
Schedutil
=========
.. note::
All this assumes a linear relation between frequency and work capacity,
we know this is flawed, but it is the best workable approximation.
PELT (Per Entity Load Tracking)
===============================
With PELT we track some metrics across the various scheduler entities, from
individual tasks to task-group slices to CPU runqueues. As the basis for this
we use an Exponentially Weighted Moving Average (EWMA), each period (1024us)
is decayed such that y^32 = 0.5. That is, the most recent 32ms contribute
half, while the rest of history contribute the other half.
Specifically:
ewma_sum(u) := u_0 + u_1*y + u_2*y^2 + ...
ewma(u) = ewma_sum(u) / ewma_sum(1)
Since this is essentially a progression of an infinite geometric series, the
results are composable, that is ewma(A) + ewma(B) = ewma(A+B). This property
is key, since it gives the ability to recompose the averages when tasks move
around.
Note that blocked tasks still contribute to the aggregates (task-group slices
and CPU runqueues), which reflects their expected contribution when they
resume running.
Using this we track 2 key metrics: 'running' and 'runnable'. 'Running'
reflects the time an entity spends on the CPU, while 'runnable' reflects the
time an entity spends on the runqueue. When there is only a single task these
two metrics are the same, but once there is contention for the CPU 'running'
will decrease to reflect the fraction of time each task spends on the CPU
while 'runnable' will increase to reflect the amount of contention.
For more detail see: kernel/sched/pelt.c
Frequency / CPU Invariance
==========================
Because consuming the CPU for 50% at 1GHz is not the same as consuming the CPU
for 50% at 2GHz, nor is running 50% on a LITTLE CPU the same as running 50% on
a big CPU, we allow architectures to scale the time delta with two ratios, one
Dynamic Voltage and Frequency Scaling (DVFS) ratio and one microarch ratio.
For simple DVFS architectures (where software is in full control) we trivially
compute the ratio as::
f_cur
r_dvfs := -----
f_max
For more dynamic systems where the hardware is in control of DVFS we use
hardware counters (Intel APERF/MPERF, ARMv8.4-AMU) to provide us this ratio.
For Intel specifically, we use::
APERF
f_cur := ----- * P0
MPERF
4C-turbo; if available and turbo enabled
f_max := { 1C-turbo; if turbo enabled
P0; otherwise
f_cur
r_dvfs := min( 1, ----- )
f_max
We pick 4C turbo over 1C turbo to make it slightly more sustainable.
r_cpu is determined as the ratio of highest performance level of the current
CPU vs the highest performance level of any other CPU in the system.
r_tot = r_dvfs * r_cpu
The result is that the above 'running' and 'runnable' metrics become invariant
of DVFS and CPU type. IOW. we can transfer and compare them between CPUs.
For more detail see:
- kernel/sched/pelt.h:update_rq_clock_pelt()
- arch/x86/kernel/smpboot.c:"APERF/MPERF frequency ratio computation."
- Documentation/scheduler/sched-capacity.rst:"1. CPU Capacity + 2. Task utilization"
UTIL_EST
========
Because periodic tasks have their averages decayed while they sleep, even
though when running their expected utilization will be the same, they suffer a
(DVFS) ramp-up after they are running again.
To alleviate this (a default enabled option) UTIL_EST drives an Infinite
Impulse Response (IIR) EWMA with the 'running' value on dequeue -- when it is
highest. UTIL_EST filters to instantly increase and only decay on decrease.
A further runqueue wide sum (of runnable tasks) is maintained of:
util_est := \Sum_t max( t_running, t_util_est_ewma )
For more detail see: kernel/sched/fair.c:util_est_dequeue()
UCLAMP
======
It is possible to set effective u_min and u_max clamps on each CFS or RT task;
the runqueue keeps an max aggregate of these clamps for all running tasks.
For more detail see: include/uapi/linux/sched/types.h
Schedutil / DVFS
================
Every time the scheduler load tracking is updated (task wakeup, task
migration, time progression) we call out to schedutil to update the hardware
DVFS state.
The basis is the CPU runqueue's 'running' metric, which per the above it is
the frequency invariant utilization estimate of the CPU. From this we compute
a desired frequency like::
max( running, util_est ); if UTIL_EST
u_cfs := { running; otherwise
clamp( u_cfs + u_rt , u_min, u_max ); if UCLAMP_TASK
u_clamp := { u_cfs + u_rt; otherwise
u := u_clamp + u_irq + u_dl; [approx. see source for more detail]
f_des := min( f_max, 1.25 u * f_max )
XXX IO-wait: when the update is due to a task wakeup from IO-completion we
boost 'u' above.
This frequency is then used to select a P-state/OPP or directly munged into a
CPPC style request to the hardware.
XXX: deadline tasks (Sporadic Task Model) allows us to calculate a hard f_min
required to satisfy the workload.
Because these callbacks are directly from the scheduler, the DVFS hardware
interaction should be 'fast' and non-blocking. Schedutil supports
rate-limiting DVFS requests for when hardware interaction is slow and
expensive, this reduces effectiveness.
For more information see: kernel/sched/cpufreq_schedutil.c
NOTES
=====
- On low-load scenarios, where DVFS is most relevant, the 'running' numbers
will closely reflect utilization.
- In saturated scenarios task movement will cause some transient dips,
suppose we have a CPU saturated with 4 tasks, then when we migrate a task
to an idle CPU, the old CPU will have a 'running' value of 0.75 while the
new CPU will gain 0.25. This is inevitable and time progression will
correct this. XXX do we still guarantee f_max due to no idle-time?
- Much of the above is about avoiding DVFS dips, and independent DVFS domains
having to re-learn / ramp-up when load shifts.
3. 한국어 전문 번역
영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.
PELT: Per Entity Load Tracking
1-43이 문서의 설명은 frequency와 CPU가 처리할 수 있는 work capacity가 선형 관계라는 가정에 기반한다. 실제 hardware에서는 정확한 가정이 아니지만 현실적으로 사용할 수 있는 가장 나은 근사다.
PELT는 개별 task, task-group slice, CPU runqueue에 이르는 여러 scheduler entity의 metric을 추적한다. 기반 계산은 Exponentially Weighted Moving Average, 즉 EWMA다. 각 1024 us period마다 y^32=0.5가 되도록 과거 값을 감쇠한다. 따라서 가장 최근 32 ms가 전체 결과의 절반을, 그보다 오래된 이력이 나머지 절반을 차지한다.
ewma_sum(u) := u_0 + u_1*y + u_2*y^2 + ...
ewma(u) = ewma_sum(u) / ewma_sum(1)이 식은 본질적으로 무한 등비급수이므로 결과를 합성할 수 있다. 즉 ewma(A) + ewma(B) = ewma(A+B)다. task가 CPU나 group 사이를 이동할 때 평균값을 다시 조합할 수 있게 하는 핵심 성질이다.
blocked task도 task-group slice와 CPU runqueue aggregate에 계속 기여한다. 이는 그 task가 다시 실행 가능해졌을 때 예상되는 부하 기여도를 반영한다.
PELT로 추적하는 두 핵심 metric은 running과 runnable이다. running은 entity가 CPU에서 실제 실행한 시간을 나타내고, runnable은 runqueue에 실행 가능한 상태로 머문 시간을 나타낸다.
task가 하나뿐이면 두 metric은 같지만 CPU 경합이 생기면 달라진다. 각 task가 CPU를 실제로 차지하는 비율만큼 running은 낮아지고, 기다리는 task가 늘어나는 경합 정도를 반영하여 runnable은 높아진다.
Frequency와 CPU invariance
45-911 GHz CPU를 50% 사용한 것과 2 GHz CPU를 50% 사용한 것은 처리한 일의 양이 다르다. LITTLE CPU를 50% 사용한 것과 big CPU를 50% 사용한 것도 같지 않다. architecture는 시간 delta에 DVFS ratio와 microarchitecture ratio 두 값을 곱해 이런 차이를 보정할 수 있다.
software가 DVFS를 완전히 제어하는 단순한 architecture에서는 현재 frequency와 최대 frequency의 비율로 DVFS scaling ratio를 계산한다.
f_cur
r_dvfs := -----
f_maxhardware가 DVFS를 더 동적으로 제어하는 system에서는 Intel APERF/MPERF나 ARMv8.4 AMU 같은 hardware counter를 사용해 이 비율을 구한다.
Intel에서는 APERF와 MPERF를 이용해 현재 frequency를 다음처럼 계산한다.
APERF
f_cur := ----- * P0
MPERF
4C-turbo; 사용 가능하고 turbo가 켜진 경우
f_max = 1C-turbo; turbo가 켜진 경우
P0; 그 밖의 경우
f_cur
r_dvfs := min(1, -----)
f_max1C turbo보다 4C turbo를 우선하는 이유는 조금 더 지속 가능한 최대 성능 기준을 사용하기 위해서다.
r_cpu는 현재 CPU의 최고 성능 수준과 system 내 다른 모든 CPU가 낼 수 있는 최고 성능 수준의 비율로 정한다.
r_tot = r_dvfs * r_cpu최종적으로 앞에서 설명한 running과 runnable metric은 DVFS frequency와 CPU type에 독립적인 값이 된다. 따라서 서로 다른 CPU 사이에서 값을 옮기고 비교할 수 있다.
원시 실행 시간에 현재 frequency 비율과 CPU 최고 성능 비율을 함께 적용해 CPU 간 비교가 가능한 invariant signal을 만든다.
- update_rq_clock_pelt()
https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/tree/kernel/sched/pelt.h?h=v6.18.37 - x86 APERF/MPERF frequency ratio 계산
https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/tree/arch/x86/kernel/smpboot.c?h=v6.18.37 - CPU capacity와 task utilization 문서
../scheduler/sched-capacity.html
UTIL_EST와 UCLAMP
93-118periodic task는 sleep하는 동안 PELT 평균값이 감쇠한다. 다시 실행되면 이전과 같은 utilization이 예상되더라도 signal이 낮아져 DVFS frequency가 다시 올라가는 ramp-up delay를 겪는다.
기본으로 활성화되는 UTIL_EST는 이 문제를 줄인다. task의 running 값이 가장 높은 dequeue 시점에 이 값을 이용해 Infinite Impulse Response, 즉 IIR EWMA를 구동한다. UTIL_EST filter는 추정치를 즉시 높일 수 있지만 낮아질 때만 점진적으로 감쇠한다.
runqueue에는 runnable task 전체에 대해 다음 합도 유지한다. 각 task의 현재 running 값과 util_est EWMA 중 큰 값을 선택해 더한다.
util_est := Sum_t max(t_running, t_util_est_ewma)각 CFS 또는 RT task에는 effective u_min과 u_max clamp를 설정할 수 있다. runqueue는 현재 실행 가능한 모든 task의 clamp를 max aggregation으로 유지한다.
Schedutil과 DVFS
120-155scheduler load tracking이 갱신될 때마다 schedutil callback을 호출해 hardware DVFS 상태를 갱신한다. task wakeup, task migration, 시간 경과가 대표적인 호출 계기다.
계산의 출발점은 CPU runqueue의 running metric이다. 앞에서 설명한 보정을 거친 값이므로 해당 CPU의 frequency-invariant utilization 추정치다. 원하는 frequency는 개념적으로 다음 순서로 계산한다.
max(running, util_est); UTIL_EST가 켜진 경우
u_cfs := running; 그 밖의 경우
clamp(u_cfs + u_rt, u_min, u_max); UCLAMP_TASK가 켜진 경우
u_clamp := u_cfs + u_rt; 그 밖의 경우
u := u_clamp + u_irq + u_dl; // 근사식, 정확한 세부는 source 참조
f_des := min(f_max, 1.25 * u * f_max)UTIL_EST가 켜져 있으면 CFS 부하는 running과 util_est 중 큰 값이다. 여기에 RT utilization을 더하고 task uclamp 범위로 제한한다. 그 결과에 IRQ와 deadline utilization을 더해 전체 u를 만들고, 약 25% headroom을 둔 desired frequency를 계산한다.
I/O completion 때문에 task가 깨어나 발생한 update라면 위 식의 u에 I/O-wait boost가 적용된다.
계산한 frequency는 P-state나 OPP를 선택하는 데 사용하거나 CPPC 형식의 hardware request로 직접 변환한다.
Sporadic Task Model을 따르는 deadline task는 workload deadline을 만족하는 데 필요한 hard f_min을 계산할 수 있다.
callback은 scheduler에서 직접 호출되므로 DVFS hardware와의 상호작용은 빠르고 non-blocking이어야 한다. hardware 제어가 느리고 비싸면 schedutil이 DVFS request rate limiting을 지원하지만, 갱신을 제한하는 만큼 governor의 효과도 낮아진다.
CFS 추정치부터 RT, uclamp, IRQ, deadline signal을 단계적으로 합친 뒤 headroom을 적용한다.
주의할 동작
158-172- DVFS가 가장 중요한 low-load 상황에서는 running 값이 실제 utilization을 상당히 가깝게 반영한다.
- saturated 상황에서 task migration은 signal에 일시적인 dip을 만든다. task 네 개로 포화된 CPU에서 하나를 idle CPU로 옮기면 기존 CPU running은 0.75가 되고 새 CPU는 0.25를 얻는다. 피할 수 없는 과도 상태이며 시간이 지나 PELT가 이를 보정한다. 원문은 idle 시간이 전혀 없을 때도 f_max가 보장되는지 확인할 TODO를 남긴다.
- 앞의 여러 장치는 DVFS frequency가 불필요하게 떨어지는 현상을 피하고, 서로 독립된 DVFS domain 사이로 load가 이동할 때 새 domain이 부하를 다시 학습하며 ramp-up해야 하는 비용을 줄이는 데 초점이 있다.
총 부하는 보존되지만 PELT signal은 CPU 사이에 0.75와 0.25로 나뉘며, 이후 시간 경과에 따라 새 실행 상태로 수렴한다.
PELT 신호
schedutil.rst:1-44PELT는 runnable, running과 load 상태를 지수 감쇠 누적으로 표현합니다. 오래된 실행 이력의 영향은 줄고 최근 활동이 더 크게 반영됩니다. task 신호를 cfs_rq와 CPU 단위로 합성할 수 있도록 같은 시간 기반과 scale을 사용합니다.