Linux►Kernel

调度算法原理详解（深入版）

调度算法原理详解（深入版）

源码路径：rk3588/kernel-6.1/kernel/sched/
内核版本：Linux 6.1（RK3588 / arm64）
关联文档：sched调度机制与原理详解.md · 上下文切换与状态保存详解.md

本文从算法与数学模型层面详细描述 Linux 6.1 调度器：公式、数据结构、逐步算法、数值示例、边界条件及 SMP 扩展。阅读时可对照 fair.c / rt.c / deadline.c / pelt.c 源码（搜索 【 可定位中文注释）。

目录

符号与约定

符号 含义
w / weight CFS 权重，nice 0 时为 NICE_0_LOAD = 1024
vruntime 虚拟运行时间（ns），CFS 公平性核心
delta_exec 本次实际运行时间（ns）
period / P CFS 调度周期或 DL 任务周期
slice CFS 物理时间片（ns）
C, T, D DL 任务 runtime、period、deadline（ns）
prio 内核优先级，数值越小优先级越高（RT/DL）
util_avg PELT 利用率，1024 = 100% 单核

一、CFS 完全公平调度算法

策略：SCHED_NORMAL / SCHED_OTHER / SCHED_BATCH / SCHED_IDLE
文件：fair.c · 调度类：fair_sched_class

1.1 理论背景：加权公平队列（WFQ）

CFS 可视为 Weighted Fair Queueing 的近似实现：

  • 理想目标：每个任务 i 在窗口 T 内获得 CPU 时间 T × (w_i / Σw_j)
  • 实现手段：维护虚拟时间 vruntime，始终让 vruntime 最小的任务运行
  • 与传统固定时间片轮转的区别：时间片随任务数和权重动态变化，无全局固定 quantum

1.2 权重与 nice 映射

nice 范围 -20 ~ +19，对应 prio_to_weight[] 查表：

nice weight（约） 相对 nice 0 的 CPU 份额
-20 88761 ~86.7×
-10 9548 ~9.3×
0 1024 1×（基准）
+10 110 ~0.11×
+19 15 ~0.015×

用户态 nice(2) / setpriority() 修改的是 动态优先级 static_prio，CFS 将其映射为 load.weight。

1.3 vruntime 更新公式（核心）

任务运行 delta_exec 纳秒后：

1
2
3
Δvruntime = calc_delta_fair(delta_exec, se)
          = delta_exec × (NICE_0_LOAD / se.load.weight)    // weight ≠ 1024 时
          = delta_exec                                      // weight = 1024 时

update_curr() 完整步骤（每次 tick、切换、入队前）：

1
2
3
4
5
6
1. delta_exec = rq_clock_task() - curr->exec_start
2. curr->exec_start = now
3. curr->sum_exec_runtime += delta_exec          // 累计物理 CPU 时间
4. curr->vruntime += calc_delta_fair(delta_exec, curr)
5. update_min_vruntime(cfs_rq)                   // 推进队列基准
6. account_cfs_rq_runtime(cfs_rq, delta_exec)  // cgroup 配额统计

数值示例：两任务公平性

假设 nice 0（w=1024）与 nice 10（w≈110）同队列运行：

事件 Task A (nice 0) Task B (nice 10)
各跑 10ms 物理时间 vruntime += 10ms vruntime += 10ms × (1024/110) ≈ 93ms
谁更该运行？ vruntime 较小者先运行 B 的 vruntime 涨得快 → A 更容易被选中
长期比例 A 获得 CPU ≈ 1024/(1024+110) ≈ 90% B ≈ 10%

这与权重比例 w_A : w_B 一致。

1.4 min_vruntime 与 vruntime 归一化

min_vruntime 更新

1
min_vruntime = max(旧 min_vruntime, leftmost.vruntime, curr.vruntime)

作用：

  1. 新任务放置基准：防止 vruntime=0 的新任务长期霸占 CPU
  2. 跨 CPU 迁移：出队/入队时做加减归一化

跨 rq 迁移规则（enqueue_entity / dequeue_entity）

1
2
3
4
5
6
7
8
9
10
出队（dequeue）:
    update_curr()
    update_min_vruntime()
    se->vruntime -= cfs_rq->min_vruntime    // 存相对值

入队（enqueue）:
    update_curr()
    update_min_vruntime()
    se->vruntime += cfs_rq->min_vruntime    // 加目标 rq 基准
    place_entity()                          // 唤醒时再调整

保证不同 CPU 上 vruntime 可比，且迁移瞬间 min_vruntime 已在两侧同步更新。

