Linux内核调度器深度实战：从CFS到EEVDF的演进与核心调度架构的工程解析

// kernel/sched/sched.h - 调度类核心结构
struct sched_class {
    const struct sched_class *next;

    void (*enqueue_task)(struct rq *rq, struct task_struct *p, int flags);
    void (*dequeue_task)(struct rq *rq, struct task_struct *p, int flags);
    void (*yield_task)(struct rq *rq);
    void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);
    struct task_struct *(*pick_next_task)(struct rq *rq);
    void (*put_prev_task)(struct rq *rq, struct task_struct *p);
    void (*set_next_task)(struct rq *rq, struct task_struct *p, bool first);
    void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
    // ...
};

// 调度类优先级链表（从高到低）
stop_sched_class → dl_sched_class → rt_sched_class → fair_sched_class → idle_sched_class

// kernel/sched/sched.h - 运行队列核心字段
struct rq {
    raw_spinlock_t          lock;
    unsigned int            nr_running;       // 可运行进程数
    unsigned long           cpu_load[5];       // CPU负载历史
    struct cfs_rq           cfs;              // CFS运行队列
    struct rt_rq            rt;               // 实时运行队列
    struct dl_rq            dl;               // Deadline运行队列
    struct task_struct      *curr;             // 当前运行进程
    struct task_struct      *idle;             // idle进程
    struct rq_flags         rq_clock_flags;    // 时钟标志
    u64                     clock;             // 运行队列时钟
    u64                     clock_task;        // 任务时钟（排除中断）
    // ...
} ____cacheline_aligned;

// kernel/sched/fair.c - vruntime更新
static void update_curr(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_clock_task(rq_of(cfs_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;
    curr->sum_exec_runtime += delta_exec;

    // vruntime = 实际运行时间 * NICE_0_LOAD / 进程权重
    curr->vruntime += calc_delta_fair(delta_exec, curr);
    update_min_vruntime(cfs_rq);
}

// kernel/sched/fair.c - 选择下一个进程（CFS）
static struct task_struct *pick_next_task_fair(struct rq *rq)
{
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se;

    if (!cfs_rq->nr_running)
        return NULL;

    do {
        se = pick_next_entity(cfs_rq, NULL);  // 从红黑树取最左节点
        set_next_entity(cfs_rq, se);
        cfs_rq = group_cfs_rq(se);             // 处理组调度嵌套
    } while (cfs_rq);

    return task_of(se);
}

// 红黑树最左节点 = vruntime最小的进程（最"亏待"的进程）
static struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
{
    struct rb_node *left = cfs_rq->tasks_timeline.rb_node;
    while (left && rb_left_deepest_node(left))
        left = rb_left_deepest_node(left);
    return rb_entry(left, struct sched_entity, run_node);
}

// kernel/sched/fair.c - 调度粒度计算
unsigned int sysctl_sched_latency      = 6000000ULL;   // 6ms：目标调度延迟
unsigned int sysctl_sched_min_granularity = 750000ULL;  // 0.75ms：最小时间片

static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    // slice = sched_latency * se.weight / cfs_rq.weight
    // 进程应得的调度片比例
    unsigned int nr = cfs_rq->load.weight;
    u64 slice = __calc_delta(se->load.weight, sched_latency, nr);
    // 每个进程至少获得 min_granularity
    return max(slice, (u64)sysctl_sched_min_granularity * NICE_0_LOAD);
}

// kernel/sched/fair.c - 唤醒抢占检查
static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
{
    struct task_struct *curr = rq->curr;
    struct sched_entity *se = &curr->se, *pse = &p->se;

    // 如果唤醒进程的vruntime比当前进程小超过Granularity
    // 则抢占当前进程
    if (wakeup_preempt_entity(se, pse) == 1) {
        goto preempt;
    }
    // Granularity 用于避免过于频繁的抢占
    // 防止"thrashing"（进程反复切换）  

preempt:
    resched_curr(rq);  // 设置TIF_NEED_RESCHED标志
}

// 策略定义（include/uapi/linux/sched.h）
#define SCHED_NORMAL    0    // CFS/EEVDF（普通分时）
#define SCHED_FIFO      1    // 实时FIFO（无时间片，运行至阻塞）
#define SCHED_RR        2    // 实时RR（带时间片轮转）
#define SCHED_BATCH     3    // 批处理（降低交互性奖励）
#define SCHED_IDLE      5    // 空闲调度（仅SCHED_IDLE优先级）
#define SCHED_DEADLINE  6    // 最早截止时间优先

// kernel/sched/rt.c - 实时进程优先级队列（bitmap + 链表）
struct rt_prio_array {
    unsigned long bitmap[BIT_SIZE(MAX_RT_PRIO)];
    struct list_head queue[MAX_RT_PRIO];  // 99个优先级的链表
};

// 使用bitmap快速找到最高优先级
static inline int sched_find_first_bit(const unsigned long *b)
{
    return __ffs(*b);  // 硬件指令级优化
}

// 用户空间设置Deadline调度参数
struct sched_attr {
    __u32 size;
    __u32 sched_policy;       // SCHED_DEADLINE
    __u64 sched_flags;
    __s32 sched_nice;
    __u32 sched_priority;
    __u64 sched_runtime;     // 最大运行时间（例：10ms）
    __u64 sched_deadline;    // 截止时间（例：20ms）
    __u64 sched_period;      // 周期（例：20ms）
};

// 调用（需root或CAP_SYS_NICE）
sched_setattr(pid, &attr, 0);

// 准入控制：确保系统总利用率不超过100%
// Σ(runtime_i / period_i) <= 1.0  (必要条件)

// kernel/sched/fair.c - 组调度实体
struct cfs_bandwidth {
    raw_spinlock_t lock;
    ktime_t period;
    u64 quota;         // 时间配额（例：100ms/100ms = 1核）
    u64 runtime;       // 剩余运行时间
    struct hlist_head throttled_cfs_rq;
};

// CGroup fs接口
// cpu.cfs_period_us = 100000  (100ms周期)
// cpu.cfs_quota_us = 200000   (200ms配额 = 2核)

// 限流逻辑：当cfs_rq的runtime耗尽时，将其从红黑树移除
// 并在下一个period重新补充
static int assign_cfs_rq_runtime(struct cfs_rq *cfs_rq)
{
    struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
    int ret;

    raw_spin_lock(&cfs_b->lock);
    ret = __assign_cfs_rq_runtime(cfs_b, cfs_rq);
    raw_spin_unlock(&cfs_b->lock);
    return ret;
}

// kernel/sched/fair.c - EEVDF核心概念
// 
// virtual runtime (vruntime) → 实际运行时间归一化
// eligibility time (eligible) → 进程有资格被调度的最早时间
// virtual deadline (deadline) → eligible + vruntime_slice
//
// 调度规则：选择deadline最早的进程运行
// 这保证了每个进程在deadline前获得其应得的运行时间

struct sched_entity {
    struct rb_node      run_node;     // 现以deadline为键（不再是vruntime）
    u64                 deadline;     // vdeadline
    u64                 vlag;         // vruntime - deadline_diff
    int                 vdeadline;    // deadline资格标志
    // ...
};

// EEVDF红黑树：以deadline为排序键
static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    rb_erase_cached(&se->run_node, &cfs_rq->tasks_timeline);
    RB_CLEAR_NODE(&se->run_node);
}

// V3补丁集中Nicolas引入的lag概念确保长期公平性
// lag = 进程"应得"运行时间 - 实际运行时间
// 正值表示该进程应该更早获得执行机会

// arch/x86/kernel/process.c - 上下文切换
__notrace_funcgraph struct task_struct *
__switch_to(struct task_struct *prev_p, struct task_struct *next_p)
{
    // 1. 保存/恢复寄存器（直接在汇编中完成）
    // 2. 惰性FPU：不使用FPU时不保存/恢复
    // 3. CR3切换 + ASID复用避免全TLB刷新
    // 4. 切换TLS段寄存器
    
    // 关键优化：task_switch_asm 直接硬件指令
    this_cpu_write(current_task, next_p);
    return prev;
}

// 性能数据（x86_64, EPYC 7763）
// 单次上下文切换：~1-2μs（仅寄存器）
// 含TLB刷新：~5-10μs（跨NUMA更慢）
// 使用PCID/ASID后TLB miss率降低50%以上

// kernel/sched/fair.c - NUMA负载均衡
struct sched_domain {
    struct sched_domain *parent;      // 上层domain（sock→mc→die→core）
    struct sched_group  *groups;      // 组链表
    unsigned long       min_interval;
    unsigned long       max_interval;
    unsigned int        imbalance_pct;
    unsigned int        flags;
    // SD_SHARE_PKG_RESOURCES / SD_ASYM_PACKING / SD_NUMA 等标志
};

// NUMA拓扑层级
// Level 1 (MC):   同一CCX/Core Complex（共享L3）
// Level 2 (DIE):  同一Die（共享内存控制器）  
// Level 3 (SOCK): 同一Socket（物理CPU）
// Level 4 (NUMA): 不同NUMA节点（远程内存）

// 自动NUMA balancing (numabalancing)
// 每1000ms扫描进程地址空间，将远程页面迁移回本地
// 或将进程迁移至数据所在节点
echo 1 > /proc/sys/kernel/numa_balancing

# bpftrace 调度延迟直方图
bpftrace -e 'tracepoint:sched:sched_switch {
    $prev = args->prev_comm;
    $ts = nsecs;
    @start[$prev] = $ts;
} 
tracepoint:sched:sched_switch /@start[args->next_comm]/ {
    $latency = $ts - @start[args->next_comm];
    @latency_hist = hist($latency / 1000);  // μs单位
    delete(@start[args->next_comm]);
}'

# 输出示例：调度延迟分布直方图
@latency_hist:
[1K, 2K)      1024 |@@@@@@@@@@@@                         |
[2K, 4K)      2048 |@@@@@@@@@@@@@@@@@@@@                 |
[4K, 8K)      4096 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@         |
[8K, 16K)     2560 |@@@@@@@@@@@@@@                       |
[16K, 32K)     512 |@@@                                  |
[32K, 64K)     128 |@                                    |