Linux内核分析之进程管理-05

第5章 进程调度

基于 Linux 6.12.38 源码分析

---

5.1 调度器架构

5.1.1 调度器设计原则

Linux 调度器采用模块化设计，支持多种调度策略：

• 公平性：确保每个进程获得公平的 CPU 时间
• 高效性：最小化调度开销
• 可扩展性：支持多核 SMP 架构
• 实时性：支持实时任务调度
• 灵活性：支持多种调度策略共存

5.1.2 调度类层次

┌────────────────────────────────────────────────────────────────┐
│                      调度器核心架构                            │
│                  (kernel/sched/core.c)                        │
├────────────────────────────────────────────────────────────────┤
│                                                                 │
│  ┌──────────────────────────────────────────────────────────┐  │
│  │              Core Scheduler                              │  │
│  │                                                          │  │
│  │   schedule()         主调度函数                          │  │
│  │   pick_next_task()   选择下一个任务                      │  │
│  │   context_switch()   上下文切换                          │  │
│  │   load_balance()     负载均衡                            │  │
│  └──────────────────────────────────────────────────────────┘  │
│                            │                                   │
│         ┌──────────────────┼──────────────────┐               │
│         │                  │                  │               │
│         ↓                  ↓                  ↓               │
│  ┌─────────────┐  ┌─────────────┐  ┌─────────────┐          │
│  │  stop_      │  │   dl_       │  │   rt_       │          │
│  │  sched_     │  │  sched_     │  │  sched_     │          │
│  │  class      │  │  class      │  │  class      │          │
│  │             │  │             │  │             │          │
│  │ 停机任务     │  │ Deadline    │  │ 实时        │          │
│  │ 最高优先级   │  │ EDF 算法    │  │ FIFO/RR     │          │
│  └─────────────┘  └─────────────┘  └─────────────┘          │
│                                              │                 │
│                                              ↓                 │
│                                      ┌─────────────┐          │
│                                      │   fair_     │          │
│                                      │  sched_     │          │
│                                      │  class      │          │
│                                      │             │          │
│                                      │ CFS         │          │
│                                      │ 完全公平     │          │
│                                      └─────────────┘          │
│                                              │                 │
│                                              ↓                 │
│                                      ┌─────────────┐          │
│                                      │   idle_     │          │
│                                      │  sched_     │          │
│                                      │  class      │          │
│                                      │             │          │
│                                      │ 空闲        │          │
│                                      │ 最低优先级   │          │
│                                      └─────────────┘          │
│                                                                 │
└────────────────────────────────────────────────────────────────┘

5.1.3 调度类优先级

位置： kernel/sched/core.c

const struct sched_class stop_sched_class;
const struct sched_class dl_sched_class;
const struct sched_class rt_sched_class;
const struct sched_class fair_sched_class;
const struct sched_class idle_sched_class;

#define sched_class_highest (&stop_sched_class)
#define sched_class_lowest  (&idle_sched_class)

调度类	优先级	策略	用途
stop_sched_class	最高	-	停机/CPU 热迁移
dl_sched_class	2	SCHED_DEADLINE	严格实时任务
rt_sched_class	3	SCHED_FIFO/RR	软实时任务
fair_sched_class	4	SCHED_NORMAL/BATCH	普通进程
idle_sched_class	最低	SCHED_IDLE	空闲任务

---

5.2 运行队列 (Run Queue)

5.2.1 struct rq

位置： kernel/sched/sched.h

/*
 * This is the main, per-CPU runqueue data structure.
 *
 * Locking rule: those places that want to lock multiple runqueues
 * (such as the load balancing or the migration code) lock grab
 * the rq lock in the order: src_rq->lock, dst_rq->lock.
 */
struct rq {
    /* runqueue lock */
    raw_spinlock_t lock;

    /*
     * nr_running and cpu_load should be in the same cacheline because
     * remote CPUs use these fields for load balancing.
     */
    unsigned int nr_running;            // 可运行任务数

    /* CPU load of this runqueue */
    u64 nr_switches;                    // 上下文切换次数
    u64 nr_load_updates;                // 负载更新次数

    u64 nr_uninterruptible;             // 不可中断睡眠任务数