1.5 调度周期与时间片（详细）

周期 period

1
2
3
4
5
6
7
sched_nr_latency = sched_latency / sched_min_granularity    // 默认 6ms/0.75ms = 8

__sched_period(nr_running):
    if nr_running > sched_nr_latency:
        return nr_running × sched_min_granularity   // 扩展周期，避免 slice 过小
    else:
        return sched_latency                          // 默认 6ms × (1 + ilog2(ncpus))

RK3588 8 核示例（ilog2(8)=3）：

1
2
3
4
5
6
sched_latency           = 6ms × 4 = 24ms
sched_min_granularity   = 0.75ms × 4 = 3ms
sched_nr_latency        = 8

若 nr_running = 4：  period = 24ms
若 nr_running = 16： period = 16 × 3ms = 48ms（而非 24ms）

时间片 slice

1
2
3
4
5
6
sched_slice(cfs_rq, se):
    period = __sched_period(nr_running)
    slice  = period × (se.weight / cfs_rq.load.weight)

    // cgroup 层次：沿 for_each_sched_entity(se) 逐层按比例切分
    // BASE_SLICE：slice = max(slice, sched_min_granularity)

数值示例：period=24ms，3 个 nice 0 任务（各 w=1024，总 weight=3072）：

1
每人 slice = 24ms × (1024/3072) = 8ms

若其中 1 个 nice 10（w=110），总 weight=2134：

1
2
nice 0 任务 slice ≈ 24ms × (1024/2134) ≈ 11.5ms
nice 10 任务 slice ≈ 24ms × (110/2134) ≈ 1.2ms → 钳位到 min_granularity 3ms

vslice（虚拟时间片）

1
sched_vslice(cfs_rq, se) = calc_delta_fair(sched_slice(cfs_rq, se), se)

用于 place_entity(START_DEBIT) 预扣一片，以及 tick 抢占比较。

1.6 place_entity：vruntime 放置（完整规则）

1
2
3
4
5
6
7
8
9
10
11
12
13
// fair.c: place_entity(cfs_rq, se, initial)
vruntime = cfs_rq->min_vruntime;

if (initial && START_DEBIT):
    vruntime += sched_vslice(cfs_rq, se);     // fork：预扣一片，不立刻抢占父进程

if (!initial):                                 // 唤醒
    thresh = (SCHED_IDLE) ? min_granularity : sched_latency;
    if (GENTLE_FAIR_SLEEPERS): thresh >>= 1;  // 睡眠补偿减半，更温和
    vruntime -= thresh;                         // 向前借 vruntime，补偿 sleep

se->vruntime = max_vruntime(se->vruntime, vruntime);
// 超长睡眠任务 entity_is_long_sleeper：直接用 vruntime，防 s64 溢出
场景 initial 效果
fork 1 vruntime = min + vslice，新任务略”吃亏”
唤醒 0 vruntime 最多向前借 latency（或一半），IO 完成后更快运行
迁移唤醒 0 + MIGRATED exec_start 清零，cache 不视为 hot

1.7 红黑树与 enqueue / dequeue

数据结构

1
2
3
4
5
6
7
8
struct cfs_rq {
    struct rb_root_cached  tasks_timeline;  // vruntime 排序
    struct sched_entity   *curr;            // 当前运行，不在树中
    u64                    min_vruntime;
    struct sched_entity   *next, *last, *skip;  // buddy
    unsigned int           nr_running;
    u64                    load;              // 总 weight
};

enqueue_entity 逐步算法

1
2
3
4
5
6
7
8
1. 若 WAKEUP/MIGRATED：renorm vruntime += min_vruntime
2. update_curr(cfs_rq)
3. 若非 curr：renorm vruntime += min_vruntime
4. update_load_avg()           // PELT
5. account_entity_enqueue()    // nr_running++, load.weight += se.weight
6. 若 ENQUEUE_WAKEUP：place_entity(se, 0)
7. 若 !curr：__enqueue_entity() 插入红黑树
8. se->on_rq = 1

dequeue_entity 要点

1
2
3
4
5
1. update_curr()
2. 若 WAKEUP/MIGRATED：vruntime -= min_vruntime（归一化）
3. 若 se != curr：从树移除
4. update_load_avg(DO_DETACH)
5. account_entity_dequeue()

set_next_entity / put_prev_entity

1
2
3
4
5
6
7
8
set_next_entity（选中运行）:
    __dequeue_entity()     // curr 移出树
    exec_start = now
    cfs_rq->curr = se

