OS06 调度

调度（Scheduling）

对调度的研究：从简化假设到现实复杂性

• 一个用户只运行一个程序；

• 一个程序只有一个线程；

• 程序彼此独立。

• 硬件多样性：单核、多核、多 CPU、GPU 集群；

• 应用类型差异：桌面交互、Web 服务、大数据处理、大语言模型（LLM）推理；

• 任务行为特征：典型程序呈现 CPU Burst 模式——短时间（通常 < 8ms）密集使用 CPU，随后长时间 I/O 阻塞。

调度器需识别任务类型并动态调整策略，以优化整体性能。

调度的评价指标

吞吐量优化常通过减少上下文切换开销、高效利用缓存实现；公平性需权衡用户 vs 任务视角。

经典调度算法

FCFS（First-Come, First-Served）

• 机制：按到达顺序执行，运行至阻塞或结束。

• 问题：
• 队头阻塞（HOL Blocking）：长任务阻塞后续短任务；
• 护航效应（Convoy Effect）：I/O 密集型任务被 CPU 密集型任务拖慢。

• 适用性：简单但性能差，仅适用于批处理场景。

RR（Round Robin）

• 机制：每个任务分配固定时间片（quantum，通常 10–100ms），时间片结束时抢占并移至队尾。

• 特性：
• 最大等待时间 ≤ (n-1) × q（n 为任务数）；
• 时间片 q 需远大于上下文切换开销（否则吞吐量下降）；
• q 过小 → 频繁切换、缓存失效；q 过大 → 退化为 FCFS。

• 优缺点：
• ✅ 公平性好，无饥饿；
• ❌ 长任务性能差，缓存命中率低于 FCFS。

严格优先级调度（Strict Priority Scheduling）

• 机制：始终运行最高优先级任务；同优先级任务 RR 调度。

• 问题：
• 低优先级任务饥饿；
• 优先级反转（Priority Inversion）：高优先级任务等待低优先级任务持有的锁（如火星探路者号故障）。

• 改进：
• 动态提升长期未运行任务的优先级；
• 为低优先级队列预留 CPU 时间。

已知任务长度的调度策略

SJF（Shortest Job First）

• 机制：所有任务就绪时，按执行时间升序调度。

• 优点：最小化平均周转时间。

• 缺点：需预知任务长度；长任务可能饥饿。

STCF / SRTF（Shortest Time to Completion First）

• 机制：SJF 的抢占版本，新任务若剩余时间更短则立即抢占。

• 特性：
• 性能 ≥ SJF；
• 对短任务极度友好，但长任务可能永久饥饿；
• 需准确预测任务长度（可通过历史 CPU Burst 拟合，如拉格朗日插值）。

预测方法：利用任务过往的 CPU Burst 长度预测未来行为。

比例份额调度（Proportional Share Scheduling）

彩票调度（Lottery Scheduling）

• 机制：
• 每个任务分配若干“彩票”；
• 调度时随机抽取一张彩票，对应任务获得 CPU；
• 短任务可分配更多彩票以提升响应性。

• 优点：
• 无饥饿（每个任务至少一张彩票）；
• 开销小，无需维护复杂状态；
• 支持彩票货币（用户发行子彩票）、转让、通胀。

• 缺点：随机性导致短期不公平。

步长调度（Stride Scheduling）

• 机制：
• 步长 = 大常数 / 彩票数；
• 每任务维护“行程”（pass），执行后增加步长；
• 调度器选择行程最小的任务。

• 优点：绝对公平，无随机波动。

• 缺点：新任务行程初始化困难。

MLFQ（Multi-Level Feedback Queue）

核心设计

• 多级队列：高优先级队列时间片短（如 1ms），低优先级队列时间片长（如 100ms）；

• 初始策略：新任务放入最高优先级队列；

• 降级规则：若任务用完时间片仍未阻塞，则移入低一级队列；

• 升级规则：若任务在时间片内主动放弃 CPU（如 I/O），则保留在当前或升入更高队列。

改进与挑战

最终规则

1. 优先运行高优先级队列任务；

2. 新任务进入最高优先级队列；

3. 用完时间配额则降级；

4. 每隔周期 S，所有任务重置到最高优先级。

MLFQ 是 Unix/Linux 早期调度器的基础。

多处理器调度

调度模型

负载均衡技术

• 工作迁移（Migration）：定期将任务从繁忙 CPU 迁移到空闲 CPU；