    /* Per-CPU load tracking */
    struct cpu_load load;               // CPU 负载
    struct cpu_load_history load_history[14];

    /* The next load balancing period */
    u64 next_balance;                   // 下次负载均衡时间

    /* For active balancing */
    int active_balance;

    /* Sched statistics */
    struct sched_statistics stats;      // 调度统计

    /* Scheduling classes */
    struct cfs_rq cfs;                  // CFS 运行队列
    struct rt_rq rt;                    // 实时运行队列
    struct dl_rq dl;                    // Deadline 运行队列

    /* Idle task */
    struct task_struct *idle;           // 空闲任务

    /* Stop task */
    struct task_struct *stop;           // 停机任务

    /* Clock */
    u64 clock;                          // 调度时钟
    u64 clock_task;                     // 任务时钟

    /* Context switch */
    unsigned int nr_context_switches;   // 上下文切换统计

    /* Various flags */
    unsigned int clock_update_flags;
    unsigned int clock_update_flags_mask;

    /* CPU */
    int cpu;                            // CPU 编号

    /* For active load balancing */
    struct cpu_stop_work stop_work;

    /* More fields... */
};

5.2.2 Per-CPU 运行队列

/* Per-CPU runqueues */
static DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);

// 获取指定 CPU 的运行队列
static inline struct rq *cpu_rq(int cpu)
{
    return &per_cpu(runqueues, cpu);
}

// 获取当前 CPU 的运行队列
static inline struct rq *this_rq(void)
{
    return this_cpu_ptr(&runqueues);
}

// 获取任务所在 CPU 的运行队列
static inline struct rq *task_rq(struct task_struct *p)
{
    return cpu_rq(task_cpu(p));
}

---

5.3 完全公平调度器 (CFS)

5.3.1 核心思想

CFS 基于虚拟运行时间 (vruntime) 调度：

• vruntime 越小，表示获得 CPU 时间越少，优先调度
• vruntime 越大，表示已获得较多 CPU 时间，延后调度
• 通过红-黑树维护按 vruntime 排序的任务队列

5.3.2 调度实体

// include/linux/sched.h
struct sched_entity {
    /* For load-balancing: */
    struct load_weight      load;            // 权重
    unsigned long           runnable_weight; // 可运行权重

    /* Entity execution state */
    u64                     exec_start;      // 执行开始时间
    u64                     sum_exec_runtime; // 总执行时间
    u64                     vruntime;        // 虚拟运行时间
    u64                     vruntime_copy;   // vruntime 副本

    /* Scheduling flag */
    unsigned int            on_rq;          // 是否在队列中

    /* RB-tree node */
    struct rb_node          run_node;       // 红-黑树节点

    /* Group scheduling */
    struct list_head        group_node;     // 组节点
    unsigned int            depth;           // 组深度
    struct cfs_rq           *cfs_rq;         // 所属 CFS 队列
    struct cfs_rq           *my_q;           // 自己的 CFS 队列

    /* Statistics */
    struct sched_statistics stats;
};

// CFS 运行队列
struct cfs_rq {
    struct load_weight load;                // 队列负载
    unsigned long runnable_weight;          // 可运行权重
    unsigned int nr_running;                // 可运行任务数
    u64 exec_clock;                         // 执行时钟

    /* RB-tree */
    struct rb_root_cached timeline;         // 任务时间线 (红-黑树)

    /* 'curr' points to currently running entity on this cfs_rq. */
    struct sched_entity *curr;              // 当前执行实体
    struct sched_entity *next;              // 下一个实体
    struct sched_entity *last;              // 上一个实体
    struct sched_entity *skip;              // 跳过的实体

    /* Statistics */
    struct sched_statistics stats;

    /* min_vruntime */
    u64 min_vruntime;                       // 最小 vruntime
#ifndef CONFIG_64BIT
    u64 min_vruntime_copy;
#endif

    /* More fields... */
};

5.3.3 vruntime 计算

// kernel/sched/fair.c

/*
 * 虚拟运行时间更新:
 * vruntime += delta_exec * (NICE_0_LOAD / weight)
 *
 * weight 越大 (nice 值越小), vruntime 增长越慢
 * weight 越小 (nice 值越大), vruntime 增长越快
 */
