故事的开端

第一章：开张日 — CPU 是面包店，进程是顾客

你是一家面包店的新任经理（调度器），店里只有一位面包师傅（单核 CPU）。每天早晨，顾客（进程）们会带着不同的需求来到店里：

  • A 女士（交互式进程）：赶时间买早餐，希望立刻被服务（低延迟）。
  • B 先生（批处理进程）：要订 100 个面包，不介意等待（高吞吐量）。
  • C 医生（实时进程）：急救中心订单，必须 10 分钟内完成（严格截止时间 deadline）。

问题：如何安排顺序，让所有人满意？

第二章：初试牛刀 — 先来先服务（FCFS）

你决定按排队顺序服务（First Come First Served，FCFS 算法）：

  1. A 女士第一个到达，买一个牛角包（短任务），耗时 2 分钟。
  2. B 先生第二个到达，处理 100 个面包订单（长任务），耗时 30 分钟。
  3. C 医生最后到达，但订单超时，急救车没等到面包（灾难性后果）。

教训：FCFS 简单，但无法处理紧急任务！

第三章：紧急事件 — 优先级调度

你引入“优先级标签”（优先级调度）：

  • 急救订单：红色标签（最高优先级），直接插队到最前面。
  • 普通顾客：绿色标签（默认优先级），按顺序排队。

结果：

  • C 医生的订单被优先处理，准时完成。
  • A 女士等待了 10 分钟，抱怨体验差（饥饿问题）。

新问题：高优先级任务霸占资源，其他任务被饿死。

第四章：时间切片 — 轮转调度（RR）

你买了一个计时器（时间片），规定每个顾客最多占用师傅 5 分钟：

  1. B 先生开始做面包，5 分钟后被暂停（时间片用完），重新排队。
  2. A 女士在等待 5 分钟后，终于买到早餐（响应时间改善）。
  3. C 医生仍可插队，但每次最多用 5 分钟（兼顾实时性）。

效果：

  • 短任务快速完成，长任务逐步推进。
  • 但频繁切换导致师傅效率下降（上下文切换开销）。

第五章：智慧升级 — 多级反馈队列（MLFQ）

你设计多级队列（Multilevel Feedback Queue Scheduling Algorithm，MLFQ 策略）：

  • 队列 1（高优先级）：新顾客 + 频繁放弃排队的顾客（I/O 密集型），时间片 = 2分钟。
  • 队列 2（中优先级）：普通顾客，时间片 = 5分钟。
  • 队列 3（低优先级）：长时间占用的顾客（CPU 密集型），时间片 = 10分钟。

规则：

  • 新顾客进队列 1，若用完时间片未完成，降到队列 2。
  • 如果顾客主动让出位置（如等面包出炉），留在原队列。
  • 每隔 1 小时，所有顾客升回队列 1（防饥饿）。

成果：

  • A 女士在队列 1 快速买到面包。
  • B 先生逐渐降到队列 3，但最终完成订单。
  • C 医生仍可抢占队列 1，保证急救订单。

第六章：分店扩张 — 多核 CPU 与负载均衡

面包店生意火爆，你开了两家分店（双核 CPU），但新问题出现：

  • 分店 1：排长队，师傅累瘫。
  • 分店 2：空闲，无事可做。

解决方案：

  1. 顾客亲和性：老顾客默认去上次服务的分店（缓存局部性优化）。
  2. 动态迁移：每隔 10 分钟检查队列长度，转移顾客到空闲分店（负载均衡）。
  3. 特殊通道：急救订单可跨店抢占（全局实时任务队列）。

第七章：午夜危机 — 中断与唤醒

深夜打烊时，突发状况：

  • 警报：烤箱过热（硬件中断）！师傅立刻停下手头工作，处理警报（中断处理程序）。
  • D 先生（阻塞进程）的订单需要等面粉到货，你记录需求后让他离开队列（加入等待队列）。
  • 面粉到货后，你打电话叫 D 先生回来（唤醒进程），并提升其优先级（防止饥饿）。

第八章：终极挑战 — 调度器的权衡艺术

