操作系统学习笔记 · 第 10 课 · CPU 调度——谁来用、用多久

从这一课起，我们进入第三个阶段：并发与同步。前面我们认识了进程、线程这些"演员"，现在要回答一个更现实的问题：舞台上只有一块 CPU，几十个"演员"都想上，该让谁上、上多久？ 这个"排班"的工作，就交给CPU 调度。

从"为什么感觉程序在同时跑"说起

你同时开着浏览器、音乐、编辑器。可你的电脑可能只有一个 CPU 核。一个核，同一时刻只能跑一个进程——那凭什么你觉得它们"同时在跑"？

答案是：CPU 在它们之间飞快地切换。一会儿跑浏览器，一会儿跑音乐，一会儿跑编辑器……切换快到人眼察觉不到，于是产生了"并行"的错觉。

这个"谁来上、上多久"的决策者，就是调度器（Scheduler），它做的事叫CPU 调度。

10.1 调度解决什么问题

一句话理解：进程数远多于 CPU 数，调度器决定"让谁上、上多久"，目标是兼顾公平、吞吐、响应时间。

调度的核心矛盾，是一个资源分配问题：CPU 就这么多，进程却一大堆，怎么分才合理？

调度器要在三个目标之间做平衡（这仨往往互相打架）：

公平：每个进程都有机会跑，别让谁饿死；
吞吐：单位时间内完成的进程尽量多；
响应时间：交互任务要"秒回"，不能让人干等。

你想想：为了吞吐高，你可能想"长任务优先跑完"；但那样短任务就被堵住、响应就慢了。没有完美答案，只有权衡。

10.2 调度发生时机

调度不是"随时随地"都能发生的，它只在几个特定时刻被触发：

一句话理解：以下四类时刻会触发调度：① 进程从运行变阻塞（等 I/O）② 进程退出 ③ 时间片用完 ④ 有更高优先级进程就绪（抢占）。

拆开看：

运行 → 阻塞：进程要等 I/O（比如读磁盘），CPU 闲着也是闲着，换人上；
进程退出：它不占 CPU 了，自然换下一个；
时间片用完：一个进程跑满它的"配额"，被换下来；
抢占：突然有个更高优先级的进程就绪了，立刻打断当前进程，让它上。

第 4 课讲的"就绪/运行/阻塞"三态转换，在这里就派上用场了——调度，本质就是在这些状态切换的瞬间，决定下一个"运行态"是谁。

10.3 四种经典调度算法

调度算法有很多，先吃透这四种"祖师爷"级别的：

算法	规则	优点	缺点
FCFS 先来先服务	谁先来谁先跑完	简单公平	短任务被长任务"堵"（护航效应）
SJF 最短作业优先	短任务先跑	平均等待最短	长任务可能饿死
RR 时间片轮转	每个进程轮流跑固定时间片	响应快、公平	时间片太小切换开销大
优先级调度	优先级高者先跑	灵活	低优先级可能饿死

逐个说人话：

FCFS（先来先服务）：就像排队打饭，谁先到谁先打，最公平。但它有个著名的毛病——护航效应：一个超长任务排在前面，后面一堆短任务全被堵住。你排在一个要打 100 份饭的人后面，哪怕你只要打一份，也得等他。
SJF（最短作业优先）：让"活儿最少"的先跑，平均等待时间最短。但问题来了——长任务可能永远轮不到（"饿死"），因为总有短任务插队。
RR（时间片轮转）：给每个进程一个固定"时间片"，轮流跑，到点就换人。响应快、公平，是交互系统的标配。但时间片如果太小，切换太频繁，开销就大了（下面细说）。
优先级调度：给进程排个"级别"，级别高的先跑。灵活好用，但低优先级的可能被饿死。

10.4 多级反馈队列（MLFQ）：现代 OS 的综合方案

上面四种各有硬伤，那现代操作系统（如 Linux）到底用哪个？答案是它们的结合体——多级反馈队列（MLFQ）。

一句话理解：MLFQ 有多个优先级队列，进程初始在高优先级、给短时间片；用不完就降到低优先级、给长时间片。既让交互任务快响应，又让计算任务跑得爽。

它的核心规则是这样的：

有多个队列，从高到低排优先级；
新进程进来，先进最高优先级队列，给一个短时间片；
如果它时间片没用完（说明它经常要等 I/O，是个"交互型"任务），就留在高优先级；
如果它时间片用完了还想要（说明它是"计算型"任务），就降到下一级，并给更长的时间片。

结果非常巧妙：