static void update_curr(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    struct rq *rq = rq_of(cfs_rq);
    u64 now = rq_clock_task(rq);
    u64 delta_exec;

    if (unlikely(!curr))
        return;

    // 计算执行时间
    delta_exec = now - curr->exec_start;
    if (unlikely((s64)delta_exec <= 0))
        return;

    curr->exec_start = now;

    // 更新 vruntime
    curr->vruntime += calc_delta_fair(delta_exec, curr);

    // 更新最小 vruntime
    update_min_vruntime(cfs_rq);
}

/*
 * 根据 nice 值计算权重
 */
static const int prio_to_weight[40] = {
     /* -20 */     88761,     71755,     56483,     46273,     36291,
     /* -15 */     29154,     23254,     18705,     14949,     11916,
     /* -10 */      9548,      7620,      6100,      4904,      3906,
     /*  -5 */      3121,      2501,      1991,      1586,      1277,
     /*   0 */      1024,       820,       655,       526,       423,
     /*   5 */       335,       272,       223,       183,       149,
     /*  10 */       120,        97,        79,        64,        52,
     /*  15 */        42,        35,        29,        24,        20,
     /*  20 */        17,        15,        13,        11,        10,
};

static const u32 prio_to_wmult[40] = {
     /* -20 */     48388,     59856,     76040,     92818,    118348,
     /* -15 */    147320,    184698,    229616,    287308,    360437,
     /* -10 */    449829,    563644,    704093,    875809,   1099582,
     /*  -5 */   1376151,   1717300,   2157191,   2700508,   3363326,
     /*   0 */   4169527,   5162522,   6370289,   7834114,   9572043,
     /*   5 */  11623260,  13980761,  16760363,  19939293,  23554169,
     /*  10 */  27601913,  31993729,  36801900,  42040296,  47658321,
     /*  15 */  53657806,  59848281,  66040189,  72169807,  78093426,
     /*  20 */  83635190,  88542949,  93182142,  97387254, 101170328,
};

5.3.4 红-黑树调度队列

CFS 运行队列的红-黑树:

                ┌─────────────────────────────────────┐
                │          timeline (rb_root)         │
                └─────────────────────────────────────┘
                              │
                              ↓
        ┌─────────────────────────────────────────────┐
        │              红黑树结构                      │
        │                                             │
        │  ┌──────────────────────┐                  │
        │  │    rb_leftmost       │ ← 最小 vruntime   │
        │  │      (Task A)        │   下一个被调度      │
        │  │   vruntime = 100      │                  │
        │  └──────────┬───────────┘                  │
        │             │                                  │
        │    ┌────────┴────────┐                      │
        │    ↓                 ↓                      │
        │  ┌─────────┐     ┌─────────┐                │
        │  │  左子树 │     │  右子树 │                │
        │  │vruntime│     │vruntime│                │
        │  │  < 100  │     │  > 100  │                │
        │  └─────────┘     └─────────┘                │
        │                                             │
        └─────────────────────────────────────────────┘

5.3.5 任务选择

// kernel/sched/fair.c

/*
 * 选择下一个要执行的任务
 */
static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    // 获取最左节点 (最小 vruntime)
    struct sched_entity *left = __pick_first_entity(cfs_rq);
    struct sched_entity *se;

    /*
     * 如果当前任务仍在队列中且 vruntime 更小，
     * 则继续执行当前任务
     */
    if (!left || (curr && entity_before(curr, left)))
        se = curr;
    else
        se = left;

    // 跳过被标记跳过的任务
    if (cfs_rq->skip == se) {
        struct sched_entity *second;

        if (se == curr)
            second = __pick_first_entity(cfs_rq);
        else
            second = __pick_next_entity(se);

        if (second && wakeup_preempt_entity(second, left) < 1)
            se = second;
    }

    return se;
}

/*
 * 将任务加入运行队列
 */
static void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    // 更新统计
    update_curr(cfs_rq);

    // 更新负载
    account_entity_enqueue(cfs_rq, se);

    // 插入红-黑树
    if (se != cfs_rq->curr) {
        /*
         * 更新 vruntime: 新任务的 vruntime 至少
         * 等于队列的最小 vruntime
         */
        place_entity(cfs_rq, se, 0);

        // 插入红-黑树
        __enqueue_entity(cfs_rq, se);
    }

    // 更新可运行任务数
    se->on_rq = 1;
}

