CPU调度
CPU调度基础
进程调度
- 进程切换和调度
- CPU是共享资源，进程按照一定的策略使用CPU资源
- 当发生进程切换时，原先的进程不再使用CPU，切换到新的进程使用CPU
- 进程切换场景
- 进程主动放弃CPU使用权
- 进程等待IO、等待资源（例如锁）
- 内核不让进程使用CPU（例如有更高优先级进程要运行）
- 进程调度需求
- 决定使用CPU的进程
- 非抢占式调度和抢占式调度
非抢占式调度
- 进程主动放弃CPU使用权（
yield) - 进程等待I/O，等待资源或特定事件（
block） - 内核调度器直接进行调度（
do_scheduler）
抢占式调度
为什么要抢占
- 让进程更加公平的使用CPU资源，避免饥饿
- 交替使用I/O和计算资源，提升资源的利用率
- 有紧急任务（高优先级进程）要先执行
基于中断进行抢占式调度
时钟中断或IO中断发生的时候，进行进程切换
- 硬件中断
- 由外部事件（外部设备）触发，例如时钟中断，硬盘读写请求完成等
- 硬件中断产生与当前正在执行的任务无关
- 软件中断（可编程中断）
按可否屏蔽划分中断
- 可屏蔽中断
- 可以关闭/开启中断
- 不可屏蔽中断
- 无法恢复的硬件错误等
中断处理的基本流程
- CPU检查中断条件是否满足
- 有中断请求
- CPU允许中断
- 如果CPU允许中断，则关中断，保证在处理中断的时候不再响应其他中断
- 保存被中断的线程
- 判断中断的类型，根据不同的中断类型调用对应的中断处理程序
- 执行中断处理程序
- 恢复现场
- 开中断
I/O中断处理
- 保存当前进程/线程的上下文
- 进行I/O，例如将数据从外设拷贝到内核内存中
- 调用调度器
时钟中断处理
- 保存当前进程/线程的上下文
- 更新系统时间，递减进程时间片
- 调用调度器
调度器
调度器的工作
- 保存当前进程/线程的上下文
- 选择下一个待运行的进程/线程
- 加载相应进程/线程的上下文，并跳转执行
什么时候会触发调度
- 进程/线程创建
- 进程/线程退出
- I/O阻塞或同步阻塞
- I/O中断
- 时钟中断
CPU调度算法
调度准则
假设
- 一个用户运行一个程序，一个程序创建一个线程
- 程序之间是独立的
常用指标
- 吞吐率：每秒处理请求数
- 响应时间（等待时间）：从提交一个请求到产生响应所用的时间（交互式系统）
- 周转时间：从作业提交到作业完成的时间间隔（批处理系统）
- 公平性：每个程序是否都有执行机会，防止挨饿
批处理和实时交互系统设计目标
- 保证公平性
- 最大化CPU资源利用率
- 最大化吞吐率
- 最小化周转时间
- 缩短响应时间
- 均衡性：满足用户需求且提升计算机系统各部件的利用率
不同类型计算机系统的需求不一样
- 服务器：看重吞吐率、响应时间和公平性
- 个人计算机：看重响应时间
- 工业控制计算机：看重实时性
先到先服务（FCFS）算法
适用于非抢占式调度，适用于批处理系统
核心理念
- 一个进程一直运行到结束
- 或一直运行到阻塞
- 或一直运行到主动放弃CPU
优点：实现简单
缺点
- 平均周转时间波动较大
- 短进程可能被排到长进程的后面
- 可能导致I/O资源利用效率低
- CPU密集型应用长期占用CPU，导致I/O密集型应用没有机会使用I/O设备
- 进而导致I/O设备空闲，I/O资源利用率低
最短时间算法
最短时间优先（STCF）算法
适用于非抢占式调度
所有作业同时到达，根据所需时间从小到大依次执行。
最短剩余时间优先（SRTCF）算法
适用于抢占式调度
选择就绪队列中剩余时间最短进程占用CPU并进入运行状态
优点：平均响应时间短
缺点
- 可能会造成饥饿
- 由于连续的短进程运行导致长进程始终无法获得CPU资源
时间片轮转（RR）算法
适用于抢占式调度，多用于交互式系统
在时间片结束的时候，调度器按FCFS算法切换到下一个就绪的进程
时间片长度的选择
- 大时间片
- 等待时间过长
- 极端情况下退化为
FSFS
- 小时间片
- 响应时间块
- 产生大量上下文切换，影响系统吞吐
- 经验规则
- 选择一个合适的时间片，使上下文切换开销处于1%以内
虚拟轮转（VRR）算法
- 引入辅助队列（
FIFO算法） - I/O密集型进程进入辅助队列（而不是就绪队列）以备调度
- 辅助队列比就绪队列有着更高的优先级
多级队列（MLQ）与优先级调度
将就绪队列分为多个独立的子队列，每个队列可有自己的调度算法
例如：将前台任务（交互式）采用RR算法，后台任务（批处理）采用FCFS算法
队列之间
- 最高优先级优先
- 固定优先级
- 先调度高优先级，在调度低优先级
- 可能导致饥饿
- 潜在问题：优先级反转
- 高优先级进程所需资源被低优先级进程占有，需要等待低优先级进程的执行
- 中优先级进程优先执行，呈现为优先级高于高优先级进程
- 解决办法：优先级继承
- 高优先级进程由于等待资源被阻塞时，自动提升低优先级进程的优先级
多级反馈队列（MLFQ）算法
进程可在不同队列间移动的多级队列算法，实现优先级动态调整
特征：
- 每一级队列分配一个时间片，时间片的大小随着优先级别的增加而减小
- 进程在当前的时间片没有完成，则降到下一个优先级
- CPU密集型进程的优先级下降很快，而I/O密集型进程则停留在高优先级
- 在一定时间周期后，将所有进程的优先级都提升到最高的等级
公平共享调度（FSS）
FSS基于份额控制用户对系统资源的访问
份额管理
- 按一定的比例在不同用户间分配份额
- 需要为突发任务预留份额
- 可以为用户设置份额上限
优先级和份额的区别
- 优先级表明任务执行的先后，可以优化周转时间、响应时间，但无法确保任务能获得应得的资源比例
- 份额对应任务使用的资源比例
彩票调度
彩票方法
- 给每个作业一定数量的彩票（份额）
- 随机抽取一张中奖彩票，中奖的作业将获得CPU
- 有较多彩票的作业能获得的调度机会更多，随着调度次数增加，每个作业的彩票数量占比趋近于调度次数占比
- 为了近似SRTCF，给短作业更多的彩票
- 为了避免饥饿，给每个作业至少一个彩票
调度算法总结
| 算法 | 适用系统 | 平均响应时间 | 公平性 | 潜在问题 |
|---|---|---|---|---|
| FCFS | 批处理 | 长 | 可能造成饥饿 | |
| STCF | 批处理 | 短 | 长进程可能饥饿 | 需要预测作业执行时间 |
| SRTCF | 批处理 | 短 | 长进程可能饥饿 | 需要预测作业执行时间 |
| RR | 交互式 | 短，I/O进程响应时间较长 | 公平对待 | 时间片小会导致吞吐率低 |
| VRR | 交互式 | 短 | 对I/O密集型进程友好 | |
| MLQ | 交互式和批处理 | 低优先级队列任务 响应时间长 | 可能造成饥饿 | 优先级反转 |
| MLFQ | 交互式和批处理 | 短 | 兼顾长短作业 | |
| 彩票算法 | 交互式和批处理 | 短 | 兼顾长短作业，考虑资源比例 |
实时调度
两种类型的实时
- 硬实时：必须满足，否则会产生错误
- 软实时：大多时候需满足，没有强制性
准入控制
只有当系统能够保证所有进程的实时性的前提下，新的实时进程才能被准入
如果满足以下条件，则作业就是可调度的 \[ \sum\frac{C_i}{T_i}\leq1 \] 其中\(C_i\)为计算时间，\(T_i\)为周期
速率单调调度
假设
- 每个周期性进程必须在其周期内完成
- 进程之间没有依赖关系
- 每个进程在每个周期内需要的CPU时间相同
- 非周期性进程没有截止时间
- 进程抢占瞬时发生（没有开销）
基本思想
- 给每个进程分配一个固定的优先级（出现频率）
- 例如每50ms运行一次，则优先级是20
- 运行最高优先级的进程
- 已经被证明是最优的静态优先级实时调度策略
最早截止时间优先调度（EDF）
假设
- 当进程运行时，它会提供其需要完成运行的截止时间
- 不一定是一个周期性的进程
基本思想
- 根据截止时间对就绪的进程进行排序
- 运行列表中的第一个进程（最早截止时间优先）
- 例如P1在30s之前结束，P2在40s之前结束，则P1先运行
- 当新的进程就绪的时候，并且其截止时间快来临时，它会抢占当前进程