大家好,欢迎来到IT知识分享网。
目录
3.1 调度算法类别(Categories of Scheduling Algorirhm)
3.2.1 First-Come, First-Served(FCFS)
3.2.6 Multi-level Feedback Queue
4.1 Ealiest Deadline First(最早截止时间优先)
1.什么是调度
一句话:决定下一个执行的进程(也被称为CPU调度)
2.进程行为
包括:
- CPU Bursts:进程需要CPU的一段时间
- I/O Bursts:进程需要I/O的一段时间
CPU bursts 和 frequency因进程而异:
- CPU-Bound 进程:长CPU bursts,少的I/O等待
- I/O-Bound 进程:短CPU bursts,频繁的I/O等待
3.CPU调度(CPU Scheduling)
什么时候调度:
- 当一个新线程创建时
- 正在运行的进程退出
- 运行进程被阻塞
- I/O中断或时钟中断
抢占(Preemptive)调度:会中断正在运行的进程, 需要释放CPU
非抢占(Non-preemptive)调度:正在运行的进程一直占用CPU,知道自己主动放弃
3.1 调度算法类别(Categories of Scheduling Algorirhm)
类别:
- 批处理系统(Batch System):非抢占算法/抢占算法,每个进程有很长的时间周期
- 交互式系统(Interactive System):抢占式必要的
- 实时系统(Real-Time System):有时不需要抢占
调度算法的目标:
- 所有系统
- 公平:任何进程都不应starvation
- 策略执行:确保政策得到实施
- 效率:尽可能保持资源繁忙
- 批处理系统
- 吞吐量(Throughput):单位时间内处理的作业数
- 周转时间(Trunaround Time):从提交进程到执行完毕并将完整输出返回给用户所花的时间(要和平均等待时间区分开,这个从提交进程就开始算到完成进程,AWT指进程要等的时间,不算CPU调度时间)
- 处理器利用率(Processer Utilization):CPU burst的比例
- 交互式系统
- 响应时间:从第一次提交请求到产生第一个响应的时间长度
- 比例性:满足用户期望
- 实时系统
- 最后期限:完成所有的deadlines
- 可预测性:相同的时间/成本无论系统上的负载如何
3.2 单处理器调度算法
批处理系统:
- First-Come First-Serverd(FCFS)
- Shortest Job First(短时间工作优先)
交互系统:
- Round Robin(轮询)
- Priority Scheduling(优先级调度)
- Multi-level Queue(多级队列) & Multi-level Feedback Queue(多级反馈队列)
- Shortest Process Next
- Guaranteed Scheduling
- Lottry Scheduling(彩票调度)
- Fair Sharing Scheduling
3.2.1 First-Come, First-Served(FCFS)
优点:实现非常简单
缺点:
- 等待时间取决于到达顺序
- 可能要等待很长时间才能被调度
- 护航效应(Convoy Effect):短时间的job需要等很长时间
- 增加了短时间job的等待时间
- 降低I/O设备的利用率
护航效应(Convoy Effect):所有I/O设备空闲,即使系统包含大量的I/O jobs
示例:
3.2.2 Shortest Job Frist(SJF)
策略: 先服务burst time(忙时间)最小的job(当所有的jobs同时到达时,SJF是最好的)
两种版本:Non-preemptive(非抢占式),Preemptice(抢占式)
前提:需要事先知道burst time才能
优点:
- 最小的平均等待时间(average wait time)
- 有助于保持IO设备的繁忙
缺点:
- 如果无法提前知道jobs的burst time,就不能用这个调度算法
- 会导致长时间的jobs starvation
非抢占式SJF示例:
抢占式SJF示例:
3.2.3 Round-robin Scheduling
概述:
- 把所有进程放入一个循环队列,然后循环调度CPU
- 每个进程获得一小部分CPU时间(时间量子(time quantum) 或者 时间切片(time slice)),通常为10-100ms
- 允许进程运行直到时间片周期过期,然后发生时钟中断,并将运行的进程放在ready队列中
- 如果该进程在时间片前阻塞或结束,则完成切换
ready队列中的N个进程和时间量子q:
- 每个进程获得1/N的CPU时间,每次最多q个时间单位
- 没有进程等待超过(n-1)q个时间单位
示例:
优点:
- 在job之间公平分配CPU,没有starvation
- 当job长度变化时,平均等待时间较短
- 最短时间的job相对较快完成
- 周转时间通常SRTF大,但响应时间更好
缺点:
- job时间长度相同时,平均等待时间不佳
- 性能取决于时间片的长度
- 如果时间片太短,就要增加上下文切换的开销
- 如果时间片太长,退化为FCFS
- 没有考虑优先级
- 频繁的上下文切换导致高开销
时间量子(Time Quantum):
- 时间量子太大:
- 可以在单个量子内完成大多数进程,所以低上下文切换开销
- 但是太大了又会导致调度为FCFS调度,响应时间差
- 时间量子太小:
- 太多的上下文切换
- CPU利用率低
3.2.4 Priority Scheduling
概述:
- 具有优先级的FCFS
- 选择优先级最高的job
- 合理的,因为高优先级的job更加关键
- SJF时优先级调度,其中优先级与下一个CPU burst长度成反比
优先级设置:
- 两种方法:
- 静态:具有静态优先级的进程在其整个生命周期内保持该优先级
- 动态:具有动态优先级的进程在其执行过程中由调度器更改其优先级
- 静态优先级和动态优先级可以共存
- 优先级可能基于:
- 用户成本
- 用户重要性
- 进程类型
- 资源需求
- Aging
- 最近X小时内使用的CPU时间的百分比
动态优先级示例:
- 根据每个进程使用的量子比例分配优先级
- P = 1/f,f是进程使用的最后一个量子的分数
- 时间片:50ms
- 进程A使用1ms,f=1/50,优先级 = 50
- 进程B使用50ms,f=50/50,优先级 = 1
优点:
- 提供一种良好的机制,可以精确地定义每个过程的相对重要性
缺点:
- 低优先级的job可能会starvation
- 可以通过Aging来避免:随着它们在系统中花费的时间增加优先级
- 可能给出不好的平均等待时间(AWT)
示例:
3.2.5 Multi-level Queue
概述:
- 优先级调度的扩展,还结合了其他策略
- 使用场景:进程可以根据属性(如进程类型)进行分组
- 将ready队列拆分成多个队列,将进程永久地分配给一个队列
- 每个队列都有自己的调度算法
队列之间的调度:
- 固定优先级抢占调度算法
- 时间切片:每个队列获得一定数量的CPU时间,它可以在其进程之间调度
优点:
- 进程被永久地分配给队列,因此它具有低调度开销的特点
- 对不同类型的进程进行单独调度是可能的
缺点:
- 最底层的进程面临starvation问题
3.2.6 Multi-level Feedback Queue
概述:
- 进程在队列之间移动
- 运行在高优先级队列中的进程,当它完成一个CPU burst时,将它移动到低优先级的队列
- 反馈 (Feedback) = 使用过去预测未来 – 优先处理过去没有大量使用CPU的job – 接近最短剩余时间优先(SRTN)调度算法
- 给定队列的job按照给定的时间片执行
- 低优先级队列中的进程只有在高优先级队列为空时才能执行
- 如果高优先级中有新的进程到达,低优先级中的进程会被中断
示例:
优点:
- 更灵活
- 允许不同进程在不同的队列之间移动
- 通过将等待较低优先级队列时间过长的进程移动到高优先级队列来防止starvation
缺点:
- 对于最佳调度器的选择,需要一些其他方法来选择值
- 会产生更多的CPU开销
- 这是最复杂的算法
题目:
3.2.7 Guaranteed Scheduling
概述:对用户做出真正的性能承诺,然后兑现承诺
示例:
- 在运行n个进程时,调度器确保每个进程获得1/n个CPU周期
- 如果有n个用户,调度器将确保每个用户获得1/n的CPU时间
调度:
- 计算实际消耗的CPU时间与分配的CPU时间的比率
- 选择比率最低的那个
- 当运行程序的比率超过其”目标比率“时,切换到另一个进程
3.2.8 Lottery Scheduling
基于概率的:
- 准备状态队列中的每个进程都被分配了一些彩票,然后算法根据随机生成的数字选择赢家
- 获胜进程将获得一个时间片
- 中将进程返回到ready队列,接收下一个进程,循环继续
- 可以为高优先级进程提供更多的彩票
彩票管理:
- 票的货币:
- 调度程序以一种货币向不同的用户提供一定数量的票据,用户可以以不同的货币向他们的进程提供票据
- 例如,两个用户A和B分别得到100张和200张票
- 用户A正在运行两个进程,A用自己的货币给每个进程50张票
- B运行1个进程,B给它的进程200张票
- 票转让:
- 进程可以将票传递给另一个进程
- 票通货膨胀:
- 使用这种技术,进程可以暂时增加或减少它有用的票的数量
优点:
- 简单
- 能支持进程之间的合作
- 解决了starvation的问题
- 易于支持优先级和比例要求
缺点:
- 本质上是不可预测的,对于操作系统设计者来说,没有办法确切地知道在彩票调度中会发生什么,可能会产生不希望的结果,所以它在现代操作系统设计中并不常用
4.真实时间系统(Real-Time Systems)
系统的正确性取决于它们的功能方面,也取决于它们的时间方面
实时的要求:
- 并不总是要求需要大量的CPU时间,但我们可能需要在适当的间隔使用它
- 需要有严格的截止时间
开始时间:任务开始执行的时间
截止时间:任务应在此之前完成的时间
完成时间:任务完成执行的时间
硬截止时间:如果错过截止时间,可能会发生灾难性或非常严重的后果
软截止时间:理想情况下,应该满足最大性能,如果错过了截止时间,性能就会下降
硬实时系统:
- 需要在保证的时间内完成一项关键任务
- 可能会导致灾难如果不能再截止时间前完成任务
- 如安全气囊控制器、飞机自动驾驶系统、核电站控制系统、医疗系统等
软实时系统:
- 错过截止时间时不可取的,但是可以容忍
- 未能满足截止时间会导致性能下降
- 例如:DVD播放机、移动通信、多媒体传输和接收
4.1 Ealiest Deadline First(最早截止时间优先)
概述:
- 对于硬实时系统,进程必须再一定时间内完成
- 周转时间和等待时间是无关的
- 我们需要知道每个进程的最大服务时间
- 必须满足进程生命周期中每个阶段的截止时间
- 截止时间越近的任务优先级越高,最先执行
实时系统中的事件:
- 周期性的
- 非周期性的
示例:
调度性:
- 指示实时系统是否能够满足其截止时间的属性
- 考虑m个周期事件,事件i发生的周期为Pi,需要Ci秒的CPU时间,如果小于1,则能满足
4.2 策略与机制
策略是指需要做什么
机制是如何去做
例子:
- 网站要求用户登录系统(策略)
- 用户可以使用用户名和密码进行登录(机制)
- 用户也可以使用或微信登录(机制)
调度策略:回答了这样一个问题,在所有准备运行的进程/线程中,应该给哪个进程/线程下一个运行的机会?
调度机制:是支持进程/线程抽象并应i选哪个调度策略如何实现的工具
策略与机制的分离:
- 策略与机制的分离是实现灵活性的设计原则
- 调度算法在某种程度上是参数化的,但参数可以由用户进程填充
- 策略由用户进程设置,机制在内核中
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://haidsoft.com/133769.html