Linux 进程调度深度解析

1. 调度器概述

操作系统内核的核心职责之一是进程调度——决定哪个进程在何时获得 CPU 资源。调度器的设计直接影响系统的响应性、吞吐量和公平性。Linux 内核采用可抢占式多任务设计，调度器必须在数十个甚至数千个进程间做出明智的决策。

在深入技术细节之前，让我们先建立对调度器的基本认知。想象一个数据中心运行着 Web 服务器、数据库和批处理作业，调度器需要在高优先级的交互式任务与计算密集型任务之间取得平衡，同时保证没有进程被饿死。

2. 调度器的演进历程

Linux 调度器经历了数次重大重构。2.4 内核使用 O(n) 调度器，每次调度都需要遍历所有进程。2.6 早期引入 O(1) 调度器，使用优先级数组实现常数时间调度决策。然而，O(1) 调度器在交互式任务识别上存在问题。

2007 年发布的 2.6.23 内核引入了完全公平调度器（CFS），由 Ingo Molnár 设计。CFS 采用完全不同的思路：它不再维护多个优先级队列，而是使用红黑树跟踪每个进程的虚拟运行时间（vruntime），始终选择 vruntime 最小的进程执行。

3. CFS 核心原理

CFS 的核心理念简单却深刻：在一个可配置的时间周期（sched_latency）内，所有可运行进程应获得相等的 CPU 时间份额。这意味着如果有两个进程，每个应获得 50% 的 CPU；如果有四个，则各得 25%。

但真实世界的进程具有不同的优先级。nice 值从 -20（最高优先级）到 19（最低优先级）允许用户调整进程的相对权重。CFS 通过权重（weight）机制实现这一点，高优先级进程获得更多的 CPU 份额。

3.1 目标延迟与最小粒度

CFS 使用两个关键参数控制调度行为：

• sched_latency：目标调度延迟，默认约 6ms。这是所有可运行进程至少被调度一次的时间窗口。
• sched_min_granularity：最小调度粒度，默认约 0.75ms。防止进程切换过于频繁。

4. 虚拟运行时间计算

虚拟运行时间（vruntime）是 CFS 的灵魂。它表示进程在"理想多任务处理器"上应获得的 CPU 时间。每当进程实际运行，其 vruntime 就根据权重增加。CFS 总是选择 vruntime 最小的进程执行，这自然实现了公平性。

4.1 vruntime 更新公式

/*
 * vruntime 增长计算
 * 
 * delta_exec: 实际执行时间（纳秒）
 * NICE_0_LOAD: 基准权重（nice 0）
 * load: 当前进程的权重
 */
delta_vruntime = delta_exec * (NICE_0_LOAD / load)

让我们分析这个公式的含义。对于 nice 0 的进程（基准权重），vruntime 与实际执行时间同步增长。高优先级进程（nice < 0）的权重更大，因此 NICE_0_LOAD / load < 1，其 vruntime 增长更慢，获得更多 CPU 时间。

/* kernel/sched/fair.c - vruntime 更新核心代码 */
static inline 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;

    schedstat_set(curr->statistics.exec_max,
                  max(curr->statistics.exec_max, delta_exec));

    curr->sum_exec_runtime += delta_exec;
    schedstat_add(cfs_rq->exec_clock, delta_exec);

    /* 关键：将物理时间转换为 vruntime */
    curr->vruntime += calc_delta_fair(delta_exec, curr);
    update_min_vruntime(cfs_rq);

    if (entity_is_task(curr)) {
        struct task_struct *curtask = task_of(curr);

        trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
        cgroup_account_cputime(curtask, delta_exec);
        account_group_exec_runtime(curtask, delta_exec);
    }

    account_cfs_rq_runtime(cfs_rq, delta_exec);
}

4.2 权重表

内核使用预计算的权重表将 nice 值映射到实际权重。相邻 nice 值之间的权重比例约为 1.25，意味着 nice -1 的进程比 nice 0 多获得约 25% 的 CPU 时间。

nice	权重	相对 nice 0
-20	88761	3.44x
-10	9548	1.82x
0	1024	1.00x
10	110	0.55x
19	15	0.37x

5. 红黑树实现

CFS 使用红黑树（自平衡二叉搜索树）管理可运行进程。树的键值是 vruntime，最左侧节点即为 vruntime 最小的进程，也就是下一个应被执行的进程。

红黑树保证查找最左节点的时间复杂度为 O(log n)。更重要的是，它天然支持 O(log n) 的插入和删除操作，这对频繁创建和销毁进程的工作负载至关重要。

/* kernel/sched/fair.c - 选择下一个任务 */
static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
{
    /* 获取最左节点 - 这就是 vruntime 最小的进程 */
    struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);

    if (!left)
        return NULL;

    return rb_entry(left, struct sched_entity, run_node);
}

/* 将进程加入红黑树 */
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;
    struct rb_node *parent = NULL;
    struct sched_entity *entry;
    bool leftmost = true;

    /*
     * 在树中找到正确的位置 - 根据 vruntime 排序
     */
    while (*link) {
        parent = *link;
        entry = rb_entry(parent, struct sched_entity, run_node);
        
        if (entity_before(se, entry)) {
            link = &parent->rb_left;
        } else {
            link = &parent->rb_right;
            leftmost = false;
        }
    }

    rb_link_node(&se->run_node, parent, link);
    rb_insert_color_cached(&se->run_node, &cfs_rq->tasks_timeline, leftmost);
}

6. 上下文切换

当调度器决定切换到新进程时，必须执行上下文切换。这涉及保存当前进程的 CPU 状态（寄存器、程序计数器等）并恢复新进程的状态。上下文切换是纯开销，操作系统设计者致力于最小化其频率和开销。

