操作系统常用调度算法,你知道几个?
【大咖・来了 第7期】10月24日晚8点观看《智能导购对话机器人实践》
在操作系统中存在多种调度算法,其中有的调度算法适用于作业调度,有的调度算法适用于进程调度,有的调度算法两者都适用。下面介绍几种常用的调度算法。
先来先服务(FCFS)调度算法
FCFS调度算法是一种最简单的调度算法,该调度算法既可以用于作业调度也可以用于进程调度。在作业调度中,算法每次从后备作业队列中选择***进入该队列的一个或几个作业,将它们调入内存,分配必要的资源,创建进程并放入就绪队列。
在进程调度中,FCFS调度算法每次从就绪队列中选择***进入该队列的进程,将处理机分配给它,使之投入运行,直到完成或因某种原因而阻塞时才释放处理机。
下面通过一个实例来说明FCFS调度算法的性能。假设系统中有4个作业,它们的提交时间分别是8、8.4、8.8、9,运行时间依次是2、1、0.5、0.2,系统�用FCFS调度算法,这组作业的平均等待时间、平均周转时间和平均带权周转时间见表2-3。
平均等待时间 t = (0+1.6+2.2+2.5)/4=1.575
平均周转时间 T = (2+2.6+2.7+2.7)/4=2.5
平均带权周转时间 W = (1+2.6+5.牡13.5)/4=5.625
FCFS调度算法属于不可剥夺算法。从表面上看,它对所有作业都是公平的,但若一个长作业先到达系统,就会使后面许多短作业等待很长时间,因此它不能作为分时系统和实时系统的主要调度策略。但它常被结合在其他调度策略中使用。例如,在使用优先级作为调度策略的系统中,往往对多个具有相同优先级的进程按FCFS原则处理。
FCFS调度算法的特点是算法简单,但效率低;对长作业比较有利,但对短作业不利(相对SJF和高响应比);有利于CPU繁忙型作业,而不利于I/O繁忙型作业。
短作业优先(SJF)调度算法
短作业(进程)优先调度算法是指对短作业(进程)优先调度的算法。短作业优先(SJF)调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业,将它们调入内存运行。而短进程优先(SPF)调度算法,则是从就绪队列中选择一个估计运行时间最短的进程,将处理机分配给它,使之立即执行,直到完成或发生某事件而阻塞时,才释放处理机。
例如,考虑表2-3中给出的一组作业,若系统�用短作业优先调度算法,其平均等待时间、平均周转时间和平均带权周转时间见表2-4。
平均等待时间 t = (0+2.3+1.4+1)/4=1.175
平均周转时间 T = (2+3.3+1.9+1.2)/4=2.1
平均带权周转时间 W = (1+3.3+3.8+6)/4=3.525
SJF调度算法也存在不容忽视的缺点:
- 该算法对长作业不利,由表2-3和表2-4可知,SJF调度算法中长作业的周转时间会增加。更严重的是,如果有一长作业进入系统的后备队列,由于调度程序总是优先调度那些 (即使是后进来的)短作业,将导致长作业长期不被调度(“饥饿”现象,注意区分“死锁”。后者是系统环形等待,前者是调度策略问题)。
- 该算法完全未考虑作业的紧迫程度,因而不能保证紧迫性作业会被及时处理。
- 由于作业的长短只是根据用户所提供的估计执行时间而定的,而用户又可能会有意或无意地缩短其作业的估计运行时间,致使该算法不一定能真正做到短作业优先调度。
注意,SJF调度算法的平均等待时间、平均周转时间最少。
优先级调度算法
优先级调度算法又称优先权调度算法,该算法既可以用于作业调度,也可以用于进程调度,该算法中的优先级用于描述作业运行的紧迫程度。
在作业调度中,优先级调度算法每次从后备作业队列中选择优先级最�{的一个或几个作业,将它们调入内存,分配必要的资源,创建进程并放入就绪队列。在进程调度中,优先级调度算法每次从就绪队列中选择优先级***的进程,将处理机分配给它,使之投入运行。
根据新的更高优先级进程能否抢占正在执行的进程,可将该调度算法分为:
- 非剥夺式优先级调度算法。当某一个进程正在处理机上运行时,即使有某个更为重要或紧迫的进程进入就绪队列,仍然让正在运行的进程继续运行,直到由于其自身的原因而主动让出处理机时(任务完成或等待事件),才把处理机分配给更为重要或紧迫的进程。
- 剥夺式优先级调度算法。当一个进程正在处理机上运行时,若有某个更为重要或紧迫的进程进入就绪队列,则立即暂停正在运行的进程,将处理机分配给更重要或紧迫的进程。
而根据进程创建后其优先级是否可以改变,可以将进程优先级分为以下两种:
- 静态优先级。优先级是在创建进程时确定的,且在进程的整个运行期间保持不变。确定静态优先级的主要依据有进程类型、进程对资源的要求、用户要求。
- 动态优先级。在进程运行过程中,根据进程情况的变化动态调整优先级。动态调整优先级的主要依据为进程占有CPU时间的长短、就绪进程等待CPU时间的长短。
高响应比优先调度算法
高响应比优先调度算法主要用于作业调度,该算法是对FCFS调度算法和SJF调度算法的一种综合平衡,同时考虑每个作业的等待时间和估计的运行时间。在每次进行作业调度时,先计算后备作业队列中每个作业的响应比,从中选出响应比***的作业投入运行。
响应比的变化规律可描述为:
根据公式可知:
- 当作业的等待时间相同时,则要求服务时间越短,其响应比越高,有利于短作业。
- 当要求服务时间相同时,作业的响应比由其等待时间决定,等待时间越长,其响应比越高,因而它实现的是先来先服务。
- 对于长作业,作业的响应比可以随等待时间的增加而提高,当其等待时间足够长时,其响应比便可升到很高,从而也可获得处理机。克服了饥饿状态,兼顾了长作业。
时间片轮转调度算法
时间片轮转调度算法主要适用于分时系统。在这种算法中,系统将所有就绪进程按到达时间的先后次序排成一个队列,进程调度程序总是选择就绪队列中***个进程执行,即先来先服务的原则,但仅能运行一个时间片,如100ms。在使用完一个时间片后,即使进程并未完成其运行,它也必须释放出(被剥夺)处理机给下一个就绪的进程,而被剥夺的进程返回到就绪队列的末尾重新排队,等候再次运行。
在时间片轮转调度算法中,时间片的大小对系统性能的影响很大。如果时间片足够大,以至于所有进程都能在一个时间片内执行完毕,则时间片轮转调度算法就退化为先来先服务调度算法。如果时间片很小,那么处理机将在进程间过于频繁切换,使处理机的开销增大,而真正用于运行用户进程的时间将减少。因此时间片的大小应选择适当。
时间片的长短通常由以下因素确定:系统的响应时间、就绪队列中的进程数目和系统的处理能力。
多级反馈队列调度算法(集合了前几种算法的优点)
多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合和发展,如图2-5 所示。通过动态调整进程优先级和时间片大小,多级反馈队列调度算法可以兼顾多方面的系统目标。例如,为提高系统吞吐量和缩短平均周转时间而照顾短进程;为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程;同时,也不必事先估计进程的执行时间。
图2-5 多级反馈队列调度算法
多级反馈队列调度算法的实现思想如下:
1.应设置多个就绪队列,并为各个队列赋予不同的优先级,第1级队列的优先级***,第2级队列次之,其余队列的优先级逐次降低。
2.赋予各个队列中进程执行时间片的大小也各不相同,在优先级越高的队列中,每个进程的运行时间片就越小。例如,第2级队列的时间片要比第1级队列的时间片长一倍, ……第i+1级队列的时间片要比第i级队列的时间片长一倍。
3.当一个新进程进入内存后,首先将它放入第1级队列的末尾,按FCFS原则排队等待调度。当轮到该进程执行时,如它能在该时间片内完成,便可准备撤离系统;如果它在一个时间片结束时尚未完成,调度程序便将该进程转入第2级队列的末尾,再同样地按FCFS 原则等待调度执行;如果它在第2级队列中运行一个时间片后仍未完成,再以同样的方法放入第3级队列……如此下去,当一个长进程从第1级队列依次降到第 n 级队列后,在第 n 级队列中便�用时间片轮转的方式运行。
4.仅当第1级队列为空时,调度程序才调度第2级队列中的进程运行;仅当第1 ~ (i-1)级队列均为空时,才会调度第i级队列中的进程运行。如果处理机正在执行第i级队列中的某进程时,又有新进程进入优先级较高的队列(第 1 ~ (i-1)中的任何一个队列),则此时新进程将抢占正在运行进程的处理机,即由调度程序把正在运行的进程放回到第i级队列的末尾,把处理机分配给新到的更高优先级的进程。
多级反馈队列的优势有:
- 终端型作业用户:短作业优先。
- 短批处理作业用户:周转时间较短。
- 长批处理作业用户:经过前面几个队列得到部分执行,不会长期得不到处理。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
终止服务,Windows7能成就下一个XP神话吗?
【大咖・来了 第7期】10月24日晚8点观看《智能导购对话机器人实践》 前段时间,微软官方发布公告,将于2020年1月14日正式终止对Windows 7操作系统的技术支持。 Windows 7系统作为Windows Vista的继任者,于2009年10月22日正式发售。得益于较低的系统配置要求和微软的全力支持,Windows 7鼎盛时期市场份额一度高达60%,根据Netmarketshare统计截止2018年12月,Windows 7市场份额仍旧高达36.9%。 此前微软耗费大量资源推广Windows 7,试图全面取代老当益壮的Windows XP系统。但如今,Windows 7的情景和当初Windows XP有太多相似之处,Windows 7让用户忘掉了XP,但随着Windows 8/10的推出,Windows 7又成为用户升级到Windows 10系统***的阻碍。 截至2016年,已经诞生十五年Windows XP仍旧占据10.9%的市场份额,位列世界上第三大操作系统。此次微软宣布终止对Windows 7的技术支持,在民间爱好者眼中,Windows 7会成为下一个老当益壮的Win...
- 下一篇
以Rust编写的类Unix操作系统Redox OS发布0.5版
【大咖・来了 第7期】10月24日晚8点观看《智能导购对话机器人实践》 Redox OS 是一个几乎完全以 Rust 语言编写的通用操作系统及周围生态(例如文件系统、显示服务器及 Rust 版本的 libc)。其遵循微内核架构,在一定程度上兼容于 POSIX。该项目于日前发布了 Redox 0.5 版本。自上次发布 Redox OS 以来已经过去了一年零四天。在此期间,Redox 团队一直在努力改善 Redox 生态系统。 大部分努力集中于relibc,这是一个用 Rust 编写并由 Redox OS 项目维护的新 C 库;此外,cookbook添加了新的软件包。 现在,relibc 的能力已经超过了 Redox 此前依赖的 C 库newlib。这一版本新增了许多重要的库和程序。 粗略看来,此版本 ISO 镜像与上一个正式发布的版本 0.3.5 无甚区别——拥有相同的登录屏幕以及相同的默认背景和应用程序。但这本身就是一项成就。因为关于 relibc 的工作很密集,几乎触及了系统的每个部分。 一旦深入了解,就会发现变化明显。事件系统经过重新设计,为 select 和 poll 提供了正确...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- 设置Eclipse缩进为4个空格,增强代码规范
- CentOS8安装Docker,最新的服务器搭配容器使用
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS8编译安装MySQL8.0.19
- SpringBoot2整合Redis,开启缓存,提高访问速度
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- Hadoop3单机部署,实现最简伪集群
- CentOS7,CentOS8安装Elasticsearch6.8.6