调度时机、调度原则与经典调度算法
调度这部分，本质上在回答：
CPU 先给谁用、给多久、什么时候换人。
单核 CPU 在同一时刻只能真正执行一个任务，因此操作系统必须从就绪任务中做选择，这个选择过程就是调度。
一、什么是调度
调度程序（scheduler）的职责，就是在多个可运行进程 / 线程之间做选择：
- 先执行哪个
- 执行多久
- 什么时候换下
- 换谁上来
如果没有调度，系统就无法在多个任务之间高效分配 CPU 资源。
二、调度时机
调度最常见的触发时机有这些：
1. 就绪态 → 运行态
系统从就绪队列中挑一个进程 / 线程上 CPU。
2. 运行态 → 阻塞态
当前任务因为 IO、锁、等待事件等原因阻塞，CPU 需要交给别人。
3. 运行态 → 结束态
当前任务运行结束退出，调度器需要再选一个新的任务。
4. 时间片用完
在抢占式调度中，当前任务运行一段时间后，CPU 会被时钟中断收回，再重新决定下一个任务。
三、非抢占式和抢占式调度
1. 非抢占式调度
一旦选中了某个任务，就让它一直运行，直到：
- 自己阻塞
- 自己退出
系统不会强行把它抢下来。
2. 抢占式调度
任务只能运行一段时间，如果时间到了还没结束，系统会把它挂起，再去调度别的任务。
抢占式调度通常依赖：
- 时钟中断
- 时间片机制
四、调度想优化什么
调度算法通常围绕这几个目标做权衡：
1. CPU 利用率
让 CPU 尽量别闲着。
2. 吞吐量
单位时间内完成尽可能多的任务。
3. 周转时间
任务从提交到完成的总时间。
4. 等待时间
任务在就绪队列中排队等待 CPU 的时间。
5. 响应时间
用户发出请求后，系统第一次给出响应所花的时间。
这些目标往往不能同时做到最优，所以调度算法本质上就是一种平衡。
五、先来先服务（FCFS）
FCFS 的规则很简单：
谁先进入就绪队列，谁先运行。
优点
- 实现简单
- 开销小
缺点
如果前面有一个长任务，它会一直占着 CPU，后面的短任务只能一直排队等待。这会导致短任务响应很差。
六、最短作业优先（SJF）
SJF 的规则是：
优先运行预计执行时间最短的任务。
优点
- 平均等待时间通常较低
- 对短任务友好
缺点
- 长任务可能长期得不到运行机会
- 现实里很难准确知道一个任务未来还要跑多久
七、高响应比优先（HRRN）
HRRN 想解决 FCFS 和 SJF 之间的平衡问题。
它的核心思想是：
- 既看任务本身长不长
- 也看它已经等了多久
这样一来：
- 短任务更容易被选中
- 等太久的长任务也能逐渐提高优先级
它在理论上更平衡，但同样存在“服务时间难以准确预测”的现实问题。
八、时间片轮转（RR）
时间片轮转的规则是：
每个任务轮流运行一小段固定时间片。
如果时间片到了，任务还没结束，就先把它放回就绪队列尾部，换下一个任务。
优点
- 公平
- 响应快
- 很适合交互式系统
缺点
关键在时间片长度：
- 太短：上下文切换过于频繁，开销大
- 太长：又会退化得像 FCFS
九、最高优先级优先（HPF）
HPF 的规则是：
优先级高的任务先运行。
优先级可以是：
- 静态优先级
- 动态优先级
优点
- 能体现任务重要性
- 适合系统任务和普通任务区分处理
缺点
如果高优先级任务很多，低优先级任务可能长期得不到运行，也就是发生饥饿。
十、多级反馈队列（MLFQ）
多级反馈队列是最综合、最经典的一类调度算法。
它的核心思想是：
- 不只一个就绪队列，而是多个优先级不同的队列
- 高优先级队列时间片更短
- 新任务先进入高优先级队列
- 如果总是把时间片吃满，就逐渐下沉到更低优先级队列
- 如果经常主动离开 CPU（比如等待 IO），通常会保留较高优先级
- 高优先级任务可以抢占低优先级任务
为什么它灵活
因为它不提前假设一个任务是长还是短，而是：
通过观察任务的实际行为，动态判断它更像短任务、交互任务，还是长任务、CPU 密集型任务。
所以它能兼顾：
- 响应时间
- 吞吐量
- 公平性
十一、怎么记这些算法
可以用最短的话记：
- FCFS：谁先来谁先跑
- SJF：谁短谁先跑
- HRRN：谁短、谁等得久，谁更容易先跑
- RR：大家轮流跑一点
- HPF：重要的先跑
- MLFQ：按行为动态分层，交互优先，长任务下沉
十二、总结
调度就是操作系统决定 CPU 先给谁、给多久以及何时换人的过程。它通常在任务状态变化或时间片结束时发生，并围绕 CPU 利用率、吞吐量、周转时间、等待时间和响应时间做权衡。经典算法包括 FCFS、SJF、HRRN、RR、HPF 和 MLFQ。其中，多级反馈队列是较为综合和灵活的一类调度算法，它通过多个优先级队列和动态反馈机制，兼顾了交互任务的快速响应和长任务的运行机会。