年末总结时，你发现：

  • 追求响应时间：需频繁切换顾客，但师傅效率下降。
  • 追求吞吐量：让长任务连续处理，但短任务抱怨增多。
  • 追求公平性：所有人等待时间相近，但急救订单可能延迟。

最终策略：

  • 混合调度框架：
    • 急救订单：绝对优先级 + 独立队列。
    • 普通顾客：MLFQ 自动升降级。
    • 批量订单：后台低优先级处理。
  • 动态调整：根据客流量（系统负载）自动缩放时间片大小。

尾声：面包店的启示

通过这场冒险，你领悟到操作系统的调度本质：

  1. 没有完美算法，只有适合场景的权衡。
  2. 分层与反馈是关键——适应变化的负载。
  3. 中断与抢占是打破“顺序执行”的魔法。
  4. 多核调度如同连锁店管理，需兼顾局部与全局。

下次当你听到上下文切换或时间片轮转时，记得那个在面包店里忙碌的经理——正是这些策略，让计算机世界中的无数任务和谐共处。

基本概念

定义与目标

  • 调度（Scheduling）：操作系统在多任务环境中，根据特定策略选择就绪队列中的进程/线程分配 CPU 资源。
  • 核心目标：
    • 最大化 CPU 利用率：减少空闲时间。
    • 优化系统性能：降低周转时间、等待时间、响应时间。
    • 保证公平性：避免进程饥饿。
    • 满足实时需求：硬实时任务必须严格满足截止时间。

调度发生的时机

  • 进程主动放弃 CPU（如等待 I/O）。
  • 进程时间片用完（时间片轮转）。
  • 更高优先级进程到达（抢占式调度）。
  • 进程终止或新进程创建。

分层调度

  • 实时任务层：优先级抢占式调度（如 EDF 算法）。
  • 交互任务层：时间片轮转（RR）或动态优先级。
  • 批处理任务层：公平共享（如 CFS 的虚拟时间分配）。

长程调度（作业调度）

  • 功能：从外存（磁盘）中选择作业加载到内存，创建进程。
  • 目标：控制多道程序设计的并发度，平衡 CPU 密集型和 I/O 密集型任务。
  • 频率：最低，通常在分钟级。

短程调度（CPU 调度）

  • 功能：从内存的就绪队列中选择进程分配 CPU。
  • 目标：高效分配 CPU，快速响应交互式任务。
  • 频率：最高（毫秒级），直接影响用户体验。

中程调度（内存调度）

  • 功能：挂起（Suspend）或激活（Resume）进程，缓解内存压力。
  • 典型场景：内存不足时，将部分进程交换到外存（交换区）。

调度算法

非抢占式调度

  • 特点：进程主动释放 CPU 前不会被中断。
  • 典型算法：
    • 先来先服务（FCFS）：
      • 按到达顺序执行，简单但可能导致“护航效应”（长任务阻塞短任务）。
      • 适用场景：批处理系统。
    • 短作业优先（SJF）：
      • 选择预计运行时间最短的进程，最小化平均等待时间。
      • 缺点：需预知运行时间，长任务可能饥饿。

抢占式调度

  • 特点：允许中断正在运行的进程，重新分配 CPU。
  • 典型算法：
    • 最短剩余时间优先（SRTF）：
      • SJF 的抢占式版本，优先执行剩余时间更短的进程。
    • 时间片轮转（RR，Round Robin）：
      • 每个进程分配固定时间片（如 10-100ms），超时后重新排队。
      • 关键参数：时间片大小（过大→退化为 FCFS；过小→上下文切换开销高）。
    • 多级反馈队列（MLFQ）：
      • 多个队列按优先级排列，进程在不同队列间迁移。
      • 规则：
        1. 高优先级队列优先执行。
        2. 进程用完时间片后降级到低优先级队列。
        3. 长时间未完成的进程可能升级到高优先级队列（防饥饿）。
      • 优点：平衡响应时间和吞吐量，广泛用于通用系统（如 Windows、Linux）。

