调度算法对比（FCFS/SJF/RR/多级反馈）实战指南

可视化演示

对比FCFS、SJF、RR与多级反馈队列四种调度算法的执行过程，通过甘特图展示进程调度顺序与等待时间差异。

进程调度基础

奶茶店开门前，店长要琢磨三件事：下一个做哪杯？一杯做多久？做一半要不要停下来做别的？操作系统里的调度器（Scheduler）就是那位店长，它手底下的“订单”叫进程（Process），而CPU就是那个唯一能干活的大师傅。

订单不可能同时全做，只能排成一串等待。这些等待中的进程排成的队伍叫做就绪队列（Ready Queue）。店长从队列里挑一份订单开工，这个过程叫调度；如果一份订单正做着，一份加急单到了，店长决定要不要放下手里的活去接急单——这就引出了调度领域最重要的一对概念：抢占式（Preemptive）和非抢占式（Non-preemptive）。非抢占式像“做就做到底”，抢占式像“有急事随时插队”。

不管是抢占还是非抢占，每次切换订单都有一笔隐形成本：店长要先把半成品收到一边，把新订单的材料摆上桌——这叫上下文切换（Context Switch），它不产生任何“奶茶产出”，纯粹是开销。因此调度算法必须在“公平分配”和“减少切换”之间找平衡。

先来先服务FCFS

先来先服务（First-Come, First-Served）是奶茶店最朴素的店规：谁先下单谁先做，一个做一个，做完再做下一个。顾客没有怨言，因为规则一目了然——先来后到，天经地义。但问题很快暴露：假如第一个顾客点了一杯耗时 30 分钟的“豪华全家桶”特调，后面四个只要 1 分钟的“冰美式”顾客都得干等着。这正是 FCFS 最大的缺陷——护航效应（Convoy Effect）。

从技术上讲，FCFS 是非抢占式的：一旦进程获得 CPU，它会一直运行到结束或阻塞。假设进程 P1（到达 0，服务 30）、P2（到达 1，服务 2）、P3（到达 2，服务 1），P2 和 P3 明明能飞快做完，却必须等 P1 慢慢跑完，平均等待时间被严重拉高。公式上，进程 $i$ 的周转时间（从到达到完成的总时间）为：

平均周转时间则为 $\displaystyle \frac{1}{n}\sum_{i=1}^{n} \left(T_{\text{完成},i} - T_{\text{到达},i}\right)$。

回到奶茶店：FCFS 店规简单、实现成本低、不会让任何人“饿死”（每个订单迟早轮到），所以早期的批处理系统很喜欢它。但它致命的护航效应让短订单用户体验极差——后面的顾客看着前面那杯“全家桶”熬了半小时，心态直接崩了。改进方向很直接：为什么不让快的先做呢？

短作业优先SJF

如果店长改个规矩——“谁做得快谁先做”——这就是短作业优先（Shortest Job First, SJF）。P1 那杯 30 分钟的特调会被放到最后，P2、P3 这些 1-2 分钟的订单先做。顾客平均等待时间会大幅下降。数学上可以严格证明：SJF 在非抢占式场景下给出了最小的平均等待时间，它是“平均等待时长”这个指标的最优解。

假设进程 A（服务 3）、B（服务 6）、C（服务 9）同时到达，SJF 的顺序是 A→B→C。平均周转时间为：

而如果按 FCFS 的任意长作业优先顺序，结果只会更差。

SJF 的问题也很明显。第一，它要求店长预知每个订单的耗时——现实中判断一杯奶茶做多久还勉强可以，但操作系统没法提前知道一个进程要跑多久。第二，如果不断有“短订单”插进来，那杯 30 分钟的外卖特调可能永远等不到开工，这种现象叫饥饿（Starvation）——不是顾客饿了，而是长进程被活活饿死。SJF 的改良版 SRTF（最短剩余时间优先）用“抢占”解决了部分问题，但预知时长这个难题依然无解。

时间片轮转RR

奶茶店再换一种玩法：每个订单先做 3 分钟，时间一到不管做到哪一步都先放一边，让下一个订单做 3 分钟，所有订单轮流来。这样就算前面有“全家桶”，每个顾客也都能在几分钟内看到自己的订单开始动工。这就是时间片轮转（Round Robin, RR）——操作系统给每个进程分配一个固定的小段 CPU 时间，叫时间片（Time Quantum），用完就切换给下一个。

时间片大小 $q$ 是 RR 的灵魂。设就绪队列有 $n$ 个进程，每个进程在时间片内运行 $q$ 毫秒，那么一个进程最多等 $(n-1)\times q$ 毫秒就能再次获得 CPU。响应时间上限为：

