操作系统 （八) - CPU调度
目录
1. 背景，CPU调度
上下文切换
- 切换CPU的当前任务，从一个进程/线程转换到另一个进程/线程；
- 但是切换之前要保护现场，保存当前进程/线程在PCB/TCP中的执行上下文(也就是CPU的状态)；
- 切换任务，当然要读取下一个进程/线程的上下文。
CPU调度：
- 从就绪队列中挑选一个进程/线程作为CPU将要运行的下一个进程/线程；
- 需要调度程序(挑选进程/线程的内核函数)；
- 需要考虑的问题是 调度的时机。
在进程/线程生命周期的什么时候进行调度？
从一个状态到另一个状态的时候会发生调度。
内核运行调度程序的条件(满足其一即可)
- 一个进程从运行状态切换到等待状态
- 一个进程被终结了
CPU调度方式，是否抢占（内核态、用户态）
- 不可抢占
- 调度程序必须等待事件结束(效率低，不采用)；
- 可以抢占
- 调度程序在中断被响应后执行；
- 当前的进程从运行切换到就绪，或者一个进程从等待切换到就绪；
- 当前运行的进程可以被换出。
注意，以上一般指用户态；内核态也可能涉及到是否抢占。
2 调度原则
2.1 调度策略
2.2 程序执行模型
执行模型：程序在CPU突发和I/O中交替
- 每个调度决定都是关于在下一个CPU突发时将哪个工作交给CPU；
- 在时间分片机制下，线程可能在结束当前CPU突发前被迫放弃CPU；
2.3 比较调度算法的准则
- CPU使用率：CPU处于忙状态所占时间的百分比；
- 吞吐量：在单位时间内完成的进程数量；
- 周转时间：一个进程从初始化到工作结束，包括所有等待时间所花费的时间；
- 等待时间：进程在就绪队列中的总时间；
- 响应时间：从一个请求被提交到产生第一次响应所花费的时间。
2.4 吞吐量 vs 延迟
- 对快的评价指标：
- 传输文件时的高带宽；玩游戏时的低延迟(这两点相互独立)；
- 减少响应时间：
- 及时处理用户的输出并尽快将输出提供给用户；
- 减少平均响应时间的波动：
- 在交互系统中，可预测性比高差异/低平均更重要；
- 增加吞吐量：
- 减少开支(操作系统开支/上下文切换)；
- 系统资源的高效利用(CPU，I/O设备)；
- 减少等待时间：
- 减少每个进程的等待时间。
- 吞吐量是操作系统的计算带宽；
- 响应时间是操作系统的计算延迟。
2.5 公平的目标
3 调度算法
实际上这些调度算法和实际的调度算法是有很多区别的(复杂的多)，但是基本的特征是类似的。
- FCFS：先来先服务
- SPN(SJF) SRT: 短进程优先(短作业优先)短剩余时间优先
- HRRN:最高响应比优先
- Round robin,轮循，使用时间切片和抢占来轮流执行任务；
- Multilevel feedback queues,多级反馈队列，多级反馈队列，优先级队列中的轮循；
- fair share scheduling, 公平共享调度；
3.1 先来先服务
FIFO队列规定，如果进程在执行中阻塞，队列中的下一个会得到CPU。
- 优点：简单；
- 缺点：平均等待时间波动较大(没有抢占)；
- 花费时间少的任务可能排在花费时间长的任务后面；
- 可能导致I/O和CPU之间的重叠处理(CPU密集型进程会导致I/O设备闲置时，I/O密集型进程也在等待)。
3.2 短进程优先
选择下一个最短的进程(短任务优先)，即按照预测的完成时间排序将任务入列；
注意，它可以是抢占的也可以是不抢占的，对于抢占类型的，才是SRT短剩余时间优先。抢占：就是如果新来一个预测时间更小的，是否会打断当前正在执行的进程。
- 优点：平均周转时间最少；(可以发现SRT的进程平均周转时间会短一些)
- 缺点：
- 可能导致饥饿(连续的短任务流会使长任务饥饿；
- 短任务可用时的任何长任务的CPU时间都会增加平均等待时间)；
需要预测完成时间
- 但是怎么预估下一个CPU突发的持续时间是一个问题
- 其中一个简单的解决办法：询问用户；
- 如果用户欺骗就杀死进程；
- 但是用户不知道怎么办？
根据历史时间分配预估未来时间的分配
3.3 最高响应比优先
- 在SPN调度的基础上改进(考虑了等待时间，改善饥饿现象)；
- 不可抢占；
- 关注进程等待了多长时间；
- 防止无限期推迟；
R = (w + s) / s (选择R值最高的进程) ，
其中 w:waiting time等待时间 s:service time执行时间
3.4 轮循
进程轮流执行
在一个叫做 时间量子(或时间切片)对离散单元中分配处理器；
如果时间片结束了，那么就接换到下一个准备好的进程(processes execute every (n-1)q time units)；
- 优点：公平；
- 缺点：
- 额外的上下文切换花销；
- 如果时间量子太大，则等待时间过长，极限情况下退化成FCFS；
- 如果时间量子太小，虽反应迅速，但是开销大；吞吐量由于大量的上下文切换开销而受到影响；
- 目标：
- 选择一个合适的时间量子；
- 经验规则：维持上下文切换开销处于1%以内。
3.5 多级反馈队列
- 对于I/O密集型任务，放在高优先级队列，这里的时间片比较短；
- 对于CPU密集型任务，防止低优先级队列，这里的时间片比较长。
- (我们希望交互性好，占用资源多的可以放在后面)
- 一个进程可以在不同的队列中移动。
- 例如，时间量子的大小岁优先级级别的增加而增加；如果任务在当前的时间量子中没有完成，那么就降到下一个优先级。
3.6 公平共享调度
站在用户的角度实现公平共享CPU资源。因为有的用户可能开的进程多，有的用户进程少。
它考虑了以下情况：
- 一些用户组比其他用户组更重要；
- 保证不重要的组无法垄断资源；
- 未使用的资源按照每个组所分配的资源的比例来分配；
- 没有达到资源使用目标的组获得更高的优先级。
3.7 不同调度模型的评价准则
- 确定性建模：确定一个工作量，然后计算每个算法的表现；
- 队列模型：用来处理随机工作负载的数学方法；
- 实现/模拟：建立一个允许算法运行实际数据的系统。
4 实时调度
4.1 概述
- 定义：正确性依赖于其时间和功能两方面的一种操作系统；
- 性能指标：时间约束的及时性(deadlines);速度和平均性能相对不重要；
- 主要特性：时间约束的可预测性；
- 强实时系统：需要在保证的时间内完成重要的任务，必须完成；
- 弱实时系统：要求重要的进程的优先级更高，尽量完成，并非必须；
一些术语，
- 任务(工作单元job)：例如：一次计算，一次文件读取，一次信息传递等；
- 属性：取得进展所需资源；定时参数。
4.2 可调度性
- 表示一个实时系统是否可以满足deadline要求，
- 决定实时任务执行的顺序；
- 静态优先级调度：运行之前优先级就是确定的；
- 动态优先级调度：优先级在运行中是动态变化的；
4.3 调度算法
RM(Rate Monotonic)速率单调调度
- 最佳静态优先级调度
- 通过周期安排优先级
- 周期越短，优先级越高
- 先执行周期最短的任务
EDF(Earliest Deadline First)最早期限调度
- 最佳的动态优先级调度
- Deadline越早，优先级越高
- 先执行Deadline最早的任务
5 多处理器调度（介绍）
- 多处理器的CPU调度更加复杂
- 多个相同的单处理器组成一个多处理器；
- 它的优点是负载共享；
- 还有对称多处理器(SMP)
- 每个处理器运行自己的调度程序；
- 需要在调度程序中同步；
6. 优先级反转
6.1 现象
6.2 解决方法
优先级天花板：“拥有资源”的优先级和“所有可以锁定该资源任务中优先级最高的那个任务”的优先级相同(T3拥有T1的资源，所以它的优先级提升到T1)；
除非当前进程的优先级高于系统中所有被锁定的资源的优先级的上线，否则任务尝试执行临界区的时候会被阻塞；
持有最高优先级上限信号量锁的任务，会继承被该锁所阻塞的任务的优先级。