CPU资源的时分复用
进程切换 CPU资源的当前占用者的切换
- 保存当前进程在 PCB中的执行上下文(CPU状态)
- 恢复下一个进程的执行上下文
处理机调度
- 从就绪队列中挑选出下一个占用CPU运行的进程
- 从多个可用CPU中挑选就绪进程可使用的CPU资源
调度程序
挑选就绪进程的内核函数 (若为多CPU 则还有挑选处理机的功能)
调度时机
内核运行调度程序的条件
- 进程从 运行状态 切换到 等待状态 (等待某个事件)
- 进程结束
非抢占系统
当前进程主动放弃CPU
可抢占系统
- 中断请求被服务例程响应完成时
- 进程从 运行状态 切换到 就绪状态
- 当前进程被抢占
- 进程时间片用完
- 某进程从 等待状态 切换到 就绪状态 (它的优先级更高 则抢占)
处理机资源使用模式
进程在 CPU计算 和 I/O操作 间交替
- 在时间片机制下 进程可能在结束 当前CPU计算前 被迫放弃 CPU
- 应选择一个合适的 时间尺度 来作为 时间片的基本单位
比较调度算法的准则
- CPU利用率
- CPU 处于忙状态的 时间百分比
- 吞吐量
- 单位时间内完成的 进程数量
- 周转时间
- 进程从 初始化 到 结束(包括等待)的总时间
- 等待时间
- 进程在 就绪队列中 的总时间
- 响应时间
- 从提交请求到产生响应所花费的总时间
处理机调度策略的目标
- 响应时间
- 吞吐量
- 公平性
处理机调度策略响应时间目标
响应时间是操作系统的计算延迟
- 减少响应时间
- 及时处理用户的输入请求 尽快将输出反馈给用户
- 减少平均响应时间的波动
- 在交互系统中 可预测性比高差异低平均更重要
处理机调度策略吞吐量目标
吞吐量是操作系统的计算带宽 (单位时间内 尽可能多的完成进程数量)
- 增加吞吐量
- 减少开销(操作系统开销 上下文切换)
- 提高系统资源的利用率(CPU I/O设备)
- 减少等待时间
- 减少每个进程的等待时间
处理机调度策略公平性目标
保证每个进程的等待时间相同 (公平通常会增加平均响应时间)
调度算法
- 先来先服务算法
- 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
先来先服务算法的周转时间(TAT Turnaround time)
周转时间 = 等待时间 + CPU使用时间
3个进程 计算时间分别为 12 3 3
先来先服务算法的特征
- 优点
- 简单
- 缺点
- 平均等待时间波动较大 (短进程排在长进程后面)
- I/O资源 和 CPU资源 利用率较低 (I/O 可以和 CPU并行)
短进程优先算法(SPN Shortest Process Next)
选择就绪队列中 预期的执行时间最短 进程占用CPU进入运行状态
当有一个新的进程进入就绪队列 且 它的预期执行时间比当前正在执行的进程所剩的执行时间还短
允许其优先 则为 SRT: Shortest Remaining Time (短剩余时间优先)
短进程优先算法的周转时间
具有最优平均周转时间
短进程优先算法的特征
- 可能导致饥饿
- 连续的短进程流会使长进程无法获得CPU资源
- 如何 预测进程的执行时间
- 询问用户 用户欺骗就结束相应进程(骗CPU自己执行时间很短 以最快占用CPU资源)
- 用过去预测未来
短进程优先算法的执行时间预估
用历史的执行时间来预估未来的执行时间
每次都带上一个衰减系数 之前的执行时间权重是最小的
最高响应比优先算法(HRRN Highest Response Ratio Next)
选择就绪队列中响应比R值最高的进程
- 基于短进程优先算法的改进
- 不可抢占
- 关注进程等待时间
- 防止无限期推迟
1 | R = (w + s) / s |
等的时间越长 它的优先级越高 在一定程度上避免 短进程优先算法导致的饥饿现象
时间片轮转算法(RR Round Robin)
- 将时间片q 作为 分配处理机资源的基本时间单位
- 时间片结束时 按 FCFS(先来先服务)算法 切换到下一个就绪进程
- 每个进程分到了 1 / n(进程总数) 的时间
时间片轮转算法平均等待时间
4个进程的执行时间
- P1 53
- P2 8
- P3 68
- P4 24
等待时间 = 周转时间 - CPU执行时间
时间片轮转算法特征
有额外的上下文切换开销 (正常情况下是在 进程进入等待状态或结束状态时 才切换进程)
- 当时间片太大时
- 等待时间过长
- 极限情况退化成 FCFS(先来先服务)
- 当时间片太小时
- 反应迅速 但产生大量的上下文切换
- 大量上下文切换开销影响系统的吞吐量(单位时间内 运行的总进程数)
- 时间片长度选择目标
- 通常为 10ms左右 为一个时间片
- 维持上下文开销处于 1% 以内
多级队列调度算法(MQ Multilevel Queues)
- 就绪队列被划分为多个独立的子序列 (分前台后台)
- 每个队列拥有自己的调度策略
- 队列间调度
- 固定优先级
- 先处理前台 后处理后台
- 可能导致饥饿
- 时间片轮转
- 每个队列都得到一个确定的能够调度其进程的CPU总时间
- 80% CPU时间用于前台 20% 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)
速率单调调度算法(RM Rate Monotonic)
通过周期安排优先级 (频率越高 周期越短 优先级越高)
最早截止时间优先算法(EDF Earliest Deadline First)
截止时间越早 优先级越高
多处理器调度
- 多个处理机组成一个多处理机系统
- 处理机间可负载共享
对称多处理器(SMP Symmetric multiprocessing)调度
- 截止时间越早 优先级越高 每个处理器运行自己的调度程序
- 调度程序对共享资源的访问需要进行同步
对称多处理器进程分配
- 静态进程分配
- 进程从开始到结束都被分配到一个固定的处理机上执行
- 每个处理机有自己的就绪队列
- 调度开销小
- 各处理机可能忙闲不均
- 动态进程分配
- 进程在执行中可分配到任意空闲处理机上执行
- 所有处理机共享一个就绪队列
- 调度开销大
- 各处理机的负载是均衡的
优先级反置(Priority Inversion)
操作系统中出现高优先级进程长时间等待低优先级进程所占用资源的现象
- 只会在 基于优先级的可抢占调度算法中出现
1 | T1 运行要占用资源 L1 |
如何解决优先级反置?
- 优先级继承(Priority Inheritance)
- 优先级天花板协议(Priority Ceiling Protocol)
优先级继承(Priority Inheritance)
占用资源的低优先级进程继承申请资源的高优先级进程的优先级 (只有在低优先级进程被阻塞时 才会提高占用资源进程的优先级)
1 | T3 进入执行状态 且在 t2 时刻占用资源s |
优先级天花板协议(Priority Ceiling Protocol)
占用资源的进程的优先级和所有可能申请该资源的进程的最高优先级相同
- 不管是否发生等待 都提升占用资源进程的优先级
- 优先级高于系统中所有被锁定的资源的优先级上限 任务执行临界区时就不会被阻塞
临界区 = 一个访问共用资源的程序片段