1965年，你是一名操作系统工程师，计算机刚刚从单任务时代进入多任务时代——现在一台计算机可以同时运行多个程序了。
但你面临一个棘手的问题：只有一个CPU，10个程序都想运行，该让谁先执行？
这是个看似简单实则困难的问题，如果处理不好，可能会出现各种各样的古怪问题：
你需要设计一个"调度器"来分配CPU时间。
第一次尝试：按到达顺序排队
你的第一个想法很简单：先来先服务，就像银行排队一样，谁先到谁先执行。
voidschedule(){if (head != tail) {structtask *t = &queue[head++]; t->run(); // 执行任务 }}
这个调度器实现非常简单，很快你就把它部署到系统上，运行了半天后用户开始抱怨，它敲击键盘输入一个字符需要等待半天才会有响应。
你帮忙排查了半天发现这个系统中有一个需要10分钟的科学计算程序，这个程序运行时系统不可能会对其它任务有相应，因为调度器是按排队顺序来的。
你意识到：简单排队根本无法满足实际需求！
引入优先级机制
你思考了很久，想出一个改进方案：给每个任务分配一个数字，数字越小越重要，总是让最重要的任务先执行。
voidschedule(){structtask *highest = NULL;// 找到数字最小（最重要）的任务for (int i = 0; i < num_tasks; i++) {if (highest == NULL || tasks[i].priority < highest->priority) { highest = &tasks[i]; } }if (highest) { highest->run(); }}
这个数字就是所谓的优先级（Priority）。
你把新系统部署出去，期待能解决先来先服务调度器的问题。
但半天后，你就收到一个严重的错误报告。
用户报告它的一个日志写入程序已经等待了2个小时，仍然没有获得CPU时间。
你一通排查，发现有一个视频解码程序优先级更高的任务一直在运行。由于它的优先级高，调度器总是选择它，日志程序永远轮不到！
这就是所谓的饥饿（Starvation）的问题：低优先级任务可能永远得不到执行机会。
1990年：给每个任务分配固定配额
你思考了很久：问题的根源是什么？
高优先级任务会无限期地占用CPU！
你想出一个新方法：给每个任务分配固定的"运行配额"，配额用完就必须让出CPU，让其他任务运行。
voidschedule(){structtask *current = get_highest_priority_task();if (current->quota > 0) { current->run(); current->quota -= 1; // 消耗1ms配额 } else {// 配额用完，放入等待队列 current->quota = 计算新配额(current->priority); 移到等待队列(current); }}
这个"运行配额"，就是所谓的时间片（Time Slice）。
你部署新系统，监控数据显示：低优先级任务终于能获得CPU时间了！饥饿问题解决了。
但很快你发现了一个恼人的问题：敲击键盘后到字符的显示能明显感觉到卡顿。
你分析原因：终端程序其实大部分时间都在等待用户输入（处于睡眠状态），只有用户敲键盘的那一刻才需要CPU，而且只需要几微秒就能处理完，但如果此时还有其它任务在排队，那么就必须等待，这类交互式任务应该被优先响应，但你的调度器根本无法区分它们。
你尝试修补：增加一套启发式规则来猜测哪些任务是交互式的，如果是交互式任务就给更高的优先级。
void 检测交互式任务(struct task *t) {// 如果任务经常主动让出CPU（等待IO），就认为它是交互式的if (t->睡眠时间 > t->运行时间) { t->is_interactive = 1; t->priority -= 5; // 给它更高优先级 }}
这个方法有时有效，有时又判断错误。一个频繁读取磁盘的数据库程序被误判为"交互式任务"，优先级被拉高，反而饿死了真正的终端程序。
你不断增加判断条件：看睡眠次数、看平均运行时间、看IO等待比例......代码越来越复杂，但效果总是时好时坏。
你开始怀疑：是不是这整个思路就有问题？
从头开始想
2004年的某个深夜，你决定把之前所有的设计推倒，从最根本的问题重新想起：我到底想要什么？
你在纸上写下答案：我想要每个任务都获得公平的CPU时间。
什么是"公平"？
你想了一个例子：如果有10个同等重要的任务，理想情况下，它们应该各自获得10%的CPU时间。
那为什么不直接追踪每个任务已经获得了多少CPU时间？总是让获得时间最少的任务先执行，不就自然公平了吗？
你开始在白板上画新的设计：
structtask {int pid; uint64 runtime; // 这个任务已经运行了多久};voidschedule(){// 找到运行时间最短的任务structtask *next = 找到runtime最小的任务(); uint64 start = now(); next->run(); uint64 delta = now() - start;// 更新运行时间 next->runtime += delta;}
思路很简单：
你部署到测试系统上，效果惊人：10个任务的CPU时间差异很小！
然后你做了一个关键测试：在编译大项目的同时，打开终端输入命令。
你屏住呼吸，敲下键盘——
字符瞬间就显示出来了。
你愣了一下，然后意识到为什么：
编译程序：一直在疯狂使用CPU → runtime 增长很快 → 比如已经累积到 5000ms终端程序：大部分时间在等待你敲键盘（睡眠状态） → runtime 几乎不增长 → 比如只有 3ms
当你敲下键盘的那一刻，终端程序从睡眠中醒来，调度器一看：它的运行时间只有 3ms，编译程序已经 5000ms了——终端程序立刻获得CPU！
你突然明白了：之前那套令人头疼的"启发式交互式检测"，在这套新方案里根本不需要了！
不需要猜测哪个任务是交互式的，不需要任何特殊规则。IO密集型任务因为频繁睡眠，运行时间天然增长得慢，醒来后天然排在队列最前面。这不是一个专门设计的特性，而是"追踪已用时间"这个思路带来的自然结果，哪个任务的运行时间少，谁先执行。
虚拟时间
然而用户任务还是需要区分重要程度——比如数据库进程应该比日志备份进程获得更多CPU时间。
该怎么实现优先级呢，能不能在记账的时候做手脚？
就像不同国家的货币有不同的汇率：
- 重要任务：实际运行10秒，账本上只记1秒（"汇率"高）
- 不重要任务：实际运行1秒，账本上记10秒（"汇率"低）
这样，重要任务的运行时间增长慢，自然会更频繁地被调度——而且仍然是同一套规则，不需要额外的机制！
你修改代码，给每个任务加上一个"汇率"：
structtask {int pid;int nice; // 用户设置的重要程度（-20到+19） u64 vruntime; // 换算后的运行时间int weight; // 汇率（由nice值决定）};voidschedule(){structtask *next = 找到vruntime最小的任务(); u64 start = now(); next->run(); u64 delta = now() - start; // 实际运行时间// 用汇率换算后再记账 next->vruntime += delta * 1024 / next->weight;}
这个"换算后的运行时间"，就是所谓的的虚拟运行时间（Virtual Runtime，简称vruntime）。
这套调度机制就是所谓的CFS调度，Completely Fair Scheduler。
最后提前祝大家新年快乐，我们年后见！
10个月宝宝每天需要喝多少奶粉？
