处理器调度概念
调度的技术背景
在此前我们已经介绍了进程和线程机制， 它们可以使得CPU能够更加有效地展现并发处理的能力。
对于资源基本管理单位的进程来说，CPU资源的当前占用者切换是基本的并发思路。
但有如下两个问题：
- 如何从就绪队列中选出下一个运行（占用CPU）的进程
- 从多个CPU中选出就绪进程中当前准备使用的的CPU
这两个选择任务就交由调度算法来实现。
调度时机
调度程序除了解决上述提到的进程线程选择之外，还需进行调度时机的选择
当前系统为非抢占系统时，内核在如下两种情况下运行调度程序：
- 进程从运行状态切换到等待状态(等待某个事件)
- 进程被终结了
当前系统为抢占系统时，内核在如下情况下运行调度程序：
- 中断请求被服务例程响应完成时
- 进程从 运行状态 切换到 就绪状态
- 当前进程被抢占
- 进程时间片用完
- 某进程从 等待状态 切换到 就绪状态 (它的优先级更高，因此会发生抢占)
调度准则
评定调度算法好坏的指标
从运行效率来说：
- CPU使用率：CPU处于忙状态的时间百分比
- 吞吐量：单位时间内完成的进程数量
从用户使用来说：
- 周转时间：进程从初始化到完成（包括等待）的时间
- 等待时间：进程在就绪队列中等待的时间
- 响应时间：从提交请求到产生响应所花费的总时间
调度算法的要求：希望“更快”的服务
对于“更快”我们有两个层面的描述：
- 传输文件时，我们希望高带宽，对应调度算法的高吞吐量
- 玩游戏时，我们希望实时响应，对应调度算法的低响应延迟
这两个因素是独立的。我们的设计也分别基于这两个方向。
调度策略的低时延目标
减少响应时间：及时处理用户的输入请求，尽快将输出反馈给用户
减少平均响应时间的波动：可预测性和稳定性比高差异低平均更好
低延迟调度改善了用户的交互体验
调度策略的吞吐量目标
增加吞吐量：减少开销并实现系统资源高效利用
减少等待时间：减少每个进程的等待时间
要点：
- 操作系统需要保证吞吐量不受用户交互影响
- 吞吐量是操作系统的计算带宽
调度的公平性目标
除上述两条对于单用户的使用设计目标外，对于多用户的使用公平性。
- 保证每个进程占用相同的CPU时间
- 保证每个进程的等待时间相同（因此，一个用户使用多个进程，其等待时间也相应增加）
公平性通常会牺牲一定程度的时延。
调度算法
就绪队列优先级
先来先服务算法(FCFS，First Come, First Served)
依据进程进入就绪队列的先后顺序排列
- 进程进入等待或结束状态时，就绪队列中下一个进程占用CPU
先来先服务算法的特征：
- 优点
- 简单
- 缺点
- 平均等待时间波动较大 (短进程排在长进程后面，如下图所示)
- I/O资源和CPU资源的利用率较低 (CPU密集型的进程导致I/O闲置时，I/O密集型进程仍然需要等待)
P1，P2，P3的到达的时间都是时刻0
短进程优先算法(SPN，Shortest Process Next)
选择就绪队列中预期的执行时间最短的进程占用CPU进入运行状态（就绪队列按照预期的执行时间来排序。）
当有一个新的进程进入就绪队列，且它的预期执行时间比当前正在执行的进程所剩的执行时间还短，允许其抢占，则为 SRT: Shortest Remaining Time (短剩余时间优先)
短进程优先算法的特征:
- 可能导致饥饿
- 连续的短进程流会使长进程无法获得CPU资源
- 如何预测进程的执行时间
- 可以询问用户，用户可能不知道；也有可能给出过于乐观的估计，比如用户觉得自己的工作能很快做完（“欺骗”），但发现卡死了，这时候可以手动中止这个运行时间较长的程序。
- 用过去预测未来。利用过去的情况来预测某个进程的执行时间。 $\tau_{n+1} = \alpha t_n + (1-\alpha)\tau_n$ ， $\tau_i$为第$i$次的估计值
最高响应比优先（HRRN）
是短进程优先算法的改进，防止预估时间较长的进程长时间被抢占出现饥饿现象
选择就绪队列中响应比R值最高的进程，响应比R定义为：$R = \frac {w + s} {s}$ （其中w为等待时间，s为预估执行时间）
这个算法关注了等待时间，防止了长进程频繁被抢占和无限期推迟。
时间控制
以上是从进程排列来考虑的调度算法，我们也可以从时间资源分配入手。
时间片轮转算法(RR，Round Robin)
- 将时间片 q 作为分配处理机资源的基本时间单位
- 时间片结束时，按 FCFS(先来先服务)算法切换到下一个就绪进程
- 每个进程分到了 1 / n(进程总数) 的时间
基于FCFS给出的进程队列，操作系统给队头交替分配相应的处理器资源。如果执行完退出，没有执行完回到队尾
时间片轮转算法特征:
有额外的上下文切换开销 (正常情况下是在 进程进入等待状态或结束状态时 才切换进程)
- 当时间片太大时
- 等待时间过长
- 极限情况退化成 FCFS(先来先服务)
- 当时间片太小时
- 反应迅速，但产生大量的上下文切换
- 大量上下文切换开销影响系统的吞吐量(单位时间内 运行的总进程数)
- 时间片长度选择目标
- 通常为 10ms左右 为一个时间片
- 维持上下文开销处于 1% 以内
多级队列调度算法(MQ，Multilevel Queues)
- 就绪队列被划分为多个独立的子序列 (例如可以分为前台和后台)
- 每个队列拥有自己的调度策略
- 队列间调度
- 固定优先级
- 先处理前台 后处理后台
- 可能导致饥饿
- 时间片轮转
- 每个队列都得到一个确定的能够调度其进程的CPU总时间
- 80% CPU时间用于前台 20% CPU时间用于后台
- 固定优先级
多级反馈队列算法(MLFQ，Multilevel Feedback Queues)
进程可在不同队列间移动的多级队列算法。
首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程；对于同一个队列中的各个进程，按照FCFS分配时间片调度。
- 时间片大小随优先级级别增加（级别增加，优先级降低）而增加
- 进程在当前时间片没有完成，则降到下一优先级（会被分配更大的时间片）
多级反馈队列算法特征：
- CPU密集型进程的优先级会下降的很快
- I/O密集型进程保留在高优先级
公平共享调度算法(FSS，Fair Share Scheduling)
FSS 控制用户对系统资源的访问
- 一些用户组比其他用户组更重要
- 保证不重要的组无法垄断资源
未使用的资源按比例分配，没有达到资源使用率目标的组获得更高优先级
传统调度算法总结
若采用某个调度算法时，每个进程都有机会被调度，则该调度算法是公平的
- 先来先服务算法(FCFS)
- 不公平 平均等待时间变动大
- 短进程优先算法(SPN)
- 平均周转时间最小
- 需要精确的预测执行时间
- 不公平，可能导致饥饿
- 最高响应比优先算法(HRRN)
- 基于 SPN调度(关注等待时间)
- 不可抢占
- 时间片轮转算法(RR)
- 公平 平均等待时间较差 交互比较好
- 多级反馈队列算法(MLFQ)
- 多种算法的集合(在实际系统中所使用)
- 公平共享调度(FSS)
- 公平
实时调度和多处理器调度
实时调度
实时操作系统不仅要求功能正确，还要约定的时间得以保证。
时间约束的及时性和可预测性比速度、平均性能更重要。
要保证时间能极大概率满足一个具体要求。
几个概念：
- 实时任务：对时限有要求的任务
周期实时任务：一系列相似的规律重复的实时任务。由周期、最大执行时间、使用率等决定。波动越小，使用率就可以越高。
硬实时和软实时：硬实时必须要满足时限，可以保证系统的确定性，否则会导致严重后果；而软实时只需尽量满足，无法达成时可以降低要求。
可调度性：一个操作系统可以满足任务的时限要求。
- 需要确定实时任务的执行顺序
- 进行动态或静态的优先级调度
这里给出两个理论上可调度的实时调度算法，不要求掌握。
- 速率单调调度算法RM：通过周期安排优先级，周期越短越早安排。
- 最早截止时间优先算法EDF：截止时间越早优先级越高。
多处理器调度
多个处理器组成一个多处理器系统，处理器之间共享负载。
对称处理器调度：
- 各处理器都有自己的调度机制
- 访问共享资源时再进行同步
对称多处理器进程分配：
- 静态进程分配
- 进程从开始到结束都被分配到一个固定的处理机上执行
- 每个处理机有自己的就绪队列
- 调度开销小
- 各处理机可能忙闲不均
- 动态进程分配
- 进程在执行中可分配到任意空闲处理机上执行
- 所有处理机共享一个就绪队列
- 调度开销大
- 各处理机的负载是均衡的
优先级反置
优先级置是我们不希望发生的一种调度状态。在该种状态下，一个高优先级任务间接被一个低优先级任务所抢先。
这往往出现在一个高优先级任务等待访问一个被低优先级任务正在使用的临界资源时。并且此时，该低优先级任务被一个次高优先级的任务所抢先，从而无法及时地释放该临界资源。从而阻塞了高优先级任务。如下图。
注：临界资源指一次只能被一个进程占用的资源，这些资源是互斥体。
如何解决优先级反置?
为了保证这个互斥体资源不被次高级进程抢走，常见地，我们有如下两种策略：
- 优先级继承(Priority Inheritance)
- 优先级天花板协议(Priority Ceiling Protocol)
优先级继承(Priority Inheritance)
占用资源的低优先级进程，继承申请资源的高优先级进程的优先级。
以下图为例，T1为优先级最高的进程，T3为最低。t4之后为什么让T3先执行，就是使用了优先级继承的策略，将T3的优先级提高到和T1一样，从而让已经占有临界区资源的进程先运行。从图中可以看出，如果t4之后资源s被次高级的T2所抢占，那么T1和T3还需要等很长时间。
注意，只有在占有资源的低优先级进程被阻塞时，才提高占有资源进程的优先级。如上图中的t3到t4之间发生的。
优先级天花板协议(Priority Ceiling Protocol)
占用资源进程的优先级，和所有可能申请该资源的进程的最高优先级相同。
- 不管是否发生等待，都提升占用资源进程的优先级
- 从而当任务执行临界区时就不会被阻塞
