操作系统第四篇【处理机调度】

处理机调度基本概念

在处理机调度上可以分为三个层次,级别从低到高

  • 哪些资源分给CPU(低)
  • 选择哪些进程到外存中(中)
  • 哪些作业放入内存(高)

处理机的调度实际上就是用不同的算法来将我们的作业合理分配,提高CPU的利用率。达到公平性、平衡性。

先来先服务算法FCFS

按照作业提交或进程变为就绪状态的先后次序,分派CPU; 当前作业或进程占用CPU,直到执行完或阻塞,才出让CPU(非抢占方式)。 在作业或进程唤醒后(如I/O完成),并不立即恢复执行,通常等到当前作业或进程出让CPU。是最简单的算法。

谁先来,就谁先执行

短进程/作业优先算法SJF

短进程优先调度算法(Shortest Process First, SPF),是指对短进程优先的算法。利用该算法,可以从就绪队列中选择一个估计运行时间最短的进程,并为之分配CPU,使其立即执行直到完成,或者在运行期间由于发生IO事件使该进程阻塞,并让出CPU,重新发生进程调度。 短作业优先调度算法SJF(Shortest Job First),是指对短作业优先调度的算法。利用该算法,可以从后备队列中选择若干估计运行最短的作业,投入内存运行

谁用的时间少、就先执行谁

1)优点

  • 1)比FCFS改善平均周转时间和平均带权周转时间,缩短作业的等待时间;假定所有任务同时到达,平均等待时间最短。
  • 2)提高系统的吞吐量

2)缺点

  • 1)对长作业非常不利,可能长时间得不到执行;长作业可能被饿死。
  • 2)未能依据作业的紧迫程度来划分执行的优先级
  • 3)难以准确估计作业(进程)的执行时间,从而影响调度性能

最高响应比优先算法HRN

最高响应比优先法(Highest Response_ratio Next,HRN)是对FCFS方式和SJF方式的一种综合平衡

FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短,而SJF方式只考虑执行时间而未考虑等待时间的长短。 因此,这两种调度算法在某些极端情况下会带来某些不便。 HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短,从中选出响应比最高的作业投入执行。

是SJF和FCFS的综合平衡,其公式是这样子的:

这里写图片描述

(1)优点

  • 1)同时到达任务,短者优先。等待时间相等时,服务时间越短,优先级越高,符合SJF思想。
  • 2)长作业随等待时间增加响应比增加。服务时间相等时,等待时间越长,优先级越高。对于长作业,只要其等待时间足够长,也能获得处理机。

(2)缺点

  • 1)吞吐量降低。这种算法是介于FCFS和SJF之间的一种折中算法。由于长作业也有机会投入运行,在同一时间内处理的作业数显然要少于SJF法,从而采用HRN方式时其吞吐量将小于采用SJF法时的吞吐量。
  • 2)系统开销增加。原因在于每次调度前要计算响应比。

最高优先数算法

在进程调度中,每次调度时,系统把处理机分配给就绪队列中优先数最高的进程。它又分为两种:非抢占式优先数算法和抢占式优先数算法。

  • 在非抢占式优先数算法下,系统一旦把处理机分配给就绪队列中优先数最高的进程后,这个进程就会一直运行,直到完成或发生某事件使它放弃处理机,这时系统才能重新将处理机分配给就绪队列中的另一个优先数最高的进程。
  • 在抢占式优先数算法下,系统先将处理机分配给就绪队列中优先数最高的进程度让它运行,但在运行的过程中,如果出现另一个优先数比它高的进程,它就要立即停止,并将处理机分配给新的高优先数进程。
  • 在抢占式优先数算法下会麻烦一些。

基于时间片的轮转调度算法

轮转(Round Robin,RR)调度算法是让每个进程在就绪队列中的等待时间与享受服务的时间成正比例。该算法适用于分时系统

  • 每个进程所享受的CPU处理时间都是一致的

过程:

