定义
- 按某种策略从就绪队列中选择一个进程，分配 CPU 给它运行
- 调度的核心目标：公平、高效、低延迟、高吞吐
调度层次
- 高级调度（作业调度）：从外存中选择作业调入内存，创建进程
- 中级调度（交换调度）：进程在内/外存之间换入换出，缓解内存压力
- 低级调度（进程调度）：从就绪队列选进程分配 CPU — 频率最高
调度时机
- 进程从运行态 → 阻塞态（等待 I/O 或事件）
- 进程从运行态 → 就绪态（时间片用完或被抢占）
- 进程从阻塞态 → 就绪态（事件发生，可能抢占）
- 进程终止
调度方式
- 非抢占式：进程运行完毕或主动阻塞才切换，简单但响应慢
- 抢占式：时间片用完或高优先级进程就绪时可强制切换，响应快但开销大
重点 调度算法
| 算法 | 描述 | 特点 |
|---|
| 先来先服务（FCFS） | 按到达顺序排队，类似银行排队叫号 | 简单，平均等待时间长，长作业有利 |
| 短作业优先（SJF/SPF） | 选择执行时间最短的进程，非抢占/抢占两种 | 平均等待时间最短，长作业可能饥饿 |
| 优先级调度 | 分静态优先级（创建时确定）和动态优先级（随运行调整） | 通用，优先级低的可能饥饿 |
| 时间片轮转（RR） | 按时间片轮流分配 CPU，用完即切 | 分时系统，响应时间均匀，时间片大小关键 |
| 多级反馈队列 | 多个队列，优先级+时间片结合 | 通用（重点），兼顾响应与吞吐 |
先来先服务（FCFS）
- 就绪队列按到达先后排序，非抢占
- 平均等待时间长，短作业排在长作业后时非常不利
- 类比：银行柜台排队，不可插队
短作业优先（SJF/SPF）
- 非抢占：进程到达时，选择预计运行时间最短的投入运行
- 抢占（SRTF）：新进程到达时，如果其剩余时间比当前进程短，则抢占
- 平均等待时间理论上最优（最优调度策略），但长作业可能无限期饥饿
- 难点：需预知进程运行时间
优先级调度
- 静态优先级：进程创建时确定，运行期间不变
- 动态优先级：随进程运行时间调整（如老化机制），防止饥饿
时间片轮转（RR）
- 每个进程分配一个固定时间片（Time Quantum），用完则切换
- 时间片过大 → 退化为 FCFS；时间片过小 → 上下文切换开销过大
- 典型值：10–100ms
多级反馈队列调度
- 设置多个就绪队列，优先级从高到低，时间片从短到长
- 新进程进入最高优先级队列
- 用完时间片未完成则降入下一级队列
- 优先级高的队列可抢占优先级低的队列中的进程
- 兼顾短作业（快速响应）和长作业（不饥饿）
Linux CFS（Completely Fair Scheduler）
- 使用红黑树（Red-Black Tree）组织就绪进程
- vruntime：进程的虚拟运行时间，CFS 选择 vruntime 最小的进程运行
- vruntime 受进程优先级（nice 值）影响：优先级高 → vruntime 增长慢
- 保证每个进程获得公平的 CPU 份额
Linux 实时调度
- SCHED_FIFO：先进先出实时调度，直到进程主动阻塞或结束
- SCHED_RR：时间片轮转实时调度，同优先级间轮转
- SCHED_DEADLINE：基于最早截止期限优先（EDF），保证实时任务按时完成