请求调度策略：FCFS、Preemptive、Length-aware、Deadline-aware 调度器技术

可视化演示

\u5c55\u793a\u5de5\u5382\u65b9\u6cd5\u6a21\u5f0f\u7684\u5bf9\u8c61\u521b\u5efa\u6d41\u7a0b\uff1a\u5ba2\u6237\u7aef\u901a\u8fc7\u5de5\u5382\u63a5\u53e3\u521b\u5efa\u4ea7\u54c1\uff0c\u65e0\u9700\u5173\u5fc3\u5177\u4f53\u5b9e\u73b0\u3002

初识调度器：排菜板上的学问

老周第一次承包后厨时，最怕的不是颠勺，而是面对满墙点单不知道先做哪道。他给自己立了条规矩：新单贴到排菜板最右端，做完一道就撕掉最左边那张。这张排菜板，就是后厨的“调度器”，而每一张点单，就是一个个等待处理的“请求”。

计算机世界里的调度器（Scheduler）扮演着同样的角色：请求先进入队列排队，调度器按照某种策略从中选出下一个任务，交给执行单元（相当于灶台）处理。调度器选得聪明，系统吞吐量就高——单位时间内能处理完的请求数多；选得糟糕，大家都堵在队列里干瞪眼。

衡量一个调度方案通常看三个目标：公平性（每个请求都被合理对待）、效率（平均等待时间短、吞吐高）、及时性（满足截止时间要求）。在排队论中，Little 定律把积压、到达率和停留时间的关系浓缩成一个简洁公式：

$$\displaystyle L = \lambda \times W$$

1. 积压量 L：当前排队等待处理的请求数量，单位是“个”。

$$\displaystyle L$$

2. 到达率 λ：单位时间内进入系统的新请求数，单位是“请求/秒”。

$$\displaystyle \lambda = \frac{N_{\text{arrivals}}}{T}$$

3. 平均停留 W：一个请求从进入队列到处理完成的平均耗时，单位是“秒”。

$$\displaystyle W = \frac{T_{\text{span}}}{N_{\text{completed}}}$$

4. 守恒关系：三者相乘得到积压，这正是 Little 定律的核心结论。

$$\displaystyle L = \lambda \times W$$

老周的排菜板就是一个小型调度器，他每次决定“下一道做谁”，都在公平、翻台率（吞吐）和出餐速度（延迟）之间做权衡。下面四种心法，正是他在不同客流量下摸索出的排菜方案——每一种都有脾气，也都有软肋。

FCFS 先来先服务

开业头一个月，老周只认死理：先来先做。客人虽然要等，但没人能指责他不公平，毕竟所有人都按先来后到排着队。他管这叫“排菜板面前人人平等”。

这对应的就是 FCFS（First Come First Serve，先来先服务）。调度器维护一条 FIFO 队列（先进先出），请求完全按到达顺序依次执行。它的优点突出：实现简单、绝对公平、没有请求会被饿死——这是它至今仍被广泛使用的原因。

但 FCFS 有个著名的毛病——尾随效应（Convoy Effect）：一个长任务挡在最前面，后面所有短任务都得陪它等。要算一个请求的等待时间也很直接：它等于排在它前面的所有请求执行时间之和。

$$\displaystyle \overline{W} = \frac{1}{n}\sum_{i=1}^{n} W_i, \qquad W_i = \sum_{j=1}^{i-1} P_j$$

1. 单请求等待 W_i：第 i 个请求要等它前面 i−1 个请求全部做完，因此等待时间等于这些请求执行时间的总和。

$$\displaystyle W_i = \sum_{j=1}^{i-1} P_j$$

2. 平均等待 W̄：把所有请求的等待时间加起来，再除以请求总数 n，就是系统整体的平均等待。

$$\displaystyle \overline{W} = \frac{1}{n}\sum_{i=1}^{n} W_i$$

3. 合成表达式：将 W_i 代入平均值公式，得到 FCFS 平均等待时间的统一形式。

$$\displaystyle \overline{W} = \frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{i-1}P_j$$

