OS: CPU Scheduling Scheme

参考: 中国科学院大学 2025年秋《高级操作系统教程》课件

调度器的目标:

• 降低周转时间
• 降低响应时间
• 实时性：在任务的截止时间内完成任务
• 公平性：每个任务都应该有机会执行，不能饿死
  越公平，周转时间越差
• 开销低：调度器是为了优化系统，而非制造性能 BUG
• 可扩展：随着任务数量增加，仍能正常工作

• 周转时间(turnaround time) = 完成时间 - 进入系统时间
• 响应时间(reponse time) = 首次运行时间 - 进入系统时间

调度的挑战:

• 缺少信息（没有先知）
  • 工作场景动态变化
• 线程/任务间的复杂交互
• 调度目标多样性
  • 不同的系统可能关注不一样的调度指标
• 许多方面存在取舍
  • 调度开销 V.S. 调度效果
  • 优先级 V.S. 公平
  • 能耗 V.S. 性能

非抢占式调度 (Non-Preemptive)

FIFO 调度/FCFS 先到先服务(First Come First Served)

• 优点：简单，易于实现
• 缺点：
  • 平均周转、响应时间较长
  • 存在护航效应

护航效应 convoy effect：耗时较少的潜在资源消费者被排在重量级的消费者之后

SJF 最短任务优先(Shortest Job First)

• 优点：平均周转时间短
• 缺点：
  • 不公平，可能导致任务饿死
  • 平均响应时间过长
  • 并不能解决护航效应的问题
  • 需要预知任务时间

抢占式调度 (Preemptive)

每次任务执行一定时间后会被切换到下一任务，而非执行至终止

通过定时触发的时钟中断实现

大量的 OS 机制是时间驱动的

• 更新系统在线时间: uptime
• 更新日历时间
• SMP 系统中，对运行队列进行负载均衡
• 运行已到期的定时器
• 更新资源和进程统计信息
  • 如time ls;对时间进行剖析

最短完成时间优先 (STCF, Shortest Time-to-Complete First)

相当于抢占式 SJF:

• 只考虑周转时间，且已知任务时间，任务只使用cpu 的情况下，是最优的
• 无法预知任务时间

Round-Robin 轮转调度

基本思路: 轮询，一个时间片运行一个工作，然后切换

• 优点：公平、平均响应时间短
• 缺点：周转时间很差
  • 当每个任务的执行时间差不多时最为明显

trade-off: 时间片(time slice) 的选择

• 长度必须是时钟中断周期的倍数
• 时间片长度越短: 响应时间越好, 上下文切换开销越高
  • 保存恢复寄存器现场
  • cache，TLB，分支预测器等的刷新
• 时间片长度越长: 类似于 FCFS

多级反馈队列 (Multi-level Feedback Queue, MLFQ)

• 起源: 1962，Corbato，时分共享系统 CTSS
• 解决的问题:
  • 优化周转时间：先执行短工作
  • 降低响应时间
• 结构: 独立的队列
  • 一个工作只能出现在一个队列里
  • 每个队列可以有多个工作
• 优先级决定执行
  • 同一队列的工作有相同的优先级：采用轮转调度
  • 每个队列有不同的优先级：优先执行高优先级任务

关键：如何设置优先级? 动态设定优先级

• 工作进入系统时，最高优先级
• 根据进程消耗时间降低优先级 accounting
• 周期性提升所有工作优先级

根据进程消耗时间降低优先级 accounting

方式 1:

• 进程主动释放 CPU（在时间片内），保持优先级不变;
• 进程长时间占用 CPU （用完时间片），降低优先级
• 问题：容易被欺骗，进程在时间片即将用完之前释放 cpu

方式 2: 进程用完在某一层的时间配额时，降低优先级

周期性提升所有工作优先级

• 解决进程的 starvation 饿死
• 可以正确对待 CPU 密集型进程与交互型(IO 密集型)进程之间的变化
• 困难：如何确定周期(voo-doo constant)？

MLFP 变体

• 大多数MLFP变体：支持不同队列可变的时间片长度
  • 高优先级时间片短，切换更快
• Solaris：提供一组表决定如何调整优先级
• FreeBSD：使用量衰减 (delay-usage) 算法

特殊使用