优先级调度

  • 静态优先级：进程创建时分配，不可变（适用于实时系统）。
  • 动态优先级：根据进程行为调整（如交互式任务优先级提升）。
  • 问题：优先级反转（低优先级进程持有高优先级进程所需资源），通过 优先级继承 解决。

实时调度算法

  • 硬实时系统：必须严格满足截止时间（如火箭控制）。
  • 软实时系统：允许偶尔错过截止时间（如视频播放）。
  • 典型算法：
    • 最早截止时间优先（EDF）：
      • 动态选择截止时间最近的进程。
    • 速率单调调度（RMS）：
      • 静态优先级，周期越短优先级越高。
      • 可调度条件：CPU 利用率 ≤ $ n(2^{1/n} - 1) $（n 为任务数）。

进程的调度

进程调度在实际操作系统中通常不是单一算法独立运行，而是多种策略组合或分层应用。

操作系统会根据任务类型、硬件环境和设计目标，动态或静态地融合多种调度策略，形成复合型调度框架。常见的组合模式包括：

多级队列调度

多级队列调度（Multilevel Queue）

  • 设计思想：将进程按属性（如优先级、类型）划分到不同队列，每个队列使用不同算法。
  • 示例：
    • 实时进程队列：使用优先级调度（如EDF算法）。
    • 交互式进程队列：使用时间片轮转（RR）。
    • 批处理进程队列：使用 FCFS 或 SJF。
  • 规则：
    • 高优先级队列的进程优先运行。
    • 同一队列内按特定算法调度。

多级反馈队列

多级反馈队列（MLFQ, Multilevel Feedback Queue）

  • 动态调整：进程在不同优先级队列间升降级。
  • 混合策略：
    • 高优先级队列：短时间片（如RR），快速响应交互任务。
    • 低优先级队列：长时间片（如FCFS），提高 CPU 密集型任务效率。
  • 优势：自动适应进程行为（如CPU密集型和I/O密集型）。

调度类（Scheduling Classes）

  • 模块化设计：不同调度算法作为独立模块，由系统按需调用。
  • 示例（Linux CFS调度器）：
    • 实时调度类（SCHED_FIFO/SCHED_RR）：优先级固定，抢占式。
    • 公平调度类（SCHED_NORMAL）：基于虚拟运行时间（vruntime）分配 CPU。
    • 空闲调度类（SCHED_IDLE）：仅在系统空闲时运行。
  • 工作流程：
    1. 检查实时队列，若有任务则运行。
    2. 若无实时任务，运行公平调度类的进程。

现代操作系统中的实际实现

Linux 的完全公平调度器（CFS）

  • 核心算法：基于红黑树追踪进程的虚拟运行时间（vruntime），选择最小vruntime的进程运行。
  • 组合策略：
    • 时间片动态计算：根据进程数量和优先级调整时间片长度。
    • 实时任务支持：通过调度类分层，实时进程（如 SCHED_FIFO）始终优先于普通进程。
    • 多核负载均衡：结合 NUMA 感知策略，跨 CPU 核心迁移任务。

Windows 的混合调度

  • 优先级队列分层：
    • 实时优先级（16-31）：固定时间片，不可被普通进程抢占。
    • 动态优先级（1-15）：根据行为动态调整（如前台进程自动升优先级）。
    • 零页线程（0）：仅用于内存管理。
  • 时间片分配：
    • 高优先级进程获得更长或固定时间片。
    • 低优先级进程可能被频繁抢占。

实时操作系统（RTOS）的混合模型

  • 硬实时任务：使用EDF（最早截止时间优先）或RM（速率单调调度）。
  • 软实时任务：与分时任务共用RR或优先级队列。
  • 背景任务：空闲时调度，可被实时任务随时抢占。

多算法组合

1. 应对多样化任务需求

  • 实时任务：需要严格截止时间保障（单一算法无法兼顾公平性）。
  • 交互式任务：要求低响应时间（需时间片轮转）。
  • 批处理任务：追求高吞吐量（适合FCFS或SJF）。

2. 平衡性能指标矛盾

  • 吞吐量 vs 响应时间：长时间片提升吞吐量，但增加响应延迟。
  • 公平性 vs 优先级：高优先级任务需快速响应，但需避免低优先级饥饿。

