Linux 内核折腾笔记：手搓一个简易调度器玩玩

前言：为何要挑战内核的心脏？

Linux 内核中最神秘、最复杂，但也最迷人的子系统是什么？内存管理？文件系统？网络协议栈？
在我看来，必须是 进程调度器 (Scheduler)。

它是操作系统的“时间管理大师”，决定了 CPU 这个稀缺资源到底该分给谁。它是系统流畅度的灵魂。你感觉到电脑卡顿？多半是调度器在“因为某些原因”没有及时让你的 GUI 进程上 CPU。

现如今的 Linux 默认使用的是 CFS (Completely Fair Scheduler，完全公平调度器)。这个名字听起来就很乌托邦。但你知道吗？在 CFS 之前，Linux 的调度器经过了 O(n) 和 O(1) 两个时代的演变。

今天这里不谈枯燥的源码分析（那是为了考试），我们要来点硬核的：在用户态手搓一个简易的调度器模型，以此来理解 CFS 的核心思想：虚拟运行时间 (vruntime)。

1. 调度器的本质

抛开所有复杂的内核数据结构，调度器的本质就是一个函数：

struct task* pick_next_task(struct runqueue* rq);

给定一个就绪队列（Running Queue），请你找出下一个该上 CPU 的进程。

最简单的策略：Round Robin (RR)

就是轮流做庄。A -> B -> C -> A …
简单，公平，但是极其低效。视频解码任务和后台日志压缩任务显然不应该获得同样的时间片。

O(1) 调度器回顾

在 Linux 2.6 早期，使用的是 O(1) 调度器。它用了两个优先级数组（Active 和 Expired）。

• 这种设计对交互式进程（比如你的 Shell，你的 VScode）判定非常复杂，需要复杂的启发式算法来“猜测”谁是交互式进程并给予奖励。
• 代码复杂，难维护，被 Linus 称为 “Heuristics are sh*t”。

2. CFS 的革命性思想

CFS 由那个写出了 Linux 内核 1% 代码的男人——Ingo Molnár 提出。他的思想极其简洁：

如果 CPU 是完美的，那么在一段时长 $P$ 内，如果有 $N$ 个进程，每个进程应该分得 $P/N$ 的时间。

由于 CPU 无法无限细分时间片，我们只能让它们轮流跑。CFS 引入了一个概念：虚拟运行时间 (vruntime)。

$$ vruntime += \frac{\text{实际运行时间} \times 1024}{\text{进程权重}} $$

• $vruntime$ 记录了进程“亏欠”了多少 CPU 时间（或者说享受了多少）。
• 权重越高，分母越大，$vruntime$ 增长得越慢。
• 调度策略极其简单：永远选择 $vruntime$ 最小的那个进程来运行！

这哪里需要什么启发式算法？这是一场单纯的数学游戏。为了快速找到最小的 $vruntime$，CFS 使用了 红黑树 (Red-Black Tree)。

graph TD
    Root((Root: vruntime=10))
    L((Left: vruntime=5))
    R((Right: vruntime=15))
    LL((Left-Left: vruntime=2))
    LR((Left-Right: vruntime=8))
    
    Root --> L
    Root --> R
    L --> LL
    L --> LR
    
    style LL fill:#f9f,stroke:#333,stroke-width:4px
    note[Pick Leftmost Node: vruntime=2]
    LL -.- note

3. 动手：在用户态模拟 CFS

光说不练假把式。我们用 C 语言写一个简单的 CFS 模拟器。我们不真的去切换 CPU 上下文（那需要动汇编），我们模拟 时间流逝。

定义任务结构体 (task_struct)

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

// 模拟的红黑树节点（为了简化，这里用链表排序代替红黑树，原理一样，效率 O(N) vs O(logN)）
typedef struct task_struct {
    int pid;
    int weight;          // 权重，模拟 nice 值
    double vruntime;     // 虚拟运行时间
    double exec_time;    // 实际已经运行的时间
    struct task_struct *next;
} task_t;

// 权重表：对应 nice 值 -20 到 19
// nice 0 的权重通常是 1024
const int prio_to_weight[40] = {
    /* -20 */ 88761, 71755, 56483, 46273, 36291,
    /* ... 简化 ... */
    /* 0 */   1024,
    /* ... */ 15
};

核心调度逻辑

我们需要一个函数，每次从队列里把 vruntime 最小的拿出来。