• 有些系统将最高优先级队列留给操作系统使用
• 有些系统允许用户给出优先级设置建议(UNIX Niceness)
  • -20 .. 19 的整数，越 nice 越让别人得到 CPU
  • -20: 极坏
  • 19: 极好

比例份额调度/公平份额调度 (proportional-share / fair-share)

最终目的: 确保每个工作获得一定比例的 CPU 时间(解决进程饿死的问题)，而非优化周转时间和响应时间

彩票调度 (lottery scheduling)

基本思路: 每个进程拥有不同的份额，每次调度从总份额里随机抽取一个数，
落到哪个进程就调度哪个进程。（从概率上满足期望的比例，但不确保）

• 占有份额的多少决定进程的优先级高低
• 转让（ticket transfer）：进程可以临时将自己的份额转让给其他进程
  • 应用于服务器/客户端交互，客户端可以加速服务器执行自己的请求
• 通胀（ticket inflation）：进程可以临时提升自己的份额数量
  • 适用于进程之间互相信任的环境

评估:

• 避免特殊的工作负载的影响
• 实现简单，几乎不需要记录任何状态，只需要一个随机数生成器
• 速度很快
• 不确定性：偶尔不能产生正确的比例
• 困难：如何为每个进程分配份额？

步长调度 (stride schedulingg)

应用于Linux Complete Fair Scheduling (CFS)

基本思路:

• 步长 stride：与份额数成反比
• 行程值 pass：计数器，累加步长，记录总体进展
• 每次调度时，选择拥有最小行程值的进程

评估:

• 解决了彩票调度的不确定性问题
• 需要为每个进程记录全局状态
• 问题：如何加入新进程？
  如果行程值设为0，则其独占CPU。

多处理器调度 (Multiprocessor Scheduling)

单队列多处理器调度 (Single Queue Multiprocessor Scheduling, SQMS)

单处理器调度策略直接加锁实现

trade-off:

• 简单，不需要太多修改
• 缺乏可扩展性(scalability)
• 不能很好地保持缓存亲和度
  • 大多数系统都引入一些亲和度机制：
  • 保持一些工作的亲和度的同时，牺牲一部分工作的亲和度

多队列多处理器调度(Multi-Queue Multiprocessor Scheduling, MQMS)

基本框架: 采用多个调度队列

• 每个 CPU 都有自己的调度队列，每个 CPU 调度之间互相独立
• 每个任务进入系统后根据一些启发性规则进入某个调度队列
• 每个队列可以使用不同的调度规则

trade-off:

• 具备可扩展性 (scalability)
• 具有良好的缓存亲和度
• 存在负载不均 (load imbalance) 问题

应对负载不均问题：迁移(migration)

• 不断迁移任务到其他 CPU 以实现负载均衡
• 工作窃取(work stealing)：任务少的队列检查其他队列的任务是不是更多，是则窃取任务
  • trade-off：寻找合适的检查频率
    • 检查太频繁：带来较高开销
    • 检查间隔太长：带来负载不均

Linux 多处理器调度

未达成共识：(Linux 3种调度算法)

O(1)调度	CFS 完全公平调度	BFS调度
多队列	多队列	单队列
基于优先级调度	基于比例调度	基于比例调度
类似 MLFQ	类似步长调度	最早最合适虚拟截止时间优先算法(EEVEF)

多处理器调度的困难之处

• 负载不均 (load imbalance) 与缓存亲和度 (cache affinity) 的 trade-off
• 优先级反转问题：
  进程持有锁时被切换到中间优先级进程，再切换到高优先级需要同样的锁的进程
• 多用户：单线程的A和10,000线程的B在CFS上共享CPU
• 异构处理器：大小核性能差异
• 分布式系统：无法避免的节点失效和网络延迟
• NUMA (Non-uniform memory access)
  共享内存密集型程序在远/近 CPU 上性能差达到数倍
• 优先级反转问题

优先级反转问题

应对:

• Linux：摆烂
• 实时系统
  • 优先级继承 (Priority Inheritance)/ 优先级提升 (Priority Ceiling)
    持有 mutex 的线程/进程会继承 block 在该 mutex 上进程的最高优先级，但也不是万能的 (例如条件变量唤醒)
  • 对潜在的优先级反转进行预警 (lockdep)
    避免高/低优先级的任务争抢资源