第14章 EEVDF 调度器详解
基于 Linux 6.12.38 源码分析
14.1 EEVDF 算法概述
14.1.1 从 CFS 到 EEVDF
CFS (Completely Fair Scheduler) 的问题：
- 基于 vruntime 的红黑树调度
- 无法保证任务的响应时间上限
- 长睡眠任务唤醒后可能获得过长的执行时间
EEVDF (Earliest Eligible Virtual Deadline First)：
- 在 CFS 基础上引入虚拟截止时间 (virtual deadline)
- 保证任务在截止时间内获得 CPU
- 提供更好的延迟保证
14.1.2 EEVDF 核心概念
1
2
3
4
5
6
7
8
9
10
| EEVDF 关键概念:
1. 虚拟运行时间 (vruntime): 任务已获得的虚拟服务
2. 虚拟截止时间 (deadline): 任务应该完成的虚拟时间
3. 虚拟滞后 (vlag): 任务相对于公平服务的偏离
4. 时间片 (slice): 任务分配的执行时间
EEVDF 方程:
deadline = vruntime + slice
lag_i = S - s_i = w_i * (V - v_i)
|
14.1.3 滞后 (Lag) 概念
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
|
14.2 EEVDF 数据结构
14.2.1 sched_entity 扩展字段
位置： include/linux/sched.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| struct sched_entity {
struct load_weight load;
struct rb_node run_node;
u64 vruntime;
u64 exec_start;
u64 sum_exec_runtime;
u64 deadline;
u64 min_vruntime;
s64 vlag;
u64 slice;
unsigned char rel_deadline;
unsigned char custom_slice;
unsigned char sched_delayed;
};
|
14.2.2 cfs_rq 扩展字段
1
2
3
4
5
6
7
8
9
10
11
12
13
| struct cfs_rq {
struct rb_root_cached timeline;
u64 min_vruntime;
u64 avg_vruntime;
unsigned long avg_load;
struct sched_entity *curr;
struct sched_entity *next;
};
|
14.3 虚拟时间与滞后
14.3.1 平均虚拟时间
位置： kernel/sched/fair.c
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
|
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)
avg = 0;
else
avg = div_s64(avg, load);
return cfs_rq->min_vruntime + avg;
}
static void avg_vruntime_add(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;
}
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;
}
|
14.3.2 滞后计算
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
|
static s64 entity_lag(u64 avruntime, struct sched_entity *se)
{
s64 vlag, limit;
vlag = avruntime - se->vruntime;
limit = calc_delta_fair(max_t(u64, 2*se->slice, TICK_NSEC), se);
return clamp(vlag, -limit, limit);
}
static void update_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
SCHED_WARN_ON(!se->on_rq);
se->vlag = entity_lag(avg_vruntime(cfs_rq), se);
}
|
14.3.3 滞后的物理意义
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 滞后示意图:
理想服务线 (平均 vruntime)
│
│
│ 任务 A (vlag < 0)
│ ╱──── (获得了超额服务)
│ ╱
──────┼──╱──────────────────────
│ ╱
│╱ 任务 B (vlag ≈ 0)
│ (正常服务)
│
│
│ 任务 C (vlag > 0)
│ ╲
│ ╲──── (服务不足)
│
└──────────────────────────→ vruntime
EEVDF 目标:
- 让 vlag > 0 的任务优先运行
- 保持 Sum(lag_i) = 0
|
14.4 任务放置 (place_entity)
14.4.1 放置策略
位置： kernel/sched/fair.c
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
|
static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
u64 vslice, 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_running) {
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 (sched_feat(PLACE_REL_DEADLINE) && 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;
}
|
14.4.2 放置策略图解
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
| 任务放置到 EEVDF timeline:
初始放置 (ENQUEUE_INITIAL):
│
│ V = avg_vruntime
│
──────┼──────────────────────────
│
│ 新任务: vruntime = V - 0.5*slice
│ deadline = vruntime + slice
│
└──────────────────────────→ vruntime
唤醒放置 (保留滞后):
│
│ V = avg_vruntime
│
──────┼──────────────────────────
│
│ 正滞后任务: vruntime = V - lag (lag > 0)
│ 被优先调度
│
│ 负滞后任务: vruntime = V - lag (lag < 0)
│ 较晚被调度
│
└──────────────────────────→ vruntime
|
14.5 权重调整 (reweight)
14.5.1 reweight_eevdf
位置： kernel/sched/fair.c
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
|
static void reweight_eevdf(struct sched_entity *se, u64 avruntime,
unsigned long weight)
{
unsigned long old_weight = se->load.weight;
s64 vlag, vslice;
if (!se->on_rq) {
vlag = se->vlag;
vlag = div_s64(vlag * old_weight, weight);
se->vruntime = avruntime - vlag;
} else {
}
se->load.weight = weight;
se->load.inv_weight = 0;
vslice = calc_delta_fair(se->slice, se);
se->deadline = se->vruntime + vslice;
}
|
14.6 EEVDF 调度流程
14.6.1 任务选择
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
|
static struct sched_entity *pick_next_entity(struct rq *rq,
struct cfs_rq *cfs_rq)
{
struct sched_entity *se;
se = __pick_first_entity(cfs_rq);
if (!se)
return NULL;
if (cfs_rq->skip == se) {
struct sched_entity *second;
if (se == cfs_rq->curr)
second = __pick_first_entity(cfs_rq);
else
second = __pick_next_entity(se);
if (second && wakeup_preempt_entity(second, se) < 1)
se = second;
}
return se;
}
|
14.6.2 实体比较
1
2
3
4
5
6
7
8
9
|
static inline bool entity_before(const struct sched_entity *a,
const struct sched_entity *b)
{
return (s64)(a->deadline - b->deadline) < 0;
}
|
14.6.3 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
| EEVDF Timeline (按 deadline 排序):
┌─────────────────────────────────────────────────────────────┐
│ cfs_rq->timeline │
│ (rb_root_cached) │
└─────────────────────────────────────────────────────────────┘
│
↓
┌────────────────────────────────────┐
│ 左子树 │
│ deadline 较大 (较晚截止) │
└────────────────────────────────────┘
│
┌────────────────────────────────────┐
│ rb_leftmost │ ← 最小 deadline
│ (下一个被调度任务) │ (最早截止)
│ se->deadline = min_deadline │
│ se->vruntime 可能较大 │
└────────────────────────────────────┘
│
┌────────────────────────────────────┐
│ 右子树 │
│ deadline 最大 (最晚截止) │
└────────────────────────────────────┘
关键区别:
- CFS: 按 vruntime 排序
- EEVDF: 按 deadline 排序
- deadline = vruntime + slice
- 所以 EEVDF 考虑了任务的紧急程度
|
14.7 EEVDF 特性控制
14.7.1 SCHED_FEAT 开关
位置： kernel/sched/features.h
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
|
SCHED_FEAT(PLACE_LAG, true)
SCHED_FEAT(PLACE_DEADLINE_INITIAL, true)
SCHED_FEAT(PLACE_REL_DEADLINE, true)
SCHED_FEAT(RUN_TO_PARITY, true)
SCHED_FEAT(PREEMPT_SHORT, true)
SCHED_FEAT(DELAY_DEQUEUE, true)
SCHED_FEAT(DELAY_ZERO, true)
SCHED_FEAT(WAKEUP_PREEMPTION, true)
|
14.7.2 调试特性开关
1
2
3
4
5
6
7
8
|
$ cat /sys/kernel/debug/sched/features
$ echo NO_PLACE_LAG > /sys/kernel/debug/sched/features
$ echo PLACE_LAG > /sys/kernel/debug/sched/features
|
14.8 EEVDF vs 纯 CFS 对比
14.8.1 关键区别
| 特性 |
纯 CFS |
EEVDF |
| 排序键 |
vruntime |
deadline = vruntime + slice |
| 选择策略 |
最小 vruntime |
最小 deadline |
| 延迟保证 |
无 |
有 (通过 deadline) |
| 滞后处理 |
简单 |
复杂 (vlag 计算) |
| 新任务放置 |
平均 vruntime |
平均 vruntime - lag |
| 时间片 |
独立计算 |
影响 deadline |
14.8.2 调度场景对比
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| 场景: 三个任务，权重不同
任务 A: weight=1024 (nice 0), vruntime=1000
任务 B: weight=512 (nice 10), vruntime=1200
任务 C: weight=256 (nice 15), vruntime=800
纯 CFS (按 vruntime 排序):
1. C (vruntime=800)
2. A (vruntime=1000)
3. B (vruntime=1200)
EEVDF (按 deadline 排序, slice=100):
A: deadline = 1000 + 100*1024/1024 = 1100
B: deadline = 1200 + 100*1024/512 = 1400
C: deadline = 800 + 100*1024/256 = 1200
1. A (deadline=1100)
2. C (deadline=1200)
3. B (deadline=1400)
差异:
- CFS 优先服务 vruntime 小的任务
- EEVDF 优先服务 deadline 小的任务
- EEVDF 考虑了任务的紧急程度
|
14.9 延迟出队 (DELAY_DEQUEUE)
14.9.1 延迟出队机制
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
|
static void dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
update_curr(cfs_rq);
if (sched_feat(DELAY_DEQUEUE) && !(flags & DEQUEUE_SLEEP)) {
se->sched_delayed = 1;
return;
}
if (se != cfs_rq->curr)
__dequeue_entity(cfs_rq, se);
if (sched_feat(DELAY_ZERO) && (flags & DEQUEUE_SLEEP))
se->vlag = 0;
}
|
14.9.2 重新入队
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
static void requeue_delayed_entity(struct sched_entity *se)
{
struct cfs_rq *cfs_rq = cfs_rq_of(se);
if (!se->sched_delayed)
return;
se->sched_delayed = 0;
update_entity_lag(cfs_rq, se);
place_entity(cfs_rq, se, 0);
if (entity_eligible(cfs_rq, se))
enqueue_entity(cfs_rq, se, ENQUEUE_WAKEUP);
}
|
14.10 EEVDF 监控
14.10.1 查看调度实体信息
1
2
3
4
5
6
7
8
|
$ bpftrace -e '
tracepoint:sched:sched_switch {
$prev = args[0]->prev_pid;
$next = args[0]->next_pid;
printf("switch: %d -> %d\n", $prev, $next);
}
'
|
14.10.2 调试参数
1
2
3
4
5
6
|
$ cat /proc/sched_debug
$ cat /proc/[pid]/sched
|
14.11 本章小结
本章详细介绍了 Linux EEVDF 调度器：
- EEVDF 概念：在 CFS 基础上引入虚拟截止时间
- 滞后计算：lag_i = S - s_i = w_i * (V - v_i)
- 平均虚拟时间：avg_vruntime 加权平均计算
- 任务放置：保留滞后，初始任务给半片
- 权重调整：reweight_eevdf 保持滞后不变
- 调度流程：按 deadline 而非 vruntime 排序
- 特性控制：PLACE_LAG, DELAY_DEQUEUE 等
- 延迟出队：任务保持在竞争中燃烧滞后
EEVDF 是 Linux 6.12 中 CFS 的默认实现模式，提供了更好的延迟保证和公平性。
