处理机调度
执行多任务的计算机必然会涉及到进程切换的问题，进程切换也是CPU当前使用者的切换，下一个使用CPU运行的进程或线程则由处理及调度来完成。与页面置换算法不同，调度策略有不一致的目标比如响应时间、吞吐量、公平性。针对不同目标，设计了不同的调度算法，各有优劣之处，无法兼顾各个指标。
CPU资源的时分复用
进程切换 CPU资源的当前占用者的切换
- 保存当前进程在 PCB中的执行上下文(CPU状态)
- 恢复下一个进程的执行上下文
处理机调度
- 选线程：从就绪队列中挑选出下一个占用CPU运行的线程
- 选CPU: 从多个可用CPU中挑选就绪进程可使用的CPU资源
调度程序 挑选就绪进程的内核函数，若为多处理系统，则还需挑选处理机
调度时机
内核运行调度程序的条件
- 进程从运行状态切换到等待状态 (等待某个事件的发生)
- 进程结束
非抢占系统
占用CPU运行的进程的主动放弃（退出、等待）
可抢占系统
- 中断请求被服务例程响应完成时
- 进程从运行状态切换到就绪状态
- 当前进程被抢占
- 进程时间片用完
- 某更高优先级进程从等待状态切换到就绪状态
调度策略
调度策略用于从就绪队列中选择下一个执行进程(与调度目标有关)。
调度算法 在调度程序中实现的调度策略
处理机资源使用模式特征
进程在CPU计算和I/O操作(CPU处于等待状态)交替
- 在时间片机制下，进程可能在结束当前CPU计算前被迫放弃CPU
- 应选择一个合适的时间尺度来作为时间片的基本单位
- 交替执行，每次执行时间很短，占用CPU执行指令的时间长度分布多数在10ms以内。
比较调度算法的准则
与之前的页面置换算法不同，比较调度算法的准则并不一致，分为以下几种，
- CPU利用率
- CPU 处于忙状态的时间百分比
- 吞吐量
- 单位时间内完成的进程数量
- 周转时间
- 进程从初始化到结束(包括等待)的总时间
- 等待时间
- 进程在就绪队列中的总时间，缩小就绪时间
- 响应时间
- 从提交请求到产生响应所花费的总时间(延迟)
处理机调度策略的目标
响应时间
响应时间时操作系统的计算延迟。
- 减少响应时间
- 及时处理用户的输入请求 尽快将输出反馈给用户
- 减少平均响应时间的波动
- 在交互系统中 可预测性比高差异低平均更重要
吞吐量
吞吐量是操作系统的计算带宽(单位时间内执行进程数)。
- 增加吞吐量
- 减少开销(操作系统开销 上下文切换)
- 提高系统资源的利用率(CPU 、I/O设备)
- 减少等待时间
- 减少每个进程的等待时间
公平性
- 保证每个进程的等待时间相同
- 保证每个进程占用CPU时间相同
- 公平通常会增加平均响应时间，会由开销来保证公平
传统调度算法
就绪队列排列顺序
- 先来先服务算法
- FCFS: First Come, First Served
- 短进程优先算法(考虑进程特征)
- SPN: Shortest Process Next
- SJF: Shortest Job First(短作业优先算法)
- SRT: Shortest Remaining Time(短剩余时间优先算法)
- 最高响应比优先算法 (进程在就绪队列里的等待时间)
- HRRN: Highest Response Ratio Next
时间长短控制
- 时间片轮转算法 (轮流，先来先服务)
- RR: Round Robin
多种算法综合
- 多级反馈队列算法 (将就绪队列分成不同子序列，不同队列使用不同的算法)
- MLFQ: Multilevel Feedback Queues
- 公平共享调度算法 (按照进程占用的资源来调度)
- FSS: Fair Share Scheduling
先来先服务算法
先来先服务算法(FCFS First Come, First Served)
依据进程进入就绪队列的先后顺序排列
- 进程进入等待或结束状态时 就绪队列中下一个进程占用CPU(主动让出)
FCFS算法的周转时间
从例子中可以看出：周转时间跟队列到达时间有很大关系。
先来先服务算法的特征
优点
- 简单
缺点
- 平均等待时间波动较大
- I/O资源和CPU资源利用率较低 (未考虑到I/O和CPU并行)
短进程优先算法
短进程优先算法(SPN Shortest Process Next)
短剩余时间优先算法(SRT short remaining time)
若进程执行过程中有新进程进入就绪队列，预期执行时间比当前进程剩余执行时间段，则允许其抢占正在执行的进程(被动)。
周转时间
SPN算法具有最优平均周转时间，具体证明如下所示：
短进程优先算法的特征
- 可能导致饥饿
- 连续的短进程流会使长进程无法获得CPU资源
- 如何预测下一个CPU计算的持续时间
- 询问用户 用户欺骗就杀死相应进程
- 用过去预测未来
执行时间预估
1 | τ(n+1) = αt(n)+(1-α)τ(n)，其中 0≤α≤1 |
预估CPU时间会越来越接近实际CPU执行时间(近似拟合)。
最高响应比优先算法
最高响应比优先算法(HRRN Highest Response Ratio Next)
1 | R = (w + s) / s |
选择就绪队列中响应比R值最高的进程
- 基于短进程优先算法的改进，但是不可抢占
- 关注进程等待时间
- 防止无限期推迟
时间片轮转算法
时间片轮转算法(Round Robin)
将时间片作为分配处理机资源的基本时间单元。在时间片结束时，按 FCFS(先来先服务)算法切换到下一个就绪进程。
- 每隔(n-1)个时间片进程执行一个时间片
以时间片为20的RR算法为例：
周转时间=等待时间+执行时间
时间片轮转算法特征
有额外的上下文切换开销
- 当时间片太大时
- 等待时间过长
- 极端情况下退化成 FCFS
- 当时间片太小时
- 反应迅速 但产生大量的上下文切换
- 大量上下文切换开销影响系统的吞吐量(单位时间内 运行的总进程数)
- 时间片长度选择目标
- 选择一个合适的时间片长度
- 维持上下文开销处于1%以内
多级队列调度算法(MQ Multilevel Queues)
就绪队列被划分为多个独立的子序列 (分前台后台)
每个队列拥有自己的调度策略
队列间调度
- 固定优先级 可能导致饥饿
- 时间片轮转 每个队列都得到一个确定的能够调度其进程的CPU总时间
多级反馈队列算法(MLFQ Multilevel Feedback Queues)
进程可在不同队列间移动的多级队列算法
- 时间片大小随优先级级别增加而增加
- 进程在当前时间片没有完成 则降到下一优先级
多级反馈队列算法特征
- CPU密集型进程的优先级会下降的很快
- I/O密集型进程保留在高优先级
公平共享调度算法(FSS Fair Share Scheduling)
FSS 控制用户对系统资源的访问
一些用户组比其他用户组更重要
保证不重要的组无法垄断资源
未使用的资源按比例分配
没有达到资源使用率目标的组获得更高优先级
传统调度算法总结
先来先服务算法(FCFS)
- 不公平 平均等待时间变动大
短进程优先算法(SPN)
- 不公平 平均周转时间最小
- 需要精确的预测执行时间
- 可能导致饥饿
最高响应比优先算法(HRRN)
- 基于 SPN调度(关注等待时间)
- 不可抢占
时间片轮转算法(RR)
- 公平 平均等待时间较差 交互比较好
多级反馈队列算法(MLFQ)
- 多种算法的集合(在实际系统中所使用)
公平共享调度(FSS)
- 公平
实时操作系统
正确性依赖于其时间和功能两方面的操作系统
- 实时操作系统的性能指标
- 时间约束的及时性(deadlines)
- 速度和平均性能相对不重要
- 实时操作系统的特性
- 时间约束的可预测性
实时操作系统分类
- 强实时操作系统
- 要求在指定时间内必须完成重要的任务
- 弱实时操作系统
- 重要进程有高优先级，但并非必须完成
实时任务
- 任务(工作单元)
- 一次计算，一次文件读取，一次信息传递等
- 任务属性
- 完成任务所需要的资源
- 规定时间
周期实时任务
一系列相似的任务
- 任务有规律地重复
- 周期p = 任务请求时间间隔 (0 < p)
- 执行时间e = 最大执行时间(0 < e < p)
- 使用率U = e / p
硬时限和软时限
硬时限和软时限对时间要求宽松程度不同，所以应对策略也有所不同。
- 硬时限(Hard deadline)
- 错过任务时会导致灾难性或非常严重的后果
- 必须验证在最坏的情况下能够满足时限
- 软时限(Soft deadline)
- 通常能满足任务时限，若不满足则降低要求
- 尽力满足任务时限
可调度性
可调度表示一个实时操作系统能够满足任务时限要求
- 需要确定实时任务的执行顺序
- 静态优先级调度(执行前确定执行顺序)
- 速率单调调度算法(RM: Rate Monotonic)
- 动态优先级调度(执行时确定执行顺序)
- 最早截止时间优先算法(EDF: Earliest Deadline First)
多处理机调度
多处理机的特征
- 多个处理机组成一个多处理机系统
- 处理机间可负载共享
对称多处理器(SMP Symmetric multiprocessing)调度
- 截止时间越早 优先级越高 每个处理器运行自己的调度程序
- 调度程序对共享资源的访问需要进行同步
对称多处理器进程分配
- 静态进程分配
- 进程从开始到结束都被分配到一个固定的处理机上执行
- 每个处理机有自己的就绪队列，刚开始队列分配后就不再切换就绪队列
- 调度开销小
- 各处理机可能忙闲不均
- 动态进程分配
- 进程在执行中可分配到任意空闲处理机上执行
- 所有处理机共享一个就绪队列
- 调度开销大
- 各处理机的负载是均衡的
优先级反置
操作系统中出现高优先级进程长时间等待低优先级进程所占用资源的现象
- 基于优先级的可抢占调度算法中存在优先级反置
T2运行中申请T1已经占用的资源，但是T1正在占用资源L1,释放之后T2才可以执行，这时候T3优先级比T1高，抢占T1进入运行状态，这时候就会出现高优先级的T2等待。
如何解决优先级反置?
- 优先级继承(Priority Inheritance)
- 优先级天花板协议(Priority Ceiling Protocol)
优先级继承
优先级天花板协议
占用资源的进程的优先级和所有可能申请该资源的进程的最高优先级相同
- 不管是否发生等待，都提升占用资源进程的优先级
- 优先级高于系统中所有被锁定的资源的优先级上限，任务执行临界区时就不会被阻塞