有一天，一桌客人点了炖牛腩，后面跟着三份素面。素面 20 秒就能出，却硬生生等了 50 分钟，客人拍桌而起。老周这才明白：FCFS 的公平只是“先来后到”的公平，代价却是大多数短请求为少数长请求陪跑。

抢占式调度 Preemptive

面馆后来有了 VIP 包厢和外卖档口。老周定下新规矩：包厢的单一到，无论手上在做哪道菜，先放下，做包厢的。客人们渐渐发现，有时候菜做到一半，厨师突然熄火换菜。

这就是抢占式（Preemptive）调度：高优先级请求可以打断正在执行的请求。被打断的任务保留当前进度，重新回到就绪队列；处理器立刻切换给新来的高优先级任务。它特别适合“响应时间敏感”的场景，比如在线交互请求优先于后台批处理。

抢占的代价是上下文切换（Context Switch）：像换锅前要洗锅一样，系统必须保存旧任务的现场、载入新任务的现场，这段纯开销会随抢占次数线性增长。同时，低优先级任务可能被反复打断，长期得不到执行——这就是饥饿（Starvation）。

$$\displaystyle T_{\text{total}} = \sum_{i=1}^{n} P_i + N_{\text{preempt}} \times C_{\text{switch}}$$

1. 有效工作量：所有任务自身需要的执行时间总和，这是绕不开的底账。

$$\displaystyle \sum_{i=1}^{n} P_i$$

2. 切换开销：每次抢占都触发一次上下文切换，单次成本记为 C_switch。

$$\displaystyle N_{\text{preempt}} \times C_{\text{switch}}$$

3. 总时间合成：有效工作量加上所有切换开销，就是抢占式调度的实际总耗时。

$$\displaystyle T_{\text{total}} = \sum_{i=1}^{n} P_i + N_{\text{preempt}} \times C_{\text{switch}}$$

老周用抢占式解决了“VIP 不满意”的难题，却很快发现：洗锅次数暴增，普通客人怨声载道。他恍然大悟——抢占解决的是“重要任务的响应速度”，而不是“后厨的整体效率”。

长度感知调度 Length-aware

一位老主顾给老周支招：先把素面、凉菜、小炒这类快菜做掉，让客人赶紧吃完腾桌子，翻台率自然上来；炖牛腩这种硬菜慢慢熬，反正客人已经坐下等了。

这就是长度感知（Length-aware）调度，典型算法是 SJF（Shortest Job First，短作业优先）：按请求的预估执行时间升序排列，最短的先做。在“所有请求同时到达、时长估计准确”的理想条件下，理论上可以证明它给出最小的平均等待时间。

直觉很简单：短任务排在前面，它让后面等它的任务数量更少、代价更小。但两个现实问题随之而来——执行长度靠预估，估错就失去最优性；长任务不断被新到的短任务推后，极端情况下会被饿死。

$$\displaystyle \overline{W}_{\text{SJF}} = \frac{1}{n}\sum_{k=1}^{n} (n - k) \times L_{(k)}$$

1. 长度排序：把任务按处理长度升序排成序列，带括号的下标表示“第 k 小”。

$$\displaystyle L_{(1)} \le L_{(2)} \le \cdots \le L_{(n)}$$

2. 影响面计算：第 k 短的任务执行时，排在它后面的 n−k 个任务都要额外等待 L(k)。

$$\displaystyle (n - k) \times L_{(k)}$$

3. 求和平均：把所有任务的“影响面”累加起来，除以任务总数 n，就是 SJF 的平均等待时间。

$$\displaystyle \overline{W}_{\text{SJF}} = \frac{1}{n}\sum_{k=1}^{n} (n - k) \times L_{(k)}$$

翻台率确实上去了，可炖牛腩的客人等到夜里十一点才吃上，气冲冲打了差评。老周苦笑：短作业优先把“平均体验”做到最优，却把“单个人”的公平牺牲了。

截止时间感知调度 Deadline-aware

外卖平台给老周下了死命令：每单必须在倒计时结束前出餐。老周于是给排菜板上每张单都贴一个“剩余时间”标签，每次先从倒计时最短的开始做。这就是截止时间感知。

