第5处理机调度幻灯片课件.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第5处理机调度,处理机的三级调度,处理机的三级调度：,作业调度,进程调度,中程调度,1.,作业的状态,作业从提交到完成要经历四种状态：,提交状态,：用户作业由,输入设备向系统外存输入,时作业所处的状态。/,录入工作，还没进入系统,后备状态,：作业输入到外存后，系统为其建立了作业控制块JCB，并把它插入到,后备作业队列,中等待调度运行。/等待调入,执行状态,：作业,在内存中执行,。,完成状态,：作业,正常或异常结束,，但作业,占有的资源还未被系统全部回收,。,进程调度,作业状态转换图,等待,就绪,运行,I/O,请求,I/O,完成,时间片完,提交,作业录入,后备,作业调度,执行状态,完成,作业调度,作业调度,作业调度又称,高级调度、宏观调度或长程调度,，其主要任务是按一定的原则从,外存上,处于,后备状态,的作业中,选择一个或多个,作业，给它们,分配,内存、输入,/,输出设备等必要的,资源，,并,建立相应的进程,，以,使该作业具有获得竞争处理机的权利。,作业调度的运行,频率较低,，通常为几分钟一次。,作业调度的功能,接纳多少作业：决定接纳作业的数目。,记录作业状况：记录作业各阶段的情况。包括资源分配、优先权、状态等。相关信息构成JCB，它是作业存在的唯一标志。,确定调度算法：决定接纳哪些作业。,做好执行前的准备工作：为选中作业建立进程并分配资源。,善后处理：作业完成后回收占用资源，撤消JCB。,2.,中程调度,中程调度又称中级调度或交换调度，其功能是将内存中暂时不用的信息移到外存，以腾出空间给内存中的进程使用，或将需要的信息从外存读入内存。,引入中程调度的目的是提高内存利用率和系统吞吐量。,中程调度的运行频率介于两者之间。,引起中程调度的原因,频繁缺页时，应换出内存的部分作业。,就绪队列中进程太多影响响应时间，应换出就绪队列中的部分进程。,等待I/O可能要一段时间，可以将这类进程换出。,为便于紧缩，可以将部分进程换出。,内存有足够空间时，可以从外存换入一些进程。,外存中进程的优先级高于内存时，可以换入。,中程调度程序,中程调度程序由换入和换出两个过程组成：,换出过程把内存中的程序或数据换到交换区。,换入过程把外存中的程序或数据换到内存。,为了加快交换速度，外存交换区采用连续分配方式。,3.,进程调度,进程调度,又称,低级调度、微观调度或短程调度,，其主要任务是按照某种策略和方法从,就绪队列,中,选取一个进程,，将,处理机分配给它。,进程调度的运行,频率很高,，一般几十毫秒要运行一次。,进程调度的,功能,记录,系统中,所有进程,的,状态、优先数和资源情况。,按调度算法,选择进程运行。,实施处理机的,分配及回收,。,引起进程调度的原因,正在运行进程,结束,运行进程因某种原因,阻塞,，如P操作、I/O等,有进程进入就绪队列且就绪队列为空，或进程优先级高于当前运行进程且为剥夺调度方式,从,系统调用或中断,返回,时间片用完,4.,选择调度算法的准则,由于操作系统的类型及目标不同，因此选择的调度算法也不同。,选择调度算法有以下准则：,面向系统,的准则,面向用户,的准则,面向,系统,的准则,公平性,：系统中的每个进程应获得合理的CPU时间。,CPU,利用率高,：对,微机和实时系统不太重要。,系统吞吐量大,：吞吐量指,单位时间内所完成的进程数。,合理利用各类资源,：让各类资源都忙碌，,对微机不太重要,。,面向,用户,的准则,周转时间短,：指从作业,提交,到作业,完成,的时间间隔。,响应时间快：,指从用户,提交请求,到,系统产生响应,的时间间隔。,截止时间的保证,：截止时间是指,某任务必须开始执行,或,必须完成,的最迟时间。,稳定性,：对某用户的作业而言，,调度策略不应使其响应时间和周转时间变化太大。,周转时间,作业的,周转时间,是指从作业,提交,到作业,完成,之间的时间间隔。,平均周转时间,是指多个作业的周转时间的平均值。个作业的平均周转时间：,T=,（,T,1,T,2,T,n,）,n,（,T,i,为,作业的周转时间）,带权周转时间,带权,周转时间,是指,作业周转时间,与作业,实际运行时间,的比。,平均带权周转时间是指多个作业的带权周转时间的平均值。个作业的平均带权周转时间：,W,（,W,1,W,2,W,n,）,/n,（,W,i,为,作业的带权周转时间）,5.2 调度算法,调度算法是指,根据系统资源分配策略,所规定的,资源分配算法,。,本章的算法有些适合,作业调度,，有些适合,进程调度,，有些适用于两者。,1,先来先服务,调度算法,先来先服务算法既,可用于作业调度，也可用于进程调度。,在,作业调度,中：从后备作业队列中,选择一个或多个,最先,进入该队列的作业，,将它们调入内存，为它们分配资源，创建进程，然后,放入就绪队列,。,进程调度,中：从就绪队列中,选择一个,最先,进入该队列的进程,，为之分配处理机，使之投入运行。该进程,一直运行到完成,或,因等待某一事件而阻塞,时,才释放处理机,。,设有,4,道作业，它们的提交时间及执行时间如下表，若按先来先服务调度算法进行调度，试计算,4,个作业的平均周转时间和平均带权周转时间。（时间单位：小时，以十进制计算）。,先来先服务调度算法例,作业,提交时间,估计运行时间,1,10,2,2,10.2,1,3,10.4,0.5,4,10.5,0.3,作业周转时间及带权周转时间的计算,平均周转时间T=(2.02.83.13.3)/4=2.8,平均带权周转时间W=(12.86.211)/4=5.25,11,6.2,2.8,1,带权周转时间,3.3,3.1,2.8,2,周转 时间,13.8,13.5,13,12,完成 时间,13.5,13,12,10,开始 时间,0.3,0.5,1,2,运行 时间,10.5,10.4,10.2,10,提交 时间,4,3,2,1,作业,周转时间：申请到完成，完成-提交,带权周转时间：周转时间与用CPU时间的比值周转/运行,先来先服务算法特点,算法简单，易于实现，,但,不利于短作业,（进程）,。,不利于短CPU，长IO的作业/长期等待,/平均运行时间更接近较大的运行时间,2.,短作业（进程）优先,调度算法,在,作业调度,中，从后备队列中,选择一个或多个估计,运行时间最短,的作业，将它们调入内存运行。,在,进程调度,中，从就绪队列中,选择一个估计运行时间最短的进程，为之分配处理机,，使之投入运行。该进程一直,运行到完成或因等待某一事件而阻塞,时才释放处理机。,短作业优先调度算法例,平均周转时间 T=(2.01.82.43.6)/4=2.45,平均带权周转时间 W=(164.83.6)/4=3.85,6,4.8,3.6,1,带权周转时间,1.8,2.4,3.6,2,周转 时间,12.3,12.8,13.8,12,完成 时间,12,12.3,12.8,10,开始 时间,0.3,0.5,1,2,运行 时间,10.5,10.4,10.2,10,提交 时间,4,3,2,1,作业,短作业优先调度算法的特点,算法调度,性能较好，,例如上例中，,先来先服务 短作业优先,平均周转时间 2.8 2.45,平均带权周转时间 5.25,3.85,但,对长作业不利,，,未考虑作业的紧迫程度,，,运行时间为估计,。,最短剩余时间,优先调度算法,最短进程优先调度算法,可以是非抢占式的，也可以是抢占式的,。,若无特别说明，,通常是指,非抢占式,的算法,。,抢占式,的最短进程优先调度算法也称为,最短剩余时间优先,调度算法，即当一个新进程进入就绪队列时，若其,需要,的,运行时间,比,当前运行进程的,剩余时间,短，则它将抢占CPU。,抢占式的短程序优先！,最短剩余时间优先算法例,时间：,1.4,2.67,1,2.125,带权周转时间,7,24,4,17,周转 时间,10,26,5,17,完成 时间,5,17,1,0,开始 时间,5,9,4,8,运行 时间,3,2,1,0,提交 时间,D,C,B,A,作业,0,A,1,2,B,3,4,5,10,D,A,17,26,C,最短剩余时间优先算法例（续）,平均周转时间 T=(174247)/4=13,平均带权周转时间 W=(2.12512.671.4)/4=1.8,1.4,2.67,1,2.125,带权周转时间,7,24,4,17,周转 时间,10,26,5,17,完成 时间,5,17,1,0,开始 时间,5,9,4,8,运行 时间,3,2,1,0,提交 时间,D,C,B,A,作业,最短平均周转时间,当一批作业,同时到达,时，,最短作业优先调度,算法才能获得,最短平均周转时间,。,设一组作业p,1,、p,2,、p,n,，,其运行时间为t,1,、t,2,、t,n,，,且假定t,1,t,2,用户,进程,对资源的需求,：执行时间，资源数量,用户要求,：紧迫程度,到达时间,：先到则优先权高,特点：简单易行，系统开销小，但不精确。,动态优先权,动态优先权,是指在创建进程时，根据进程的特点及相关情况确定一个优先权，在进程运行过程中再,根据情况的变化调整优先权,。,确定原则有：,占用CPU时间,，,等待时间,。,/占的长的，滚边去，新来的，滚边去,例：优先数=CPU使用时间/2+基本优先数,CPU,使用时间衰减函数:,Decay(CPU)=CPU/2,5.最高响应比优先调度算法,最高响应比,优先调度算法是对短作业优先调度算法和先来先服务调度算法的一种综合。,响应比,响应比定义如下：,响应比作业响应时间/估计运行时间,响应比=等待时间+需要CPU时间/需要CPU时间,R=(W+S)/S,由于响应时间为作业进入系统后的等待时间加上估计运行时间。因此,响应比1作业,等待时间,/估计,运行时间,最高响应比优先调度算法思想,在每次调度作业运行时，先计算后备作业队列中每个作业的响应比，然后挑选响应比最高者投入运行。,特点：,有利于短作业,-等待时间相同，短作业优先，,考虑等待时间,-运行时间相同，等待时间长的作业优先运行。,响应比,1,作业,等待时间,/,估计,运行时间,最高响应比优先算法例,设有A、B、C、D、E五个进程，其到达时间分别为0、1、2、3、4，要求运行时间依次为3、6、4、5、2，采用最高响应比优先调度算法，试计算其平均周转时间和平均带权周转时间。,分析作业的调度顺序,A、B、C、D、E,的到达时间依次为0、1、2、3、4，要求运行时间依次为3、6、4、5、2,0：A运行，BCD依次到达；,3：r,B,=1+2/6，,r,C,=1+1/4，,r,D,=1,；B先运行。,9：r,C,=1+7/4，,r,D,=1+6/5，,r,E,=1+5/2,；E先运行。,11：r,C,=1+9/4，,r,D,=1+8/5,；C先运行。,由此可知作业的运行顺序为A、B、E、C、D。,周转时间的计算,顺序,A、B、E、C、D,平均周转时间 T=(381317+7)/5=9.6,平均带权周转时间 W=(11.333.253.4+3.5)/5=2.496,3.4,3.25,1.33,1,带权周转时间,17,13,8,3,周转 时间,20,15,9,3,完成 时间,15,11,3,0,开始 时间,5,4,6,3,运行 时间,3,2,1,0,提交 时间,D,C,B,A,作业,3.5,7,11,9,2,4,E,6.,多级队列,调度算法,实现思想：根据作业,性质或类型,不同，将进程,就绪队列分为多个,，每个队列采用,不同的调度算法。,例如：终端型作业为前台作业，批处理作业为后台作业。,前台采用时间片轮转算法，后台采用先来先服务，前台作业的优先级高。,7.,多级,反馈,队列,调度算法（,1,）,应,设置多个就绪队列,，并为每个队列赋予,不同的优先级,。第,1,个队列的优先级最高，第,2,队列次之，其余队列的优先级,逐次降低,。,每个队列中,进程执行的,时间片大小也各不相同,，进程,所在队列的优先级越高,，其相应的,时间片就越短。,多级反馈队列调度算法（2）,当一个新进程进入系统时，首,先将它放入,第1个队列的末尾,，按,先来先服务,fcfs,的原则排队等待调度。当轮到该进程执行时，如,能在此时间片内完成,，便可准备撤离系统；,如果它在一个时间片结束时尚未完成,，调度程序便将该进程,转入第2队列的末尾,，再同样地按先来,先服务原则,fcfs,等待调度执行。如此下去，,最后一个队列中,使用时间片轮转调度算法,RR,。,除最后一个用RR，其他的全部FCFS！,多级反馈队列调度算法（3）,仅当第1个队列为空时，调度程序才调度第2队列中的进程运行；,仅当第1个至第（i1）个队列均为空时，才会调度第i,个队列中的进程运行。,当处理机正在为第,i,个队列中的某进程服务时，若又,有新进程进入优先级较高的队列中,，则此时新,进程将,抢占正在运行进程的处理机,，即由调度程序,把正在执行进程放回第i,个,队列末尾,，重新将处理机分配给新进程。,前面的队列都空了，才能接下个队列,队列间的进程允许优先级抢占,多级反馈队列调度算法示意图,就绪队列1,CPU,就绪队列2,就绪队列n,CPU,CPU,完成,完成,完成,没完成,下放到,下一个,队列,多级反馈队列调度算法例,设有A、B、C、D、E五个进程，其到达时间分别为0、1、3、4、5，要求运行时间依次为3、8、4、5、7，采用多级反馈队列调度算法，系统中共有3个队列，其时间片依次为1、2和4，试计算其平均周转时间和平均带权周转时间。,13：,EE,运行，BCD等待；,调度分析,A、B、C、D、E,到达时间依次为0、1、3、4、5，要求运行时间依次为3、8、4、5、7,1：B运行，A等待；,2：A运行，B等待；,3：,C,运行，BA等待,；,4：,D,运行，BAC等待；,5：,E,运行，BACD等待；,6：,BB,运行，ACDE等待；,8：,A,运行，CDE等待；B等待,9：,CC,运行，DE等待；B等待,11：,DD,运行，E等待；BC等待,15：,BBBB,运行，CDE等待；,19：,C,运行，DEB等待；,20：,DD,运行，EB等待；,22：,EEEE,运行，B等待,；,0：A运行；,26：,B,运行,。,周转时间的计算,平均周转时间 T=(9261718+21)/5=18.25,平均带权周转时间 W=(33.254.253.6+3)/5=3.42,3.6,4.25,3.25,3,带权周转时间,18,17,26,9,周转 时间,22,20,27,9,完成 时间,4,3,1,0,开始 时间,5,4,8,3,运行 时间,4,3,1,0,提交 时间,D,C,B,A,作业,3,21,26,5,7,5,E,多级反馈队列调度算法的性能,多级反馈队列调度算法能较好满足各类用户的需求：,终端型用户,：大多能在一个时间片内完成，响应时间较短；,短批处理作业用户,：能在前几个队列完成，周转时间较短；,长批处理作业用户,：依次在1n,队列中运行，不会长时间得不到处理。,8.公平分享调度算法,公平分享调度,算法,基于,进程组,来分配CPU时间，其实现思想是对系统中的,每个用户赋予某种权值,，根据,用户权值大小，按比例分配处理机时间。,公平分享调度有许多实现方案，本节讲述UNIX中的一种实现方案。,UNIX中的公平分享调度,UNIX,基于优先权调度，,优先数,越大,优先权,越低,。对进程组k中进程j的优先数计算公式如下：,CPU,j,（i）,=CPU,j,（i-1）/2；,进程j,在时间段i使用的CPU时间,GCPU,k,（i）,=GCPU,k,（i-1）/2；,进程组k,在时间段i使用的CPU时间,P,j,(i),=,Base,j,+CPU,j,(i)/2+GCPU,k,(i)/4W,k,；,进程j在时间段i的优先数，,Base,j,为进程j的基本优先数,，,W,k,为进程组k的权值。,0=,W,k,=1且=1,公平分享调度例,下例中,W,k,为0.5，,Base,为60,。相应的优先数计算公式为：,CPU,j,（i）=CPU,j,（i-1）/2；,GCPU,k,（i）=GCPU,k,（i-1）/2；,P,j,（i）=60+CPU,j,（i）/2+GCPU,k,（i）/2,公平分享调度例,进程A,进程B,进程C,时间,优先数 计数 组,优先数 计数 组,优先数 计数 组,0 60 0 0,60 0 0,60 0 0,1 1,2 2,60 60,1 90,30 30,60 0 0,60 0 0,1 1,1,2 2,2,60 60,60,公平分享调度例（续1）,进程A,进程B,进程C,时间,优先数 计数 组,优先数 计数 组,优先数 计数 组,2 74,15 15,90,30 30,75,0 30,16 16,17 17,75 75,3 96,37 37,74,15 15,67,0 15,16,1 16,17,2 17,75,60 75,公平分享调度例（续2）,进程A,进程B,进程C,时间,优先数 计数 组,优先数 计数 组,优先数 计数 组,4 78,18 18,81,7 37,93,30 37,19 19,20 20,78 78,5 98,39 39,70,3 18,76,15 18,习题,P103,2,10,11,UNIX的进程调度（P255）,UNIX,的进程调度采用多级反馈队列调度算法，系统设置了多个就绪队列。进程调度程序执行时：,核心首先从处于“内存就绪”或“被剥夺”状态的进程中选择一个优先级最高的进程；,若系统中同时有多个进程都具有最高优先级，则核心将选择其中处于就绪状态最久的进程，将它从所在队列移出，恢复其上下文，使之执行；,仅当最高优先级队列中没有进程时，才从次高优先级队列中找出其队首进程，令它执行一个时间片后，又剥夺该进程的执行；,然后，再从优先级最高的队列中取出下一个就绪进程投入运行。,进程优先级的分类,在UNIX,系统中，进程的优先级分为两类：,核心优先级。它又可进一步分为可中断和不可中断两类优先级。当一个软中断信号到达时，若进程正处于可中断优先级上睡眠，则进程立即被唤醒；若进程处于不可中断的优先级上，则进程继续睡眠。,用户优先级。又可分成n+,级，其中第0级为最高优先级，第n级的优先级最低。,进程优先级范围图,优先级,进程,核心态优先级,优先级阈值,用户态优先级,不可中断,可中断,对换,等待磁盘I/O,等待缓冲区,等待索引节点,等待tty输入,等待tty输出,等待子进程退出,用户级0,用户级1,用户级n,优先数的计算,UNIX System,中的用户优先级是可变的，它随着占用CPU时间的增加而降低。核心每隔1秒钟便根据一个衰减函数来调整每个进程的最近CPU使用时间，并按下述公式对各进程重新计算其用户优先数（优先数越大优先级越低，优先数越小优先级越高）。,decay(CPU)CPU/2,优先数最近使用CPU的时间/2基本用户优先数+nice值,进程切换,在操作系统中，凡是要进行中断处理和进程调度时，都将涉及到进程上下文的保存和恢复。,中断时系统所保存和恢复的是同一个进程的上下文。而进程调度时则要进行进程上下文切换，此时系统所保存的是当前进程的上下文，而恢复的则是调度程序所选中进程的上下文。,进程上下文的保存与恢复,发生中断时，如果处理机的当前运行级低于该中断级别，则处理机将响应该中断。核心对中断的处理过程分为以下几步：,保存当前进程的寄存器上下文；,确定中断源；,查找中断向量；,执行该中断处理程序；,恢复前一上下文层。,引起进程,上下文切换,的原因,引起进程上下文切换的原因是由于进程调度程序选中了一个新的进程运行。,在UNIX系统中，由于采用了可剥夺的调度方式，因而引起进程调度的原因有时间片完、当前进程执行了sleep例程、进程执行完等，它们都会导致进程上下文的切换。,进程上下文切换的步骤,进程上下文的切换过程可分成以下四步：,确定是否要进行上下文切换；,利用save_context,函数（UNIX系统中实现进程上下文保存的函数）保存当前进程的上下文；,由调度程序按一定的策略选择一个在内存中就绪的进程；,用resume_context函数恢复被选中进程的上下文，此后便进入新进程的上下文中执行。,此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢,