CPU调度算法原理与实践

可视化演示

交互对比FCFS、SJF、Round Robin和Priority四种CPU调度算法的执行过程，通过甘特图展示进程调度顺序并计算平均等待时间与周转时间。

调度核心概念

奶茶店为什么需要店长？因为店员只有一双手，顾客却不止一位。店长不负责做奶茶，只负责回答一个问题：下一个做单的人是谁。在操作系统里，这个“回答下一个问题”的角色就是调度器。它的专业说法是：从就绪队列中挑选一个进程，把 CPU 分配给它。

调度器不是随时都在做决定，只有在特定“调度时机”才会出手。你可以理解为店长通常不会每秒钟都盯着店员，而是等某个时刻发生了才重新排单：新顾客进店、店员做完一杯、某个顾客临时改单走了、或者计时器响了。对应到操作系统，就是进程创建、进程退出、进程阻塞、中断或时间片耗尽。这些时刻决定了系统何时需要重新“排班”。

有了调度时机，还要回答“能不能打断当前这杯奶茶”。如果店员正在做一杯大果茶，而新来了一位只点柠檬水的顾客，店长能不能让他把柠檬水插队先做？如果可以，就是抢占式调度；如果必须等大果茶做完，就是非抢占式调度。抢占需要硬件定时器支持，就像需要一个“闹钟”到点提醒店长该重新排单。

调度器很像奶茶店的店长：平时不显眼，但一忙起来，店长的排单策略直接决定顾客会不会等得发火。理解“谁来决定、何时决定、能不能打断”这三件事，后面所有算法都只是店长排单的不同套路而已。

评价指标

怎么判断一个店长排单排得好不好？不能只看店员是否一刻不停，还要看顾客等多久、店里一小时能出多少杯奶茶。操作系统调度也有四个常用指标：CPU 利用率，即 CPU 真正干正事的时间占比；吞吐量，即单位时间完成的进程数；周转时间，即从进程进入系统到完成所花的总时间；响应时间，即从提交请求到用户第一次感觉“有反应”的时间。

我们用一个简单公式衡量平均等待时间：让每个顾客记录自己从进店排队到开始做单等了多久，再求平均。一个优秀的调度算法往往能降低这个平均值，但也可能带来其他代价。比如只顾着让 CPU 一直忙，可能会让长任务霸占资源，短任务体验极差。

这四个指标就像奶茶店门口的顾客满意度问卷：有的顾客在意“多久拿到奶茶”，有的在意“店员是不是先理我一下”。不存在一个算法能让四项指标同时最优，店长必须先想清楚这家店最重视什么，再选择对应的排单策略。

先来先服务

如果店长采用最简单的“先来后到”，那就是先来先服务（FCFS）。顾客进店后按顺序排队，店员从队头开始一杯一杯做，不插队也不暂停。这个策略很公平，写起来也简单：只需要维护一个先进先出队列。但它有个致命缺点——如果排在最前面的顾客点了二十杯大果茶，后面每位顾客都得瞪着他做完。

这种“一个长任务堵住后面所有人”的现象，叫作护航效应，就像一辆超慢的车走在单行道上，后面所有车只能慢慢跟着。FCFS 的平均等待时间可能非常长，尤其当长任务比短任务先到时。但它对批处理任务友好：因为没有频繁切换，店员不用反复“洗杯子换手”，系统开销很低。

FCFS 就像奶茶店的“傻瓜排单法”：规则简单、不会打起来，但一遇到大单就把整条队伍拖垮。它告诉我们，公平不等于高效，有时候“先来的大单”恰恰是让后面所有人痛苦的源头。

短作业优先

假如店长学聪明了：他决定先做耗时短的订单，让那些只点一杯柠檬水的顾客先拿到奶茶，长单最后再做。这个策略就是短作业优先（SJF）。从数学上看，它可以显著降低平均等待时间，因为短任务不必等长任务做完，整体队伍流动更快。

SJF 还有一种抢占版本，叫作最短剩余时间优先（SRTF）：如果新来的任务剩余时间比当前正在执行的任务短，店长会立刻“抢单”先做新任务。这在理论上能进一步降低平均等待时间，但代价是系统需要知道每个任务还要多久才能完成。现实中最难的不是算法本身，而是准确预估“这杯奶茶到底要做多久”。

短作业优先像“聪明店长”的排单法，但它有个大问题：如果不断有更短的订单插进来，那个超大果茶订单可能会从开门等到打烊都做不上。这就是饥饿。算法再“最优”，也不能饿死顾客；所以在真实系统里，SJF 往往要和优先级、老化等机制配合使用。

优先级调度

有些奶茶店会有会员，会员订单可以优先做。这种“按身份插队”的策略，就是优先级调度。每个进程有一个优先级数值，调度器每次从就绪队列中选择优先级最高的进程执行。优先级可以静态设定，比如系统进程高于用户进程；也可以动态调整，比如响应延迟变高就把优先级提高。

优先级调度有两种形态：如果当前正在执行的进程允许被更高优先级的进程打断，就是抢占式优先级调度；否则就是非抢占式。高优先级进程获得更快响应，但低优先级进程可能长期得不到 CPU，就像普通顾客看着 VIP 一个接一个插队，自己永远轮不上。

优先级调度的精髓不是“谁身份高谁先做”，而是“身份高的人也要记得让低身份的人有机会上桌”。老化就是店长给普通顾客偷偷加码：等太久的人会慢慢变成“临时 VIP”，这样既有优先级，又不至于饿死任何人。

时间片轮转