task_t* pick_next_task(task_t* head) {
    if (!head) return NULL;
    
    task_t *min_task = head;
    task_t *curr = head->next;
    
    while (curr) {
        if (curr->vruntime < min_task->vruntime) {
            min_task = curr;
        }
        curr = curr->next;
    }
    return min_task;
}

模拟时钟中断 (Tick)

Linux 并不是一直在做调度。调度通常发生在：

1. 进程阻塞（IO）。
2. 时间片用完（时钟中断触发 scheduler_tick）。

我们要模拟这个过程：

void run_simulation(task_t* runqueue, int total_ticks) {
    int current_tick = 0;
    
    while (current_tick < total_ticks) {
        // 1. 选出红黑树最左边的节点
        task_t* current = pick_next_task(runqueue);
        
        if (!current) break;
        
        // 2. 模拟运行一个 tick (假设 1 tick = 1ms)
        printf("[Tick %d] PID: %d is running (vruntime: %.2f)\n", 
               current_tick, current->pid, current->vruntime);
        
        // 3. 更新时间
        double delta_exec = 1.0; 
        current->exec_time += delta_exec;
        
        // 核心公式：vruntime update
        // vruntime += delta_exec * NICE_0_LOAD / weight
        double delta_vruntime = delta_exec * 1024.0 / current->weight;
        current->vruntime += delta_vruntime;
        
        current_tick++;
    }
}

跑起来看看！

假设我们需要跑两个任务：

• Task A: Nice 0 (权重 1024)，普通任务。
• Task B: Nice -10 (权重 ~9000)，高优先级任务。

根据 CFS 逻辑，Task B 的权重是 A 的 9 倍左右。这意味着 B 的 vruntime 增长速度是 A 的 1/9。
结果预测：Task B 跑 9 次，vruntime 才追上 Task A 跑 1 次的量。所以 B 会霸占 CPU 很长时间，直到它的 vruntime 终于超过了 A。

这完美实现了：权重越高，分得的实际 CPU 时间越多，但大家在虚拟时间轴上是公平赛跑的。

4. 真实内核中的黑魔法

当然，真实的 kernel/sched/fair.c 远比我们这个玩具复杂。

1. 睡眠补偿 (Sleeper Fairness)

如果一个进程去睡觉了（比如等待键盘输入），睡了 10 秒。那回来的时候 vruntime 岂不是也是 0？那它岂不是会连续霸占 CPU 10秒钟来“追赶”？
这会导致系统极其卡顿。
解决：当进程被唤醒（enqueue）时，内核会把它的 vruntime 设为当前队列里的 min_vruntime 减去一点点作为奖励。既保证它能立刻抢占 CPU，又不至于饿死别人。

2. 调度实体 (sched_entity) 与组调度 (Group Scheduling)

在 Docker/Cgroups 容器化时代，我们不希望一个容器里的 1000 个进程把主机上的 CPU 抢光。
Linux 实现了层级调度。task_struct 内部包含了一个 sched_entity。红黑树不仅可以挂进程，还可以挂“进程组”。
调度器先选出 vruntime 最小的 进程组，再在组内选出 vruntime 最小的 进程。

这也是为什么你在 Kubernetes 里限制了 CPU Limit 后，底层能精准控制的关键。

3. 多核负载均衡 (Load Balancing)

每个 CPU 核心都有自己的 Runqueue。如果 Core 0 忙得要死，Core 1 在摸鱼，这就浪费了。
内核会定期触发 Load Balance，把忙碌 CPU 上的任务“偷” (Steal) 一些到空闲 CPU 上。这涉及到复杂的锁机制和 CPU 缓存亲和性 (Cache Affinity) 考量——轻易迁移进程会导致 L1/L2 Cache 失效，性能反而下降。

5. 总结：设计的艺术

折腾了一圈，你会发现 CFS 真正的魅力在于：用最简单的数据结构（红黑树）和最朴素的数学公式（加权分配），解决了计算机科学中最复杂的资源分配问题。

不需要复杂的 AI 预测，不需要繁琐的启发式规则。
Simple is efficient.

如果你想真正深入了解 Linux 调度器，建议去阅读 kernel/sched/core.c 和 fair.c。不过在那之前，先像我一样，试着自己模拟一遍，你会发现源码里那些看起来可怕的变量名，突然变得亲切起来。

下次当你在终端敲下 nice -n -5 ./compile_linux 时，希望你能脑补出那棵红黑树正在为你调整节点的奇妙画面。

Keep hacking!