• 工作窃取（Work Stealing）：空闲 CPU 主动从其他队列“窃取”任务。

Linux 实践：O(1) 和 CFS 使用多队列；BFS（Brain Fuck Scheduler）使用单队列。

多处理中的自旋锁优化

基本自旋锁

性能问题与优化

• 问题：test_and_set 是写操作，导致缓存行在核心间“乒乓”传递。

• 优化：Test-Test-and-Set
• 减少不必要的原子写，降低缓存一致性开销。

适用场景

• 等待时间极短（< 上下文切换开销）；

• 多核系统中屏障同步。

Gang Scheduling

• 思想：协作线程组（如并行任务）应同时被调度到多个 CPU 上。

• 优势：
• 减少自旋等待时间；
• 提升并行效率。

• 现代实践：OS 调度单位是线程，但可通过 CPU 亲和性（affinity）绑定线程组。

实时调度（Real-Time Scheduling）

硬实时 vs 软实时

经典算法

EDF 最优但开销大；RMS/DMS 简单但保守。

饥饿（Starvation）与解决方案

饥饿定义

各算法的饥饿风险

解决思路

• 老化（Aging）：随等待时间增加，动态提升优先级；

• 定期重置：如 MLFQ 的周期性重置；

• 资源预留：为低优先级任务保留最小 CPU 份额。

根本目标：在效率与公平间取得平衡，优先保障 I/O 密集型和交互式任务。

调度策略的演变历程

1. 1960s–1970s：分时系统与优先级

• 目标：大型机上混合 CPU 密集型（科学计算）与交互式任务（终端）；

• 方法：交互任务高优先级，后台任务低优先级。

2. 1980s：个人计算机与公平性

• 需求：防止单任务垄断 CPU（如渲染阻塞用户操作）；

• 代表：Unix nice 值（-20 到 19），用户自愿降低优先级。

3. 1990s–2000s：互联网与可预测性

• 挑战：服务器整合、突发流量；

• 重点：延迟 SLO（如 P95 < 100ms）、资源隔离。

Linux 调度器演进

O(1) 调度器（Linux 2.6）

核心设计

• 140 级优先级：
• 0–99：实时任务（不可 nice）；
• 100–139：用户任务（nice -20 → 100，nice +19 → 139）。

• 双队列（Active/Expired）：
• Active：当前可运行任务；
• Expired：时间片耗尽任务；
• Active 空时原子交换两队列。

• 位图优化：140 位位图快速定位最高优先级非空队列。

动态优先级调整

• I/O 密集型任务：频繁睡眠 → 提升优先级；

• CPU 密集型任务：长时间运行 → 降低优先级；

• 防饥饿：Expired 队列中长期未运行任务优先级提升。

时间片分配

• 公式：时间片 = BASE + (140 - priority) × GRANULARITY

• 示例：优先级 100 → 200ms，139 → 10ms。

优势：O(1) 复杂度，实时任务绝对优先；缺陷：启发式规则复杂，公平性不足。

CFS（Completely Fair Scheduler，Linux 2.6.23+）

核心思想

关键机制

• 虚拟运行时（vruntime）：
• vruntime += 实际运行时间 × 1024 / 权重
• 权重由 nice 值决定：权重 = 1024 / (1.25)^nice

• 红黑树：以 vruntime 为键，O(log N) 定位最小 vruntime 任务。

• 时间片动态计算：
• 时间片 = max(目标延迟 / 任务数, 最小粒度)
• 默认：目标延迟 = 20ms，最小粒度 = 1ms。

交互性优化

• 睡眠补偿：睡眠期间 vruntime 不增长，唤醒后优先调度；

• 新任务优待：初始 vruntime 设为当前最小值。

对比 O(1)

CFS 通过数学化机制，在公平性、吞吐量、响应性间取得平衡。

死锁（Deadlock）

死锁 vs 饥饿

• 饥饿：部分线程无进展，但系统整体有进展；

• 死锁：所有相关线程互相等待，系统停滞。

死锁四条件（Coffman 条件）

1. 互斥（Mutual Exclusion）：资源一次仅一任务使用；

2. 持有并等待（Hold and Wait）：持有资源同时等待其他资源；

3. 非抢占（No Preemption）：资源只能自愿释放；

4. 循环等待（Circular Wait）：等待关系成环。

破坏任一条件即可避免死锁。

哲学家进餐问题