1)将系统中所有的就绪进程按照FCFS原则,排成一个队列。 2)每次调度时将CPU分派给队首进程,让其执行一个时间片。时间片的长度从几个ms到几百ms。 3)在一个时间片结束时,发生时钟中断。 4)调度程序据此暂停当前进程的执行,将其送到就绪队列的末尾,并通过上下文切换执行当前的队首进程。 5)进程可以未使用完一个时间片,就出让CPU,如进程阻塞时。

最短剩余时间优先算法

最短剩余时间优先(Shortest Remaining Time Next,SRTN)调度算法多用于剥夺式的调度中。 在进程调度中,每次调度时,系统把处理机分配给就绪队列中运行完所需时间最短的进程。 最短剩余时间优先算法也可用于不剥夺式调度方式中,此时退化为短作业优先算法

也就是短作业优先算法的升级版,只不过它是抢占式的。

多级反馈排队算法

  • 1)设置多个就绪队列,分别赋予不同的优先级,如逐级降低,队列1的优先级最高。每个队列执行时间片的长度也不同,规定优先级越低则时间片越长,如逐级加倍。
  • 2)新进程进入内存后,先投入队列1的末尾,按FCFS算法调度;若按队列1一个时间片未能执行完,则降低投入到队列2的末尾,同样按FCFS算法调度;如此下去,降低到最后的队列,则按“时间片轮转”算法调度直到完成。
  • 3)仅当较高优先级的队列为空,才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列,则抢先执行新进程,并把被抢先的进程投入原队列的末尾。

选择调度方式和调度算法的准则

这里写图片描述

原文发布于微信公众号 - Java3y(java3y)

原文发表时间:2018-04-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Spark学习技巧

Spark2.4.0发布了!

http://spark.apache.org/releases/spark-release-2-4-0.html

1661
来自专栏知识分享

STM32采集电阻触摸贴膜

公司的项目用电阻屏,触摸的时候发现获取的位置会漂,后来自己发现是由于压力的问题....如果亲们用电阻屏发现触摸的位置有问题,可以看一下这篇文章,,先测量触摸的压...

2986
来自专栏北京马哥教育

浅谈TCP优化

很多人常常对TCP优化有一种雾里看花的感觉,实际上只要理解了TCP的运行方式就能掀开它的神秘面纱。Ilya Grigorik 在「High Performanc...

4715
来自专栏安富莱嵌入式技术分享

【安富莱原创开源应用第3期】花式玩转网络摄像头之VNC远程桌面版本,稳定运行2年不死机

1、前段时间开源了一个网络摄像头的TCP版本 https://www.cnblogs.com/armfly/p/9173167.html,这次再来一个远程VNC...

1112
来自专栏企鹅号快讯

分布式TensorFlow入坑指南:从实例到代码带你玩转多机器深度学习

AI UNION 人工智能产业技术创新战略联盟 这里是人工智能联盟,汇聚了最新的AI新闻资讯,还有最前沿的国内外AI开源技术,最具价值的AI创新企业,最具权威的...

2057
来自专栏涂小刚的专栏

Spark Cache 性能测试

此测试的目的在于评判各种Cache IO的性能,测试中采用Spark自带的Kmeans算法作为测试基准(Spark版本为2.1),该算法Shuffle数据量较小...

1.1K0
来自专栏州的先生

重新开始一个完整的Django Restful WEB项目

在前面7章中,我们首先编写了一个简单的电影爬虫,采集了猫眼电影的部分电影数据,再通过Django框架的2.0版本创建了一个Python WEB应用,并且借助于d...

1371
来自专栏晨星先生的自留地

大数据比赛的一个小心得

3415
来自专栏安恒信息

LOCKY勒索者新花样:通过PDF投递

摘 要 最近安恒APT团队截获一个新版的LOCKY勒索者病毒样本,区别之前大多数样本采用WORD文档投递并用宏代码远程下载执行的方式,该样本在原有的WORD文档...

2796
来自专栏精讲JAVA

key / value 数据库的选型

这个项目有很多 key/value 数据(约 100 GB)需要使用,使用时基本是只读的,偶尔更新时才会批量导入,且可以忍受短暂的停机导入。我一想 TiKV 和...

2793

扫码关注云+社区