3. 动态适应系统负载

  • 突发交互任务：临时提升其优先级（如Windows的前台进程加速）。
  • CPU密集型转I/O密集型：在多级反馈队列中自动降级。

调度算法协同工作的示例

场景：Linux中的 Web 服务器+后台数据分析

  1. 实时进程（如网络中断处理）：
    • 使用 SCHED_FIFO 调度类，立即抢占CPU。
  2. 交互式进程（如SSH 会话）：
    • 在 CFS 公平调度中分配较短时间片，保证快速响应。
  3. 批处理进程（如日志分析）：
    • 在 CFS 中累积较高vruntime，获得较大时间片。
  4. 内核线程（如内存回收）：
    • 使用 SCHED_IDLE，仅在 CPU 空闲时运行。

调度性能评估指标

指标定义公式优化目标应用场景
周转时间 (Turnaround Time)作业从提交到完成的总时间周转时间 = 完成时间 - 到达(调度系统)时间最小化平均周转时间批处理系统，衡量作业整体处理效率
等待时间 (Waiting Time)进程在就绪队列中等待 CPU 的总时间等待时间 = 周转时间 - 执行时间（突发时间）最小化平均等待时间
响应时间（Response Time）从作业提交到首次获得响应（如首次 CPU 分配）的时间响应时间 = 首次运行时间 - 到达(就绪队列)时间优化交互式任务体验交互式系统（如分时操作系统），影响用户体验
吞吐量单位时间内完成的任务数最大化吞吐量
公平性各进程获得 CPU 时间的均衡程度避免饥饿，保证公平

多处理器与多核调度

挑战

  • 负载均衡：避免部分 CPU 空闲而其他过载。
  • 缓存亲和性：进程尽量在同一个 CPU 上执行，减少缓存失效。
  • 同步开销：多核间共享数据需同步（如自旋锁、信号量）。

调度策略

  • 对称多处理（SMP）：所有 CPU 共享就绪队列，动态分配任务。
  • 非对称多处理（AMP）：指定 CPU 处理特定任务（如主核处理中断）。
  • NUMA 感知调度：优先在本地内存节点分配任务，减少远程访问延迟。

实际系统中的调度器

Linux CFS（完全公平调度器）

  • 核心机制：
    • 使用红黑树记录进程的 虚拟运行时间（vruntime），选择 vruntime 最小的进程。
    • 通过 时间补偿 保证公平性（低优先级进程逐渐积累 vruntime）。
  • 特点：支持抢占、动态优先级调整，适用于服务器和桌面环境。

Windows 调度器

  • 多级反馈队列：32 个优先级队列，动态调整优先级。
  • 交互式优化：前台任务优先级提升，减少响应时间。

实时操作系统（如 VxWorks）

  • 严格优先级调度：硬实时任务优先级最高，允许抢占内核。

高级话题与扩展

上下文切换开销

  • 过程：保存当前进程状态（寄存器、页表等）→ 加载下一进程状态。
  • 优化：减少切换频率（如增大时间片）、硬件加速（TLB 缓存）。

能耗感知调度

  • 动态电压频率调整（DVFS）：降低 CPU 频率以节省能耗。
  • 任务合并：将短任务集中到少数核心执行，其他核心休眠。

虚拟化与容器调度

  • 虚拟机调度：宿主机需公平分配物理 CPU 给多个虚拟机。
  • Kubernetes 调度：基于资源需求、亲和性策略分配容器到节点。

总结

CPU 调度是操作系统的核心功能之一，需在 效率、公平性、实时性 之间权衡。

  • 批处理系统：优先考虑吞吐量（如 SJF）。
  • 交互式系统：优化响应时间（如 RR、MLFQ）。
  • 实时系统：确保截止时间（如 EDF、RMS）。

参考资料：

> https://www.bilibili.com/video/BV1juzZYhEG2/?spm_id_from=333.337.search-card.all.click&vd_source=af39da37b48042b538f2e6f4b7b2e7c8