• 场景：N 哲学家，N 筷子，需同时获取左右筷子；

• 死锁条件：所有哲学家同时拿起左筷子；

• 解决方案：
• 资源排序（如先拿编号小的筷子）；
• 限制同时进餐人数 ≤ N-1。

死锁处理策略

1. 预防（Prevention）

• 程序员责任：编写无死锁代码；

• 方法：
• 资源排序：所有线程按全局偏序（如地址）请求锁；
• 一次性分配：启动时申请所有资源。

2. 避免（Avoidance）

• OS 责任：在分配前检查是否进入不安全状态；

• 银行家算法：
• 模拟分配后，检查是否存在安全序列（所有任务可完成）；
• 安全则分配，否则阻塞。

3. 检测与恢复

• 定期检测：构建资源分配图，检测环；

• 恢复：终止任务、回滚状态、抢占资源。

4. 忽略

• 现实策略：内核避免死锁，用户态死锁由应用处理（如重启）。

根本解决：减少资源共享、虚拟化资源、要求一次性申请。

现代计算机系统的调度研究

关键概念

前沿调度系统

1. ZygOS：微秒级低尾延迟

• 问题：数据中心 RPC 的尾延迟难以满足 SLO；

• 方案：
• 单队列 + 工作窃取：全局负载均衡，避免多队列局部过载；
• 数据平面优化：无共享架构，减少锁竞争；
• 精简内核：降低上下文切换开销。

• 效果：尾延迟降低至 SLO 的 10 倍以内，吞吐量提升 1.5 倍。

洞见：单队列在尾延迟敏感场景优于多队列。

2. Shinjuku：动态时间片 RR

• 核心：根据任务优先级动态调整时间片；

• 应用：亚毫秒级 RPC 服务；

• 效果：尾延迟比传统 RR 降低 40%。

3. Tiresias：分布式深度学习调度

• 挑战：
• 任务执行时间不可预测；
• GPU 资源需同时分配 Worker 和 PS；
• 强制合并放置导致资源浪费。

• 方案：
• 二维调度（2DAS）：同时考虑 GPU 数量（空间）和剩余时间（时间）；
• 智能放置：基于 RDMA 分析，动态决定是否合并；
• 离散化 LAS：避免高成本抢占。

• 效果：平均作业完成时间（JCT）降低 5.5 倍。

4. DRF（Dominant Resource Fairness）

• 问题：多资源（CPU、内存、GPU）公平分配；

• 核心：
• 主导资源：用户占用比例最高的资源；
• 主导份额：在主导资源上的占用比例；
• 分配原则：最大最小公平化主导份额。

• 示例：
• 总资源：9 CPU, 18 GB；
• 用户 A（1 CPU, 4 GB）→ 主导资源 = 内存；
• 用户 B（3 CPU, 1 GB）→ 主导资源 = CPU；
• DRF 分配：A 得 2 CPU+8 GB（主导份额 66%），B 得 6 CPU+2 GB（主导份额 66%）。

• 优势：满足策略无关性（strategy-proof）、帕累托最优。

5. FairRide：公平缓存共享

• 问题：传统缓存（LRU/LFU）不公平，易被欺骗；

• 方案：
• 最大最小公平：初始均分缓存；
• 概率阻塞：共享文件访问按 p = 1/(n+1) 阻塞（n 为共享用户数）；

• 保证：
• 隔离性：性能 ≥ 静态分配；
• 策略无关性：无法通过作弊获益。

• 折中：放弃严格帕累托效率，实现“近最优”。

新兴场景调度

Jolteon：Serverless Workflow 调度

• 目标：在成本与延迟间权衡；

• 建模：
• 白盒：计算耗时 ∝ 1/资源量；
• 黑盒：无先验，动态学习；

• 优化：给定成本最小化延迟，或给定延迟最小化成本。

DistServe / LoongServe：大语言模型调度

• 挑战：
• Prefill（计算密集）与 Decode（内存密集）阶段特性不同；
• 长上下文导致显存与计算超线性增长；
• 静态并行策略不适应负载变化。

• 方案：
• 解耦 Prefill/Decode：分别 batching；
• 弹性并行度：动态调整 GPU 数量，减少通信开销；
• KV Cache 优化：降低显存碎片与传输开销。

总结与对比

未来方向：结合 ML 预测任务特征、探索量子调度、面向 Serverless/LLM 的专用调度器。