2、Linux内核调度器演进：从O(n)到CFS，RT调度类的诞生
调度器，说白了就是内核的“交通指挥官”。它决定哪个进程上CPU，哪个继续等。我入行那会儿，Linux调度器还处在蛮荒时代。这些年一路走过来，看着它从O(n)进化到O(1)，再到今天的CFS，感触挺深的。
今天咱们就聊聊这段演进史。你想想看，一个操作系统，如果调度做不好，实时性就是空谈。
2.1 远古时代：O(n)调度器
Linux 2.4内核用的就是O(n)调度器。为什么叫O(n)？因为每次调度，它都要遍历整个进程链表。进程越多，耗时越长。
核心设计：一个全局的runqueue，所有可运行进程都挂在这个链表上。每次选下一个进程，就从头到尾扫一遍，算算谁的“好度”最高。
好度计算：
goodness = 进程优先级 + 剩余时间片 / 2嗯，这里要注意。这个算法有个致命问题——当进程数达到几百个时，调度延迟会飙升到几十毫秒。我在项目中遇到过，一个嵌入式设备上跑了200多个线程，系统响应直接崩了。查了半天，发现是调度器在“拖后腿”。
O(n)调度器的痛点：
- 时间复杂度O(n)，进程越多越慢
- 多核CPU下，全局锁竞争激烈
- 交互式进程响应差，用户体验糟糕
- 没有实时调度支持
2.2 里程碑：O(1)调度器
Linux 2.6内核引入了O(1)调度器。这是调度器的一次革命。为什么叫O(1)？因为调度决策的时间是常数，跟进程数量无关。
核心思想：用两个优先级数组——active数组和expired数组。每个优先级对应一个链表。调度时直接从active数组中找最高优先级的非空链表，取出第一个进程就行。
struct prio_array {
unsigned long bitmap[BITMAP_SIZE]; // 优先级位图
struct list_head queue[MAX_PRIO]; // 每个优先级一个链表
int nr_active; // 活跃进程数
};我个人习惯把O(1)调度器比作“银行柜台”。每个优先级是一个窗口，VIP客户（高优先级）优先办理。普通客户（低优先级）等前面办完再说。
时间片分配：
| 优先级范围 | 时间片（毫秒） | 适用场景 |
|---|---|---|
| 0-99（实时） | 固定时间片 | 实时任务 |
| 100-139（普通） | 100ms - 800ms | 交互/批处理 |
O(1)调度器解决了O(n)的性能问题，但它有个硬伤——对交互式进程的识别不够智能。我曾经调试过一个桌面系统，鼠标总是卡顿。后来发现是调度器把X server当成了批处理任务，给了太少的时间片。
避坑指南：O(1)调度器虽然快，但公平性不足。高优先级进程可能长时间霸占CPU，导致低优先级进程“饿死”。我曾经在服务器上遇到过，一个高优先级的日志进程吃掉了90%的CPU，业务进程全在等。
2.3 现代基石：CFS调度器
Linux 2.6.23引入了CFS（Completely Fair Scheduler）。这是调度器设计的又一次飞跃。CFS的理念很简单——让每个进程都能公平地获得CPU时间。
核心设计：用红黑树代替优先级数组。每个进程有一个“虚拟运行时间”（vruntime）。调度器总是选择vruntime最小的进程运行。
// CFS的核心数据结构
struct cfs_rq {
struct rb_root tasks_timeline; // 红黑树根节点
struct rb_node *rb_leftmost; // 最左节点（vruntime最小）
u64 min_vruntime; // 最小虚拟运行时间
unsigned int nr_running; // 运行队列中的进程数
};为什么用红黑树？因为插入和删除都是O(log n)，比O(n)快得多。而且红黑树天然有序，找最小vruntime的节点就是最左边的节点，时间复杂度O(1)。
vruntime计算：
vruntime += 实际运行时间 * (NICE_0_LOAD / 进程权重)说白了，优先级高的进程，vruntime增长得慢，所以更容易被选中。优先级低的进程，vruntime增长得快，运行一会儿就得让位。
我在项目中遇到过一个问题：一个计算密集型的进程，总是被交互式进程抢占。后来发现是CFS的“睡眠公平”机制在起作用。交互式进程经常睡眠，醒来后vruntime会被补偿，所以更容易获得CPU。
个人经验：调优CFS时，重点关注这几个参数：
sched_latency_ns：调度延迟，默认6mssched_min_granularity_ns：最小时间片，默认0.75mssched_nr_migrate：负载均衡时迁移的进程数
我一般把sched_latency_ns调小到3ms，交互式应用的响应会明显提升。
2.4 实时调度类（RT）的引入
实时调度，说白了就是“说到做到”。普通调度器追求公平，实时调度器追求确定性。Linux的实时调度类，就是为这个目标设计的。
实时调度策略：
- SCHED_FIFO：先进先出，直到主动让出CPU或被更高优先级抢占
- SCHED_RR：时间片轮转，同优先级进程轮流运行
- SCHED_DEADLINE：基于截止时间的调度，最严格的实时保证
优先级范围：实时进程的优先级是0-99，数值越大优先级越高。普通进程的优先级是100-139。所以实时进程永远优先于普通进程。
// 设置实时调度策略和优先级
struct sched_param param;
param.sched_priority = 80; // 实时优先级80
sched_setscheduler(pid, SCHED_FIFO, ¶m);嗯，这里要注意。实时调度虽然好，但用不好会出大问题。我曾经在项目中遇到过一个坑：一个SCHED_FIFO进程死循环了，结果整个系统卡死，连ssh都连不上。因为实时进程优先级太高，普通进程根本抢不到CPU。
避坑指南：使用实时调度时，一定要设置CPU亲和性，把实时进程绑定到特定CPU上。同时，给实时进程设置一个“看门狗”，防止它跑飞。我曾经因为没做这些，导致产线停机了2小时。
2.5 知识体系总览
下面这张图，是我自己画的调度器演进路线。你可以看到，从O(n)到CFS，每一步都是对前一代的扬弃。
从这张图可以看得很清楚：O(n)调度器是“蛮力型”，O(1)调度器是“效率型”，CFS是“公平型”，RT调度类是“确定型”。每个调度器都有自己的定位和适用场景。
我的建议：做实时系统调优时，不要一上来就用RT调度类。先试试CFS，把sched_latency_ns调小，把进程的nice值调高。如果还不行，再考虑SCHED_FIFO或SCHED_RR。记住，实时调度是把双刃剑，用好了是利器，用不好是灾难。
好了，调度器的演进就聊到这儿。下一节咱们深入看看CFS的源码实现，到时候我会带着你一行一行地读代码。