调度：谁先运行

调度：谁先运行

假设你是一家诊所的护士，候诊室里有 20 个病人。你怎么决定谁先看病？先来先得？最快能看完的先来？还是根据病情紧急程度？这个决策过程就是调度（Scheduling）——操作系统用完全一样的逻辑决定哪个进程/线程下一个获得 CPU。

好的调度器需要同时满足多个矛盾的目标：让每个任务响应迅速、让 CPU 利用率最大化、让紧急任务优先、让长任务也能最终完成。没有一个调度算法能对所有场景都最优——这就是调度算法研究了几十年还没有"标准答案"的原因。

Level 1：建立直觉

为什么需要调度

CPU 只有一个（或几个核），但同时运行的进程可能有几百个。调度器的工作是：

• 在任意时刻，从"可运行"的进程中选一个让它运行
• 决定它运行多久（时间片）
• 决定什么时候切换到另一个进程

可运行队列（Run Queue）：
  [进程A] [进程B] [进程C] [进程D] ...

调度器每隔 1-10ms 问一次：
"现在应该让谁运行？"

基础调度算法

先来先服务（FCFS - First Come First Served）

最简单的策略：先到的进程先运行，直到完成或阻塞。

进程  到达时间  执行时间
A     0ms      100ms
B     1ms      10ms
C     2ms      5ms

执行顺序：A(100ms) → B(10ms) → C(5ms)
B 等了 99ms 才运行，C 等了 109ms

问题：长任务拖累短任务（护航效应）。

轮转调度（Round Robin）

每个进程轮流运行一个固定时间片（如 10ms），用完就切换：

时间片 = 10ms：
A: ██ (10ms) → B: ██ → C: ██ → A: ██ → B → A → A → A → A → A → 完成

A(100ms)等待时间 = 4次 × 10ms = 40ms
B(10ms)等待时间 = 10ms  
C(5ms)等待时间  = 20ms（加上切换开销）

优先级调度

给每个进程一个优先级，高优先级的优先运行：

Linux 优先级范围：-20（最高）到 +19（最低）
内核线程：最高优先级
普通进程：nice值0（默认）
后台任务：可以设置 nice 19

# 用低优先级运行 CPU 密集型任务
nice -n 19 ./heavy_computation

# 提高运行中进程的优先级（需要 root）
renice -n -5 -p 1234

问题：低优先级进程可能永远等不到 CPU（饥饿）。解决：老化（Aging）——随着等待时间增加，动态提升优先级。

抢占式 vs 协作式

协作式调度（Cooperative）：进程主动让出 CPU（调用 sleep()、yield() 或等待 I/O）。不主动让出就一直运行。

• 优点：切换少，开销小
• 缺点：一个进程死循环，整个系统卡死
• macOS 早期版本、早期 Windows 使用这个

抢占式调度（Preemptive）：操作系统可以在任意时刻强制切换进程（通过时钟中断）。

• 优点：公平，防止单个进程霸占 CPU
• 缺点：需要处理并发安全
• Linux、现代 Windows 使用这个

Level 2：原理剖析

Linux CFS：完全公平调度

Linux 2.6.23（2007年）引入 CFS（Completely Fair Scheduler），至今仍是默认调度器。

核心思想：让每个进程感觉自己独占了 CPU。

实现方式：虚拟运行时间（vruntime）

vruntime = 实际运行时间 × (默认权重 / 进程权重)

权重由 nice 值决定（nice=-20 最高权重，nice=+19 最低）

每次调度：选 vruntime 最小的进程运行
→ 运行时间最少的进程优先
→ 自然实现公平分配

数据结构：红黑树（按 vruntime 排序）

CFS 红黑树：
          [vt=100]
         /        \
    [vt=50]     [vt=150]
    /    \         \
[vt=20] [vt=80]  [vt=200]

每次调度：选最左节点（vt最小）= O(log n) 操作
运行完后：更新 vt，重新插入树 = O(log n)

CFS 的优雅之处：nice -20 的进程权重是 nice +19 的 ~1000 倍，但不会让低优先级进程完全饥饿——只是运行得更少。

时间片的权衡

时间片太长：响应性差（用户感觉卡顿） 时间片太短：切换开销大（每次切换 ~5-10µs，时间片 1ms 则 0.5-1% CPU 被调度开销消耗）

Linux CFS 的解决方案：动态时间片，根据可运行进程数调整：

# Linux CFS 时间片计算（简化）
TARGET_LATENCY = 6ms     # 目标：每个进程每 6ms 运行一次
MIN_GRANULARITY = 0.75ms # 最小时间片（防止切换太频繁）

def calc_timeslice(nr_running):
    if nr_running <= 8:
        return TARGET_LATENCY / nr_running
    else:
        return MIN_GRANULARITY  # 进程太多时，固定最小时间片

I/O 密集型 vs CPU 密集型

调度器需要区别对待两类进程：

CPU 密集型（如视频编码、科学计算）：
  - 很少等待 I/O
  - 总是有计算要做
  - 希望得到长时间片，减少切换

I/O 密集型（如 Web 服务器、数据库查询）：
  - 频繁等待网络、磁盘
  - 等待时不需要 CPU
  - 希望 I/O 完成后立刻能运行（响应性）

