10.1 调度指标与经典算法

现在轮到你来决定谁先上 CPU 了。多个进程/线程在就绪队列里排队，调度器需要选择下一个。这里没有完美的策略，只有针对不同场景的权衡。

synchronization 决定 thread 何时 runnable，scheduler 决定 runnable task 何时获得 CPU。本篇用可计算 workload 比较 FCFS、SJF、RR、priority 与 MLFQ；Linux 的调度类、CFS 与 EEVDF放到下一篇。

一份“公平”的顺序可能让所有人都不满意

用三项同时到达的工作比较调度策略：

Task	CPU service	说明
A	10	长批处理
B	1	短请求
C	2	后台任务

这里只有一个 CPU，并暂时忽略 I/O、context-switch cost 与多核。各任务的完成与首次响应时间会随顺序变化。在本例的单 CPU、无额外开销且不主动闲置的模型里，全部完成的时刻始终是 13。CPU 没变快，谁先交作业变了。

现实任务不会预先交出准确“总运行时间”。这里的 service time 是教学模型输入，用于比较策略，不是 OS 可以直接读取的属性。

不同指标回答不同问题

设 task i 的 arrival、first-run、completion、CPU service 分别为 a_i、f_i、c_i、s_i。

text

response_i   = f_i - a_i
turnaround_i = c_i - a_i
waiting_i    = turnaround_i - service_i   # 仅适用于无 I/O 的简化模型

还常关注：

throughput：单位时间完成多少项；
CPU utilization：CPU 忙于有效工作占观察时间的比例；
tail latency：p95/p99 response/turnaround，而非只看平均；
slowdown：turnaround/service，避免长任务把绝对时间尺度完全主导；
fairness / starvation bound：各 task 的 CPU 份额是否符合权重，最长要等多久；
deadline miss ratio：实时 workload 中多少 job 错过 deadline。

“响应快、周转短、公平”不是严格只有三个指标，也没有一个算法能同时把所有指标独立最小化。频繁 preemption 可改善短任务 response，却增加 cache disruption 和 scheduler overhead；保留 CPU affinity 又可能牺牲全局 load balance。

FCFS：arrival order 决定 convoy

first-come, first-served 在一个 non-preemptive CPU 上让当前 task 运行到完成或 block。若 A、B、C 按表中顺序进入：

text

timeline: A [0,10) -> B [10,11) -> C [11,13)

response:   A=0,  B=10, C=11
turnaround: A=10, B=11, C=13

短任务被长任务挡在后面，形成 convoy effect。FCFS 容易实现、arrival order 清楚，但不适合需要短 response 的交互 workload。

称它“最不公平”也不准确。它对等待顺序很公平，却不区分 service length 与 urgency。公平必须先定义。

SJF 与 SRTF：理论优势依赖已知未来

若所有 task 在 t=0 已到达，且 service time 已知，non-preemptive shortest-job-first 依 B、C、A 排序：

text

timeline: B [0,1) -> C [1,3) -> A [3,13)

response:   B=0, C=1, A=3
turnaround: B=1, C=3, A=13

在“所有工作已就绪、已知长度、单机、无抢占开销”等条件下，shortest-processing-time order 最小化平均 completion/turnaround。把这个结论删掉条件，就会误导。

shortest-remaining-time-first 是 preemptive 版本：新 task 到达时，若它的剩余 service 比当前 task 小，就抢占。它仍要求准确知道或预测剩余长度；持续到来的短 task 还可能让长 task starvation。

通用 OS 常根据过去 CPU burst、sleep/wake pattern 和 priority 做间接判断，而不是知道整个 process 还会执行几秒。指数平滑可预测下一段 burst：

text

prediction_next = α × observed + (1-α) × prediction_previous

α 通常取 [0,1]，越大越重视最近一次 burst。预测误差与 adversarial workload 会改变调度效果。

Round Robin：quantum 把 response 与 overhead 连在一起

RR 维护 runnable queue，每次给 task 最多一个 quantum；没完成就排到队尾。对 A/B/C、quantum=1：

text

[0,1) A
[1,2) B completes
[2,3) C
[3,4) A
[4,5) C completes
[5,13) A completes

response:   A=0, B=1, C=2
turnaround: A=13, B=2, C=5

B 在 t=2 完成，C 在 t=5 完成；平均 turnaround 为 (13+2+5)/3 = 20/3。这里把 A 最后连续得到的 quantum 合并展示。

quantum 很长时，RR 接近 FCFS；很短时，runnable task 更快轮到，却增加 scheduling、cache/TLB 与 timer overhead。合适值取决于 workload、CPU topology、scheduler design 和 latency target，不能写成“现代 OS 都是 1–20 ms”之类固定范围。