put_prev_entity（停止运行）:
    if (on_rq): update_curr(); __enqueue_entity()  // 插回树
    cfs_rq->curr = NULL

1.8 pick_next_entity（完整优先级）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1. left = 红黑树最左（vruntime 最小）
2. 若 curr 存在且 entity_before(curr, left)：left = curr
3. se = left

4. 若 skip buddy 存在且 skip 不是 left：
       尝试选 __pick_next_entity(skip) 作为 second
       若 second 存在且 wakeup_preempt_entity(second, left) < 1：
           se = second                    // 跳过 yield 标记的任务

5. 若 next buddy 且 wakeup_preempt_entity(next, left) <= 0：
       se = next                          // 刚唤醒，cache 热
6. else 若 last buddy 且 wakeup_preempt_entity(last, left) <= 0：
       se = last                          // 刚被抢占，cache 热

7. return se

wakeup_preempt_entity(a, b) 返回值：

1
2
3
4
vdiff = a.vruntime - b.vruntime
vdiff <= 0  → -1  （a 不应抢占 b，a 的 vruntime 更大或相等）
vdiff > gran →  1  （a 应抢占 b）
else         →  0  （差距不够，不抢占）

1.9 三类抢占（详细条件）

（1）Tick 抢占 — check_preempt_tick

1
2
3
4
5
6
7
8
9
10
11
12
13
ideal_runtime = sched_slice(cfs_rq, curr)
delta_exec    = curr.sum_exec_runtime - curr.prev_sum_exec_runtime

条件 A：delta_exec > ideal_runtime
    → resched_curr(); clear_buddies(); return

条件 B：delta_exec < min_granularity
    → return（运行太短，不抢占）

条件 C：leftmost = __pick_first_entity()
         delta = curr.vruntime - leftmost.vruntime
         delta > ideal_runtime
    → resched_curr()（curr vruntime 已领先太多，该让 leftmost 运行）

条件 C 防止 wake 抢占 narrowly missed 时还要等满一个 slice。

（2）唤醒抢占 — check_preempt_wakeup

1
2
3
4
5
6
7
8
9
1. 若 cgroup throttle：return
2. 若 nr_running >= sched_nr_latency：set_next_buddy(wakee)
3. 若 curr 已有 TIF_NEED_RESCHED：return
4. 若 curr 是 IDLE 策略且 wakee 不是：preempt
5. 若 wakee 是 BATCH 或 WAKEUP_PREEMPTION 关闭：return（靠 tick 驱动）
6. update_curr()
7. 若 wakeup_preempt_entity(curr, wakee) == 1：
       set_next_buddy(wakee); resched_curr()
8. 若 LAST_BUDDY：set_last_buddy(curr)（被抢占者标记 cache hot）

wakeup_gran(se) ≈ sysctl_sched_wakeup_granularity 按 weight 缩放，高权重任务 gran 更大（更难被抢占）。

（3）主动让出 — yield_task_fair

1
2
3
set_skip_buddy(curr)           // 标记 skip
若 curr 仍在树中：requeue
resched_curr()

下次 pick_next_entity 会尽量跳过 skip buddy。

1.10 CFS Bandwidth Control（cgroup CPU 配额）

1
2
3
4
5
6
7
8
9
10
11
cfs_bandwidth：
    quota  = 每 period 允许运行的 ns（如 50000us）
    period = 统计周期（如 100000us）

运行时：account_cfs_rq_runtime(cfs_rq, delta_exec)
超限：throttle_cfs_rq() → 组内任务 dequeue，hrtimer 下一 period 解除

与 vruntime 关系：
    - quota 是硬上限（cgroup 层面）
    - vruntime 是组内/全局公平（权重层面）
    二者独立同时生效

1.11 SCHED_BATCH / SCHED_IDLE

策略 算法差异
SCHED_BATCH check_preempt_wakeup 直接 return；减少 wake 抢占；倾向连续运行
SCHED_IDLE 极低 weight；se_is_idle() 路径；sched_idle_min_granularity；仅当无正常 CFS 任务时运行

1.12 CFS 完整生命周期示例

场景：Task X read() 阻塞，IO 完成后唤醒。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1. read() 阻塞 → schedule() → deactivate_task(DEQUEUE_SLEEP)
   put_prev_entity → update_curr → 插回红黑树

2. IO 完成 → try_to_wake_up(X)
   select_task_rq_fair() 选 CPU（可能 EAS）
   activate_task → enqueue_entity(ENQUEUE_WAKEUP)
     place_entity：vruntime -= latency（补偿 sleep）
   check_preempt_wakeup → 若 vdiff > gran → resched_curr

