3. 常见调度算法（上）：先来先服务、短作业优先、时间片轮转

调度算法这东西，说白了就是「谁先上机器」的排队规则。我早年刚接触分布式计算时，总觉得调度不就是排个队嘛，有啥好研究的？直到有一次线上集群因为调度策略不当，导致大量短任务被长任务堵死，整个系统吞吐量直接腰斩……嗯，从那以后我再也不敢小看调度算法了。

今天咱们先聊三个最经典的调度算法：先来先服务（FCFS）、短作业优先（SJF）、时间片轮转（RR）。别看它们简单，很多现代调度器（比如 Kubernetes 的默认调度器、Linux 的 CFS）的核心思想，都能追溯到这些基础算法上。

3.1 先来先服务（FCFS）

FCFS 是最朴素的调度策略。谁先到，谁先上。就像银行柜台排队，你来得早，就优先办理。

核心逻辑：

• 维护一个 FIFO（先进先出）队列
• 新任务到达时，追加到队列尾部
• 调度器从队列头部取出任务执行
• 任务执行完毕，再取下一个

优点：

• 实现简单，几乎零开销
• 公平性直观——先来后到，没人插队
• 不会发生饥饿（每个任务最终都会被执行）

缺点：

• 平均等待时间可能很长
• 对短任务不友好——一个长任务堵在前面，后面所有短任务都得等着
• 不适合交互式系统

适用场景： 任务执行时间大致相同、且对响应时间不敏感的场景。比如离线日志处理、定时报表生成。

3.2 短作业优先（SJF）

SJF 的思路很直接：谁先做完，谁先上。调度器预估每个任务的执行时间，然后挑最短的那个先执行。

你想想看，这就像超市收银台——如果有个顾客只买一瓶水，你让他先结账，后面买一车东西的人多等一会儿，整体效率反而更高。

核心逻辑：

• 调度器需要知道（或预估）每个任务的执行时间
• 每次调度时，从就绪队列中选择执行时间最短的任务
• 可以是非抢占式的（任务一旦开始，就执行完）
• 也可以是抢占式的（称为 SRTF，最短剩余时间优先）

优点：

• 理论上能获得最小平均等待时间
• 对短任务极其友好
• 系统吞吐量高

缺点：

• 长任务可能永远得不到执行——这就是饥饿问题
• 需要预估执行时间，实际中很难做到精确
• 如果预估不准，效果可能比 FCFS 还差

适用场景： 任务执行时间可预估、且长任务可以接受一定延迟的场景。比如 MapReduce 中的小任务调度。

3.3 时间片轮转（RR）

RR 算法解决了 FCFS 和 SJF 的一个核心痛点：响应时间不可控。它的做法是给每个任务分配一个固定长度的时间片（time slice），轮流执行。

说白了，就是「每人玩一会儿，时间到了换人」。这就像幼儿园老师让小朋友轮流玩滑梯——每人玩 2 分钟，然后换下一个。

核心逻辑：

• 维护一个就绪队列（通常是循环队列）
• 每个任务执行一个时间片（比如 100ms）
• 时间片用完，任务还没结束，就把它放回队列尾部
• 调度器继续取队列头部的下一个任务

关键参数：时间片大小

时间片大小	优点	缺点
过大	上下文切换开销小	响应时间变长，退化为 FCFS
过小	响应时间短，交互性好	上下文切换开销大，CPU 利用率下降

优点：

• 响应时间可控，适合交互式系统
• 公平性好——每个任务都能得到 CPU 时间
• 不会发生饥饿

缺点：

• 上下文切换开销不可忽视
• 平均等待时间可能比 SJF 长
• 时间片大小需要精心调优

适用场景： 交互式系统、分时操作系统、需要保证响应时间的场景。

3.4 三种算法对比

特性	FCFS	SJF	RR
调度依据	到达时间	执行时间	时间片
平均等待时间	高	低（理论最优）	中等
响应时间	差	差（长任务可能饥饿）	好
饥饿问题	无	有（长任务）	无
实现复杂度	低	中（需要预估时间）	中
适用场景	批处理	可预估的批处理	交互式系统

3.5 核心逻辑流程图

下面我用一张 SVG 图来展示这三种算法的核心调度逻辑对比。你可以直观地看到任务在队列中是如何被选择和执行的。

这张图把三种算法的核心差异展示得很清楚：FCFS 是排队上车，SJF 是让跑得快的先跑，RR 是每人玩一会儿。你想想看，这三种思路其实对应了三种不同的「公平」定义——先来后到、效率优先、机会均等。

3.6 小结

这三种算法是调度领域的「三原色」。虽然现代调度器（比如 Linux CFS、Kubernetes 调度器）已经复杂得多，但核心思想都能追溯到它们身上。

我个人建议初学者先把这三种算法吃透。你可以在纸上画一画任务到达时间、执行时间，然后手动模拟调度过程。我当年就是这么干的——画了整整一沓纸，才真正理解为什么 SJF 的平均等待时间最短，为什么 RR 的响应时间最好。

嗯，下一节咱们会聊更高级的调度算法，包括优先级调度、多级反馈队列这些。但今天这三个，是基础中的基础，值得你花时间好好消化。