如果只有 A runnable，它通常可连续获得后续 quantum，不必为了轮转给不存在的竞争者制造 switch。

用可执行模拟器核对时间线

保存为 scheduling.py，用 Python 3.10+ 运行。任务名必须是唯一非空字符串，arrival 是非负整数，service 与 quantum 是正整数；空 workload 返回空结果。模型会复制输入，tie 按名称排序。

python

from collections import deque
from dataclasses import dataclass, replace

@dataclass
class Task:
    name: str
    arrival: int
    service: int
    remaining: int = 0
    first_run: int | None = None
    completion: int | None = None

    def fresh(self):
        return replace(self, remaining=self.service,
                       first_run=None, completion=None)

def fresh_workload(tasks):
    copies = []
    names = set()
    for task in tasks:
        if (not isinstance(task.name, str) or not task.name
                or task.name in names):
            raise ValueError("task names must be unique nonempty strings")
        if type(task.arrival) is not int or task.arrival < 0:
            raise ValueError("arrival must be a nonnegative integer")
        if type(task.service) is not int or task.service <= 0:
            raise ValueError("service must be a positive integer")
        names.add(task.name)
        copies.append(task.fresh())
    return copies

def summarize(tasks):
    return {
        task.name: {
            "response": task.first_run - task.arrival,
            "turnaround": task.completion - task.arrival,
        }
        for task in tasks
    }

def run_nonpreemptive(tasks, key):
    pending = fresh_workload(tasks)
    time = min((task.arrival for task in pending), default=0)
    completed = []

    while pending:
        ready = [task for task in pending if task.arrival <= time]
        if not ready:
            time = min(task.arrival for task in pending)
            continue

        task = min(ready, key=key)
        task.first_run = time
        time += task.service
        task.remaining = 0
        task.completion = time
        pending.remove(task)
        completed.append(task)
    return completed

def run_round_robin(tasks, quantum):
    if type(quantum) is not int or quantum <= 0:
        raise ValueError("quantum must be a positive integer")

    pending = sorted(fresh_workload(tasks),
                     key=lambda task: (task.arrival, task.name))
    ready = deque()
    completed = []
    time = pending[0].arrival if pending else 0

    while pending or ready:
        while pending and pending[0].arrival <= time:
            ready.append(pending.pop(0))
        if not ready:
            time = pending[0].arrival
            continue

        task = ready.popleft()
        if task.first_run is None:
            task.first_run = time

        duration = min(quantum, task.remaining)
        task.remaining -= duration
        time += duration

        while pending and pending[0].arrival <= time:
            ready.append(pending.pop(0))
        if task.remaining == 0:
            task.completion = time
            completed.append(task)
        else:
            ready.append(task)
    return completed

workload = [
    Task("A", arrival=0, service=10),
    Task("B", arrival=0, service=1),
    Task("C", arrival=0, service=2),
]

fcfs = run_nonpreemptive(workload,
                         key=lambda task: (task.arrival, task.name))
sjf = run_nonpreemptive(workload,
                        key=lambda task: (task.service,
                                         task.arrival, task.name))
rr = run_round_robin(workload, quantum=1)

assert summarize(fcfs) == {
    "A": {"response": 0, "turnaround": 10},
    "B": {"response": 10, "turnaround": 11},
    "C": {"response": 11, "turnaround": 13},
}
assert summarize(sjf) == {
    "B": {"response": 0, "turnaround": 1},
    "C": {"response": 1, "turnaround": 3},
    "A": {"response": 3, "turnaround": 13},
}
assert summarize(rr) == {
    "B": {"response": 1, "turnaround": 2},
    "C": {"response": 2, "turnaround": 5},
    "A": {"response": 0, "turnaround": 13},
}

模拟器没有扣 context-switch cost，也没表示 I/O burst 或多核。当前约定把 quantum 结束时已到达的新任务先入队，再把尚未完成的当前 task 放回队尾；改变这个顺序会改变 trace。列表扫描和 pop(0) 也不是高效调度数据结构，这里优先让事件顺序可见。

priority scheduling 必须处理 starvation

priority 可以表达业务 importance、deadline class 或资源权重。static priority scheduler 若总选最高优先级，低优先级 task 可能永远 runnable 却得不到 CPU。

aging 会随等待时间提高 effective priority；weighted fair scheduling 保证长期份额；admission control 则在实时系统中拒绝无法满足的 workload。选择哪种取决于“重要”的定义。

nice 值也不是“越高越紧急”的通用 priority。Unix nice 数值通常越大，普通任务权重越低；real-time policy 使用另一套 priority 语义。应用不能把 product business priority 直接映射到 kernel RT priority，否则一个 bug 就可能饿死系统服务。

priority inversion 来自锁依赖

假设 low-priority L 持有 mutex，high-priority H 等它；medium-priority M 不需要 mutex，却持续抢占 L。H 因此被 M 间接阻塞。

text

L owns lock
H blocks on lock
M preempts L
=> H waits for M, although H outranks M

priority inheritance 让 L 在持有 H 所需 mutex 时临时继承较高 priority，尽快运行并释放。priority ceiling 是另一种协议。两者都要求 mutex implementation、scheduler policy 与 lock graph 配合，不是给 thread 调一次 nice 就能补救。

实时设计还要限制 critical-section 长度，避免在持锁时 page fault、allocation 或 unbounded I/O。priority inheritance 不能消除所有 blocking。

MLFQ 用行为近似工作类型

multi-level feedback queue 维护多级 runnable queue。一个常见教学规则是：

新 task 从高优先级、短 quantum 开始；
用满 allotment 的 CPU-heavy task 逐级下降；
经常 block 的 interactive task 保持较高响应等级；
定期 priority boost，防止底层 starvation。

只看“是否在单个 quantum 用完前 sleep”容易被 task 通过频繁短 sleep 欺骗，也会让 I/O-heavy background job 过度奖励。较完整模型按一段时间内的累计 allotment 降级，并结合 aging/boost。

MLFQ 是调度思想家族，不是“所有通用 OS 都基于同一个 MLFQ”。不同系统采用 priority queue、fair scheduler、deadline、work stealing 等组合。

多核调度多了一维：放在哪个 CPU

单核算法只选择“谁先”。SMP scheduler 还要决定：

task 留在 warm-cache CPU，还是迁移到空闲 CPU；
wakeup 是否优先回到上次运行 CPU；
simultaneous multithreading sibling 是否共享执行资源；
NUMA memory 是否离目标 CPU 很远；
heterogeneous core 的 capacity/energy 是否适合该 task；
per-CPU run queue 怎样 load balance。

global queue 容易公平但竞争大，per-CPU queue 扩展好却要 balance。work-stealing runtime 让 idle worker 从别处取 task，也会遇到 locality 与 stealing granularity 的取舍。

应用 thread pool 的 task scheduling 与 kernel CPU scheduling 是两层。pool 决定哪个 job 交给哪个 worker，kernel 决定 worker thread 何时在哪个 CPU 运行。

hard real-time 不以平均 latency 为目标

general-purpose scheduler 关注吞吐、交互性和长期份额；hard real-time 系统要求在已知 workload 与资源上证明 deadline bound。

EDF、rate-monotonic、fixed-priority preemptive 等算法都有 admission 与 utilization 条件。平均 response 很好但偶尔超时，在 hard real-time 场景仍是失败。

软实时音频/视频容忍极少 drop，常用 RT policy、memory locking、preallocation 和 bounded code path。盲目提高 priority 可能让 machine 无法响应管理任务，必须配合 resource limit、watchdog 与测试。

动手计算而不是背排名

给模拟器加入不同 arrival time，明确 simultaneous event 的 queue 顺序。
实现 SRTF，并构造长 task starvation 的 workload。
为 RR 加入每次实际切换 1 time unit 的成本，逐步缩短整数 quantum，比较有效执行时间与切换开销占比；同一 task 连续运行不计为任务切换。
输出 average 与 p95 response；找一组平均更好但 tail 更差的调度。
实现带 periodic boost 的 MLFQ，测试 CPU-heavy task 最长等待时间。
把模拟器扩展到两个 CPU，比较 global queue 与 per-CPU queue 的 migration 数。

下一层：Linux 把公平与延迟写进调度类

经典算法给出词汇和边界，却不能直接描述当前 Linux。下一篇以官方文档为准，区分 historic CFS、正在使用的 EEVDF 思路、real-time 与 deadline class，再解释 nice、lag 和 virtual deadline。

第1章逻辑

第2章集合论

第3章证明方法

第4章递归、归纳与递推

第5章关系与函数

第6章组合数学

第7章图论

第8章概率与统计

第9章数论

第10章线性代数

第11章微积分与优化

第12章信息论与数值计算

10.1 调度指标与经典算法

一份“公平”的顺序可能让所有人都不满意

不同指标回答不同问题

FCFS：arrival order 决定 convoy

SJF 与 SRTF：理论优势依赖已知未来

Round Robin：quantum 把 response 与 overhead 连在一起

用可执行模拟器核对时间线

priority scheduling 必须处理 starvation

priority inversion 来自锁依赖

MLFQ 用行为近似工作类型

多核调度多了一维：放在哪个 CPU

hard real-time 不以平均 latency 为目标

动手计算而不是背排名

下一层：Linux 把公平与延迟写进调度类