处理机调度
1. 处理机调度概念
进程切换：CPU资源的当前占用者切换
（保护当前进程在PCB中的执行上下文，恢复下一个进程的执行上下文）
处理机调度：
- 从就绪队列中挑选下一个占用CPU运行的进程
- 从多个可用CPU中挑选就绪进程可用的CPU
调度程序：挑选就绪进程的内核函数
- 调度策略
- 调度时机
调度时机：
从运行到等待
进程被终结了
2. 调度准则
2.1 调度策略
确定如何从就绪队列中选择在一个执行进程
处理机资源的使用模式：
进程在CPU计算和I/O操作间交替
2.2 调度准则
比较调度算法的准则：
- CPU使用率
- 吞吐量（单位时间完成的进程数量）
- 周转时间（进程从初始化到结束（包括等待）的总时间）
- 等待时间（在就绪队列的时间）
- 响应时间
希望得到
高吞吐量和低响应延迟
这两个因素是独立的
处理机调度目标:
- 减少响应时间
- 减少平均响应时间的波动
- 增加吞吐量
- 减少等待时间
公平性目标：
保证每个进程占用相同的CPU时间（如果每个用户有多个进程，不公平）
保证每个进程的等待时间相同
3. 调度算法
3.1 先来先服务 （FCFS：First Come First Start）
依据进程进入就绪状态的先后顺序排列
例：
周转时间 与 队列 关系很大
优点：
- 简单
缺点：
- 平均等待时间波动较大
- I/O资源和CPU资源的利用率较低
3.2 短进程优先 (SPN：Shortest Process Next)
选择就绪队列中，执行时间最短的进程，占用CPU进入运行状态
就绪队列按预期的执行时间来排序。
特征：
具有最优平均周转时间
证明过程
缺点：
- 可能导致饥饿（连续的短进程流会导致长进程无法获得CPU资源）
- 需要预知未来
- 如何预估下一个计算时间？
- 简单方法：询问用户
- 用户欺骗就杀死相应进程
- 用户不知道怎么办？ -> 过去预测未来
执行时间预估：
用历史的执行时间来预测未来的执行时间
话说这个预测公式很像 计网 的那个啥子公式….
3.2.1 变种：短剩余时间优先算法（SRT）
SPN算法的可抢占改进
3.3 最高响应比优先调度算法 （HRRN：Highest Response Ratio Next）
选择就绪队列中响应比R值最高的进程
w: 等待时间
s: 执行时间
3.4 时间片轮转算法 （RR：Round Robin）
时间片：分配处理机资源的基本时间单位
算法思路：
时间片结束时，按照FSFC算法切换到下一个进程。
每隔（n-1)时间片执行下一个进程p
例题：
求等待时间
RP算法开销：
- 额外的上下文开销
- 时间片太长：
- 等待时间太长
- 极限情况退化成FCFS 先来先服务
- 时间片太短：
- 反应迅速，产生大量上下文切换
- 上下文切换太多影响系统吞吐量
- 时间片长度选择合适
经验原则：维持上下文开销处于1%以内
比较FCFS和RP
FCFS抖动很大
RP较稳定
3.5 多级反馈队列算法 （MFQ：Multilevel Feedback Queues)
就绪队列被划分多个独立的子队列
前台-RP
后台-FCFS
队列间的调度：先处理前台，然后处理后台
时间片轮转：
例：80%时间前台，20%时间后台
算法思路：
- 时间片大小随优先级增加而增加
- 进程在当前时间片没有完成，则降到下一个优先级
MLFQ特征：
- CPU密集型进程的优先级下降很快
- I/O密集型进程停留在高优先级
3.6 公平共享调度算法 (Fair Share Scheduling)
FSS控制用户对系统资源的访问
- 一些用户组比其他用户组更重要
- 保护不重要的组无法垄断资源
4. 实时调度
对时间有要求的调度算法
性能指标：
- 时间约束的及时性
- 速度和平均性能相对不重要
实时任务(相对，绝对截止时间；执行时间)
周期实时任务
硬实时和软实时
可调度性
静态：速率单调调度算法
周期越短优先级越高
动态：最早截止时间优先算法
截止时间越早优先级越高
5. 多处理机调度
特征：
- 多个处理机组成一个多个处理机系统
- 处理机间可负载共享
静态和动态进程分配
6. 优先级繁殖
操作系统中出现高优先级进程长时间等待低优先级进程占用资源的现象
T3的长时间运行导致高优先级的T1进行长时间等待
基于优先级的可抢占调度算法存在优先级反置
两种处理办法：
6.1 优先级继承
占用资源的低优先级进程 继承 申请资源的高优先级的优先级
6.2 优先级天花板协议
占用资源进程的优先级和所有可能申请资源的进程的最高优先级相同
坏处：所有进程的优先级都可能提到最高，这样就没意义了。