3. 内核抢占点 → __schedule()
   pick_next_entity → 可能选 next_buddy(X)
   context_switch → X 运行

4. 每个 tick → entity_tick → update_curr → check_preempt_tick
入队运行抢占是enqueue_entityrenorm vruntimeupdate_load_avg PELTplace_entity 唤醒补偿插入红黑树set_next_entity 出树运行 on CPUupdate_curr 累加 vruntimetick / wake / yieldcheck_preempt_*put_prev_entity 插回树pick_next_entity

二、RT 实时调度算法

策略：SCHED_FIFO / SCHED_RR
文件：rt.c · 调度类：rt_sched_class

2.1 优先级体系（易混淆点）

层级 范围 说明
用户 sched_param.sched_priority 1–99 sched_setscheduler() 传入
内核 task_struct->prio 0–99 数值越小优先级越高
映射 prio = MAX_RT_PRIO - 1 - user_prio 或等价变换

CFS 任务 prio = 120 + nice（约 100–139），永远低于 RT。

2.2 数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
struct rt_rq {
    struct rt_prio_array  active;     // active.queue[100] + active.bitmap
    unsigned int          rt_nr_running;
    u64                   rt_time;      // 本周期已运行 RT 时间
    int                   rt_throttled;
    struct rt_bandwidth   rt_bandwidth;
};

struct sched_rt_entity {
    struct list_head  run_list;       // 同优先级 FIFO 链
    unsigned long     timeout;        // RR 用
    struct sched_rt_entity *back;     // group scheduling
};

选任务 _pick_next_task_rt

1
2
3
4
5
6
7
8
rt_se = pick_next_rt_entity(&rq->rt):
    idx = find_first_bit(active.bitmap)     // 最高优先级非空档
    return list_first_entry(active.queue[idx])

若 CONFIG_RT_GROUP_SCHED：
    while (group_rt_rq(rt_se)):
        沿组层次向下递归 pick
return rt_task_of(rt_se)

复杂度：O(1)（bitmap 常数 100 + 链表头）。

2.3 SCHED_FIFO 详细行为

1
2
3
4
5
6
7
入队：enqueue_task_rt → 插入 active[prio] 链表尾部
运行：一直运行直到
  (a) sched_yield / 阻塞（mutex、wait）
  (b) 更高 prio RT 唤醒 → check_preempt_curr_rt
  (c) RT bandwidth 耗尽 → 整组 throttle
  (d) 更高调度类（DL）抢占
不出队：除非主动阻塞；不会因时间片到而轮转

2.4 SCHED_RR 详细行为

1
2
3
4
5
6
7
8
9
10
11
12
sched_rr_timeslice = RR_TIMESLICE / HZ ≈ 100ms（可 sysctl 调节）

fork/唤醒时：p->rt.time_slice = sched_rr_timeslice

task_tick_rt（每个 tick）:
    update_curr_rt()                    // 统计 + 带宽检查
    if (policy != SCHED_RR) return
    if (--time_slice > 0) return
    time_slice = sched_rr_timeslice
    if (同优先级队列中不只有自己):
        requeue_task_rt()               // 移到队尾
        resched_curr()

同优先级多任务 RR 时间线（prio=50，slice=100ms）：

1
2
3
4
T0: Task1 运行
T100ms: tick → Task1 队尾，Task2 运行
T200ms: Task2 队尾，Task1 运行
...

2.5 update_curr_rt 与带宽 throttle

1
2
3
4
5
6
7
8
9
10
11
update_curr_rt():
    delta_exec = now - exec_start
    exec_start = now

    for each rt_rq in hierarchy:
        rt_rq->rt_time += delta_exec
        if sched_rt_runtime_exceeded(rt_rq):
            rt_rq->rt_throttled = 1
            sched_rt_rq_dequeue()       // 整组 RT 出队
            do_start_rt_bandwidth()     // hrtimer 下一 period
            resched_curr()

sched_rt_runtime_exceeded

1
2
3
4
5
6
runtime_limit = sched_rt_runtime_us（默认 950ms）
period        = sched_rt_period_us（默认 1s）

if rt_rq->rt_time > runtime_limit:
    rt_throttled = 1
    return 1

效果：每 1 秒窗口内 RT 最多跑 950ms，剩余 ≥50ms 给 CFS/idle，防锁死。

2.6 SMP：RT 迁移（cpupri + push/pull）

1
2
3
4
5
6
7
8
9
10
11
12
问题：多 RT 任务挤在同一 CPU，其他核空闲

