操作系统】Operation System"/>
【操作系统】Operation System
操作系统—调度
背景
上下文切换
- 切换CPU的当前任务,从一个进程/线程到另一个
- 保存当前 进程/线程 在 PCB/TCB 中的执行上下文(CPU状态)
- 读取下一个进程/线程的上下文
CPU调度
- 从就绪队列中挑选一个进程/线程作为CPU将要运行的下一个进程/线程
- 调度程序:挑选进程/线程的内核函数(通过一些调度策略)
- 什么时候进行调度?
CPU调度时间
补充:
调度原则
调度策略
-
调度策略
➢ 确定如何从就绪队列中选择下一个执行进程
-
调度策略要解决的问题
➢ 挑选就绪队列中的哪一个进程?
➢ 通过什么样的准则来选择?
-
调度算法
➢ 在调度程序中实现的调度策略
-
比较调度算法的准则
➢ 哪一个策略/算法较好?
程序执行模型
比较调度算法的准则
-
CPU使用率
➢ CPU处于忙状态所占时间的百分比
-
吞吐量
➢ 在单位时间内完成的进程数量
-
周转时间
➢ 一个进程从初始化到结束,包括所有等待时间所花费的总时间
-
等待时间
➢ 进程在就绪队列中的总时间
-
响应时间
➢ 从一个请求被提交到产生第一次相应所花费的总时间
吞吐量 vs 延迟
-
人们通常都需要 ”更快“ 的服务
-
什么是更快?
➢ 传输文件时的高带宽
➢ 玩游戏时的低延迟
➢ 这两个因素是独立的
-
和水管类比
➢ 低延迟:喝水的时候想要一打开水龙头水就流出来(响应时间)
➢ 高带宽:给游泳池充水时希望从水龙头里同时流出大量的水,并且不介意是否存在延迟(吞吐量)
-
我们的目标:
➢ 减少响应时间:及时处理用户的输出并且尽快将输出提供给用户
➢ 减少平均响应时间的波动:在交互系统中,可预测性比高差异性低平均更重要
➢ 增加吞吐量—两个方面:
√ 减少开销(操作系统开销,上下文切换)
√ 系统资源的高效率用(CPU,I/O设备)
➢ 减少等待时间:减少每个进程的等待时间
其实这些指标是有矛盾的,比如很难同时满足 最小响应时间 和 最大吞吐量,要么只顾及某一点,要么对两点进行折中。
-
低延迟调度增加了交互式表现
➢ 如果移动了鼠标,但是屏幕中的光标却没动,我们可能会重启电脑
-
操作系统需要保证低吞吐量不受影响
➢ 我想要结束长时间的编程,所以操作系统必须不时进行调度,即使存在许多交互任务
-
吞吐量是操作系统的计算带宽
-
响应时间是操作系统的计算延迟
公平的目标
-
举例
➢ 保证每个进程占用相同的CPU时间
➢ 这公平吗?如果一个用户比其他用户运行更多的进程怎么办
-
举例
➢ 保证每个进程都等待相同的时间
-
公平通常会增加平均响应时间
调度算法
先来先服务算法(FCFS)
FCFS:First Come,First Served
-
依据进程进入就绪状态的先后顺序排列
➢ 如果进程进入阻塞或结束状态时,就绪队列中的下一个进程会得到CPU
优点
- 简单
缺点
-
平均等待时间波动较大
-
花费时间少的任务可能排在花费时间长的任务后面
-
可能导致I/O和CPU之间的重叠处理
➢ CPU密集型进程会导致I/O设备闲置时,I/O密集型进程也在等待
短进程优先算法(SPN(SJF) / SRT)
SPN:Shortest Process Next(短进程优先算法)
SJF:Shortest Job First(短作业优先算法)
SRT:Shortest Remaining Time(短剩余时间优先算法)
-
选择下一个最短的进程(短任务优先)
➢ 按照预测的完成时间来将任务入队
-
可以是抢占的或者是不可抢占的
➢ 可抢占:又叫 Shortest-Remaining-Time (SRT) (最短剩余时间)
短进程优先算法具有最优平均周转时间。
-
可能导致饥饿
➢ 连续的短任务流会使场任务饥饿
➢ 短任务可用时的任何场任务的CPU时间都会增加平均等待时间
-
需要预测未来
➢ 怎么预估下一个CPU突发的持续时间
➢ 简单的解决:询问用户
➢ 如果用户欺骗就杀死进程
➢ 如果不知道怎么办
短进程优先算法的执行时间预估
预估执行时间
最高响应比优先算法(HRRN)
HRRN:Highest Response Ratio Next
-
选择就绪队列中响应比R值最高的进程
-
在短进程优先算法的基础上改进
-
不可抢占
-
关注进程的等待时间
-
防止无限期推迟
轮循算法(RR)
时间片轮转算法(Round Robin,RR)
-
时间片
➢ 分配处理机资源的基本时间单元
-
时间片结束时,按FCFS算法切换到下一个就绪进程
-
每隔 ( n – 1 ) (n – 1) (n–1) 个时间片进程执行一个时间片 q q q
设置时间片为 20 20 20,每个进程轮流的占用时间片:
-
RR 花销:额外的上下文切换(保证每个进程都有机会执行)
-
时间量子太大
➢ 等待时间过长
➢ 极限情况退化成FCFS
-
时间量子太小
➢ 反应迅速,但产生大量上下文切换
➢ 吞吐量由于大量的上下文切换开销受到影响
-
目标
➢ 选择一个合适的时间量子
➢ 经验规则:维持上下文切换开销处于1%以内
看起来好像FCFS更好一点,因为在FCFS中没有频繁的上下文切换,所以它总等待时间反而还会降低,但是我们还要权衡,因为在FCFS中它达不到像RR一样每一个进程及时得到相应。
公平性会带来一定的代价。
多级反馈队列算法(MFQ)
MFQ:Multilevel Feedback Queues
多级队列调度算法(MQ)
-
就绪队列被划分成独立的队列
➢ 如:前台(交互),后台(批处理)
-
每个队列拥有自己的调度策略
➢ 如:前台 — RR,后台 — FCFS
-
调度必须在队列间进行
➢ 固定优先级
√ 先处理前台,然后处理后台
√ 可能导致饥饿
➢ 时间切片(时间片轮转)
√ 每个队列都得到一个确定的能够调度其进程的CPU总时间
√ 如:80%给使用RR的前台,20%给使用FCFS的后台
在多级队列中,各个队列之间是没有交互的,进一步改进,进程可在不同队列间移动的多级队列算法:
-
多级反馈队列算法(MFQ)
➢ 可以根据情况(反馈)调整进程的优先级、队列。
优先级越高的队列中它的时间片就越短。
优点
- CPU密集型任务的优先级下降很快
- I/O密集型任务停留在高优先级
公平共享调度算法(FSS)
FSS:Fair Share Scheduling
-
FSS控制用户对系统资源的访问
➢ 一些用户组比其他用户组更重要
➢ 保证不重要的组无法垄断资源
➢ 未使用的资源按照每个组所分配的资源的比例来分配
➢ 没有达到资源使用率目标的组获得更高的优先级
评价方式
调度算法总结
-
先来先服务算法(FCFS)
➢ 不公平,平均等待时间较差
-
短进程优先算法(SPN(SJF) / SRT)
➢ 不公平,但是平均等待时间最小
➢ 需要精确预测计算时间
➢ 可能导致饥饿
-
最高响应比优先算法(HRRN)
➢ 基于SPN调度改进
➢ 不可抢占
-
轮循算法(RR)
➢ 公平,但是平均等待时间较差
-
多级反馈队列算法(MFQ)
➢ 和SPN类似,多种算法的集成
-
公平共享调度算法(FSS)
➢ 公平是第一要素
实时调度
实时系统
-
定义
➢ 正确性依赖于其时间和功能两方面的一个操作系统
-
性能指标
➢ 时间约束的及时性(deadlines)
➢ 速度和平均性能相对不重要
-
主要特征
➢ 时间约束的可预测性
分类
-
强实时系统
➢ 需要在保证时间内完成重要的任务,必须完成
-
弱实时系统
➢ 要求重要的进程的优先级更高,尽量完成,并非必须
实时任务
周期实时任务
硬时限和软时限
-
硬时限(Hard deadline)
➢ 如果错过了最后期限,可能会发生灾难性或非常严重的后果
➢ 必须验证:在最坏的情况下也能够满足时限吗?
➢ 保证确定性
-
软时限(Soft deadline)
➢ 理想情况下,时限应该被最大满足。如果有时限没有被满足,那么就相应地降低要求
➢ 尽最大努力去保证
可调度性
单调速率(RM)
速率单调调度算法(RM,Rate Monotonic)
- 最佳静态优先级调度
- 通过周期安排优先级
- 周期越短优先级越高
- 执行周期最短的任务
截止日期最早优先(EDF)
最早期限调度 (EDF,Earliest Deadline First)
- 最佳动态优先级调度
- Deadline越早优先级越高
- 执行Deadline最早的任务
多处理器调度
-
多处理器的CPU调度更复杂
➢ 多个相同的单处理器组成一个多处理器
➢ 优点:复杂共享
-
对称多处理器(SMP)
➢ 每个处理器运行自己的调度程序
➢ 需要在调度程序中同步
优先级反转
优先级继承(Priority Inheritance)
优先级天花板协议(priority ceiling protocol)
整理自 【清华大学】 操作系统
更多推荐
【操作系统】Operation System
发布评论