四章处理机调度.ppt
《四章处理机调度.ppt》由会员分享,可在线阅读,更多相关《四章处理机调度.ppt(49页珍藏版)》请在三一办公上搜索。
1、第四章 处理机调度,4.1 作业的概念及其状态4.2 作业调度4.3 进程调度4.4 调度算法,4.1.1 作业与作业步,作业:就是要求计算机给以计算(或处理)的一个相对独立的任务.也是一个相对独立的计算任务在计算机上的执行过程,作业步:是一个作业在执行过程中,从逻辑上可以细分成一个一个 顺序处理的基本单位.这个基本单位称为作业步.,典型的作业控制过程:“编译”、“连接装配”、“运行”。,4.1 作业的概念及其状态,.典型的作业步,在作业执行过程中,各个作业之间联系密切,上一作业步的执行结果作为下一步的执行前提。,作业、作业步与进程之间的关系,用户,作业,作业,作业步,作业步,.,作业,进程,
2、进程,.,4.1.2 作业控制方式,作业的类型与组织形式,脱机作业:,是指用户不能和计算机直接交互需要通过操作员从中干预的作业,联机作业:,是用户通过外围设备直接与计算机系统进行交互,并且控制作业的运行,这种作业也叫交互型作业。,联机作业多出现在分时系统中,而脱机作业经常出现在批处理系统中。,作业的组成:,程序、数据和作业说明书,作业说明书:,作业基本情况描述作业控制描述作业资源要求描述,作业说明书是用户用作业控制语言编写的。,4.1.3 作业的状态,作业在整个活动期间经历的四种状态是:,提交状态:把一个作业输入到计算机中的一个过程。后备状态:作业在磁盘上的后备队列中所处的状态。执行状态:把处
3、于后备状态的作业调入内存的状态。完成状态:一个作业的主进程执行结果时所处的状态。,提交状态,后备状态,完成状态,运行状态,运行,就绪,等待,作业调度,Spooling,作业的状态及转换,4.1.4 作业控制块(JCB),作业控制块(JCB:Job Control Block)用以标识作业的存在,记录了与该作业有关的信息,其具 体内容根据作业调度的要求而定。对于不同的系统,JCB 的内容有所不同。,作业控制块,占用CPU的时间,作业提交之后,有一定的调度策略,总得在一定的时间内完成。,程序执行时需要,为作业调度提供一定的调度依据,脱机还是联机的,长作业还是短作业I/O型还是计算型,和资源要求配合
4、使用,作业调度对一个作业而言只使用一次进程调度对一个进程而言可能使用多次。,注意:,4.2.1 作业调度的功能,4.2 作业调度,作业调度:作业管理程序按一定策略从后备作业中挑选一个作业,把它装入内存并且为它们分配必要的资源,并为作业创 建一个主进程以便它能够执行。,作业调度的功能:,通过调度算法从后备队列中挑选一个作业投入运行为选中的作业做好运行前的准备工作。在作业结束时做好善后工作(回收资源),作业调度的作用:,完成作业从后备状态到执行状态和从执行态到完成状态的转换,作业从后备态到执行状态,算法1:,BEGIN 从后备队列中选出一个作业;While(资源要求不满足)放弃该作业;If(后备作
5、业队列为空)EXIT 按调度算法从后备队列中挑出一个作业;调用存储管理,设备管理程序看是否满足资源要求;分配资源;调用进程管理程序建立进程;进程调度;END,作业从执行状态到完成状态,算法2:,BEGIN 回收分给该作业各个进程的全部资源;计算该作业的执行时间;撤销所有进程及作业的JCB;转入调用下一个作业;END,4.2.2 衡量调度性能的指标,1、调度算法应达到的目标,每次运行尽可能多的作业让处理机保持忙碌状态使输入输出设备得以充分利用对所有的作业公平合理,吞吐量,利用率问题,公平性原则,2、确定调度算法时应考虑的因素,调度算法应与系统的总体设计目标一致注意系统资源的均衡使用,使输入输出繁
6、忙的作业与CPU繁忙的作业搭配运行应保证进入系统的作业在规定的截至时间内运行结束,3、调度算法性能的衡量,批处理系统中衡量作业调度算法性能的两个指标:,平均周转时间和平均带权周转时间,(1)周转时间:,i作业的周转时间定义为:,Ti=Tsi-Tti,其中:Tsi为i作业完成时间,Tti为作业的提交时间。,平均周转时间:,T=,1,n,i=1,n,Ti,一个作业的周转时间可分为2部分:,(1)等待时间(从后备态到执行态);(2)执行时间,可以表示为:,Ti=Twi+Tri,(2)带权周转时间:,i=,其中:Ti是作业周转时间,Tri是作业执行时间,Ti,Tri,平均带权周转时间:,n,i=1,1
7、,n,W=,i,4.2.3 作业调度算法,1、先来先服务调度算法:,严格按照作业先来后到的次序进行调度。,例:,有四个作业,它们的提交、执行时间如下,2、短作业优先调度算法:,选取执行时间最短的作业作为下次服务的对象,例:,有四个作业,它们的提交、执行时间如下,3、响应比高者优先调度算法:,介于(FCFS)和短作业优先调度算法(SJF)之间的算法,是对二者的折中,响应比=,(等待时间+执行时间),执行时间,=,1+,等待时间,执行时间,例:,有四个作业,它们的提交、执行时间下表,如采用响应比高者优先调度算法(HRN)来计算平均周转时间和平均带权周转时间(其中时间单位为小时,按十进制计算.,r2
8、=1+(10.0-8.3)/0.5=4.4,r3=1+(10.0-8.5)/0.1=16,r4=1+(10.0-9.0)/0.4=3.75,此时,各作业的响应比为:,r2=1+(10.1-8.3)/0.5=4.6,r4=1+(10.1-9.0)/0.4=3.75,此时,各作业的响应比为:,r4=1+(10.6-9.0)/0.4=5,此时,各作业的响应比为:,平均周转时间为(2.0+1.6+2.3+2.0)/5=1.975,4、优先数调度算法:,可以综合考虑有关因素,如作业缓急程序,作业长短,等待时间的长短,外部设备,使用情况等,并根据系统设计目标分析这些因素的重要程度,按比例确定各作业的优先数
9、,系统按优先数高来调度作业.,例:,在后备作业队列中等待运行的同时有3个作业1、2、3,已知它们的各自运行时间为a、b、c,且a b c.,证明:采用短作业优先调度算法能获得最小平均周转时间,证明:采用短作业优先调度算法,因此作业执行顺序为:123。作业1执 行时间为a,等待时间为0.作业2执行时间为b,等待时间为a.作业3执 行时间为c,等待时间为(a+b).因此:3个作业总的周转时间 T1=(a+(a+b)+(a+b+c)=3a+2b+c,不失一般性,假设调度顺序为213,则其总的周转时间为 T2=b+(b+a)+(b+a+c)=3b+2a+c,T2-T1=(3b+2a+c)-(3a+2b
10、+c)=(b-a)0,例:,有一个具有2道作业的批处理系统,作业调度采用短作业优先的调度算法,进程调度采用高优先级优先的抢占式调度算法。在下表所示的作业序列作业优先数即为进程优先数,优先数越小,优先级越高。,列出所有作业进入内存时间及结束时间计算平均周转时间,各作业的周转时间为:,作业A:20(执行)30(内存内等待)20(执行)70作业B:30(执行)作业C:20(内存外等待B执行)20(内存外等待A执行)50(执行)90作业D:20(内存为等待A执行)50(内存内等待C执行)20(执行)90,作业的平均周转时间为:(70309090)/470(分钟),例:,在某多道程序系统中,供用户使用的



- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 处理机 调度

链接地址:https://www.31ppt.com/p-5378334.html