CFS 的 I/O 奖励机制：当一个进程从阻塞（等待 I/O）中恢复时，它的 vruntime 不会是"应有的最低值"（这样会让它运行太长），而是设为当前最小 vruntime + 一个小量（"唤醒预支"），让它能很快被调度到，保证交互响应性。

多核调度

单核调度的所有原则都适用，但多核有新问题：

负载均衡：把进程均匀分配到各个核，避免某核忙死、某核空闲：

NUMA 意识调度：
  服务器有 2 个 CPU（各 16 核），各有自己的内存
  进程最好留在它的"主核"附近，减少跨 NUMA 内存访问延迟

CPU 亲和性（CPU Affinity）：
  让某个进程只在指定的 CPU 核上运行
  减少缓存失效（每次迁移都会导致 L1/L2 缓存失效）

# 将进程 1234 绑定到 CPU 核 0 和 1
taskset -cp 0,1 1234

# 查看进程的 CPU 亲和性
taskset -p 1234

缓存感知调度：进程在一个核上积累了缓存，迁移到另一核会损失缓存（"缓存迁移成本"）。调度器会倾向于让进程留在同一核上（cache warm），除非负载严重不均衡。

调度延迟和 jitter

调度延迟（Scheduling Latency）：从进程"就绪"到真正开始运行的时间。

影响因素：

1. 有多少进程在排队
2. 是否有更高优先级进程在运行
3. 中断是否被屏蔽

Linux CFS 目标延迟：6ms（少于 8 个进程时）到 0.75ms × n（进程多时）。

调度 jitter：延迟的波动。实时系统最怕 jitter——你无法容忍"通常 1ms，偶尔 50ms"。

Level 3 · 规范怎么定义的（资深）

调度策略的标准与形式化分析

POSIX 标准定义了三种调度策略：SCHED_FIFO（实时先进先出）、SCHED_RR（实时轮转）和 SCHED_OTHER（默认，由实现定义）。实时策略的优先级范围至少为 1-32（Linux 实现为 1-99），实时任务始终优先于普通任务执行。POSIX 还要求实现提供 sched_setscheduler() 和 sched_getparam() 等接口来查询和修改调度参数。

Linux 的 CFS（Completely Fair Scheduler） 由 Ingo Molnár 在 2007 年引入（内核 2.6.23）。CFS 使用红黑树按"虚拟运行时间"（vruntime）排序所有可运行任务，每次选择 vruntime 最小的任务执行。CFS 的设计理论基于 公平排队（Fair Queuing）算法——源自网络领域的 WFQ（Weighted Fair Queueing），由 Demers、Keshav 和 Shenker 在 1989 年提出。CFS 的时间复杂度是 O(log n)（红黑树操作），这也是它能高效处理数万个进程的基础。

2024 年，Linux 内核引入了 EEVDF（Earliest Eligible Virtual Deadline First） 调度器替代 CFS，进一步改善了延迟敏感任务的响应时间。EEVDF 基于 Stoica 和 Abdel-Wahab 1995 年的论文，核心改进是为每个任务计算一个"虚拟截止时间"，优先调度截止时间最近的任务，从而避免 CFS 中"所有任务都公平但没有任务获得及时响应"的问题。

Level 4 · 边界与陷阱（所有人）

陷阱 1：优先级反转可以让高优先级任务饿死

当高优先级任务 H 等待低优先级任务 L 持有的锁，而 L 又被中优先级任务 M 抢占时，H 实际上被 M 阻塞了——尽管 H 的优先级比 M 高。这就是优先级反转（Priority Inversion）。1997 年火星探路者号（Mars Pathfinder）着陆后频繁重启，原因正是优先级反转导致看门狗定时器超时。修复方案是优先级继承（Priority Inheritance）：当 L 持有 H 需要的锁时，L 的优先级被临时提升到 H 的级别，防止 M 抢占 L。Linux 的 PTHREAD_PRIO_INHERIT 互斥锁属性和内核的 rt_mutex 都实现了这一机制。

陷阱 2：CPU 亲和性设置不当导致性能不升反降

将线程绑定到特定 CPU 核心（sched_setaffinity()/taskset）可以减少缓存失效——线程不会在核心间迁移，L1/L2 Cache 中的数据始终有效。但如果绑定策略不合理（如把所有线程绑到同一个核心），反而导致该核心过载，其他核心空闲。更隐蔽的问题是 NUMA 架构下的绑核：如果线程被绑到远端 NUMA 节点的核心上，它访问的内存却在本地节点，每次内存访问都要跨越 NUMA 互连，延迟增加 50-100%。正确做法是同时绑定 CPU 亲和性和内存策略（numactl --cpubind=0 --membind=0）。

陷阱 3：时间片太短增加开销，太长损害交互性

CFS 的默认调度延迟（sched_latency）是 6ms，最小时间片（sched_min_granularity）是 0.75ms。如果系统中有 100 个可运行进程，每个进程的时间片仅 0.06ms（60μs），而一次上下文切换本身就需要 1-5μs——切换开销占了总时间的 2-8%。反过来，如果把时间片设得太长（如 100ms），桌面环境中鼠标移动和键盘输入会出现明显卡顿。Linux 提供了 /proc/sys/kernel/sched_latency_ns 等调优参数，服务器通常增大这些值（减少切换），桌面系统则使用默认值或更小的值。