cpupri：
    每个 CPU 记录该核 RT 队列最高 prio
    cpupri_find() O(1) 找能运行 p 的最低 prio CPU

push：
    put_prev_task_rt → enqueue_pushable_task()
    RT push IPI → 目标核 pull_rt_task()

pull：
    空闲核 balance_rt() 从 busy 核拉 RT 任务

2.7 RT 与 CFS/DL 关系

1
2
3
4
5
选任务顺序：stop > dl > rt > fair > idle

RT 运行中：
    CFS 任务无法被选中（除非 RT throttle 且 DL 为空）
DL 任务 deadline 更早者可以抢占 RT（动态 prio 计算）

三、Deadline 调度算法（EDF + CBS）

策略：SCHED_DEADLINE
文件：deadline.c · 调度类：dl_sched_class

3.1 任务模型与参数

通过 sched_setattr() 设置 struct sched_attr：

字段 符号 含义
sched_runtime C 每个 job 需要的 CPU 时间（预算，ns）
sched_period T 任务周期（ns）
sched_deadline D 相对 deadline（ns），通常 D ≤ T

语义：每 T 时间内需完成 C 单位 CPU 工作；每个 job 须在绝对 deadline 前完成。

参数示例

1
2
3
C = 2ms, T = 10ms, D = 10ms（implicit deadline，D = T）
→ 带宽 U = C/T = 20%
→ 每 10ms 窗口至少跑 2ms CPU，否则 miss deadline
1
2
C = 3ms, T = 10ms, D = 5ms（constrained deadline，D < T）
→ 更紧的 deadline，带宽仍 U = 30%，但 job 须 5ms 内完成

3.2 EDF（Earliest Deadline First）

1
2
3
4
5
dl_rq 红黑树按 sched_dl_entity.deadline（绝对时间）升序

pick_next_task_dl():
    se = 树中 deadline 最小的实体
    return task_of(se)

单核最优性：若任务集在单核上可调度，EDF 可找到可行调度（利用率 ≤ 100% 时）。

动态内核 prio：

1
2
dl_prio(deadline) = MAX_DL_PRIO - 1 - (deadline >> DL_SCALE)
deadline 越早 → prio 数值越小 → 优先级越高

3.3 运行时：update_curr_dl

1
2
3
4
5
6
7
8
9
now = rq_clock_task(rq)
delta_exec = now - dl_se->exec_start
exec_start = now

dl_se->runtime -= delta_exec          // 消耗当前 job 预算

if (runtime <= 0):
    __dequeue_dl_entity()             // throttle，移出运行队列
    start_dl_timer()                  // hrtimer 在 deadline 触发 replenish

3.4 CBS（Constant Bandwidth Server）详解

设计动机

纯 EDF 下，任务 overrun（跑超 C）会推迟后续 job 的 deadline，可能拖累其他任务。CBS 保证每个任务带宽不超过 U = C/T，overrun 只影响自身。

replenish_dl_entity（预算补充）

1
2
3
4
5
6
7
8
while (runtime <= 0):
    deadline += dl_period              // 推迟绝对 deadline
    runtime  += dl_runtime             // 补充预算

if (deadline < rq_clock):             // 滞后过多
    replenish_dl_new_period()          // 重置：deadline = now + D, runtime = C

dl_throttled = 0

关键：overrun 时通过 deadline += period 把任务「推」到未来，而非无限占用 CPU。

唤醒规则 update_dl_entity

1
2
3
4
5
6
7
8
if (deadline 已过期 || dl_entity_overflow(now)):

    if (constrained deadline: D < T) && !implicit && !boosted:
        update_dl_revised_wakeup()     // Revised CBS：缩减 runtime，不超 U
    else:
        replenish_dl_new_period()      // Original CBS
            deadline = now + D
            runtime  = C

overflow 判定 dl_entity_overflow

概念上检查：

1
runtime / (deadline - now)  >  dl_runtime / dl_deadline

即：剩余预算相对剩余时间的比例超过声明带宽 → 不能沿用当前 deadline/runtime，必须 replenish 或 revised wakeup。

3.5 准入控制（Admission Control）

1
2
3
4
5
6
7
8
root_domain->dl_bw 维护系统 DL 总带宽

新任务入队前：
    Σ (C_i / T_i) + C_new/T_new  <=  GLOBAL_DL_BW

GLOBAL_DL_BW 默认约为 0.95 × 总 CPU 容量（留 5% 给 CFS）

sched_setattr() 失败 → EINVAL，防止不可调度任务集

3.6 完整 CBS 时间线示例

