操作系统第四处理机调度

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,操作系统第四处理机调度,图,4.1,作业的状态,与,其转换,2,第四章 处理机调度,4.1.1,作业的状态,与,转换,作业一般都要经历提交、收容、执行和完成等,4,个状态。,提交,收容,完成,用户,作业录入,作业调度,作业调度,执行,就绪,等待,运行,进程调度,3,4.1.3 作业和进程的关系,作业是用户需要计算机完成某项任务时要求计算机所作工作的集合。进程是已提交完毕程序的执行过程的描述，是资源分配的根本单位。区别与关系：,(1)作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业之后，系统将它放入外存中的作业等待队列中等待执行。而进程那么是完成用户任务的执行实体，是向系统申请分配资源的根本单位。任一进程，只要它被创立，总有相应的局部存在于内存中。,4,(2)一个作业可由多个进程组成。且必须至少由一个进程组成，但反过来不成立。,(3)作业的概念主要用在批处理系统中。而进程的概念那么用在几乎所有的多道系统中。,5,作业调度,作业调度的功能,1、通过作业控制块JCB(如图4.2)记录系统中各作业的情况。,2、从后备队列中选出一个或几个作业进入内存。,3、为选中的作业做好执行前的准备工作，如分配必要的资源并建立相应的进程。,4、作业执行完毕后做好善后工作，如收回资源、撤销作业控制块等。,6,图,4.3,作业调度中状态的转换过程,7,4.2.2,作业调度目标与性能衡量,这里先介绍调度目标。,一般来说，调度目标主要是以下,4,点：,(1),对所有作业应该是公平合理的；,(2),应使设备有高的利用率；,(3),每天执行尽可能多的作业；,(4),有快的,响应时间,。,由于这些目标的,相互冲突,，任一调度算法要想同时满足上述目标是不可能的。,8,1.周转时间：,作业i的周转时间Ti为,Ti=Tei-Tsi,其中Tei为作业i的完成时间，Tsi为作业的提交时间。,对于被测定作业流所含有的nn=1个作业来说，其平均周转时间为：,一个作业的周转时间说明了该作业在系统内停留的时间，包含两局部：等待时间；执行时间，即：,Ti=TwiTri,这里，Twi主要指作业i由后备状态到执行状态的等待时间，它不包括作业进入执行状态后的等待时间。,9,2.带权周转时间,作业的周转时间包含了两个局部，即等待时间和执行时间。为了更进一步反映调度性能，使用带权周转时间的概念。带权周转时间是作业周转时间与作业执行时间的比：,Wi=Ti/Tri,对于被测定作业流所含有的几个作业来说，其平均带权周转时间为：,对于分时系统，除了要保证系统吞吐量大、资源利用率高之外，还应保证有用户能够容忍的响应时间。因此，在分时系统中，仅仅用周转时间或带权周转时间来衡量调度性能是不够的。,10,3.响应时间,响应时间是用户从提交一个请求开场直到在屏幕上显示出结果或显示正在处理的提示信息为止的这段时间间隔。,不同场合对响应时间的要求,分时系统和实时信息处理系统类似，响应时间都以人所能承受的等待时间来确定，通常是35秒钟，否那么分时系统的用户就没有独占计算机的感觉，实时信息处理系统的终端用户就没有与时处理的感觉。,对实时控制系统，响应时间要求有很大的差异，它是以控制对象所要求的开场截止时间或完成截止时间来确定，一般为秒级、毫秒级、甚至有的要低于100微秒。,11,(4.4)作业调度算法,1、先来先效劳,2、短作业优先,3、小作业优先,4、响应比高者优先,作业等待时间+估计运行时间,估计运行时间,响应比,=,12,4.3 进程调度,进程调度的功能,1、由PCB记录系统中进程的执行情况。,2、选择占有处理机的进程。,3、进展进程上下文切换。,上下文切换:,进程调度是由进程调度程序实现的，它的主要任务是：,1)保护离开CPU的那个进程的现场。,2)按照一定的算法，从就绪进程中选一个进程，准备把CPU分配给它。,3)恢复选中进程的现场。,13,何时调度,每当CPU有空的时候，就要重新调度。CPU有空是指：,1、正在执行的进程正常完毕。,2、执行中的进程因阻塞原语而阻塞。,3、执行中的进程调用了P操作。,4、执行中的进程提出IO请求。,5、分时系统中时间片用完。,6、执行完系统调用。,7、就绪队列中的进程优先级发生变化。,14,4.3.3 进程调度性能评价,进程调度虽然是系统内部的低级调度，但进程调度的优劣直接影响作业调度的性能。,进程调度性能的衡量方法可分为定性和定量两种。,在定性衡量方面:调度的可靠性、简洁性,进程调度的定量评价：类似作业高度评价,CPU的利用率评价,进程在就绪队列中的等待时间与执行时间之比等。,一般情况下，大多利用模拟或测试系统响应时间的方法来评价进程调度的性能。,15,4.4 进程调度算法,1、先来先效劳,实现方法,系统只要有按FIFO规那么建立的后备作业队列或就绪进程队列即可，就是一个作业控制块JCB或进程控制块PCB参加队列时加在相应队列末尾。,调度退出队列时从相应队列首开场顺序扫描，将相关的JCB或PCB调度移出相应队列。,16,调度例子,假设在一个多道程序系统中，有用户区空间100KB，并规定作业相应程序装入内存连续区域，并不能被移动，作业调度和进程调度均采用FCFS算法。现有5个作业，它们的作业名、进入输入井的时间、需要计算时间以与内存量要求如表5_1所示，并假设输入井中有作业进展调度。,17,作业名,进入“输入井”时间,需计算时间（分）,需内存量（,KB,）,A,8,：,06,42,15,B,8,：,18,30,60,C,8,：,30,24,50,D,8,：,36,24,10,E,8,：,42,12,20,按照调度算法调度的次序是,:,，,.,18,作业名,装入内存时间,开始执行时间,结束执行时间,周转时间,带权周转时间,A,8,：,06,8,：,06,8,：,48,42,42/42,B,8,：,18,8,：,48,9,：,18,60,60/30,C,8,：,36,9,：,18,9,：,42,66,66/24,D,9,：,18,9,：,42,10,：,06,96,96/24,E,9,：,18,10,：,06,10,：,18,96,96/12,5,个作业的平均周转时间,T,和平均带权周转时间,W,如下：,T,(42+60+66+96+96)/5=72(,分钟,),W,19,优缺点,FCFS调度算法具有一定的公平性，并且实现也比较容易，这是它的优点。但是，它的缺点是实际上不公平，它比较有利于长作业长进程，而不利于短作业短进程。因为当计算时间很长的作业先进入输入井被选中装入内存运行时，就可能使那些计算时间短的后进入输入井的作业等待很长时间，而且使计算时间短的作业周转时间变长，从而使作业的平均周转时间也变长，降低了系统的吞吐能力。,20,2、短作业短进程优先调度算法,短作业优先调度算法SJF，是指对执行时间短的作业优先调度的算法。,的实现方法,该调度算法是从后备作业队列中选择一个或假设干个，估计运行时间最短且当时系统能满足它们资源要求的作业，将它们装入内存运行。,21,作业名,进入“输入井”时间,需计算时间（分）,需内存量（,KB,）,A,8,：,06,42,15,B,8,：,18,30,60,C,8,：,30,24,50,D,8,：,36,24,10,E,8,：,42,12,20,按照,SJF,调度算法调度的次序是,:,A B D E C,22,作业名,装入内存时间,开始执行时间,结束执行时间,周转时间,带权周转时间,A,8,：,06,8,：,06,8,：,48,42,42/42,B,8,：,18,8,：,48,9,：,18,60,60/30,D,8,：,36,9,：,18,9,：,42,66,66/24,E,9,：,18,9,：,42,9,：,54,72,72/12,C,9,：,18,9,：,54,10,：,18,108,108/24,平均周转时间T和平均带权周转时间W如下：分钟W=(1+2+11/4+6+9/2)/5=3.25,23,3、优先级法,系统或用户按某种原那么为进程执行一个优先级别，反响进程需要CPU轻重缓急的程度。,1)静态优先级,优先级一旦确定，就不再改变。,2)动态优先级,根据需要改变动态优先级。,占用,CPU,时间增加,优先级降低,等待,CPU,时间增加,优先级升高,24,作业名,进入输入井时间,需要计算时间（分钟）,优先级（数大级高）,A,8,：,00,60,1,B,8,：,30,50,2,C,8,：,40,30,4,D,8,：,50,10,3,25,作业名,输入时间,运行时间（分）,开始执行时间,结束执行时间,周转时间（分）,带权周转时间,A,8,：,00,60,8,：,00,9,：,00,60,60/60,C,8,：,40,30,9,：,00,9,：,30,50,50/30,D,8,：,50,10,9,：,30,9,：,40,50,50/10,B,8,：,30,50,9,：,40,10,：,30,120,120/50,平均周转时间T和平均带权周转时间W为：T=(60+50+50+120)/4=70分钟,26,4、时间片轮转法,让每个进程在就绪队列中的等待时间与享受效劳的时间成比例.,F,C,B,A,CPU,完成,轮转法调度,27,4,时间片轮转调度算法,调度算法(如图4.4),进程就绪队列往往按进程到达时间的先后排列。进程调度程序总是把处理机分配给队首进程，并规定其执行一段时间，即一个时间片。,当进程执行完该时间片时，由一个计时器发出时钟中断，调度程序便根据此中断信号停顿该进程的执行，并将它送入就绪队列末尾；然后，把处理机分配给就绪进程队列中新的队首进程一个时间片。,28,优点,这种调度算法可以保证就绪队列中的所有进程，在一给定的时间内，都能获得在处理机上执行一个时间片的时间。,时间片大小的选择,如果时间片过大，可使时间片轮转调度算法已退化为FCFS调度算法，因而无法获得令用户满意的响应时间。,如果时间片取得太小，其处理机调度开销将会变得很大，而处理机实际用于运行用户程序的时间比例将会变小。,29,5 多级反响队列调度算法,多级反响队列调度算法，是一种考虑较全面灵活的调度算法，它不必事先知道各作业所需执行时间，且它可以满足各种类型进程的需要，因此它是目前公认较好的一种进程调度算法。,多级反响队列调度法:设置多条就绪队列,进程被调度执行后,在被剥夺或放弃处理机后而在就绪时，可以改变其就绪队列(见以下图。,30,第一级队列,(FIFO),使用处理机,完成,使用处理机,完成,使用处理机,完成,抢占,抢占,抢占,第二级队列,(FIFO),第,n,级队列,（时间片轮转）,31,调度算法的实施过程,设置多级就绪队列。系统中有多个就绪进程队列，每个就绪队列对应一个调度级别，各级具有不同的优先级。第1级队列的优先级最高，第2级队列优先级次之，其余级队列的优先级随级增大而降低。,各级就绪队列具有不同大小的时间片。优先级最高的第1级队列中进程的时间片最小，随着队列的级数增大其中进程的优先级降低，但时间片却增大。,32,一个新进程在系统就绪队列中排队的规那