Deadline-aware 调度的代表是 EDF（Earliest Deadline First，最早截止优先）：按绝对截止时间升序执行，截止时间越近优先级越高。实时系统、带 SLA 约束的数据任务都爱用它，因为“按时完成”是硬指标。

在可抢占、任务相互独立、周期等于截止时间的理想模型下，EDF 被证明是最优的：只要所有任务的总利用率不超过 1，就能保证每个任务都在截止时间前完成。这个可调度条件用公式表达为：

$$\displaystyle U = \sum_{i=1}^{n} \frac{C_i}{T_i} \le 1$$

1. 最坏执行时间 C_i：任务 i 在最坏情况下的执行时间，是计算利用率的分子。

$$\displaystyle C_i$$

2. 周期与截止 T_i：任务 i 的到达周期，理想模型中等于它的截止时间，作为分母。

$$\displaystyle T_i$$

3. 单任务利用率：它表示任务 i 在单位时间内占用处理器的时间比例。

$$\displaystyle \frac{C_i}{T_i}$$

4. 总利用率条件：所有任务占用比例之和不超过 1，EDF 就能保证所有任务满足截止时间。

$$\displaystyle U = \sum_{i=1}^{n} \frac{C_i}{T_i} \le 1$$

换了这套排法，外卖差评清零了。但老周心里清楚：如果订单多到后厨利用率超过 100%，再聪明的倒计时排序也没用——过载时 EDF 反而会连环超时，像多米诺骨牌一样一张接一张倒下。

调度器对比：没有银弹，只有场景

三个月后，老周把四种心法都贴在后厨墙上，对着上菜口喊号：早市素面多，先做快的；晚市包厢多，VIP 优先；外卖高峰，倒计时优先；普通时段，先来先做。每种场景配一套打法。

四种策略其实各自优化了不同的目标：FCFS 保公平与简单；抢占式保高优先级响应；长度感知降平均等待；截止时间感知保按时完成。没有全局最优的调度器，只有与业务场景最匹配的调度器。

选型时可以给四个维度打分，再用业务权重合成。权重代表业务诉求，比如外卖平台把“按时率”的权重拉满，而街坊小店可能更在乎“翻台率”。

$$\displaystyle S = \alpha F + \beta T + \gamma L + \delta D, \qquad \alpha + \beta + \gamma + \delta = 1$$

1. 四维评分：F（公平）、T（吞吐）、L（延迟）、D（准时率）分别代表策略在四个维度上的得分。

$$\displaystyle F, \ T, \ L, \ D$$

2. 业务权重：α、β、γ、δ 是业务对四个维度的看重程度，它们之和必须为 1。

$$\displaystyle \alpha + \beta + \gamma + \delta = 1$$

3. 加权总分：把四项评分按权重合成，得到综合得分 S，哪个策略 S 高就选哪个。

$$\displaystyle S = \alpha F + \beta T + \gamma L + \delta D$$

老周的排班表越用越顺，他还发明了组合拳：先按紧急度分桶，桶内再按出菜时长排序。这套“分级后再排序”的做法，正是生产系统中多级队列（Multi-level Queue）的雏形。

工程实践与演进：用数据做决策

老周不再拍脑袋了。他每天记账：平均出餐时间、等最久的客人等了多久、外卖超时了几单。数据一出来，该调哪个参数一目了然，面馆生意跟着蒸蒸日上。

工程上落地调度器，核心就两件事：定义指标、持续调参。线上系统最常用的指标有平均等待时间、P99 延迟（最慢的 1% 请求的表现）和 SLA 满足率。没有指标约束的调度器，就像没有记账的面馆，永远在凭感觉经营。

SLA（Service Level Agreement，服务等级协议）满足率是 deadline-aware 系统最关心的监控指标，它衡量“按时完成”的比例：

$$\displaystyle SLA = \frac{N_{\text{succ}}}{N_{\text{total}}} \times 100\%$$

1. 总请求数 N_total：统计窗口内进入系统的全部请求数量。

$$\displaystyle N_{\text{total}}$$

2. 达标请求数 N_succ：其中在截止时间前完成的请求数量。

$$\displaystyle N_{\text{succ}}$$

3. 计算满足率：两者相除得到达标比例，再乘以 100% 转成百分比。

$$\displaystyle SLA = \frac{N_{\text{succ}}}{N_{\text{total}}} \times 100\%$$

当 SLA 指标恶化时，老周就调整队列长度、插队阈值、长度预估系数。他的演进路线也清晰：从单一策略出发，逐步走向多级队列，最终根据实时客流自动切换策略——这正是自适应调度的方向。道理相通：调度没有银弹，只有观察、调整、再观察。

AI 应用场景

Python 演示

# -*- coding: utf-8 -*-"""四种请求调度策略对比：FCFS / SJF(长度感知) / EDF(截止时间) / 抢占式优先级"""  def fcfs(jobs):    jobs = sorted(jobs, key=lambda x: x["arrival"])    t = 0    for j in jobs:        t = max(t, j["arrival"]) + j["length"]        j["done"] = t        j["miss"] = j["done"] > j["deadline"]    return jobs  def sjf(jobs):    jobs = sorted(jobs, key=lambda x: x["length"])    t = 0    for j in jobs:        t = max(t, j["arrival"]) + j["length"]        j["done"] = t        j["miss"] = j["done"] > j["deadline"]    return jobs  def edf(jobs):    jobs = sorted(jobs, key=lambda x: x["deadline"])    t = 0    for j in jobs:        t = max(t, j["arrival"]) + j["length"]        j["done"] = t        j["miss"] = j["done"] > j["deadline"]    return jobs  def preemptive_priority(jobs, priority):    jobs = sorted(jobs, key=lambda x: x["arrival"])    todo = list(jobs)    remain = {j["name"]: j["length"] for j in jobs}    t = 0    while todo:        ready = [j for j in todo if j["arrival"] <= t]        if not ready:            t += 1            continue        nxt = min(ready, key=lambda j: priority[j["name"]])        t += 1        remain[nxt["name"]] -= 1        if remain[nxt["name"]] == 0:            nxt["done"] = t            nxt["miss"] = nxt["done"] > nxt["deadline"]            todo.remove(nxt)    return jobs  def report(title, jobs):    print("==" + title + "==")    for j in jobs:        print(j["name"], "done:", j["done"], "deadline:", j["deadline"], "--", "MISS" if j["miss"] else "ok")    print()  if __name__ == "__main__":    master = [        {"name": "A", "arrival": 0, "length": 30, "deadline": 90},        {"name": "B", "arrival": 0, "length": 50, "deadline": 60},        {"name": "C", "arrival": 0, "length": 20, "deadline": 130},        {"name": "D", "arrival": 0, "length": 40, "deadline": 170},    ]    report("FCFS", fcfs([dict(j) for j in master]))    report("SJF-length-aware", sjf([dict(j) for j in master]))    report("EDF-deadline-aware", edf([dict(j) for j in master]))    prio = {"B": 0, "D": 1, "A": 2, "C": 3}    report("Preemptive-priority", preemptive_priority([dict(j) for j in master], prio))

1. jobs = sorted(jobs, key=lambda x: x["arrival"])按到达时间排序，这是 FCFS 的排队基础。
2. t = max(t, j["arrival"]) + j["length"]当前时刻推进到该请求执行完成的时刻。
3. j["miss"] = j["done"] > j["deadline"]完成时刻超过截止时间即标记为超时。
4. jobs = sorted(jobs, key=lambda x: x["length"])长度感知调度的核心：最短的排最前。
5. jobs = sorted(jobs, key=lambda x: x["deadline"])EDF 的核心：截止时间最早的排最前。
6. remain = {j["name"]: j["length"] for j in jobs}记录每个请求的剩余执行时间。
7. nxt = min(ready, key=lambda j: priority[j["name"]])抢占式每次选出优先级最高的任务执行一个时间片。
8. report("EDF-deadline-aware", edf([dict(j) for j in master]))用浅拷贝保证四种策略互不污染数据。

常见误区

面试题