6.1 切换时机

上下文切换可能发生在以下场景：

1. 周期性的调度滴答（tick）：时钟中断触发，检查是否需要抢占
2. 进程主动放弃 CPU：调用 schedule() 或进入睡眠
3. 唤醒高优先级进程：新唤醒的进程可能抢占当前进程
4. 系统调用返回：检查 TIF_NEED_RESCHED 标志

/*
 * 核心调度函数 schedule()
 * 选择最高优先级的可运行任务并切换
 */
asmlinkage __visible void __sched schedule(void)
{
    struct task_struct *tsk = current;

    sched_submit_work(tsk);
    do {
        preempt_disable();
        __schedule(false);
        sched_preempt_enable_no_resched();
    } while (need_resched());
    sched_update_worker(tsk);
}

static void __sched notrace __schedule(bool scheduling)
{
    struct task_struct *prev, *next;
    unsigned long *switch_count;
    struct rq *rq;
    int cpu;

    cpu = smp_processor_id();
    rq = cpu_rq(cpu);
    prev = rq->curr;

    /* 
     * 选择下一个任务 - 这会调用 pick_next_task_fair() 
     * 对于 CFS，它最终调用 __pick_next_entity()
     */
    next = pick_next_task(rq, prev, &rf);
    
    if (likely(prev != next)) {
        /* 执行实际的上下文切换 */
        rq = context_switch(rq, prev, next, &rf);
    }
}

7. 实践：观察调度行为

让我们通过实际观察验证理论。Linux 提供多种工具监控调度行为：

7.1 使用 tracepoint 观察调度事件

# 启用 sched_switch tracepoint
$ echo 1 > /sys/kernel/debug/tracing/events/sched/sched_switch/enable

# 读取 trace 日志
$ cat /sys/kernel/debug/tracing/trace_pipe
          <idle>-0       [001] d.h.  1234.567890: sched_switch: prev_comm=swapper/1 prev_pid=0 prev_prio=120 prev_state=R ==> next_comm=myapp next_pid=1234 next_prio=120

# 使用 perf 更友好的查看
$ perf sched record -- sleep 10
$ perf sched latency

-----------------------------------------------------------------------------------------------------------------
  Task                  |   Runtime ms  | Switches | Average delay ms | Maximum delay ms | Maximum delay at       |
 -----------------------------------------------------------------------------------------------------------------
  myapp:1234            |     15.234    |    234   |     0.045        |     2.123        | 1234.567890 secs       |
  kworker/0:1:123       |      5.123    |     89   |     0.023        |     0.567        | 1235.123456 secs       |
 -----------------------------------------------------------------------------------------------------------------
  TOTAL:                |    234.567    |   5678   |     0.067        |                  |                        |
 -----------------------------------------------------------------------------------------------------------------

7.2 编写测试程序验证 CFS 公平性

/* cfs_fairness_test.c - 验证 CFS 公平性 */
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>
#include <sched.h>
#include <sys/wait.h>

static inline unsigned long long rdtsc(void)
{
    unsigned int lo, hi;
    __asm__ __volatile__ ("rdtsc" : "=a" (lo), "=d" (hi));
    return ((unsigned long long)hi << 32) | lo;
}

int main(int argc, char *argv[])
{
    int nproc = argc > 1 ? atoi(argv[1]) : 2;
    int nice_val = argc > 2 ? atoi(argv[2]) : 0;
    
    printf("测试 CFS 公平性: %d 个进程, nice=%d\n", nproc, nice_val);
    
    cpu_set_t cpuset;
    CPU_ZERO(&cpuset);
    CPU_SET(0, &cpuset);
    sched_setaffinity(0, sizeof(cpuset), &cpuset);
    
    pid_t *pids = malloc(nproc * sizeof(pid_t));
    
    for (int i = 0; i < nproc; i++) {
        pids[i] = fork();
        if (pids[i] == 0) {
            /* 子进程 - 绑定到 CPU 0 */
            sched_setaffinity(0, sizeof(cpuset), &cpuset);
            
            /* 设置 nice 值 - 进程 0 使用指定值，其他使用 0 */
            if (i == 0 && nice_val != 0) {
                nice(nice_val);
            }
            
            unsigned long long start = rdtsc();
            volatile unsigned long long counter = 0;
            
            /* 运行 5 秒 */
            while (rdtsc() - start < 5ULL * 3000000000ULL) {
                counter++;
            }
            
            printf("进程 %d (nice %d): counter = %llu\n", 
                   i, (i == 0 ? nice_val : 0), counter);
            exit(0);
        }
    }
    
    for (int i = 0; i < nproc; i++) {
        waitpid(pids[i], NULL, 0);
    }
    
    free(pids);
    return 0;
}

8. 小结

本章深入剖析了 Linux CFS 调度器的设计原理与实现机制。我们从调度器的历史演进出发，理解了 CFS 的创新之处：通过虚拟运行时间和红黑树实现 O(log n) 的公平调度。

关键要点回顾：

• CFS 追求公平性而非严格的优先级抢占，通过 vruntime 保证每个进程获得其应得的 CPU 份额
• 权重机制将 nice 值映射到实际 CPU 份额，相邻 nice 值相差约 1.25 倍
• 红黑树提供高效的 O(log n) 插入、删除和查找操作
• 调度决策是延迟驱动的，目标是在 sched_latency 内让每个进程至少运行一次

理解调度器对于系统性能调优至关重要。无论是优化交互式应用的响应延迟，还是最大化服务器吞吐量，都需要对调度器行为有深入理解。在下一章，我们将探索 Linux 内存管理子系统，看看内核如何管理物理和虚拟内存资源。