RR 的响应时间比 FCFS 好太多——每个顾客都能快速看到自己的订单“被做过一次”。但代价也清晰：每次时间片用完都要上下文切换，切换是有开销的。如果 $q$ 太小，CPU 大部分时间都在切换而不是干活，就像店员每做 10 秒就换一杯，奶茶没做几杯，时间全耗在清洗杯子上了；如果 $q$ 太大，RR 就退化成 FCFS——“每人做 30 分钟”，跟排队没区别。工程上通常取 $q$ 在 10-100ms 之间，让切换开销占比低于 1%。

多级反馈队列

能不能把前三种算法的优点揉在一起？多级反馈队列（Multi-Level Feedback Queue, MLFQ）就是这个“缝合怪”，也是现代操作系统（如 Linux、Windows）事实上的调度主力。它的核心思想是：设置多条优先级不同的队列，新进程先进最高优先级队列，如果时间片用完还没做完，就降级到下一条队列；低优先级队列时间片更长，但获得 CPU 的机会更少。

MLFQ 的流程可以描述为：Q1 时间片 1ms，Q2 时间片 2ms，Q3 时间片 4ms。新进程 P 进入 Q1，若在 1ms 内做完则直接离开；否则降到 Q2 获得 2ms；再超时则到 Q3。这样，短进程在 Q1 就能快速完成（享受 SJF 的待遇），长进程虽然在低优先级慢慢做，但绝不会饿死（保证 FCFS 的公平底线）。队列内用 RR 轮转，队列间用优先级抢占。

MLFQ 最巧妙的地方在于无需预知进程时长——它通过“降级”机制自动识别长进程，用“反馈”代替了 SJF 所需的先知能力。但要注意两个陷阱：一是队列参数需要调优（几条队列、各自时间片多少），二是可能被游戏规则——一个进程如果故意在时间片末尾放弃 CPU 再重新进入，就能永远留在 Q1。现代 MLFQ 加入了“定期把所有进程提升到最高优先级”的机制来对抗这种作弊，就像店长每小时重整一次队形，让所有顾客重新排队。

性能评价指标

四种算法各有千秋，拿什么衡量好坏？业界有四个核心指标，对应奶茶店经营的四个数字。

周转时间（Turnaround Time）：从顾客下单到拿到奶茶的全程时间，就是前面公式里的 $T_{\text{完成}} - T_{\text{到达}}$。它衡量的是“整体效率”——顾客在店里总共耗了多久。

等待时间（Waiting Time）：进程在就绪队列里纯等待的时间总和，不含执行时间。奶茶店的场景里，就是顾客下单后傻坐着等的那段时间，不含师傅制作的时间。这是调度算法真正能优化的部分：

响应时间（Response Time）：从进程到达队列到第一次获得 CPU 的时间。顾客衡量的是“多久开始做我的单”，而不是“多久做完”——交互式系统（比如你敲键盘的响应）看的就是这个。最后是吞吐量（Throughput）：单位时间内完成的进程数，奶茶店的“每小时出杯数”。

这四个指标之间存在根本性矛盾：追求最小周转时间，就要让短进程插队（SJF），但这会拉长响应时间和公平性；追求最小响应时间，就要频繁切换（RR），但切换太多又降低吞吐量。

店长的经营哲学最终归结为：想清楚你要优化哪个数字。外卖店在意吞吐量（多出杯），高端堂食店在意响应时间（先上杯水让顾客安心），排队餐厅在意周转时间（翻台率）——没有全能的算法，只有最匹配目标的算法。

算法选型实战

面对四种算法，真实系统怎么选？批处理系统（如银行夜间结算、科学计算集群）没有用户盯着屏幕，不在乎响应时间，只看吞吐量，因此常用 SJF 的变体——比如最短完成时间优先（Shortest Completion Time First）或最高响应比优先（HRRN），后者用公式 $\frac{\text{等待时间} + \text{服务时间}}{\text{服务时间}}$ 来动态权衡，避免长作业饿死。

交互式系统（如 Linux 桌面、手机系统）必须保证快速响应，否则用户会砸键盘。Linux 的 CFS（完全公平调度）就是 RR 与 MLFQ 思想的现代演进——用红黑树记录每个进程的“虚拟运行时间”，谁跑得少谁优先，既保证了公平又兼顾了响应。

实时系统（如自动驾驶、飞行控制）对调度有硬性要求：任务必须在截止时间前完成，否则就是事故。这类系统用速率单调调度（RMS）或最早截止时间优先（EDF），它们与通用调度算法完全不同，属于另一个战场。