如果店长不想让任何一个顾客等太久，可以改成“每人做 30 秒”的轮流制：店员按队列顺序做单，每杯奶茶最多做固定的一段时间，时间一到就换下一位，做了一半的订单重新排到队尾。这就是时间片轮转（RR）。它让每个进程都能定期获得 CPU，响应时间变得均匀，特别适合交互式系统，比如你边敲键盘边等程序响应。

时间片 q 的选择非常关键。q 太大，轮转就退化成 FCFS，短任务依然要等很久；q 太小，店员频繁“换手”，光顾着洗杯子做交接，真正做奶茶的时间变少。于是系统需要在“响应够快”和“切换开销够低”之间找平衡。

时间片轮转就像奶茶店里“一人做三十秒”的规则：很公平，但换手太频繁会让店员累得做不出几杯。好的店长会把时间片设得恰到好处——短到让顾客感觉人人有份，长到店员能把一杯奶茶比较完整地做出来。

多级反馈队列

真正高级的奶茶店不会只有一条队伍，而是把顾客分成好几条队列：只点一杯的“快单”走快速通道，点了很多杯的“大单”走慢速通道。多级反馈队列（MLFQ）就是这个思路的调度版本。系统有多个优先级队列，进程先进入最高层队列，如果它在给定时间内没用完时间片（说明它是交互型短任务），就留在高层；如果它用完时间片还没结束（说明它是计算型长任务），就被降到下一层。

MLFQ 的“反馈”体现在它观察进程的历史行为：主动让出 CPU 的进程说明需要频繁交互，继续保持高优先级；总是吃满时间片的进程说明是 CPU 密集型，降到低层让它少打扰别人。这样系统不需要预先知道任务长度，也能做到“短任务快速响应，长任务在后台慢慢跑”。

MLFQ 是店长们的“集大成智慧”：先用优先级让短单快跑，又用反馈识别哪些订单其实很耗时间，把它们请到后面的队伍慢慢做。现代操作系统里许多调度器都借鉴了它的思想，因为它既不需要神预言，又能适应动态变化的负载。

实践与调优

调度算法的最终归宿是真实系统。在实时系统中，调度器不仅要选最快的任务，还要保证任务在截止时间前完成，比如无人驾驶必须定时处理传感器数据；在多核系统里，调度器要把进程分布到多个 CPU 上，避免一个核忙死、其他核闲着的“负载不均”。

Linux 的 CFS 调度器是很好的实践案例。它没有把进程抽象成“谁能插队”，而是给每个进程维护一个虚拟运行时间 vruntime。每次调度时，CFS 选择 vruntime 最小的进程执行，让所有进程在虚拟时间里尽量公平；nice 值小的进程权重高，运行同样时间 vruntime 涨得慢，自然获得更多 CPU。

实践中的调优，就像店长根据高峰期数据决定要不要加人、要不要把部分订单分流到小程序自取：先用指标观察 CPU 利用率、平均等待时间、响应延迟，再调整时间片、优先级、nice 值或队列层级。调度没有银弹，只有不断度量、对照场景、选择策略的工程循环。

AI 应用场景

Python 演示

class Process:    def __init__(self, pid, arrive, burst):        self.pid = pid        self.arrive = arrive        self.burst = burst        self.wait = 0  def make_procs():    return [        Process('P1', 0, 5),        Process('P2', 1, 3),        Process('P3', 2, 2),        Process('P4', 3, 4)    ]  def fcfs(procs):    procs.sort(key=lambda p: p.arrive)    t = 0    for p in procs:        if t < p.arrive:            t = p.arrive        p.wait = t - p.arrive        t += p.burst    return sum(p.wait for p in procs) / len(procs)  def sjf(procs):    left = procs[:]    t = 0    done = []    while left:        ready = [p for p in left if p.arrive <= t]        if not ready:            t = min(p.arrive for p in left)            continue        nxt = min(ready, key=lambda p: p.burst)        left.remove(nxt)        nxt.wait = t - nxt.arrive        t += nxt.burst        done.append(nxt)    return sum(p.wait for p in done) / len(done)  def rr(procs, quantum):    q = [(p, p.burst) for p in procs]    t = 0    wait_total = 0    while q:        p, remain = q.pop(0)        if t < p.arrive:            t = p.arrive        if remain <= quantum:            wait_total += t - p.arrive            t += remain        else:            wait_total += t - p.arrive            t += quantum            p.arrive = t            q.append((p, remain - quantum))    return wait_total / len(procs)  if __name__ == '__main__':    print('FCFS avg wait:', round(fcfs(make_procs()), 2))    print('SJF  avg wait:', round(sjf(make_procs()), 2))    print('RR q=1 avg wait:', round(rr(make_procs(), 1), 2))

1. procs.sort(key=lambda p: p.arrive)按到达时间排序，模拟顾客进店的先后顺序。
2. p.wait = t - p.arrive记录进程从进店到真正开始执行的等待时长。
3. left = procs[:]复制一份进程列表，避免修改原始数据。
4. ready = [p for p in left if p.arrive <= t]筛选出当前时刻已经排到店里等待中的进程。
5. nxt = min(ready, key=lambda p: p.burst)在已到达进程中选择服务时间最短的那个，体现 SJF 核心逻辑。
6. if remain <= quantum:判断当前进程剩余时间能否在一个时间片内完成。
7. p.arrive = t进程被抢占后重新记录它下次进入队列的时间，用于累计等待时间。
8. q.append((p, remain - quantum))未完成的进程带着剩余时间重新回到队尾，等待下一轮执行。

常见误区

面试题