/*
 * 将任务从运行队列移除
 */
static void dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    // 更新统计
    update_curr(cfs_rq);

    // 从红-黑树移除
    if (se != cfs_rq->curr)
        __dequeue_entity(cfs_rq, se);

    // 更新负载
    account_entity_dequeue(cfs_rq, se);

    // 更新状态
    se->on_rq = 0;
}

---

5.4 实时调度器

5.4.1 实时策略

// include/linux/sched.h
#define SCHED_NORMAL        0   // 普通进程
#define SCHED_FIFO          1   // 实时 FIFO
#define SCHED_RR            2   // 实时 RR (轮转)
#define SCHED_BATCH         3   // 批处理
#define SCHED_IDLE          5   // 空闲
#define SCHED_DEADLINE      6   // Deadline 调度

5.4.2 实时调度实体

// include/linux/sched.h
struct sched_rt_entity {
    struct list_head run_list;        // 运行队列
    unsigned long timeout;            // 超时时间
    unsigned int time_slice;          // 时间片

    struct sched_rt_entity *back;     // 后备
    struct sched_rt_entity *parent;   // 父实体
    struct rt_rq *rt_rq;              // 所属 RT 队列
};

// RT 运行队列
struct rt_rq {
    struct rt_prio_array active;      // 优先级数组
    unsigned long rt_nr_running;       // 可运行任务数
    u64 rt_time;                       // 运行时间
    u64 rt_runtime;                    // 运行时间预算

    int rt_throttled;                  // 是否被限流
};

5.4.3 优先级数组

/*
 * 100 个优先级队列 (0-99)
 * 每个优先级一个链表
 */
struct rt_prio_array {
    DECLARE_BITMAP(bitmap, MAX_RT_PRIO); // 优先级位图
    struct list_head queue[MAX_RT_PRIO]; // 100 个队列
};

/* 查找最高优先级非空队列 */
static inline struct task_struct *
pick_next_task_rt(struct rq *rq, struct task_struct *prev)
{
    struct rt_rq *rt_rq = &rq->rt;
    struct rt_prio_array *array = &rt_rq->active;
    struct sched_rt_entity *rt_se;
    int idx;

    // 查找最高优先级非空队列
    idx = sched_find_first_bit(array->bitmap);
    BUG_ON(idx >= MAX_RT_PRIO);

    // 获取队列第一个任务
    rt_se = pick_next_rt_entity(rq, rt_rq, idx);

    return rt_task_of(rt_se);
}

5.4.4 FIFO vs RR

SCHED_FIFO：

• 先进先出调度
• 任务运行直到主动让出或被更高优先级任务抢占
• 没有时间片概念

SCHED_RR：

• 轮转调度
• 每个任务有时间片
• 时间片用完后重新排队到同优先级队尾

// kernel/sched/rt.c
static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued)
{
    struct sched_rt_entity *rt_se = &p->rt;

    // 更新运行时间
    update_curr_rt(rq);

    // SCHED_RR 时间片用完
    if (p->policy != SCHED_RR)
        return;

    if (--p->rt.time_slice)
        return;

    // 重新排队
    requeue_task_rt(rq, p);
}

---

5.5 Deadline 调度器

5.5.1 EDF 算法

Deadline 调度器采用最早截止时间优先 (Earliest Deadline First) 算法：

• 每个任务有：运行时间、截止时间、周期
• 调度截止时间最近的任务
• 保证任务在截止时间前完成

5.5.2 Deadline 调度实体

// include/linux/sched.h
struct sched_dl_entity {
    struct rb_node rb_node;

    /* Original scheduling parameters */
    u64 dl_runtime;       // 运行时间预算
    u64 dl_deadline;      // 相对截止时间
    u64 dl_period;        // 周期
    u64 dl_bw;            // 带宽 (runtime/period)

    /* Actual scheduling parameters */
    s64 runtime;          // 剩余运行时间
    u64 deadline;         // 绝对截止时间
    unsigned int flags;