任务：C=2ms, T=10ms, D=10ms，t=0 启动。

1
2
3
4
5
6
t=0ms:   enqueue, deadline=10ms, runtime=2ms, 开始运行
t=2ms:   runtime=0, throttle 出队, 启动 timer(deadline=10ms)
t=2~10ms: 不运行（即使 CPU 空闲，CBS 限速；除非 GRUB 回收策略）
t=10ms:  hrtimer → replenish: deadline=20ms, runtime=2ms, 重新入队
t=10ms:  若 EDF 最高则运行
...

若 t=0~3ms 跑满 3ms（overrun 1ms）：

1
2
3
4
t=3ms:   runtime=-1ms → replenish 循环：
           deadline: 10→20ms, runtime: -1+2=1ms
         继续跑 1ms 至 runtime=0
→ 总占用 3ms，但 deadline 被推到 20ms，带宽仍 ≤ C/T
CBSdl_rqDL JobCBSdl_rqDL Jobloop[每次 update_curr_dl]等待至 deadlineenqueue(deadline=D0, runtime=C)EDF 选中运行runtime -= deltaruntime<=0 throttlehrtimer(deadline)replenish deadline+=T runtime+=C重新入队竞争

3.7 DL 与 RT/CFS 优先级

1
2
3
4
5
6
调度类链：stop > dl > rt > fair

同 CPU 上：
    DL 任务按 deadline 与 RT prio 动态比较
    DL 通常高于 CFS
    多个 DL 任务之间纯 EDF

四、PELT 负载跟踪算法

文件：pelt.c · 头文件：sched.h / pelt.h

4.1 数学模型

将历史负载表示为几何级数：

1
2
3
4
load_avg = u_0 + u_1·y + u_2·y² + u_3·y³ + ...

y = 0.5^(1/32)  ≈ 0.9786
y^32 = 0.5      →  约 32ms 前的贡献权重减半

时间轴按 1024μs（≈1ms） 分段：

1
2
3
[--1024us--][--1024us--][--1024us--]...
    p0          p1          p2
  (当前)     (~1ms前)    (~2ms前)

u_i = 第 i 段内实体可运行比例 × 权重（load）或运行比例（util）。

4.2 三个平均值

字段 计算来源 用途
load_sum → load_avg runnable × weight CFS 迁移权重
runnable_sum → runnable_avg 是否 runnable 负载均衡 imbalance
util_sum → util_avg 是否 actually running schedutil 调频、EAS、misfit

转换（简化）：

1
2
load_avg = load_sum × load_avg_inv >> LOAD_AVG_SHIFT
util_avg = util_sum × LOAD_AVG_MAX >> SCHED_CAPACITY_SHIFT   // 1024 = 100%

4.3 accumulate_sum 逐步算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入：delta（ns）, load, runnable, running 标志

1. delta += period_contrib
2. periods = delta / 1024
3. if periods > 0:
       load_sum     = decay_load(load_sum, periods)
       runnable_sum = decay_load(runnable_sum, periods)
       util_sum     = decay_load(util_sum, periods)
       delta %= 1024
       contrib = __accumulate_pelt_segments(periods, ...)  // 跨段几何求和
4. period_contrib = delta
5. load_sum     += load * contrib
6. runnable_sum += runnable * contrib << SCHED_CAPACITY_SHIFT
7. util_sum     += running * contrib << SCHED_CAPACITY_SHIFT

4.4 decay_load O(1) 实现

1
2
3
4
5
6
decay_load(val, n):
    if n >= 32*63: return 0
    val >>= n / 32              // 每 32 period 减半
    n %= 32
    val = val * yN_inv[n] >> 32 // 余数查表
    return val

避免 O(n) 循环，tick 路径高效。

4.5 更新时机与意义

事件 更新
enqueue_entity DO_ATTACH，runnable 增加
dequeue_entity DO_DETACH
update_curr / entity_tick running 贡献 util
migration 双方 rq 的 cfs_rq avg

物理含义：util_avg=512 ≈ 该 task 近期平均占用 50% 单核算力（已按 CPU capacity 缩放）。

五、SMP 负载均衡算法

文件：fair.c（load_balance）、topology.c

5.1 sched_domain 层次（RK3588）

1
2
3
DIE 域（8 CPUs，全芯片）
  └── MC 域（4 CPUs，同 cluster：A76×4 或 A55×4）
        └── CPU 域（单逻辑 CPU）

域标志：

