1 .. SPDX-License-Identifier: GPL-2.0 1 .. SPDX-License-Identifier: GPL-2.0
2 .. include:: ../disclaimer-zh_CN.rst 2 .. include:: ../disclaimer-zh_CN.rst
3 3
4 :Original: Documentation/scheduler/schedutil.r 4 :Original: Documentation/scheduler/schedutil.rst
5 5
6 :翻译: 6 :翻译:
7 7
8 唐艺舟 Tang Yizhou <tangyeechou@gmail.com> 8 唐艺舟 Tang Yizhou <tangyeechou@gmail.com>
9 9
10 ========= 10 =========
11 Schedutil 11 Schedutil
12 ========= 12 =========
13 13
14 .. note:: 14 .. note::
15 15
16 本文所有内容都假设频率和工作 16 本文所有内容都假设频率和工作算力之间存在线性关系。我们知道这是有瑕疵的，
17 但这是最可行的近似处理。 17 但这是最可行的近似处理。
18 18
19 PELT（实体负载跟踪，Per Entity Load Tr 19 PELT（实体负载跟踪，Per Entity Load Tracking）
20 ============================================== 20 ==============================================
21 21
22 通过PELT，我们跟踪了各种调度器实 22 通过PELT，我们跟踪了各种调度器实体的一些指标，从单个任务到任务组分片到CPU
23 运行队列。我们使用指数加权移动 23 运行队列。我们使用指数加权移动平均数（Exponentially Weighted Moving Average，
24 EWMA）作为其基础，每个周期（1024us 24 EWMA）作为其基础，每个周期（1024us）都会衰减，衰减速率满足y^32 = 0.5。
25 也就是说，最近的32ms贡献负载的一 25 也就是说，最近的32ms贡献负载的一半，而历史上的其它时间则贡献另一半。
26 26
27 具体而言： 27 具体而言：
28 28
29 ewma_sum(u) := u_0 + u_1*y + u_2*y^2 + ... 29 ewma_sum(u) := u_0 + u_1*y + u_2*y^2 + ...
30 30
31 ewma(u) = ewma_sum(u) / ewma_sum(1) 31 ewma(u) = ewma_sum(u) / ewma_sum(1)
32 32
33 由于这本质上是一个无限几何级数 33 由于这本质上是一个无限几何级数的累加，结果是可组合的，即ewma(A) + ewma(B) = ewma(A+B)。
34 这个属性是关键，因为它提供了在 34 这个属性是关键，因为它提供了在任务迁移时重新组合平均数的能力。
35 35
36 请注意，阻塞态的任务仍然对累加 36 请注意，阻塞态的任务仍然对累加值（任务组分片和CPU运行队列）有贡献，这反映了
37 它们在恢复运行后的预期贡献。 37 它们在恢复运行后的预期贡献。
38 38
39 利用这一点，我们跟踪2个关键指标 39 利用这一点，我们跟踪2个关键指标：“运行”和“可运行”。“运行”反映了一个调度实体
40 在CPU上花费的时间，而“可运行” 40 在CPU上花费的时间，而“可运行”反映了一个调度实体在运行队列中花费的时间。当只有
41 一个任务时，这两个指标是相同的 41 一个任务时，这两个指标是相同的，但一旦出现对CPU的争用，“运行”将减少以反映每个
42 任务在CPU上花费的时间，而“可运 42 任务在CPU上花费的时间，而“可运行”将增加以反映争用的激烈程度。
43 43
44 更多细节见：kernel/sched/pelt.c 44 更多细节见：kernel/sched/pelt.c
45 45
46 46
47 频率 / CPU不变性 47 频率 / CPU不变性
48 ================ 48 ================
49 49
50 因为CPU频率在1GHz时利用率为50%和CPU 50 因为CPU频率在1GHz时利用率为50%和CPU频率在2GHz时利用率为50%是不一样的，同样
51 在小核上运行时利用率为50%和在大 51 在小核上运行时利用率为50%和在大核上运行时利用率为50%是不一样的，我们允许架构
52 以两个比率来伸缩时间差，其中一 52 以两个比率来伸缩时间差，其中一个是动态电压频率升降（Dynamic Voltage and
53 Frequency Scaling，DVFS）比率，另一个 53 Frequency Scaling，DVFS）比率，另一个是微架构比率。
54 54
55 对于简单的DVFS架构（软件有完全控 55 对于简单的DVFS架构（软件有完全控制能力），我们可以很容易地计算该比率为::
56 56
57 f_cur 57 f_cur
58 r_dvfs := ----- 58 r_dvfs := -----
59 f_max 59 f_max
60 60
61 对于由硬件控制DVFS的更多动态系统 61 对于由硬件控制DVFS的更多动态系统，我们使用硬件计数器（Intel APERF/MPERF，
62 ARMv8.4-AMU）来计算这一比率。具体 62 ARMv8.4-AMU）来计算这一比率。具体到Intel，我们使用::
63 63
64 APERF 64 APERF
65 f_cur := ----- * P0 65 f_cur := ----- * P0
66 MPERF 66 MPERF
67 67
68 4C-turbo; 如果可用并且使 68 4C-turbo; 如果可用并且使能了turbo
69 f_max := { 1C-turbo; 如果使能了turbo 69 f_max := { 1C-turbo; 如果使能了turbo
70 P0; 其它情况 70 P0; 其它情况
71 71
72 f_cur 72 f_cur
73 r_dvfs := min( 1, ----- ) 73 r_dvfs := min( 1, ----- )
74 f_max 74 f_max
75 75
76 我们选择4C turbo而不是1C turbo，以使 76 我们选择4C turbo而不是1C turbo，以使其更持久性略微更强。
77 77
78 r_cpu被定义为当前CPU的最高性能水 78 r_cpu被定义为当前CPU的最高性能水平与系统中任何其它CPU的最高性能水平的比率。
79 79
80 r_tot = r_dvfs * r_cpu 80 r_tot = r_dvfs * r_cpu
81 81
82 其结果是，上述“运行”和“可运 82 其结果是，上述“运行”和“可运行”的指标变成DVFS无关和CPU型号无关了。也就是说，
83 我们可以在CPU之间转移和比较它们 83 我们可以在CPU之间转移和比较它们。
84 84
85 更多细节见: 85 更多细节见:
86 86
87 - kernel/sched/pelt.h:update_rq_clock_pelt() 87 - kernel/sched/pelt.h:update_rq_clock_pelt()
88 - arch/x86/kernel/smpboot.c:"APERF/MPERF freq 88 - arch/x86/kernel/smpboot.c:"APERF/MPERF frequency ratio computation."
89 - Documentation/translations/zh_CN/scheduler/ 89 - Documentation/translations/zh_CN/scheduler/sched-capacity.rst:"1. CPU Capacity + 2. Task utilization"
90 90
91 91
92 UTIL_EST !! 92 UTIL_EST / UTIL_EST_FASTUP
93 ======== !! 93 ==========================
94 94
95 由于周期性任务的平均数在睡眠时 95 由于周期性任务的平均数在睡眠时会衰减，而在运行时其预期利用率会和睡眠前相同，
96 因此它们在再次运行后会面临（DVFS 96 因此它们在再次运行后会面临（DVFS）的上涨。
97 97
98 为了缓解这个问题，（一个默认使 98 为了缓解这个问题，（一个默认使能的编译选项）UTIL_EST驱动一个无限脉冲响应
99 （Infinite Impulse Response，IIR）的EWMA 99 （Infinite Impulse Response，IIR）的EWMA，“运行”值在出队时是最高的。
100 UTIL_EST滤波使其在遇到更高值时立 !! 100 另一个默认使能的编译选项UTIL_EST_FASTUP修改了IIR滤波器，使其允许立即增加，
>> 101 仅在利用率下降时衰减。
101 102
102 进一步，运行队列的（可运行任务 103 进一步，运行队列的（可运行任务的）利用率之和由下式计算：
103 104
104 util_est := \Sum_t max( t_running, t_util_es 105 util_est := \Sum_t max( t_running, t_util_est_ewma )
105 106
106 更多细节见: kernel/sched/fair.c:util_est_ 107 更多细节见: kernel/sched/fair.c:util_est_dequeue()
107 108
108 109
109 UCLAMP 110 UCLAMP
110 ====== 111 ======
111 112
112 可以在每个CFS或RT任务上设置有效 113 可以在每个CFS或RT任务上设置有效的u_min和u_max clamp值（译注：clamp可以理解
113 为类似滤波器的能力，它定义了有 114 为类似滤波器的能力，它定义了有效取值范围的最大值和最小值）；运行队列为所有正在
114 运行的任务保持这些clamp的最大聚 115 运行的任务保持这些clamp的最大聚合值。
115 116
116 更多细节见: include/uapi/linux/sched/type 117 更多细节见: include/uapi/linux/sched/types.h
117 118
118 119
119 Schedutil / DVFS 120 Schedutil / DVFS
120 ================ 121 ================
121 122
122 每当调度器的负载跟踪被更新时（ 123 每当调度器的负载跟踪被更新时（任务唤醒、任务迁移、时间流逝），我们都会调用
123 schedutil来更新硬件DVFS状态。 124 schedutil来更新硬件DVFS状态。
124 125
125 其基础是CPU运行队列的“运行”指 126 其基础是CPU运行队列的“运行”指标，根据上面的内容，它是CPU的频率不变的利用率
126 估计值。由此我们计算出一个期望 127 估计值。由此我们计算出一个期望的频率，如下::
127 128
128 max( running, util_est ); 如果 129 max( running, util_est ); 如果使能UTIL_EST
129 u_cfs := { running; 其它 130 u_cfs := { running; 其它情况
130 131
131 clamp( u_cfs + u_rt, u_min, u_m 132 clamp( u_cfs + u_rt, u_min, u_max ); 如果使能UCLAMP_TASK
132 u_clamp := { u_cfs + u_rt; 133 u_clamp := { u_cfs + u_rt; 其它情况
133 134
134 u := u_clamp + u_irq + u_dl; [估 135 u := u_clamp + u_irq + u_dl; [估计值。更多细节见源代码]
135 136
136 f_des := min( f_max, 1.25 u * f_max ) 137 f_des := min( f_max, 1.25 u * f_max )
137 138
138 关于IO-wait的说明：当发生更新是因 139 关于IO-wait的说明：当发生更新是因为任务从IO完成中唤醒时，我们提升上面的“u”。
139 140
140 然后，这个频率被用来选择一个P-st 141 然后，这个频率被用来选择一个P-state或OPP，或者直接混入一个发给硬件的CPPC式
141 请求。 142 请求。
142 143
143 关于截止期限调度器的说明: 截止 144 关于截止期限调度器的说明: 截止期限任务（偶发任务模型）使我们能够计算出满足
144 工作负荷所需的硬f_min值。 145 工作负荷所需的硬f_min值。
145 146
146 因为这些回调函数是直接来自调度 147 因为这些回调函数是直接来自调度器的，所以DVFS的硬件交互应该是“快速”和非阻塞的。
147 在硬件交互缓慢和昂贵的时候，sche 148 在硬件交互缓慢和昂贵的时候，schedutil支持DVFS请求限速，不过会降低效率。
148 149
149 更多信息见: kernel/sched/cpufreq_scheduti 150 更多信息见: kernel/sched/cpufreq_schedutil.c
150 151
151 152
152 注意 153 注意
153 ==== 154 ====
154 155
155 - 在低负载场景下，DVFS是最相关的 156 - 在低负载场景下，DVFS是最相关的，“运行”的值将密切反映利用率。
156 157
157 - 在负载饱和的场景下，任务迁移 158 - 在负载饱和的场景下，任务迁移会导致一些瞬时性的使用率下降。假设我们有一个
158 CPU，有4个任务占用导致其饱和， 159 CPU，有4个任务占用导致其饱和，接下来我们将一个任务迁移到另一个空闲CPU上，
159 旧的CPU的“运行”值将为0.75，而 160 旧的CPU的“运行”值将为0.75，而新的CPU将获得0.25。这是不可避免的，而且随着
160 时间流逝将自动修正。另注，由 161 时间流逝将自动修正。另注，由于没有空闲时间，我们还能保证f_max值吗？
161 162
162 - 上述大部分内容是关于避免DVFS下 163 - 上述大部分内容是关于避免DVFS下滑，以及独立的DVFS域发生负载迁移时不得不
163 重新学习/提升频率。 164 重新学习/提升频率。
164 165
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.