    /* State flags */
    unsigned int dl_throttled:1;    // 是否被限流
    unsigned int dl_boosted:1;      // 是否被提升
    unsigned int dl_yielded:1;      // 是否主动让出
    unsigned int dl_non_contending:1; // 是否非竞争

    /* Bandwidth enforcement timer */
    struct hrtimer dl_timer;         // 带宽定时器

    /* Inactive timer */
    struct hrtimer inactive_timer;   // 非活跃定时器

    /* Queue */
    struct dl_rq *dl_rq;             // 所属 DL 队列
};

5.5.3 Deadline 运行队列

struct dl_rq {
    /* run queue */
    struct rb_root_cached rb_root;
    unsigned long dl_nr_running;      // 可运行任务数

    /* Bandwidth */
    u64 dl_bw;                       // 总带宽
    struct dl_bw dl_bw;

    /* Statistics */
    u64 running_bw;                  // 运行中带宽
};

/* 选择 deadline 最早的任务 */
static struct sched_dl_entity *
pick_next_task_dl(struct rq *rq, struct task_struct *p)
{
    struct dl_rq *dl_rq = &rq->dl;
    struct sched_dl_entity *dl_se;

    // 获取红-黑树最左节点 (最早截止时间)
    dl_se = rb_entry(dl_rq->rb_root.rb_leftmost,
                    struct sched_dl_entity, rb_node);

    BUG_ON(!dl_se || dl_se->dl_nr_running == 0);

    return dl_se;
}

---

5.6 上下文切换

5.6.1 切换流程

// kernel/sched/core.c
static __always_inline struct rq *
context_switch(struct rq *rq, struct task_struct *prev,
               struct task_struct *next, struct rq_flags *rf)
{
    struct mm_struct *mm, *oldmm;

    prepare_task_switch(rq, prev, next);

    mm = next->mm;
    oldmm = prev->active_mm;

    /*
     * 切换地址空间
     * 内核线程: mm = NULL, 借用 prev 的 active_mm
     */
    switch_mm_irqs_off(oldmm, mm, next);

    /*
     * 切换寄存器状态
     * 体系相关，调用 switch_to 宏
     */
    switch_to(prev, next, prev);

    finish_task_switch(rq, prev);

    return rq;
}

5.6.2 switch_to (x86_64)

/* arch/x86/include/asm/switch_to.h */
#define switch_to(prev, next, last)                    \
    asm volatile("pushq %%rbp\n\t"                     \
                 "movq %%rsp, %P[thread_rsp](%[prev])\n\t" \
                 "movq %P[thread_rsp](%[next]), %%rsp\n\t" \
                 "call __switch_to\n\t"                \
                 "popq %%rbp\n\t"                      \
                 : "=a" (last)                         \
                 : [prev] "D" (prev),                  \
                   [next] "S" (next)                   \
                 : "memory", "rcx", "rbx", "r8", "r9", \
                   "r10", "r11", "r12", "r13", "r14", "r15");

/* arch/x86/kernel/process_64.c */
__visible __notrace_funcgraph struct task_struct *
__switch_to(struct task_struct *prev_p, struct task_struct *next_p)
{
    struct thread_struct *prev = &prev_p->thread;
    struct thread_struct *next = &next_p->thread;
    struct fpu *prev_fpu = &prev->fpu;
    struct fpu *next_fpu = &next->fpu;
    int cpu = smp_processor_id();

    // 保存 FPU 状态
    if (test_thread_flag(TIF_NEED_FPU_LOAD))
        switch_fpu_finish(prev_fpu, next_fpu, cpu);

    // 切换 GS 段
    load_TLS(next, cpu);

    // 返回上一个任务
    return prev_p;
}

---

5.7 schedule() 主调度函数

5.7.1 入口点

// kernel/sched/core.c
asmlinkage __visible void __sched schedule(void)
{
    struct task_struct *tsk = current;

    sched_submit_work(tsk);

    do {
        __schedule(SM_NONE);
    } while (need_resched());
}

// 抢占式调度
asmlinkage __visible void __sched schedule_preempt_disabled(void)
{
    __schedule(SM_PREEMPT);
}

5.7.2 __schedule() 实现