标志 含义
SD_LOAD_BALANCE 允许本层 load balance
SD_ASYM_CPUCAPACITY 非对称容量（big.LITTLE）
SD_SHARE_CPUCAPACITY 共享 L2/L3 cache
SD_WAKE_AFFINE 唤醒亲和

5.2 负载不平衡度量

1
2
3
4
5
6
load = runnable_avg（或 misfit 时用 util）

imbalance = busiest_load - dst_load
         （经 capacity 缩放、group 权重、NUMA 因子 adjust）

目标：使各 CPU load/capacity 趋于均衡

5.3 load_balance 完整步骤

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
load_balance(this_cpu, sd, idle_type):

1. should_we_balance(env)
       - 本 CPU 是否 busy/idle 符合 idle_type
       - 域 busy_idx 与 idle_idx 是否有效
       - nohz 平衡是否允许

2. find_busiest_group(env)
       遍历 sched_group，算 group_load / group_capacity
       选 load 最高且超过阈值的组

3. find_busiest_queue(env, group)
       组内找 load 最高的 rq

4. detach_tasks(env)
       从 busiest 摘下可迁移任务（can_migrate_task）
       最多 sysctl_sched_nr_migrate 个
       任务标记 TASK_ON_RQ_MIGRATING

5. attach_tasks(env)
       挂到 this_rq，触发 remote enqueue

6. 若 active_balance 仍不平衡：
       stop_one_cpu_nowait(busiest, active_balance)
       在 busy 核上强制 push

5.4 can_migrate_task 约束

1
2
3
4
5
- cpus_allowed 掩码
- cache_hot：刚运行任务不迁移（除非 idle balance 紧急）
- nr_running：busy 核仅 1 个任务时不 pull（避免 ping-pong）
- misfit：高 util 任务在小核 → 优先迁大核
- throttled cgroup 任务不迁移

5.5 触发路径

路径 函数 场景
周期 tick scheduler_tick → trigger_load_balance → rebalance_domains 每 ~4ms softirq
newidle newidle_balance CPU 即将 idle 前主动 pull
唤醒 select_task_rq_fair 选 CPU，非严格 load_balance
active active_balance misfit / 持续不平衡

5.6 wake_affine

1
2
3
4
5
唤醒时 select_task_rq_fair:
    if (prev_cpu 空闲 && wake_affine 域标志 && sync 唤醒):
        倾向 prev_cpu（L1/L2 cache 仍热）
    else:
        find_idlest_cpu / find_energy_efficient_cpu

六、EAS 能耗感知选核算法

文件：fair.c：find_energy_efficient_cpu
平台：RK3588 4×A76 + 4×A55

6.1 启用条件（全部满足）

  1. root_domain->pd（Energy Model perf_domain）非空
  2. !rd->overutilized（系统未全局过载）
  3. cpufreq 为 schedutil
  4. 存在 SD_ASYM_CPUCAPACITY 调度域
  5. EM 复杂度 < EM_MAX_COMPLEXITY（2048）

6.2 算法逐步（find_energy_efficient_cpu）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
输入：task p, prev_cpu

1. 若 !pd || overutilized || util_est=0 && uclamp_min=0 → fallback

2. sync_entity_load_avg(&p->se)
   eenv_task_busy_time(&eenv, p, prev_cpu)

3. for each perf_domain pd（A76 域、A55 域）:
       for each cpu in pd:
           util = cpu_util_next(cpu, p)      // 预测放置 p 后的 util
           if !util_fits_cpu(util, uclamp):  // 容量不够则 skip
               continue
           spare_cap = capacity - util
           记录 max_spare_cap_cpu

       base_energy = compute_energy(prev_cpu, pd)
       for candidate in pd:
           cur_delta = compute_energy(candidate) - base_energy
           选 cur_delta 最小的 candidate

4. 在 prev_cpu 与 best_energy_cpu 间比较 energy_delta
5. return 能耗增量最小的 CPU

6.3 compute_energy 概念

1
2
3
4
5
6
7
Energy = Σ_cpu  power(freq(cpu)) × time

power 来自 Energy Model 表（频率-功耗曲线）
freq 由预测 util 经 schedutil 映射

迁移收益 = E(run on candidate) - E(run on prev_cpu)
选 ΔE 最小（或为负且绝对值最大）的核

6.4 RK3588 典型决策

任务 util 典型选择 原因
低（<512） A55 小核能效高
高（>512） A76 A55 capacity 不足，misfit
中 比较 ΔE EAS 能量差决定 
1
cpu_capacity: A76 ≈ 1024, A55 ≈ 512（相对值，arch_scale_cpu_capacity）

七、Idle / Stop 调度

