操作系统2-调度
进程调度
如果存在多个进程竞争CPU，那么需要选择下一个要运行的进程；
- 调度程序
- 调度算法
目标：满足系统目标（响应时间，吞吐量，处理器效率）的方式，将进程分配称一个或多个处理器上执行；
调度层次类型：长程/中程/短程……
长程调度
决定外存上后备队列中哪个作业进入内存处理
考虑两个问题：
- 何时创建进程
- 取决于多道程序的并发度；
- 处理器的空闲时间超过某个阈值，也可能启动长程调度；
- 选择哪些作业进行调度
- 取决于调度算法
中程调度
属于对换功能的一部分，用以提高内存的利用率和系统的吞吐量；
- 内存紧张时，选择一个进程换出到外存
- 内存充裕时，从外存选择一个挂起的进程调度到内存
- 只有支持进程挂起的操作系统支持中程调度
短程调度
决定就绪队列中哪个进程应该获得处理器；
- 运行频率最高；
- 现代操作系统几乎都设计了短程调度功能；
- 引发原因：时钟中断，io中断，操作系统调度，信号；
调度规则
周转时间
构成：作业提交给系统，到作业完成的时间间隔
- 驻外存等待调度时间
- 驻内存等待调度时间
- 执行时间
- 阻塞时间
平均周转时间
$$
T=\frac1 n \sum_{i=1}^n T_i
$$
带权周转时间
$$
W_i=\frac {T_i}{T_{service}}
$$
平均带权周转时间
$$
T=\frac1 n \sum_{i=1}^n W_i
$$
响应时间
从用户提交请求开始， 到系统首次产生响应的时间；
- 输入传送时间
- 处理时间
- 响应传送时间
截止时间
- 某任务必须开始执行的最迟时间；
- 必须完成的最迟时间；
系统吞吐量
在单位时间内系统完成的作业数；
需求
- 面向用户
- 响应时间快：使绝大多数用户的请求能在能够接受响应的时间完成，常用于评价分时系统
- 平均周转时间短：常用语评价批处理系统
- 截止时间：常用语评价实时系统
- 面向系统：
- 系统吞吐量大：评价批处理系统
- 处理器利用率高：评价大型用户系统
- 公平性
- 资源平衡使用
- 优先权高进程优先调度
决策模式
- 抢占（剥夺）方式：中断当前进程，让优先级较高的进程执行
- 非抢占（非剥夺）方式：执行进程只有在执行完毕时才会释放处理机的进程，不适合即时性较高的场景
调度算法
系统的资源 分配策略 规定的资源分配算法，以针对不同的系统目标；
常见的调度算法：
- 先来先服务
- 时间片轮转
- 短作业优先
- 剩余时间最短
- 最高响应比优先
- 反馈
先来先服务FCFS
选择最先进入就绪队列的进程投入执行，进程按照请求CPU的顺序使用CPU
评价：
- 属于非抢占调度方式
- 有利于CPU繁忙的进程，不利于IO繁忙的进程
- 不利于直接用于分时系统
- 平均周转时间长
- 对于长进程有利，不利于短进程
- 简单，但是相对公平
时间片轮转RR
CPU被每个进程分配自己的时间片，在时间片结束时进程还在运行，则抢占其CPU分配个下一个进程；
被剥夺CPU的进程插入到队列末尾等待下一次的调度；
如果该进程在时间片内注射或结束，则立即切换CPU；
评价：
- 属于抢占式调度
- 常用语分时系统和事务处理系统
- 时间片设置和系统性能，响应时间密切相关（时间片短导致调度程序和中断次数多，时间片长引起短交互请求的响应时间变长）
- 时间片的大小的确定要考虑最大最大用户数量，响应时间，系统效率
虚拟轮转法VRR
增加一个基于FCFS的辅助队列，接受I/O阻塞完成的进程，调度优先于主就绪队列，但是占用处理机时间小于主就绪队列的时间片
评价：
- VRR相较RR公平
- 常用语分时系统，事务处理系统
短进程优先SPN/SJN
进程的执行时间预知，选择短进程优先调度
评价：
- SPN属于非抢占式调度算法
- 对长作业不利，可能导致饥饿
- 有利于短进程，减小了平均周转时间
- 缺少剥夺机制，不适用分时系统或事务
- 算法不一定准确，不一定真正做到短作业优先
剩余时间最短者优先SRT
调度程序总是选择预期时间最短的进程
当新进程加入就绪队列，若它比当前运行进程更短的剩余时间，就会发生抢占
在SPN上增加了剥夺机制；
评价：
- 不像FCFS偏爱长进程，也不像RR产生额外的中断，减小了开销
- 在周转时间方面，SRT性能比SPN更好，短作业可以立即被选择执行
- 需要预估服务时间，可能存在进程饥饿，必须记录进程的已服务时间
最高响应比优先HRRN
当前进程执行完毕/需要阻塞时，选择就绪队列中响应比最该的进程投入执行；
$$
R_p=\frac{T_{wait}+T_{service}}{T_{service}}
$$
评价：
- HRRN本质上是动态优先权调度算法
- 结合了FCFS和SPN，既照顾了短进程，又考虑了到达的先后次序，不会使长进程长期得不到服务
- 每次调度前需要计算响应比，既增大了开销又难以准确计算
反馈调度法FB
采用多级队列区别对待，惩罚长进程；
- 准备多个独立的，优先级不同的就绪队列
- 优先级高的队列被优先调度
- 进程执行过程可能 被降级，整个生命周期内可能位于不同的队列；
以基于时间片轮转的FB算法为例：
- 设置多个就绪队列，其优先级不同
- 优先级约到的队列，进程执行的时间片越小
- 新进程进入，首先放入第一个队列的队尾，FCFS原则排队
- 若进程在规定时间片完成，则退出
- 队列$i$调度的进程允许执行$2^i$的时间，才会被抢占
- 若时间片完则被抢占被抢占的进程降级到下一个优先队列
- 到末尾队列不再降级
- 当且仅当上一个队列空闲，下一个队列的进程才被调度
评价：
- FB算法具有较好的性能，平衡了各类需求
- 有利于终端作业用户，这类通常为短作业，一般能在第一队列规定的时间片做完
- 对于长批处理作业，也能在前几个队列规定时间片完，但是不断有长进程到来时，可能存在饥饿
实时系统和实时调度
实时系统
系统能及时响应外部事件的请求，规定时间内完成对该事件的处理，控制所有的实时任务协调运行
实时操作系统的特点
- 可确定性：任务按照固定的预先确定的时间间隔进行
- 可响应性：关注系统知道中断后为中断提供服务时间
- 用户控制：用户能区分软实时和硬实时任务，控制任务优先级
- 可靠性：实时控制，响应事件，保障性能
- 失效弱化：不能满足所有任务的实时性时，优先满足重要的，优先级高的任务期限，减少系统故障
调度方式 - 基于时间片的轮转抢占式
- 进程按照时间片轮转方式执行，到达进程放在就绪队列末尾
- 时间片完进行调度，响应时间为秒级，广泛用于分时系统和一般实时处理系统
- 基于优先级的非抢占式
- 进程按照优先级，非抢占的方式，新来的进程在就绪队列的头部
- 当前进程阻塞或完成时，立即调度新来的进程
- 响应时间为数百毫秒到数秒，用于多道批处理系统和不太严格的实时系统
- 基于优先级的抢占点抢占调度
- 进程按照优先级，抢占方式执行
- 下一个剥夺点到来时，立即占用CPU
- 响应时间为数十毫秒，用于一般实时系统
- 立即抢占式调度
- 按照优先级，抢占方式
- 响应时间在微妙级，用于苛刻的实时系统
实时任务
具有及时性，常常被重复执行，往往预先设定的特定进程，在实时系统中称为任务
- 开始截止时间：该时间之前任务必须执行
- 完成截止时间：该时间之前任务必须结束
分类： - 按截止时间划分：硬实时任务，软实时任务
- 按周期性划分：周期性实时任务，非周期性实时任务
实时调度
静态表驱动调度
用于调度周期性实时任务
按照任务周期到达的时间，执行时间，完成截止时间以及任务的优先级，制定调度表，调度实时任务
比如：最早截止时间优先(EDF)调度算法
任何任务调度申请改动都会引起调度表的修改，带来不灵活性；
静态优先级抢占调度
多用于非实时多道程序系统
优先级确定方法很多
实时系统一般对任务的限定时间赋予优先级；
比如：速度单调算法(RMS)为实时任务赋予静态优先级
- 任务速率：任务周期以赫兹为单位
- 优先级确定：任务周期越短，优先级越高；优先级函数时任务速度的单调递增的函数
- 系统按任务优先级的高低工作进行调度；
基于动态规划的调度
实时任务到达以后，系统为新到达的任务和正在执行的任务动态创建调度表
在当前执行进程不会错过截止时间的条件下，如果也能使新到达任务在截止时间完成下，则立即调度执行新任务；
动态尽力调度法
广泛用于非周期性实时任务调度
当任务到达时，系统根据属性赋予优先级，优先级高的先调度；
比如EDF算法总是尽力尽早调度紧迫任务；
缺点：当任务完成或者截止时间到达时，很难知道该任务是否满足其约束时间；
限期调度
对具有完成期限的周期性实时任务
这类任务往往周期性可预测的；
一般采用最早截止时间优先调度算法EDF；
对具有开始期限的非周期性实时任务
这类任务往往是非周期的不可预测的；
预先知道任务的截止时间可采用允许CPU空闲的EDF调度算法；
- 优先调度截止时间最早的合格任务，并运行完毕
- 合格任务可以是还未就绪，但是事先知道开始截止时间的任务
- CPU利用率不高，但是系统的任务都能按要求完成
实时系统处理能力限制
假定系统中有$m_i$个周期性硬实时任务，处理时间分别为$c_i$，周期为$p_i$,则在单处理机的情况下，满足如下限制
$$\sum_{i=1}^m \frac{c_i}{p_i} \le 1$$
CPU利用率=任务执行时间/任务周期；
各个任务的处理器利用率总和不超过1；
优先级反转
一个高优先级任务简介被一个低优先级任务所抢占，使得两个任务的相对优先级被倒置；
系统不希望这种调度任务状态，但是可发生于任何基于优先级的可抢占的调度方案；
解决方案：优先级继承，优先级较低的任务继承任何与其共享同一资源的优先级较高的任务的优先级