// kernel/sched/core.c:6599
static void __sched notrace __schedule(int sched_mode)
{
    struct task_struct *prev, *next;
    bool preempt = sched_mode > SM_NONE;
    unsigned long *switch_count;
    unsigned long prev_state;
    struct rq_flags rf;
    struct rq *rq;
    int cpu;

    // 获取当前 CPU 运行队列和当前任务
    cpu = smp_processor_id();
    rq = cpu_rq(cpu);
    prev = rq->curr;

    schedule_debug(prev, preempt);

    // 禁用中断
    local_irq_disable();
    rcu_note_context_switch(preempt);

    // 锁定运行队列
    rq_lock(rq, &rf);
    smp_mb__after_spinlock();

    // 更新时钟
    rq->clock_update_flags <<= 1;
    update_rq_clock(rq);

    // 选择下一个任务
    next = pick_next_task(rq, prev, &rf);
    clear_tsk_need_resched(prev);
    clear_preempt_need_resched();

    if (likely(prev != next)) {
        // 更新统计
        rq->nr_switches++;
        rcu_switch_count++;

        // 切换任务
        rq = context_switch(rq, prev, next, &rf);
    } else {
        // 没有可运行任务，运行空闲任务
        next = pick_next_task(rq, prev, &rf);
        rq = context_switch(rq, prev, next, &rf);
    }
}

---

5.8 负载均衡

5.8.1 负载均衡时机

1. 周期性负载均衡 - 时钟中断触发
2. CPU 空闲时 - 本 CPU 没有任务时从其他 CPU 偷任务
3. 创建新进程时 - 选择最空闲的 CPU
4. CPU 热迁移时 - CPU 下线前迁移任务

5.8.2 PELT 负载跟踪

// Per-Entity Load Tracking
/*
 * 负载衰减模型:
 * load = load * y^N
 * 其中 y = 0.5 (每 1ms)
 */

static __always_inline u64
___update_load_sum(u64 now, u64 last_update, u64 period)
{
    long delta = now - last_update;

    if (delta > period) {
        // 负载衰减
        u64 y = calc_load_n(period / 2, last_update, now);
        delta *= y;
    }

    return delta;
}

5.8.3 load_balance()

// kernel/sched/fair.c
static int load_balance(int this_cpu, struct rq *this_rq,
                       struct rq_flags *rf)
{
    int busiest, active;
    struct sched_group *group;
    struct rq *busiest_rq;

    // 查找最繁忙的 CPU 组
    group = find_busiest_group(&env, sds);
    if (!group)
        goto out_balanced;

    // 查找最繁忙的运行队列
    busiest_rq = find_busiest_queue(&env, group);
    if (!busiest_rq)
        goto out_balanced;

    // 从繁忙队列迁移任务
    if (busiest_rq->nr_running > 1) {
        // 移动任务到当前 CPU
        detach_tasks(&env);
        attach_tasks(&env);
    }

    return 0;
}

---

5.9 调度延迟与吞吐量优化

5.9.1 调度延迟

sched_latency_ns - 目标调度延迟

// kernel/sched/debug.c
unsigned int sysctl_sched_latency = 6000000ULL; // 6ms

sched_min_granularity_ns - 最小调度粒度

unsigned int sysctl_sched_min_granularity = 750000ULL; // 750us

5.9.2 吞吐量优化

sched_wakeup_granularity_ns - 唤醒粒度

unsigned int sysctl_sched_wakeup_granularity = 1000000ULL; // 1ms

sched_nr_migrate - 批量迁移任务数

unsigned int sysctl_sched_nr_migrate = 32;

---

5.10 本章小结

本章介绍了 Linux 进程调度机制：

1. 调度器架构：模块化设计，支持多种调度类
2. 运行队列：Per-CPU 运行队列，包含多种调度类的队列
3. CFS：基于 vruntime 的完全公平调度，使用红-黑树
4. 实时调度：FIFO 和 RR 策略，支持软实时任务
5. Deadline 调度：EDF 算法，支持严格实时任务
6. 上下文切换：切换地址空间和寄存器状态
7. 主调度函数：schedule() 和 __schedule()
8. 负载均衡：PELT 负载跟踪和 CPU 间任务迁移

下一章将介绍进程状态与转换。