7.1 idle_sched_class（idle.c）

1
2
3
4
5
6
7
每 CPU 一个 idle 线程，非 SCHED_IDLE 策略

do_idle() 循环:
    cpuidle_idle_call() 或 poll
    if need_resched: schedule_idle()

仅当 fair/rt/dl 均无 runnable 时被 pick_next_task 选中

7.2 stop_sched_class（stop_task.c）

1
2
3
stop_machine 等内核操作使用
绝对最高优先级，不抢占、不让出、不迁移
pick_next_task_stop → rq->stop

八、算法对比与选型

维度 CFS RT Deadline
目标 比例公平 + 交互响应 低延迟确定性 周期 deadline 保证
优先级 动态 vruntime 静态 1–99 动态 deadline
数据结构 vruntime 红黑树 100 级 bitmap+FIFO deadline 红黑树
时间模型 动态 slice RR: ~100ms 固定 C/T 预算周期
带宽限制 cgroup quota 950ms/s 全局 CBS + 准入 95%
抢占 gran + tick 立即（高 prio） 更早 deadline
过载行为 公平分摊 throttle 全 RT CBS 推迟 deadline
SMP PELT + LB + EAS cpupri push/pull cpudl 迁移
典型用例 普通 App 音视频 pipeline 工业控制、PLC

选型建议

1
2
3
4
普通线程 / 99% 场景     → SCHED_OTHER (CFS)
已知优先级、可接受秒级抖动 → SCHED_FIFO/RR + 带宽意识
硬实时、周期可建模       → SCHED_DEADLINE（需正确 C/T/D）
极低优先级后台          → SCHED_IDLE

九、源码函数与算法步骤对照

CFS（fair.c）

函数 算法步骤
calc_delta_fair delta × NICE_0_LOAD / weight
__sched_period 按 nr_running 选 latency 或 nr×min_gran
sched_slice period × weight/total，cgroup 分层
update_curr vruntime += calc_delta_fair；update_min_vruntime
place_entity START_DEBIT / 唤醒补偿
enqueue_entity / dequeue_entity 归一化 vruntime；PELT；红黑树
pick_next_entity leftmost + skip/next/last buddy
wakeup_preempt_entity vdiff vs gran → {-1,0,1}
check_preempt_tick slice 耗尽 / vruntime 领先过多
check_preempt_wakeup BATCH 过滤；wake 抢占
load_balance busiest → detach → attach
find_energy_efficient_cpu EM ΔE 最小 CPU

RT（rt.c）

函数 算法步骤
enqueue_task_rt 插入 active[prio]
_pick_next_task_rt bitmap + FIFO
check_preempt_curr_rt wakee.prio < curr.prio
task_tick_rt RR time_slice–；requeue
update_curr_rt rt_time += delta；throttle 检查
sched_rt_runtime_exceeded rt_time > 950ms

Deadline（deadline.c）

函数 算法步骤
enqueue_task_dl update_dl_entity；EDF 入树
pick_next_task_dl 最小 deadline
update_curr_dl runtime -= delta；throttle
replenish_dl_entity while runtime≤0: deadline+=T, runtime+=C
update_dl_entity overflow → Original/Revised CBS
dl_entity_overflow 带宽比例比较
start_dl_timer hrtimer @ deadline

PELT（pelt.c）

函数 算法步骤
decay_load O(1) × y^n
accumulate_sum 跨 1024us 段衰减+累加
___update_load_avg sum → avg

附录：sysctl 与默认参数

CFS

sysctl 默认（单核基准） 多核缩放
sched_latency_ns 6ms × (1 + ilog2(ncpus))
sched_min_granularity_ns 0.75ms × (1 + ilog2(ncpus))
sched_wakeup_granularity_ns 1ms × (1 + ilog2(ncpus))
sched_nr_migrate 32 单次 LB 最多迁移任务数
sched_autogroup_enabled 1 终端 autogroup

RT

sysctl 默认
sched_rt_period_us 1,000,000（1s）
sched_rt_runtime_us 950,000（950ms）
RR timeslice ~100ms

DL

sysctl 默认
sched_deadline_period_max_us ~4s
sched_deadline_period_min_us 100us
全局 DL 带宽 ~95% CPU

EAS / 其他

接口 说明
/proc/sys/kernel/sched_energy_aware EAS 开关
schedutil/target_load Rockchip 调频曲线（默认 80）

文档基于 RK3588 / Linux 6.1 内核 kernel/sched 源码整理。

文章互动

阅读 --

留言

0 条留言

正在加载留言…