最后说现代混合策略：多级反馈队列可以说是“通用答案”——Linux 早期使用的 O(1) 调度器就是 MLFQ 的实现，Windows 自 NT 以来的调度器也是 MLFQ 的变体。它用“新进程优先、超时降级、定期重置”三条规则，优雅地平衡了响应时间、周转时间、公平性和吞吐量四个指标，也是面试中“如果让你设计一个调度器，你会怎么做”的标准答案。

AI 应用场景

Python 演示

"""调度算法对比模拟器：在同一组进程上运行四种调度算法，输出每个进程的周转时间和等待时间，并对比平均指标。运行: python scheduler_sim.py"""from collections import deque class Process:    def __init__(self, pid, arrive, burst):        self.pid = pid        self.arrive = arrive        self.burst = burst        self.remain = burst        self.complete = 0        self.wait = 0        self.started = False def fcfs(procs):    queue = sorted(procs, key=lambda p: p.arrive)    time = 0    for p in queue:        if time < p.arrive:            time = p.arrive        p.wait = time - p.arrive        time += p.burst        p.complete = time    return time def sjf(procs):    procs = sorted(procs, key=lambda p: p.arrive)    time = 0    done = []    rest = procs[:]    while rest:        ready = [p for p in rest if p.arrive <= time]        if not ready:            time = rest[0].arrive            continue        ready.sort(key=lambda p: p.burst)        p = ready[0]        p.wait = time - p.arrive        time += p.burst        p.complete = time        rest.remove(p)    return time def rr(procs, quantum=2):    time = 0    queue = deque()    rest = sorted(procs, key=lambda p: p.arrive)    idx = 0    while idx < len(rest) or queue:        while idx < len(rest) and rest[idx].arrive <= time:            queue.append(rest[idx])            idx += 1        if not queue:            time = rest[idx].arrive            continue        p = queue.popleft()        if p.remain == p.burst:            p.wait = time - p.arrive        if p.remain <= quantum:            time += p.remain            p.remain = 0            p.complete = time        else:            time += quantum            p.remain -= quantum            while idx < len(rest) and rest[idx].arrive <= time:                queue.append(rest[idx])                idx += 1            queue.append(p)    return time def mlfq(procs, q_levels=(1, 2, 4)):    time = 0    rest = sorted(procs, key=lambda p: p.arrive)    queues = [deque() for _ in q_levels]    idx = 0    while idx < len(rest) or any(queues):        while idx < len(rest) and rest[idx].arrive <= time:            queues[0].append(rest[idx])            idx += 1        active = next((q for q in queues if q), None)        if active is None:            time = rest[idx].arrive            continue        p = active.popleft()        if p.remain == p.burst:            p.wait = time - p.arrive        level = None        for i, q in enumerate(queues):            if p in q:                level = i                break        if level is None:            level = 0        use = min(q_levels[level], p.remain)        time += use        p.remain -= use        if p.remain == 0:            p.complete = time        else:            new_level = min(level + 1, len(q_levels) - 1)            queues[new_level].append(p)    return time def report(procs, total, algo):    avg_turn = sum(p.complete - p.arrive for p in procs) / len(procs)    avg_wait = sum(p.wait for p in procs) / len(procs)    print(f"[{algo}] 完成时刻: {total}, 平均周转: {avg_turn:.1f}, 平均等待: {avg_wait:.1f}")    for p in sorted(procs, key=lambda x: x.pid):        print(f"  P{p.pid}: 到达={p.arrive} 服务={p.burst} 完成={p.complete} 等待={p.wait}") if __name__ == "__main__":    base = [Process(1, 0, 5), Process(2, 1, 3),            Process(3, 2, 2), Process(4, 3, 4)]    for algo, fn in [("FCFS", fcfs), ("SJF", sjf),                     ("RR(q=2)", lambda ps: rr(ps, 2)),                     ("MLFQ(q=1,2,4)", mlfq)]:        procs = [Process(p.pid, p.arrive, p.burst) for p in base]        total = fn(procs)        report(procs, total, algo)

1. ready.sort(key=lambda p: p.burst)SJF 每次从已到达的进程中挑出服务时间最短的那个，这就是“最短作业优先”的核心操作。
2. while idx < len(rest) and rest[idx].arrive <= time:RR 和 MLFQ 的“新进程到达”逻辑：时刻推进时，将所有已到达的进程送入就绪队列。
3. if p.remain <= quantum: time += p.remainRR 中进程剩余时间不足一个时间片时，直接跑完并记录完成时刻。
4. queues[new_level].append(p)MLFQ 中进程用完了当前队列的时间片仍没完成，就被降级到下一级队列，这是“反馈”机制的灵魂。
5. avg_turn = sum(p.complete - p.arrive for p in procs) / len(procs)计算平均周转时间，用于算法横向对比。

常见误区

面试题