调度算法与上下文切换 — 专题笔记
CPU 只有一个，等着跑的进程有几十个——调度本质上在回答：下一秒把 CPU 给谁？
要解决什么问题
| 指标 | 含义 | 谁最看重 |
|---|---|---|
| CPU 利用率 | CPU 别闲着 | 所有系统 |
| 吞吐量 | 单位时间完成多少作业 | 批处理 |
| 周转时间 | 作业从提交到完成的总时间 | 批处理 |
| 等待时间 | 在就绪队列里等 CPU 的时间 | 交互式系统 |
| 响应时间 | 用户请求到第一次响应的时间 | 交互式系统 |
周转时间公式：
多道程序并发后，就绪队列里同时排着多个进程。调度不是随便挑一个，而是在这些互相矛盾的目标之间找平衡。
调度的三个层次
| 层次 | 本质 | 做什么 |
|---|---|---|
| 高级调度 | 资源准入 | 从后备队列选作业调入内存 |
| 中级调度 | 内存调节 | 内存紧张时换出进程到磁盘，宽裕时换回 |
| 低级调度 | 资源复用 | 从就绪队列选进程上 CPU，决定怎么轮流用 |
调度算法
一、高级调度：作业调度算法 — 决定”谁有资格进内存”
| 算法 | 缩写 | 规则 | 优点 | 缺点 |
|---|---|---|---|---|
| 先来先服务 | FCFS | 谁先到谁先上 | 简单公平 | 短作业排长作业后面一直等 |
| 短作业优先 | SJF | 优先选估计运行时间最短的 | 平均周转时间最优 | 无法预知运行时间；长作业可能饥饿 |
| 高响应比优先 | HRRN | 选响应比最高的 | 折中——短作业天然高，长作业等久了也会升高 | 计算响应比有额外开销 |
高响应比公式：
二、中级调度：内存调度 — 决定”谁在内存，谁去硬盘待命”
内存和外存之间的换入换出（挂起/解挂）。内存紧张时挂起部分进程换出到磁盘，内存宽裕时换回。目的是节省物理内存，让更多作业能并发执行。
FreeRTOS 无 MMU 的场景不涉及这一层。
三、低级调度：进程/线程调度 — 决定”内存里的进程怎么轮流用 CPU”
调度粒度：ULT vs KLT — 调的是进程还是线程？
| 用户级线程（ULT） | 内核级线程（KLT） | |
|---|---|---|
| 内核感知线程？ | ❌ 内核只看到进程 | ✅ 内核直接管理每个线程 |
| 调度对象 | 进程（再内部分配） | 具体线程 |
| 线程切换执行者 | 用户态线程库 | 内核 |
| 切换开销 | 低（不经过内核） | 较高（需内核介入） |
| 一线程阻塞的影响 | 整个进程通常一起被挂 | 只阻塞该线程，其他线程不受影响 |
| 时间片分配 | 给整个进程 | 可给每个线程单独分配 |
| 本质 | 进程拿到 CPU 后内部再分配 | 内核直接给某个线程发 CPU 使用权 |
1. 调度算法 — 策略层：决定选谁
| 算法 | 缩写 | 核心规则 | 关键参数 | 适用场景 |
|---|---|---|---|---|
| 优先级调度 | — | 优先级高的先拿 CPU | 静态/动态优先级；抢占/非抢占 | 通用，几乎所有 OS 都结合使用 |
| 时间片轮转 | RR | 轮流跑一个时间片，用完回队尾 | 时间片长度：太小→切换开销大，太大→退化成 FCFS | 分时系统 |
| 多级队列 | — | 多个优先级队列，先看高优先级 | 队列数量、每层队列的调度策略 | 进程类型明显不同的系统 |
| 多级反馈队列 | — | 新进程进最高级，用完时间片逐级下沉 | 级数、每级时间片倍数（通常 2×）、降级规则 | 通用——兼顾短作业响应和长作业公平 |
| 公平调度 | CFS 等 | 保证每个进程拿到相对公平的 CPU 份额 | 权重、调度周期 | 现代通用 OS（Linux CFS） |
优先级调度补充
| 维度 | 分类 |
|---|---|
| 是否可抢占 | 非抢占式 / 抢占式 |
| 优先级是否变化 | 静态优先级 / 动态优先级 |
| 经验规则 | 系统进程 > 用户进程；I/O 型 > CPU 计算型；交互型 > 非交互型 |
多级反馈队列结构
| 队列级别 | 优先级 | 时间片 | 放什么进程 |
|---|---|---|---|
| 第 1 级 | 最高 | 最短 | 新到达的、短作业、交互型 |
| 第 2 级 | 中 | 中（通常第 1 级的 2 倍） | 第 1 级未完成的 |
| 第 N 级 | 最低 | 最长 | 长作业逐步下沉至此 |
2. 调度方式
| 非抢占式 | 抢占式 | |
|---|---|---|
| 触发切换 | 进程主动阻塞 / 主动结束 | 更高优先级就绪 / 时间片用完 / 系统强行抢 |
| 实现复杂度 | 低 | 高 |
| 适用场景 | 早期批处理 | 分时系统、实时系统 |
| 响应保证 | 弱——短任务可能被长任务阻塞 | 强——高优先级立刻上 CPU |
3. 切换机制 — 机制层：决定怎么切
切换过程 5 步
| 步骤 | 动作 | 写入位置 |
|---|---|---|
| 1 | 保存当前进程现场（PC、通用寄存器、PSW、栈指针） | — |
| 2 | 写入该进程的 PCB 或内核栈 | PCB / 内核栈 |
| 3 | 按调度算法从就绪队列选一个进程 | — |
| 4 | 恢复它的现场（上次被切走时保存的） | — |
| 5 | CPU 从断点继续执行 | — |
三个角色
| 角色 | 职责 | 类比 |
|---|---|---|
| 排队器 | 把就绪进程组织成就绪队列 | 排队 |
| 调度算法 | 从队列中挑出下一个运行的进程 | 挑谁 |
| 分派器 + 上下文切换器 | 保存当前现场 + 恢复下一个进程现场 + 交出 CPU | 送上去跑 |
模式切换 vs 上下文切换
| 模式切换 | 上下文切换 | |
|---|---|---|
| 切换什么 | 用户态 ↔ 内核态 | 进程 A → 进程 B（或线程 A → 线程 B） |
| 触发原因 | 系统调用、中断、异常 | 调度器决定换人 |
| 发生在同一进程内？ | ✅ 可以 | ❌ 不可能（定义上就是换执行对象） |
| 开销 | 较小（换特权级） | 较大（现场保存 + 恢复 + TLB/Cache 冲刷） |
闲逛进程
| 属性 | 说明 |
|---|---|
| 名称 | 闲逛进程 / idle process |
| 优先级 | 最低 |
| 运行条件 | 就绪队列为空 |
| 做什么 | 不做业务，只让 CPU 不空转（执行 HLT 等低功耗指令） |
| 对应 FreeRTOS | prvIdleTask |
中断驱动的切换细节（PendSV、SVC）见 中断与任务协作；FreeRTOS 上下文切换实现见 FreeRTOS 调度与上下文切换。
多处理机调度
| 单处理机调度 | 多处理机调度 | |
|---|---|---|
| 核心问题 | 一个 CPU 先给谁 | 多个 CPU 之间怎么分摊任务 |
| 额外考虑 | — | 负载均衡、处理器亲和性、任务迁移开销 |
| 队列设计 | 单就绪队列 | 每 CPU 各自队列 或 全局共享队列 |
和 FreeRTOS 的直觉对应
| 通用 OS 概念 | FreeRTOS 对应 | 说明 |
|---|---|---|
| 高级调度 | 没有 | MCU 无”后备队列→内存”这一层 |
| 中级调度 | 没有 | MCU 无内存对换 |
| 低级调度 | 任务调度器 +PendSV 异常 | 策略：抢占式/合作式/时间片；机制：PendSV 上下文切换 |
| 抢占 | 高优先级任务就绪立即抢占 | FreeRTOS 默认行为 |
| 闲逛进程 | prvIdleTask | 就绪列表为空时运行，可挂低功耗钩子 |
| 时间片轮转 | configUSE_TIME_SLICING | 同优先级任务间可选开启 |
FreeRTOS 没有高级和中级调度，只做低级调度——任务调度器负责策略（选谁），PendSV 负责机制（怎么切），一切以快和确定为核心。详见 FreeRTOS 调度与上下文切换。
如果你正在跟随梳理，返回 MOC ←