交互任务（比如你打字的编辑器，动不动就停下来等输入）→ 用不完时间片 → 一直留在高优先级 → 响应飞快；
计算任务（比如视频压缩，一口气要算很久）→ 时间片总不够用 → 慢慢降到低优先级 → 但拿到了更长的时间片，一次跑个够，减少切换开销 → 吞吐不亏。

一句话总结：MLFQ 用一个"用不完就降级"的机制，自动把"爱等的"和"爱算的"分开对待，鱼和熊掌兼得。这就是它成为"综合最优"实用方案的原因。

10.5 时间片大小的影响

时间片是 RR 和 MLFQ 里的关键参数，它设多大，影响巨大：

一句话理解：时间片太短 → 频繁切换，开销占比大；太长 → 响应变慢，退化成 FCFS。典型取 10~100ms。

太短（比如 1ms）：进程还没跑几下就被切走，CPU 花在"切换"上的时间占比越来越高，实际干活的时间变少；
太长（比如 1 秒）：一个进程霸着 CPU 太久，别的进程响应慢吞吞——时间片无限长时，就退化成了 FCFS。

参考数字：上下文切换一次大约几微秒。如果时间片设成 1ms，切换开销可能吃掉 1% 以上的 CPU——听着不多，但对大规模服务器就是实打实的浪费。所以典型时间片取 10~100ms，在"响应快"和"切换省"之间取平衡。

动手实验：C 语言写一个时间片轮转调度模拟器

// lesson10.c —— 时间片轮转（Round-Robin）调度模拟器
#include <stdio.h>

#define MAX 5

typedef struct {
    char name[8];
    int remain;   // 剩余需要运行的时间
} Process;

int main(void) {
    Process procs[MAX] = {
        {"P1", 5}, {"P2", 3}, {"P3", 8}, {"P4", 6}, {"P5", 2}
    };
    int quantum = 2;   // 时间片
    int time = 0;

    printf("时间片轮转调度（时间片=%d）\n", quantum);
    while (1) {
        int done = 1;
        for (int i = 0; i < MAX; i++) {
            if (procs[i].remain > 0) {
                done = 0;
                int run = procs[i].remain < quantum ? procs[i].remain : quantum;
                procs[i].remain -= run;
                time += run;
                printf("[t=%d] %s 运行 %d，剩余 %d\n", time, procs[i].name, run, procs[i].remain);
            }
        }
        if (done) break;   // 全部完成
    }
    printf("全部完成，总时间 %d\n", time);
    return 0;
}

编译运行：

gcc lesson10.c -o lesson10 && ./lesson10

观察输出：每个进程被"切"成一个个时间片，轮流执行，直到全部跑完。这就是 RR 调度的直观呈现。

动手进阶：把 quantum 改成 1 和 100，对比总耗时与切换次数，亲身体会时间片大小的影响——1 时切换频繁，100 时几乎就是 FCFS 了。

深入点：两个值得知道的细节

① 上下文切换的代价

"切换进程"不是免费的。CPU 要保存当前进程的状态（寄存器、程序计数器、页表等），再恢复下一个进程的状态。这套"保存 + 恢复"的动作，就叫上下文切换，是有成本的。

这也解释了为什么时间片不能无限细切——切得越细，花在"切换"上的钱越多，干活的越少。

② Cgroups 与 CFS

现代 Linux 实际用的是 CFS（完全公平调度器），思路和 RR/MLFQ 一脉相承，追求"每个进程公平地分到 CPU 时间"。配合 cgroup，还能做资源隔离——给某些进程组"限额"，限制它们最多用多少 CPU。这个隔离思想，第 29 课讲容器时会再次出现（容器本质上就是靠 cgroup 限资源、namespace 限视野）。

小结与思考题

这一课，我们回答了"CPU 给谁用"的问题：

调度解决的是"进程多、CPU 少"的分配问题，要在公平、吞吐、响应之间权衡；
调度在四类时机发生：阻塞、退出、时间片用完、抢占；
四种经典算法：FCFS / SJF / RR / 优先级，各有优劣（护航效应、饿死、切换开销）；
MLFQ 用"用不完就降级"自动区分交互/计算任务，是现代 OS 的实用方案；
时间片取 10~100ms，太小切换开销大、太大响应慢。

留三个问题：

FCFS 的"护航效应"是什么意思？
时间片设得太小会怎样？太大呢？
为什么 MLFQ 能同时照顾"响应快"和"吞吐高"？

这一课，我们默认"只有一个 CPU 核"。下一课，我们要面对更复杂的情况：多核、以及那些"必须准时完成"的实时任务。当 CPU 有好几个核、任务又有时限时，调度会有什么新花样？我们下回分解。