[toc]
kernel/sched/fair.c 完全公平调度器(Completely Fair Scheduler, CFS) Linux默认的普通进程调度策略
历史与背景
这项技术是为了解决什么特定问题而诞生的？
kernel/sched/fair.c 是Linux内核**完全公平调度器（Completely Fair Scheduler, CFS）**的核心实现。它的诞生是为了彻底取代在它之前的O(1)调度器，并解决其固有的复杂性和公平性问题。
O(1)调度器虽然调度决策速度快，但它依赖于一套非常复杂的、启发式的算法来“猜测”一个进程是否是“交互式”的，并动态地调整其优先级。这导致了以下问题：
- 公平性不足：其启发式算法并不完美，常常导致某些进程获得不公平的CPU时间份额。
- 代码复杂难懂：包含大量“魔法数字”和复杂的逻辑，难以维护和调试。
- 可调优性差：
nice值对进程行为的影响不直观，难以预测。
CFS的出现，旨在用一个极其简单、优雅且可证明的公平模型来取代这一切。其核心目标不再是使用复杂的技巧去追踪进程行为，而是去模拟一个**“理想的、完美多任务的CPU”**。在这个理想模型中，每个进程都以同等的速度并行执行，绝对公平。CFS的所有设计都是为了在真实的、一次只能运行一个任务的CPU上，尽可能地逼近这个理想模型。
它的发展经历了哪些重要的里程碑或版本迭代？
CFS的发展是Linux调度器历史上的一次革命。
- 诞生 (Kernel 2.6.23)：由Ingo Molnar主导开发，CFS在Linux 2.6.23中被合并，正式取代了O(1)调度器，成为
SCHED_NORMAL和SCHED_BATCH策略的默认实现。这是Linux调度器发展史上最重要的里程碑之一。
- 组调度（Group Scheduling）的集成：CFS与控制组（cgroups）紧密集成，实现了组调度功能。这使得可以公平地在不同的用户、服务或容器（cgroups）之间分配CPU时间，而不仅仅是在进程之间。
- NUMA感知与负载均衡：CFS的负载均衡器不断演进，以更好地适应非统一内存访问（NUMA）架构，试图在CPU缓存亲和性和跨节点负载均衡之间取得最佳平衡。
- 持续的微调与优化：自诞生以来，CFS的核心模型保持不变，但其内部实现（如唤醒抢占、负载跟踪等）一直在不断地被社区优化，以适应新的硬件特性和不断变化的工作负载。
目前该技术的社区活跃度和主流应用情况如何？
CFS是当前所有通用Linux系统（桌面、服务器、移动设备）的默认调度器，是内核中最核心、最活跃的组件之一。
- 主流应用：它是Linux之所以能在从Android手机到世界顶级超级计算机等各种设备上都表现出色的关键因素之一。任何以
SCHED_NORMAL（默认策略）运行的进程，其CPU时间的分配都由fair.c中的CFS逻辑来决定。
核心原理与设计
它的核心工作原理是什么？
CFS的核心原理出奇地简单，它围绕着一个关键概念——**虚拟运行时间（virtual runtime, vruntime）**来运转。
虚拟运行时间 (vruntime)：
vruntime不是进程真实运行的物理时间，而是一个标准化的、加权的运行时间。它记录了一个进程“理应”运行了多久。- 一个进程在CPU上运行得越久，它的
vruntime就增长得越快。
- 权重（Weight）：进程的
nice值（-20到+19）被映射为一个权重。nice值越低（优先级越高），权重就越大。vruntime的增长速度与权重成反比。这意味着，高优先级的进程其vruntime增长得更慢。
数据结构：红黑树（Red-Black Tree）：
- 每个CPU的CFS运行队列（
struct cfs_rq）不再是简单的链表，而是一棵以vruntime为键值排序的红黑树。
- 所有可运行的普通进程都存在于这棵树中。
调度决策：永远选择最“饥饿”的：
- 当CFS需要选择下一个要运行的进程时，它的决策规则只有一个：永远选择红黑树最左边的那个节点。
- 因为红黑树按
vruntime排序，最左边的节点就是vruntime最小的那个。vruntime最小，意味着这个进程是当前所有可运行进程中，被“亏欠”CPU时间最多的，即最“饥apro饿”的。
时间片（Timeslice）的概念：
- CFS中没有传统意义上的固定时间片。一个进程会一直运行，直到：
a. 它自愿阻塞（如等待I/O）。
b. 一个vruntime比它更小的进程被唤醒（抢占）。
c. 它运行了一小段时间后，其vruntime不再是树中的最小值。
- 这个“一小段时间”是由系统的目标延迟（
sched_latency_ns）动态决定的。系统会尝试让每个可运行任务都在这个延迟周期内至少运行一次。
它的主要优势体现在哪些方面？
- 极致的公平性：公平性是其设计的出发点和核心，不再是事后的弥补。
- 模型简单优雅：用
vruntime和红黑树取代了复杂的启发式算法，代码逻辑更清晰。
- 天然的交互式任务支持：交互式任务（如编辑器）大部分时间都在睡眠等待用户输入。当它们被唤醒时，它们的
vruntime因为长时间没有增长而非常小，因此能立即抢占CPU，获得极佳的响应速度。
- 高效的进程选择：在红黑树上查找最小值和插入/删除操作的时间复杂度都是O(log N)，其中N是可运行进程的数量，扩展性非常好。
它存在哪些已知的劣势、局限性或在特定场景下的不适用性？
- 非实时：CFS的目标是公平，而不是满足严格的时间截止。它不提供任何实时保证。
- 对纯吞吐量场景可能非最优：对于一组纯粹的、长时间运行的计算任务，过于频繁的抢占以保证“公平”可能会导致不必要的上下文切换和缓存污染，从而轻微降低总吞吐量。
SCHED_BATCH策略就是为了缓解这个问题而设计的。
- NUMA调度的复杂性：在大型多CPU、多节点的NUMA系统上，是应该将任务保持在当前CPU以利用热缓存（cache hot），还是将其迁移到空闲的CPU以获得即时执行，这是一个极其复杂的权衡，CFS的负载均衡器一直在为此进行优化。
使用场景
在哪些具体的业务或技术场景下，它是首选解决方案？
CFS是所有非实时工作负载的默认和首选调度器。
- 桌面系统：完美平衡了后台编译任务、前台视频播放和用户UI响应等多种需求。
- 服务器：为Web服务器、数据库、应用服务器等承载的成千上万个线程和进程提供了公平的CPU时间分配。
- 移动设备 (Android)：Android的内核就是标准的Linux内核，CFS负责调度所有的应用程序和系统服务。
是否有不推荐使用该技术的场景？为什么？
- 硬实时或软实时应用：任何对任务执行延迟或截止时间有严格要求的场景，都绝对不能使用CFS。这些场景必须使用
SCH-ED_FIFO、SCHED_RR（由rt.c实现）或SCHED_DEADLINE（由dl.c实现）。
对比分析
请将其 与 其他相似技术 进行详细对比。
在Linux内核中，最恰当的对比就是将其与其他调度类进行比较。
| 特性 |
CFS (SCHED_NORMAL/BATCH) |
实时调度器 (SCHED_FIFO/RR) |
截止时间调度器 (SCHED_DEADLINE) |
| 核心调度目标 |
公平性 (Fairness) |
可预测性 (Predictability) |
保证截止时间 (Deadline Guarantee) |
| 决策依据 |
虚拟运行时间 (vruntime) |
静态优先级 (0-99) |
任务的(runtime, period, deadline)参数 |
| 任务选择复杂度 |
O(log N) (N为可运行任务数) |
O(1) (位图查找) |
O(1) (从红黑树取最左节点) |
| 公平性 |
非常好 (核心目标) |
不保证 (高优先级会饿死低优先级) |
不保证 (只关心截止时间) |
| 对普通任务 |
专门为此设计 |
会被其完全抢占和饿死 |
会被其完全抢占和饿死 |
| 适用场景 |
所有通用计算负载（桌面、服务器）。 |
传统的软实时应用（工业控制、音频）。 |
需要可验证的硬实时保证的系统。 |
kernel/sched/fair.c
init_cfs_rq 初始化完全公平调度器运行队列
- 这个设计的目的是为了解决vruntime的回绕（wrap-around）问题，并保证调度公平性。
- vruntime是单调递增的: 在CFS中，任务的vruntime会随着其运行而不断增加。理论上，它是一个无限增长的值。
- 回绕的风险: 作为一个64位的无符号整数，vruntime最终会达到最大值（2^64 - 1）然后回绕到0。如果处理不当，一个刚刚回绕到0的“老”任务，其vruntime会变得比所有其他任务都小，从而获得不公平的、超长的运行时间，饿死其他任务。
- min_vruntime的作用: min_vruntime是整个队列的“时间地平线”。所有任务的vruntime在进行比较和放置时，都是以vruntime - min_vruntime的形式，即相对值来进行的。调度器通过周期性地将所有任务的vruntime和队列的min_vruntime同时减去一个很大的值（重新归一化，normalize），来防止它们无限增长。
- 初始化的目的:
将min_vruntime初始化为一个巨大的正数，就好像是把队列的“时间地平线”设置在了遥远的未来。
当第一个任务被place_entity放置时，它的vruntime会被设置为大约等于avg_vruntime()，而avg_vruntime()又是基于min_vruntime计算的。
关键在于: 内核不希望vruntime从0开始。如果从0开始，那么当系统运行很长时间后，一个新创建的任务以接近0的vruntime加入队列，它会获得巨大的抢占优势。更重要的是，从一个非常大的正数开始，可以给vruntime的回绕处理留下充足的缓冲空间。
通过将vruntime置于一个远离0和2^64-1的中间地带，内核可以更安全、更从容地检测和处理即将到来的回绕，而不会在边界值附近出现突变。
-(1LL << 20)这个具体的值并没有绝对的魔法。它只是选择了一个足够大的、可以提供充足缓冲的初始偏移量。选择2^20可能是因为它是一个不大不小、恰到好处的2的幂次方。
1
2
3
4
5
6
7
8
9
| void init_cfs_rq(struct cfs_rq *cfs_rq)
{
cfs_rq->tasks_timeline = RB_ROOT_CACHED;
cfs_rq->min_vruntime = (u64)(-(1LL << 20));
#ifdef CONFIG_SMP
raw_spin_lock_init(&cfs_rq->removed.lock);
#endif
}
|
fair_server_init 初始化公平服务器
1
2
3
4
5
6
7
8
| void fair_server_init(struct rq *rq)
{
struct sched_dl_entity *dl_se = &rq->fair_server;
init_dl_entity(dl_se);
dl_server_init(dl_se, rq, fair_server_has_tasks, fair_server_pick_task);
}
|
DEFINE_SCHED_CLASS(fair)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
DEFINE_SCHED_CLASS(fair) = {
.enqueue_task = enqueue_task_fair,
.dequeue_task = dequeue_task_fair,
.yield_task = yield_task_fair,
.yield_to_task = yield_to_task_fair,
.wakeup_preempt = check_preempt_wakeup_fair,
.pick_task = pick_task_fair,
.pick_next_task = __pick_next_task_fair,
.put_prev_task = put_prev_task_fair,
.set_next_task = set_next_task_fair,
#ifdef CONFIG_SMP
.balance = balance_fair,
.select_task_rq = select_task_rq_fair,
.migrate_task_rq = migrate_task_rq_fair,
.rq_online = rq_online_fair,
.rq_offline = rq_offline_fair,
.task_dead = task_dead_fair,
.set_cpus_allowed = set_cpus_allowed_fair,
#endif
.task_tick = task_tick_fair,
.task_fork = task_fork_fair,
.reweight_task = reweight_task_fair,
.prio_changed = prio_changed_fair,
.switched_from = switched_from_fair,
.switched_to = switched_to_fair,
.get_rr_interval = get_rr_interval_fair,
.update_curr = update_curr_fair,
#ifdef CONFIG_FAIR_GROUP_SCHED
.task_change_group = task_change_group_fair,
#endif
#ifdef CONFIG_SCHED_CORE
.task_is_throttled = task_is_throttled_fair,
#endif
#ifdef CONFIG_UCLAMP_TASK
.uclamp_enabled = 1,
#endif
};
|
for_each_sched_entity 遍历调度实体
1
2
| #define for_each_sched_entity(se) \
for (; se; se = NULL)
|
sysctl_sched_base_slice 最小抢占粒度
- 调度延迟与粒度的权衡: CFS需要在一个矛盾中寻找平衡：
- 低延迟（Low Latency）: 为了让交互式任务（如GUI、终端）感觉流畅，调度器应该频繁地切换任务，让每个任务都能尽快得到响应。这要求调度粒度非常小。
- 高吞吐量（High Throughput）: 对于CPU密集型任务（如科学计算、视频编码），频繁的上下文切换是有害的。每次切换都会带来缓存失效（cache miss）、TLB刷新等开销。为了提高吞吐量，应该让任务尽可能长时间地运行。这要求调度粒度非常大。
sysctl_sched_latency_ns: CFS引入了一个“目标抢占延迟”（sched_latency_ns，默认约6ms）。它试图保证在sched_latency_ns这么长的时间内，所有可运行的任务都至少能被调度一次。- 时间片的计算: 一个任务的“时间片（timeslice）”是通过
sched_latency_ns按其权重比例分配的。公式大致为：
slice = sched_latency_ns * (task_weight / cfs_rq_total_weight)
sched_base_slice的角色: 如果CPU上的可运行任务非常多，按比例计算出的slice可能会变得非常小（小于1ms），这将导致过于频繁的上下文切换，损害吞吐量。sysctl_sched_base_slice就是为了解决这个问题而存在的。它为时间片设定了一个下限。CFS计算出的时间片永远不会小于sched_base_slice。- 动态调整: 注释中提到的
0.70 msec * (1 + ilog(ncpus))是一个动态调整公式。它意味着在一个拥有更多CPU核心的系统上，这个最小抢占粒度会适当增大。这是因为在多核系统上，上下文切换的开销更大，而且通过任务迁移进行负载均衡的机会更多，因此可以容忍稍大的调度粒度。700000ULL (即0.7ms) 是这个公式的基础值。
1
2
3
4
5
6
7
8
9
10
|
unsigned int sysctl_sched_base_slice = 700000ULL;
static unsigned int normalized_sysctl_sched_base_slice = 700000ULL;
__read_mostly unsigned int sysctl_sched_migration_cost = 500000UL;
|
cfs_rq_min_slice 获取CFS运行队列的最小时间片
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| static inline u64 cfs_rq_min_slice(struct cfs_rq *cfs_rq)
{
struct sched_entity *root = __pick_root_entity(cfs_rq);
struct sched_entity *curr = cfs_rq->curr;
u64 min_slice = ~0ULL;
if (curr && curr->on_rq)
min_slice = curr->slice;
if (root)
min_slice = min(min_slice, root->min_slice);
return min_slice;
}
|
update_load_add update_load_sub update_load_set 更新负载权重
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| static inline void update_load_add(struct load_weight *lw, unsigned long inc)
{
lw->weight += inc;
lw->inv_weight = 0;
}
static inline void update_load_sub(struct load_weight *lw, unsigned long dec)
{
lw->weight -= dec;
lw->inv_weight = 0;
}
static inline void update_load_set(struct load_weight *lw, unsigned long w)
{
lw->weight = w;
lw->inv_weight = 0;
}
|
__pick_root_entity 获取CFS运行队列的根调度实体
1
2
3
4
5
6
7
8
9
10
11
12
13
| #define __node_2_se(node) \
rb_entry((node), struct sched_entity, run_node)
struct sched_entity *__pick_root_entity(struct cfs_rq *cfs_rq)
{
struct rb_node *root = cfs_rq->tasks_timeline.rb_root.rb_node;
if (!root)
return NULL;
return __node_2_se(root);
}
|
avg_vruntime 算一个CFS运行队列（cfs_rq）的加权平均虚拟运行时（vruntime）
- 在CFS/EEVDF调度器中，它的核心作用是计算一个CFS运行队列（cfs_rq）的加权平均虚拟运行时（vruntime）。这个“平均vruntime”代表了当前队列中所有可运行任务的“平均进度”，是新唤醒任务在队列中寻找其初始位置的核心基准点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
u64 avg_vruntime(struct cfs_rq *cfs_rq)
{
struct sched_entity *curr = cfs_rq->curr;
s64 avg = cfs_rq->avg_vruntime;
long load = cfs_rq->avg_load;
if (curr && curr->on_rq) {
unsigned long weight = scale_load_down(curr->load.weight);
avg += entity_key(cfs_rq, curr) * weight;
load += weight;
}
if (load) {
if (avg < 0)
avg -= (load - 1);
avg = div_s64(avg, load);
}
return cfs_rq->min_vruntime + avg;
}
|
avg_vruntime_sub 从CFS运行队列（cfs_rq）的平均vruntime统计中减去一个调度实体（se）的vruntime贡献
1
2
3
4
5
6
7
8
9
| static void
avg_vruntime_sub(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
unsigned long weight = scale_load_down(se->load.weight);
s64 key = entity_key(cfs_rq, se);
cfs_rq->avg_vruntime -= key * weight;
cfs_rq->avg_load -= weight;
}
|
update_min_vruntime 重新计算并更新该队列的min_vruntime成员
- 在CFS运行队列（cfs_rq）的成员发生变化（入队、出队、当前任务更新）后，重新计算并更新该队列的min_vruntime成员。 min_vruntime是整个CFS公平性得以实现、并防止vruntime无限增长的 “时间基线”或“水平面”。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
static void update_min_vruntime(struct cfs_rq *cfs_rq)
{
struct sched_entity *se = __pick_root_entity(cfs_rq);
struct sched_entity *curr = cfs_rq->curr;
u64 vruntime = cfs_rq->min_vruntime;
if (curr) {
if (curr->on_rq)
vruntime = curr->vruntime;
else
curr = NULL;
}
if (se) {
if (!curr)
vruntime = se->min_vruntime;
else
vruntime = min_vruntime(vruntime, se->min_vruntime);
}
cfs_rq->min_vruntime = __update_min_vruntime(cfs_rq, vruntime);
}
|
update_curr 核算当前正在CPU上运行的CFS任务的虚拟运行时（vruntime）
- 核算当前正在CPU上运行的CFS任务（cfs_rq->curr）从上次记账到当前时刻，所消耗的物理CPU时间，并将这段物理时间转换为加权的“虚拟运行时（vruntime）”，然后累加到该任务的vruntime上。
这个函数是CFS实现其“完全公平”调度理念的数学和逻辑基石。调度器在做出任何重要决策之前（如抢占、入队、出队），都必须调用update_curr来确保所有任务的vruntime都是最新的，因为vruntime是CFS进行一切比较和排序的唯一度量衡
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
static void update_curr(struct cfs_rq *cfs_rq)
{
struct sched_entity *curr = cfs_rq->curr;
struct rq *rq = rq_of(cfs_rq);
s64 delta_exec;
bool resched;
if (unlikely(!curr))
return;
delta_exec = update_curr_se(rq, curr);
if (unlikely(delta_exec <= 0))
return;
curr->vruntime += calc_delta_fair(delta_exec, curr);
resched = update_deadline(cfs_rq, curr);
update_min_vruntime(cfs_rq);
if (entity_is_task(curr)) {
struct task_struct *p = task_of(curr);
update_curr_task(p, delta_exec);
if (dl_server_active(&rq->fair_server))
dl_server_update(&rq->fair_server, delta_exec);
}
account_cfs_rq_runtime(cfs_rq, delta_exec);
if (cfs_rq->nr_queued == 1)
return;
if (resched || did_preempt_short(cfs_rq, curr)) {
resched_curr_lazy(rq);
clear_buddies(cfs_rq, curr);
}
}
|
account_entity_enqueue 更新CFS运行队列的负载和排队任务数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| static void
account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
update_load_add(&cfs_rq->load, se->load.weight);
#ifdef CONFIG_SMP
if (entity_is_task(se)) {
struct rq *rq = rq_of(cfs_rq);
account_numa_enqueue(rq, task_of(se));
list_add(&se->group_node, &rq->cfs_tasks);
}
#endif
cfs_rq->nr_queued++;
}
|
account_entity_dequeue 从CFS运行队列中移除一个调度实体，并更新负载和排队任务数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
| static void
account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
update_load_sub(&cfs_rq->load, se->load.weight);
#ifdef CONFIG_SMP
if (entity_is_task(se)) {
account_numa_dequeue(rq_of(cfs_rq), task_of(se));
list_del_init(&se->group_node);
}
#endif
cfs_rq->nr_queued--;
}
## calc_delta_fair 将一个任务的物理执行时间（delta_exec），根据其负载权重，转换为虚拟运行时（vruntime）
- 计算 delta_exec * weight / lw->weight
- 在内核中，直接进行64位整数的乘法和除法是昂贵且容易溢出的。例如，delta_exec * weight的结果可能超过64位。直接使用浮点运算是不可接受的
1. 反转权重 (inv_weight): 内核预先为每个可能的权重W计算了一个“反转权重” I = 2^32 / W。这个I是一个定点数，可以看作是1/W的放大表示。
2. 变除法为乘法: 原始的 / lw->weight 操作，被转换为 * lw->inv_weight 再加上一个右移操作。即：X / W 约等于 (X * (2^32 / W)) >> 32。
3. 防止溢出: 即便如此，delta_exec * fact (fact是另一个权重) 仍然可能溢出。因此，__calc_delta函数使用了一系列**位移（shift）和高位检查（fls）**的技巧。它会检查乘法操作的中间结果是否会溢出32位或64位，如果会，就先将操作数向右移动几位以“腾出空间”，然后将移动的位数从最终的右移位数中减去。这确保了所有中间计算都在64位整数的表示范围内。
```c
static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
{
u64 fact = scale_load_down(weight);
u32 fact_hi = (u32)(fact >> 32);
int shift = WMULT_SHIFT;
int fs;
__update_inv_weight(lw);
if (unlikely(fact_hi)) {
fs = fls(fact_hi);
shift -= fs;
fact >>= fs;
}
fact = mul_u32_u32(fact, lw->inv_weight);
fact_hi = (u32)(fact >> 32);
if (fact_hi) {
fs = fls(fact_hi);
shift -= fs;
fact >>= fs;
}
return mul_u64_u32_shr(delta_exec, fact, shift);
}
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
if (unlikely(se->load.weight != NICE_0_LOAD))
delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
return delta;
}
|
reweight_task_fair 动态调整一个已在运行队列中的任务的调度权重
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
unsigned long weight)
{
bool curr = cfs_rq->curr == se;
if (se->on_rq) {
update_curr(cfs_rq);
update_entity_lag(cfs_rq, se);
se->deadline -= se->vruntime;
se->rel_deadline = 1;
cfs_rq->nr_queued--;
if (!curr)
__dequeue_entity(cfs_rq, se);
update_load_sub(&cfs_rq->load, se->load.weight);
}
se->vlag = div_s64(se->vlag * se->load.weight, weight);
if (se->rel_deadline)
se->deadline = div_s64(se->deadline * se->load.weight, weight);
update_load_set(&se->load, weight);
#ifdef CONFIG_SMP
do {
u32 divider = get_pelt_divider(&se->avg);
se->avg.load_avg = div_u64(se_weight(se) * se->avg.load_sum, divider);
} while (0);
#endif
if (se->on_rq) {
place_entity(cfs_rq, se, 0);
update_load_add(&cfs_rq->load, se->load.weight);
if (!curr)
__enqueue_entity(cfs_rq, se);
cfs_rq->nr_queued++;
update_min_vruntime(cfs_rq);
}
}
static void reweight_task_fair(struct rq *rq, struct task_struct *p,
const struct load_weight *lw)
{
struct sched_entity *se = &p->se;
struct cfs_rq *cfs_rq = cfs_rq_of(se);
struct load_weight *load = &se->load;
reweight_entity(cfs_rq, se, lw->weight);
load->inv_weight = lw->inv_weight;
}
|
place_entity 为一个调度实体（se）计算一个合适的初始vruntime（虚拟运行时）和deadline（虚拟截止时间），以决定它在红黑树中的初始位置
- place_entity是CFS调度器中的一个核心辅助函数。当一个新唤醒的或迁移来的任务需要被放入CFS运行队列（红黑树）时，此函数被调用。
它的核心作用是：为一个调度实体（se）计算一个合适的初始vruntime（虚拟运行时）和deadline（虚拟截止时间），以决定它在红黑树中的初始位置。 这个“放置”策略直接决定了新任务的响应速度和对现有任务的公平性。
其工作原理基于**EEVDF (Earliest Eligible Virtual Deadline First)**调度算法，这是一种比传统CFS更先进的公平调度算法。其原理可以概括为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
u64 vslice;
u64 vruntime = avg_vruntime(cfs_rq);
s64 lag = 0;
if (!se->custom_slice)
se->slice = sysctl_sched_base_slice;
vslice = calc_delta_fair(se->slice, se);
if (sched_feat(PLACE_LAG) && cfs_rq->nr_queued && se->vlag) {
struct sched_entity *curr = cfs_rq->curr;
unsigned long load;
lag = se->vlag;
load = cfs_rq->avg_load;
if (curr && curr->on_rq)
load += scale_load_down(curr->load.weight);
lag *= load + scale_load_down(se->load.weight);
if (WARN_ON_ONCE(!load))
load = 1;
lag = div_s64(lag, load);
}
se->vruntime = vruntime - lag;
if (se->rel_deadline) {
se->deadline += se->vruntime;
se->rel_deadline = 0;
return;
}
if (sched_feat(PLACE_DEADLINE_INITIAL) && (flags & ENQUEUE_INITIAL))
vslice /= 2;
se->deadline = se->vruntime + vslice;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
## avg_vruntime_add 将一个调度实体（se）的vruntime贡献累加到CFS运行队列（cfs_rq）的平均vruntime统计中
```c
/*
* 这是一个静态内联函数，用于计算一个实体在其cfs_rq中的排序键。
* @cfs_rq: 该实体所属的CFS运行队列。
* @se: 目标调度实体。
* 返回值：实体相对于队列min_vruntime的“相对虚拟运行时”。
*/
static inline s64 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
/* 返回实体的绝对vruntime与队列的最小vruntime基线之差。这是一个有符号值。*/
return (s64)(se->vruntime - cfs_rq->min_vruntime);
}
/*
* 从每个任务的服务数计算虚拟时间：
*
* 公平调度器遵循滞后守恒原则：
*
* Σ lag_i = 0
*
* 其中lag_i由下式给出：
*
* lag_i = S - s_i = w_i * (V - v_i)
*
* S是理想的服务时间，V是其虚拟时间对应物。因此：
*
* Σ lag_i = 0
* Σ w_i * (V - v_i) = 0
* Σ w_i * V - w_i * v_i = 0
*
* 从中我们可以解出V关于v_i的表达式（v_i我们已在se->vruntime中持有）：
*
* Σ v_i * w_i Σ v_i * w_i
* V = -------------- = --------------
* Σ w_i W
*
* 具体来说，这是所有实体虚拟运行时的加权平均值。
*
* [[ 注意：这只在加入/离开操作发生在lag_i = 0的条件下，才等于理想
* 调度器。否则，虚拟时间会有相当于 V +-= lag_i / W 的
* 非连续运动。另见place_entity()中处理此问题的注释。]]
*
* 然而，由于v_i是u64，乘法可能轻易溢出，因此将其转换为
* 使用更小数值的相对形式：
*
* 替换：v_i == (v_i - v0) + v0
*
* Σ ((v_i - v0) + v0) * w_i Σ (v_i - v0) * w_i
* V = ---------------------------- = --------------------- + v0
* W W
*
* 我们使用以下变量来跟踪它：
*
* v0 := cfs_rq->min_vruntime
* Σ (v_i - v0) * w_i := cfs_rq->avg_vruntime
* Σ w_i := cfs_rq->avg_load
*
* 由于min_vruntime是一个单调递增的、紧密跟踪每个任务服务的变量，
* 这些增量：(v_i - v0)，将处于系统中由于量化而引起的最大（虚拟）
* 滞后的数量级。
*
* 此外，我们使用scale_load_down()来减小数值的大小。
*
* 根据测量，(key * weight)的最大值在一次内核构建中约为44位。
*/
/*
* 这是一个静态函数，当一个实体se被加入cfs_rq时，用于更新队列的平均vruntime统计。
* @cfs_rq: 目标CFS运行队列。
* @se: 被加入的调度实体。
*/
static void
avg_vruntime_add(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
/* @weight: 获取实体se的负载权重，并使用scale_load_down进行可能的缩放。*/
unsigned long weight = scale_load_down(se->load.weight);
/* @key: 调用entity_key计算实体se的相对vruntime。*/
s64 key = entity_key(cfs_rq, se);
/* 将该实体的加权相对vruntime，累加到cfs_rq的avg_vruntime总和中。*/
cfs_rq->avg_vruntime += key * weight;
/* 将该实体的权重，累加到cfs_rq的avg_load总和中。*/
cfs_rq->avg_load += weight;
}
|
__enqueue_entity 将一个已经计算好vruntime和deadline的调度实体（se），物理地插入到CFS运行队列（cfs_rq）的**红黑树（tasks_timeline）**中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
static inline bool min_vruntime_update(struct sched_entity *se, bool exit)
{
u64 old_min_vruntime = se->min_vruntime;
u64 old_min_slice = se->min_slice;
struct rb_node *node = &se->run_node;
se->min_vruntime = se->vruntime;
__min_vruntime_update(se, node->rb_right);
__min_vruntime_update(se, node->rb_left);
se->min_slice = se->slice;
__min_slice_update(se, node->rb_right);
__min_slice_update(se, node->rb_left);
return se->min_vruntime == old_min_vruntime &&
se->min_slice == old_min_slice;
}
RB_DECLARE_CALLBACKS(static, min_vruntime_cb, struct sched_entity,
run_node, min_vruntime, min_vruntime_update);
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
avg_vruntime_add(cfs_rq, se);
se->min_vruntime = se->vruntime;
se->min_slice = se->slice;
rb_add_augmented_cached(&se->run_node, &cfs_rq->tasks_timeline,
__entity_less, &min_vruntime_cb);
}
|
enqueue_entity 将单个调度实体（sched_entity）插入到其所属的CFS运行队列（cfs_rq）的红黑树中
- enqueue_entity是CFS调度器中负责将单个调度实体（sched_entity）插入到其所属的CFS运行队列（cfs_rq）的红黑树中的底层核心函数。它是上层enqueue_task_fair等函数的最终执行者，是“入队”操作的最小原子单位。
它的核心作用是：在更新完所有与实体相关的统计数据（特别是vruntime和负载）之后，调用__enqueue_entity将实体物理地插入红黑树，并更新队列的状态。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
bool curr = cfs_rq->curr == se;
if (curr)
place_entity(cfs_rq, se, flags);
update_curr(cfs_rq);
if (!curr)
place_entity(cfs_rq, se, flags);
account_entity_enqueue(cfs_rq, se);
if (flags & ENQUEUE_MIGRATED)
se->exec_start = 0;
if (!curr)
__enqueue_entity(cfs_rq, se);
se->on_rq = 1;
if (cfs_rq->nr_queued == 1) {
}
}
|
enqueue_task_fair 将一个指定的任务（p）及其调度实体（se），正确地插入到CFS的运行队列（红黑树）中，并更新所有相关的调度统计数据（如虚拟运行时、负载、利用率等）
- enqueue_task_fair是**公平调度类（fair_sched_class）**的enqueue_task方法实现。当一个属于CFS调度的任务变为可运行状态（例如，从睡眠中被唤醒，或新创建的任务被激活）时，调度器核心就会调用此函数。
它的核心作用是：将一个指定的任务（p）及其调度实体（se），正确地插入到CFS的运行队列（红黑树）中，并更新所有相关的调度统计数据（如虚拟运行时、负载、利用率等）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
|
static void
enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
{
struct cfs_rq *cfs_rq;
struct sched_entity *se = &p->se;
int h_nr_idle = task_has_idle_policy(p);
int h_nr_runnable = 1;
int task_new = !(flags & ENQUEUE_WAKEUP);
int rq_h_nr_queued = rq->cfs.h_nr_queued;
u64 slice = 0;
if (flags & ENQUEUE_DELAYED) {
requeue_delayed_entity(se);
return;
}
if (task_new && se->sched_delayed)
h_nr_runnable = 0;
for_each_sched_entity(se) {
if (se->on_rq) {
if (se->sched_delayed)
requeue_delayed_entity(se);
break;
}
cfs_rq = cfs_rq_of(se);
if (slice) {
se->slice = slice;
se->custom_slice = 1;
}
enqueue_entity(cfs_rq, se, flags);
slice = cfs_rq_min_slice(cfs_rq);
cfs_rq->h_nr_runnable += h_nr_runnable;
cfs_rq->h_nr_queued++;
cfs_rq->h_nr_idle += h_nr_idle;
if (cfs_rq_is_idle(cfs_rq))
h_nr_idle = 1;
flags = ENQUEUE_WAKEUP;
}
for_each_sched_entity(se) {
cfs_rq = cfs_rq_of(se);
se->slice = slice;
if (se != cfs_rq->curr)
min_vruntime_cb_propagate(&se->run_node, NULL);
slice = cfs_rq_min_slice(cfs_rq);
cfs_rq->h_nr_runnable += h_nr_runnable;
cfs_rq->h_nr_queued++;
cfs_rq->h_nr_idle += h_nr_idle;
}
if (!rq_h_nr_queued && rq->cfs.h_nr_queued) {
if (!rq->nr_running)
dl_server_update_idle_time(rq, rq->curr);
dl_server_start(&rq->fair_server);
}
add_nr_running(rq, 1);
enqueue_throttle:
hrtick_update(rq);
}
|
update_entity_lag 计算并更新该实体se的“虚拟延迟（vlag）”值
- vlag是一个度量，它反映了实体se的vruntime相对于其所属的CFS运行队列cfs_rq的平均vruntime的偏离程度。
- 其基本原理如下：
- 理想的公平: 在一个理想的CFS系统中，所有可运行任务的vruntime都应该大致相等，并与队列的平均vruntime保持一致。
- 延迟（Lag）的定义:
- lag_i = S - s_i，其中S是系统的虚拟时间（用avg_vruntime近似），s_i是任务i的虚拟时间（se->vruntime）。
- 如果vlag为一个大的正数，意味着se->vruntime远小于平均值。这说明该任务被“亏欠”了很多运行时间，它是一个“受害者（victim）”，在下次被调度时应该得到补偿。
- 如果vlag为一个大的负数，意味着se->vruntime远大于平均值。这说明该任务“超前”运行了太多时间，它是一个“超前者（over-runner）”，在下次调度时应该被延后。
- vlag的作用: se->vlag这个值主要被**Per-Entity Load Tracking (PELT)**算法所使用。PELT是内核用于计算任务和运行队列平均负载及利用率的机制。vlag作为PELT的一个输入，可以帮助算法更精 确地评估任务在遭受延迟或抢占时的真实负载贡献，从而影响负载均衡和CPU频率选择的决策。
- 限制（Clamping）: 由于avg_vruntime是一个近似的平均值，在任务加入/离开队列或权重改变时，它可能会跳变，导致计算出的vlag出现极端值。为了防止这种瞬时抖动对PELT算法造成过大影响，函数 会对计算出的vlag进行限制，将其“钳位（clamp）”在一个合理的范围内。这个范围由任务的时间片（slice）动态决定。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
static void update_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
s64 vlag;
s64 limit;
WARN_ON_ONCE(!se->on_rq);
vlag = avg_vruntime(cfs_rq) - se->vruntime;
limit = calc_delta_fair(max_t(u64, 2*se->slice, TICK_NSEC), se);
se->vlag = clamp(vlag, -limit, limit);
}
|
__dequeue_entity 从CFS运行队列中移除一个调度实体（sched_entity）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
rb_erase_augmented_cached(&se->run_node, &cfs_rq->tasks_timeline,
&min_vruntime_cb);
avg_vruntime_sub(cfs_rq, se);
}
|
dequeue_entity 将单个调度实体（sched_entity）从其所属的CFS运行队列（cfs_rq）中移除
- 在将一个实体从红黑树中摘下之前和之后，完成所有与该实体相关的、必要的统计数据更新和状态变更
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
static bool
dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
bool sleep = flags & DEQUEUE_SLEEP;
int action = UPDATE_TG;
update_curr(cfs_rq);
clear_buddies(cfs_rq, se);
if (flags & DEQUEUE_DELAYED) {
WARN_ON_ONCE(!se->sched_delayed);
} else {
bool delay = sleep;
if (flags & DEQUEUE_SPECIAL)
delay = false;
WARN_ON_ONCE(delay && se->sched_delayed);
if (sched_feat(DELAY_DEQUEUE) && delay &&
!entity_eligible(cfs_rq, se)) {
update_load_avg(cfs_rq, se, 0);
set_delayed(se);
return false;
}
}
if (entity_is_task(se) && task_on_rq_migrating(task_of(se)))
action |= DO_DETACH;
update_entity_lag(cfs_rq, se);
if (sched_feat(PLACE_REL_DEADLINE) && !sleep) {
se->deadline -= se->vruntime;
se->rel_deadline = 1;
}
if (se != cfs_rq->curr)
__dequeue_entity(cfs_rq, se);
se->on_rq = 0;
account_entity_dequeue(cfs_rq, se);
if ((flags & (DEQUEUE_SAVE | DEQUEUE_MOVE)) != DEQUEUE_SAVE)
update_min_vruntime(cfs_rq);
if (flags & DEQUEUE_DELAYED)
finish_delayed_dequeue_entity(se);
return true;
}
|
dequeue_entities 执行跨越整个cgroup层级的、实际的“出队”操作
- 从一个给定的调度实体（se）开始，沿着cgroup层级树向上，将该实体及其所有可运行的祖先实体，从它们各自所属的CFS运行队列（红黑树）中移除，并级联更新所有层级的统计数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
|
static int dequeue_entities(struct rq *rq, struct sched_entity *se, int flags)
{
bool was_sched_idle = sched_idle_rq(rq);
int rq_h_nr_queued = rq->cfs.h_nr_queued;
bool task_sleep = flags & DEQUEUE_SLEEP;
bool task_delayed = flags & DEQUEUE_DELAYED;
struct task_struct *p = NULL;
int h_nr_idle = 0;
int h_nr_queued = 0;
int h_nr_runnable = 0;
struct cfs_rq *cfs_rq;
u64 slice = 0;
if (entity_is_task(se)) {
p = task_of(se);
h_nr_queued = 1;
h_nr_idle = task_has_idle_policy(p);
if (task_sleep || task_delayed || !se->sched_delayed)
h_nr_runnable = 1;
}
for_each_sched_entity(se) {
cfs_rq = cfs_rq_of(se);
if (!dequeue_entity(cfs_rq, se, flags)) {
if (p && &p->se == se)
return -1;
slice = cfs_rq_min_slice(cfs_rq);
break;
}
cfs_rq->h_nr_runnable -= h_nr_runnable;
cfs_rq->h_nr_queued -= h_nr_queued;
cfs_rq->h_nr_idle -= h_nr_idle;
return 0;
if (cfs_rq->load.weight) {
slice = cfs_rq_min_slice(cfs_rq);
se = parent_entity(se);
break;
}
flags |= DEQUEUE_SLEEP;
flags &= ~(DEQUEUE_DELAYED | DEQUEUE_SPECIAL);
}
for_each_sched_entity(se) {
cfs_rq = cfs_rq_of(se);
se->slice = slice;
if (se != cfs_rq->curr)
min_vruntime_cb_propagate(&se->run_node, NULL);
slice = cfs_rq_min_slice(cfs_rq);
cfs_rq->h_nr_runnable -= h_nr_runnable;
cfs_rq->h_nr_queued -= h_nr_queued;
cfs_rq->h_nr_idle -= h_nr_idle;
}
sub_nr_running(rq, h_nr_queued);
if (rq_h_nr_queued && !rq->cfs.h_nr_queued)
dl_server_stop(&rq->fair_server);
if (unlikely(!was_sched_idle && sched_idle_rq(rq)))
rq->next_balance = jiffies;
if (p && task_delayed) {
WARN_ON_ONCE(!task_sleep);
WARN_ON_ONCE(p->on_rq != 1);
hrtick_update(rq);
__block_task(rq, p);
}
return 1;
}
|
dequeue_task_fair 将一个指定的任务（p）及其相关的调度实体（se），从CFS的运行队列（红黑树）中正确地移除，并在此之前更新所有相关的调度统计数据
- 当一个属于CFS调度的任务变为不可运行状态（例如，开始睡眠等待I/O，或者即将被迁移到另一个CPU）时，调度器核心就会调用此函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
static bool dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)
{
if (dequeue_entities(rq, &p->se, flags) < 0)
return false;
return true;
}
|
微信
