4. 调度算法基础

调度算法，说白了就是操作系统怎么决定「下一个该谁上CPU跑」。

我做了这么多年并发系统，见过太多因为调度策略选错而导致的性能灾难。今天咱们就把五种经典调度算法掰开揉碎了讲清楚。

一、先来先服务（FCFS）——最朴素的公平

FCFS 就像银行排队，谁先到谁先办。实现简单，但问题也很明显。

核心逻辑： 维护一个就绪队列，新进程加到队尾，调度器从队头取进程执行。

我遇到过最典型的案例：一个后台批处理任务占着CPU跑了20秒，结果所有前台交互都卡死了。用户以为系统崩溃了，其实只是FCFS在「公平」地排队。

二、短作业优先（SJF）——理论最优，实践坑多

SJF 的思路很直接：谁执行时间短，谁先上。理论上，它能最小化平均等待时间。

但问题来了——你怎么知道一个作业要跑多久？

两种实现方式：

• 非抢占式： 等当前进程执行完，再选最短的
• 抢占式（SRTF）： 新来的更短，就抢当前进程的CPU

我建议你记住这个公式：

平均等待时间 = (所有进程等待时间之和) / 进程数

举个例子：三个进程 P1(6ms)、P2(8ms)、P3(3ms)。

• FCFS 顺序：P1→P2→P3，平均等待 = (0+6+14)/3 = 6.67ms
• SJF 顺序：P3→P1→P2，平均等待 = (0+3+9)/3 = 4ms

你看，SJF 确实更优。但实际中，你很难准确预估执行时间。我见过有人用历史平均值来估算，结果偏差大到离谱。

三、时间片轮转（RR）——交互式系统的救星

RR 解决了 FCFS 的「长任务霸占CPU」问题。每个进程分到一个时间片，用完就换下一个。

关键参数：时间片大小

• 时间片太大 → 退化成 FCFS
• 时间片太小 → 上下文切换开销爆炸

我一般建议时间片设在 10-100ms 之间。Linux 默认是 100ms，但实际会根据负载动态调整。

// 伪代码示意
while (队列不为空) {
    取出队首进程
    设置定时器为时间片长度
    执行进程
    时间片到 → 保存上下文
    进程放回队尾
    调度下一个
}

嗯，这里要注意：上下文切换不是免费的。每次切换要保存寄存器、程序计数器、栈指针……这些开销加起来，时间片设得太小反而得不偿失。

四、优先级调度——给任务分三六九等

有些任务天生就该优先跑。比如键盘中断、网络包处理。优先级调度就是干这个的。

两种模式：

• 静态优先级： 创建时定死，简单但不够灵活
• 动态优先级： 运行时调整，比如老化机制防止饥饿

我当年在嵌入式系统里就踩过这个坑。一个高优先级的中断处理线程，硬生生被一个低优先级的日志写入线程堵了500ms。排查了三天才发现是优先级反转。

解决方案：

• 优先级继承：低优先级任务临时提升到高优先级
• 优先级天花板：设定锁的最高优先级

五、多级反馈队列——集大成者

这是目前操作系统用得最多的调度算法。Linux、Windows 都在用。

核心思想： 多个队列，每个队列不同优先级，不同时间片。

• 新进程进最高优先级队列（时间片最短）
• 用完时间片没完成 → 降级到下一级队列
• 低优先级队列的进程，等待时间过长 → 提升优先级（老化）

说白了，就是给短作业快速通道，长作业也有机会跑，不会饿死。

知识体系总览

下面这张图帮你理清五种算法的关系：

五种算法对比表

算法	核心思想	优点	缺点	适用场景
FCFS	先到先服务	实现简单	平均等待时间长	批处理系统
SJF	最短优先	平均等待最优	难以预估执行时间	批处理（已知时长）
RR	时间片轮转	响应时间短	上下文切换开销	交互式系统
优先级	按优先级调度	灵活区分任务	可能饥饿、反转	实时系统
多级反馈	多队列+老化	综合性能好	参数调优复杂	通用操作系统