《操作系统》3处理机管理

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第3章 处理机管理,本章目录,3.1 处理机调度概述,3.1.1 处理机调度的三个层次,3.1.2 进程调度的功能、时机和基本策略,3.2 作业调度算法,3.2.1 先来先服务调度算法,3.2.2 短作业优先调度算法,3.5.3 Linux的进程调度算法,3.2.3 最短剩余时间优先调度算法,3.1.3 调度算法的性能评价指标,3.4 实时处理与实时调度算法,3.4.1 实时处理的特征,3.4.2 最早截止时间优先调度算法,3.4.3 速率单调调度算法,3.5 Linux的处理机调度,3.5.1 涉及调度的进程分类,3.5.2 Linux的可运行队列,3.2.4 最高响应比调度算法,3.3 进程调度算法,3.3.1 先来先服务调度算法,3.3.2 轮转调度算法,3.3.3 优先级调度算法,3.3.4 多级队列调度算法,3.3.5 多级反馈队列调度算法,3.1,处理机调度概述,3.1.1 处理机调度的三个层次,高级调度,1.,当系统决定接纳一个作业时，就要为它开辟一个作业控制块（JCB），以便随时记录作业的信息。,.,.,被系统接纳的作业，在没有投入运行前是以“后备作业”的形式存放在辅存里。所有后备作业的JCB链接在一起，形成“后备作业队列”。这些作业没有资格参与对处理机的竞争，但系统从它们的里面去挑选参与CPU竞争的作业。,.,高级调度决定哪个后备作业可进入系统去接受处理，它控制着多道程序设计环境的“度”：进到系统的作业多，资源的利用率提高了，但每个作业获得处理结果的时间可能会长；进到系统的作业少，每个作业很快就得到自己的处理结果，但资源的利用率可能会下降。,低级调度,2.,.,低级调度真正决定CPU下一次执行哪一个进程，它将按照一定的算法，从就绪队列里挑选出可运行的进程投入运行。低级调度的各种算法，是我们讨论的主要目标。低级调度也被称为“进程调度”。,中级调度,3.,.,中级调度是介于高级调度和低级调度之间的一种调度，如果系统为进程设置有“挂起”状态，那么就会涉及到中级调度。也就是说，中级调度与实施进程的内、外存交换有关。,CPU,就绪队列,低级调度,释放,中级调度,就绪/挂起队列,时间片到,高级调度,阻塞/挂起队列,阻塞队列,中级调度,事件等待,事,件,发,生,交互用户,作业,后备作业队列,.,系统中出现过高并发度时，就应将内存中的某些进程暂时换出,到外存；系统的并发,度较低时，就应该将,外存中的某些进程换,入到内存。进程在内、外存,间的换出和换入，就是中级调度承担的责任，通过这种交换，以求达到调节和平衡系统“并发度”的目的。,.,高级调度执行的频繁程度很低，它,只是粗略地决定是否接受一个新进程以,及接受哪一个；中级调度为了实施交换,决策，执行的频率相对要频繁一些；低,级调度要精确地决定执行哪一个进程，因此执行的频度为最高。,返回目录,3.1.2 进程调度的功能、时机和基本策略,1.,进程调度程序的功能,.,保护现场,.,挑选运行对象,.,恢复现场,2.,发生进程调度的时机,当某进程正常完成自己的运行或被终止时，为不让CPU空闲，必须实行调度，以便从就绪队列里挑选新的进程投入运行。,.,.,分时系统中，时钟中断处理程序发现分配给某个进程的时间片用完时，就强制它交出CPU，重新进行CPU调度。,.,运行中的进程提出I/O请求，或要等待别的进程发来消息，于是自己被阻塞。,.,执行操作系统提供的某些系统调用命令，如wait()等。,.,某进程的状态从阻塞变为就绪时，要由调度程序决定让哪一个进程投入运行：是新就绪进程、是正在运行的进程继续运行、还是调度另一个进程运行。,3.,进程调度的基本策略,非抢占式：在把CPU分配给某个进程后，就一直让它使用下去，直到进程完成自己的工作，或因要等待某事件的发生而交出CPU，否则不允许其他进程夺取CPU。,.,.,抢占式：在调度程序把CPU分配给某进程使用后，只要满足某条件，就允许立即把CPU从运行进程手中夺取过来，分配给满足条件的进程使用。,返回目录,特定作业从提交给系统到获取结果所经历的时间间隔。因此，设作业,i,向系统提交的时间为T,pi,，完成时间是,T,ci,，那么它的周转时间,T,i,为：,T,i,=,T,ci,-,T,pi,。,3.1.3 调度算法的性能评价指标,1.,2.,吞吐量,周转时间,所谓“吞吐量”，是指单位时间内,CPU,完成作业的数量。,.,有的作业属于“处理机限制”型的，即需要花费大量的,CPU,时间，很少输入/输出，也称“,CPU,繁忙”型；有的属于“,I/O,限制”型的，即它在运行期间主要是输入/输出，很少进行计算和处理，也称“,I/O,繁忙”型。,.,.,作业的周转时间,作业的周转时间是指作业的执行时间加上作业的等待时间。设作业,i,的等待时间为,T,wi,，执行时间为,T,si,，那么它的周转时间T,i,为：,T,i,=,T,wi,+,T,si,。,（1）,（2）,.,作业的平均周转时间,n,个作业，每个作业的周转时间为T,i,，那么它们的平均周转时间为：,T,=(,T,i,),i,=,1,n,n,1,利用平均周转时间，可以基于同一批作业，来衡量不同调度算法的调度性能。,.,.,作业的“带权周转时间”，指该作业的周转时间与所需运行时间之比。设作业,i,周转时间为,T,i,，所需执行时间为,R,i,，那么它的带权周转时间,W,i,为：,.,作业的平均带权周转时间,（3）,n,个作业，每个作业的带权周转时间为W,i,，那么它们的平均周转时间为：,.,W=(,),T,i,R,i,1,n,利用平均带权周转时间，可基于同一调度算法，对不同批次作业的调度性能做出比较。,.,.,CPU,的利用率,3.,所谓“,CPU,的利用率”，是指在一定的时间区间内，,CPU,为用户提供服务的时间与其总运行时间的比率。,作业,i,的,CPU,利用率,U,i,，是指该作业的执行时间,C,i,与周转时间,T,i,的比率。即：,.,W,i,=T,i,/R,i,U,i,=C,i,/T,i,.,如果系统内有,n,个作业，那么整个系统,CPU,的平均利用率应为：,U,=(,C,i,/,T,i,),i,=,1,n,n,1,公平性：调度的设计，应该顾及到所有作业或进程对,CPU,的不同需求，尽量做到公平合理，不偏不倚。,设计目标：设计目标是决定算法的主要因素，目标不同，要求肯定不一样。比如批处理系统的调度，应尽量提高各种资源的利用率，以及整个系统的吞吐量；分时系统的调度，应将对用户提出的请求作出回应的速度，控制在用户能够容忍的范围内；实时系统的调度，应保证对所发生的的事件做出及时的响应和处理；如此等等。,响应比,4.,.,所谓作业的“响应比”，是指一个特定作业的周转时间与它所需的执行时间之比。,.,作业,i,的等待时间为,T,wi,，执行时间为,T,si,，那么该作业的响应比,RR,i,是：,RR,i,=(T,wi,+T,si,)/T,si,影响调度算法设计的因素,.,（1）,（2）,（3）,均衡性：调度算法应考虑资源使用的均衡性，使系统中的各种资源都能得到充分地利用。比如，把“处理机限制”和“I/O限制”作业搭配，就有可能收到良好的效果。,（4）,兼顾性：调度算法应既考虑长作业的要求，也考虑短作业的要求；既考虑高优先级进程的要求，也要顾及低优先级进程的利益。只偏袒某一方，所造成的后果有可能是严重的，甚至是无法弥补的。,返回目录,右示三个作业，按1、2、3的顺序提交给系统，采用FCFS调度算法。画出它们的“甘特图”，计算每个作业的周转时间及平均周转时间。（忽略系统调度所需额外的时间开销）,作业1第1个被作业调度程序选中运行，花费24个,CPU时间运行完毕，故周转时间是：T1=24-0=24；作业2等待24个CPU时间后被调度运行，花费3个CPU时间运行完毕，故周转时间是：T2=27-0=27；作业3的周转时间是：T3=30-0=30。这三个作业的平均周转时间为,(24+27+30)/3=27。,3.2.1 先来先服务调度算法,3.2 作业调度算法,先来先服务（FCFS）作业调度算法，基于作业到达后备队列的先后次序以及作业对系统资源的需求，从中挑选进入内存、成为参与CPU竞争的作业对象。有时也称为先进先出（FIFO）作业调度算法。,.,例3-1,：,作业,所需CPU时间,1,2,3,24,3,3,解,：,作业1,作业2,作业3,24,3,3,.,所谓“甘特图”，即是指能够反映作业调度顺序及占用CPU时间的一种进度图。,右示五个作业，采用FCFS 作业和进程调度算法，可供5个作业 使用的内存空间为100KB，需要时按 序分配。作业进入内存后，不许在内 存中移动。计算每个作业的周转时间和平均周转时间。（忽略系统调度时间，作业都没有输入/输出请求）,例3-2,：,作业,所需CPU时间,1,2,3,4,5,10.1,10.3,10.5,10.6,10.7,到达时间,所需内存量,0.7,0.5,0.4,0.4,0.2,15KB,70KB,50KB,20KB,10KB,解,：,.,各作业的周转时间,装入内存时间,完成时间,10.1,10.3,11.3,11.3,10.7,开始运行时间,周转时间,10.8,11.3,11.9,12.3,11.5,0.7,1.0,1.4,1.7,0.8,10.1,10.8,11.5,11.9,10.3,.,作业运行时的内存分配情况,作业,1,(,15KB,),作业,2,(,70KB,),作业,5,(,10KB,),空闲,(,5KB,),到,10.7,时,内存情形,空闲,(,15KB,),作业,2,(,70KB,),作业5(10KB),空闲,(,5KB,),到,10.8,作业,1,完成时内存情形,作业,3,(,50KB,),作业,4,(,20KB,),作业,5,(,10KB,),空闲,(,5KB,),(c),到11.3作业2,完成时内存情形,空闲,(,15KB,),这批作业的调度顺序是：,12534，,系统的平均作业周转时间为：,(0.7+1.0+1.4+1.7+0.8)/5=1.12,.,返回目录,各自的开始运行时间、完成时间、周转时间以及带权周转时间如下所示。,五个作业的调度顺序是ABECD。,有5个作业AE，情况如表所示，按照SJF进行作业调度。计算它们各自的开始运行时间、完成时间、周转时间以及带权周转时间。,短作业优先（SJF）调度算法，总是在作业后备队列里选择要求运行时间最短的、满足其资源需要的作业进入内存，参与对CPU的竞争。,3.2.2,短作业优先调度算法,.,.,.,例3-4,：,作业,所需CPU时间,A,B,C,D,E,0,2,4,6,8,到达时间,3,6,4,5,2,解,：,作业调度的gantt图：,作业A,作业B,作业C,作业E,作业D,3,6,4,2,5,.,开始运行时间,带权周转时间,0,3,11,15,9,完成时间,周转时间,3,7,11,14,3,1,1.17,2.75,2.80,1.50,3,9,15,20,11,返回目录,3.2.3 最短剩余时间优先调度算法,.,最短剩余时间优先（SRTF）作业调度算法，是在调度时从后备作业队列里挑选所需运行时间最短的作业投入运行。运行过程中，若有运行时间更短的作业达到，那么它就抢占CPU，让当前正在运行的作业暂停执行。,例3-5,：,有5个作业AE，情况如表所示，按照SRTF进行作业调度。计算它们的开始运行时间、完成时间、周转时间以及带权周转时间。,作业,所需CPU时间,A,B,C,D,E,0,2,4,6,8,到达时间,3,6,4,5,2,解,：,.,各自的开始运行时间、完成时间、周转时间以及带权周转时间如下所示。,五个作业的调度顺序是：ABCEBD。,.,作业调度的gantt图：,.,开始运行时间,带权周转时间,0,3,4,15,8,完成时间,周转时间,3,13,4,14,2,1,2.17,1.0,2.80,1.0