第5章 处理机调度1.ppt

1、第5章 处理机调度,一个作业从提交到完成通常要经历多级调度。,5.1 处理机调度的类型,处理机调度需要解决： 多任务以何种方式共享处理机。互斥 处理机时间的分配及长短确定。合理 处理机分配策略。如何分配 进程切换频度与系统效率的权衡。频繁开销大，反之则并发性低,处理机的三级调度,处理机的三级调度： 作业调度 进程调度 交换调度,1.作业的状态,作业从提交到完成要经历四种状态： 提交状态：用户作业由输入设备向系统外存输入时作业所处的状态。 后备状态：作业输入到外存后，系统为其建立了作业控制块，并把它插入到后备作业队列中等待调度运行。 执行状态：作业在内存中执行。 完成状态：作业正常或异常结束，但

2、作业占有的资源还未被系统全部回收。,作业状态转换图,等待,就绪,运行,I/O请求,I/O完成,时间片完,提交,作业录入,后备,作业调度,进程调度,执行状态,完成,作业调度,5.1.1 作业调度,作业调度又称高级调度、宏观调度或长程调度，其主要任务是按一定的原则从外存上处于后备状态的作业中选择一个或多个作业，给它们分配内存、输入/输出设备等必要的资源，并建立相应的进程，以使该作业具有获得竞争处理机的权利。 作业调度的运行频率较低，通常为几分钟一次。,作业调度的功能,接纳多少作业：决定接纳作业的数目。 记录作业状况：记录作业各阶段的情况。包括资源分配、优先权、状态等。相关信息构成JCB，它是作业存

3、在的唯一标志。 确定调度算法：决定接纳哪些作业。 做好执行前的准备工作：为选中作业建立进程并分配资源。 善后处理：作业完成后回收占用资源，撤消JCB。,5.1.2 中程调度,中程调度又称中级调度或交换调度，其功能是将内存中暂时不用的信息移到外存，以腾出空间给内存中的进程使用，或将需要的信息从外存读入内存。 引入中程调度的目的是提高内存利用率和系统吞吐量。 中程调度的运行频率介于两者之间。,引起中程调度的原因,频繁缺页时，应换出内存的部分作业。 就绪队列中进程太多影响响应时间，应换出就绪队列中的部分进程。 等待I/O可能要一段时间，可以将这类进程换出。 为便于紧缩，可以将部分进程换出。 内存有足

4、够空间时，可以从外存换入一些进程。 外存中进程的优先级高于内存时，可以换入。,中程调度程序,中程调度程序由换入和换出两个过程组成： 换出过程把内存中的程序或数据换到交换区。 换入过程把外存中的程序或数据换到内存。 为了加快交换速度，外存交换区采用连续分配方式。,5.1.3 进程调度,进程调度又称低级调度、微观调度或短程调度，其主要任务是按照某种策略和方法从就绪队列中选取一个进程，将处理机分配给它。 进程调度的运行频率很高，一般几十毫秒要运行一次。,进程调度的功能,记录系统中所有进程的状态、优先数和资源情况。 按调度算法选择进程运行。 实施处理机的分配及回收。,引起进程调度的原因,正在运行进程结

5、束 运行进程因某种原因阻塞，如P操作、I/O等 有进程进入就绪队列且就绪队列为空，或进程优先级高于当前运行进程且为剥夺调度方式 从系统调用或中断返回 时间片用完,5.1.4 选择调度算法的准则,由于操作系统的类型及目标不同，因此选择的调度算法也不同。 选择调度算法有以下准则： 面向系统的准则 面向用户的准则,面向系统的准则,公平性：系统中的每个进程应获得合理的CPU时间。 CPU利用率高：对微机和实时系统不太重要。 系统吞吐量大：吞吐量指单位时间内所完成的进程数。 合理利用各类资源：让各类资源都忙碌，对微机不太重要。,面向用户的准则,周转时间短：指从作业提交到作业完成的时间间隔。 响应时间快：

6、指从用户提交请求到系统产生响应的时间间隔。 截止时间的保证：截止时间是指某任务必须开始执行或必须完成的最迟时间。 稳定性：对某用户的作业而言，调度策略不应使其响应时间和周转时间变化太大。,周转时间,作业的周转时间是指从作业提交到作业完成之间的时间间隔。 平均周转时间是指多个作业的周转时间的平均值。个作业的平均周转时间： T =（T1T2 Tn）n（Ti为作业的周转时间）,带权周转时间,带权周转时间是指作业周转时间与作业实际运行时间的比。 平均带权周转时间是指多个作业的带权周转时间的平均值。个作业的平均带权周转时间： W （W1W2 Wn）/n（Wi为作业的带权周转时间）,5.2 调度算法,调度

7、算法是指根据系统资源分配策略所规定的资源分配算法。 本章的算法有些适合作业调度，有些适合进程调度，有些适用于两者。,5.2.1 先来先服务调度算法,先来先服务算法既可用于作业调度，也可用于进程调度。 在作业调度中：从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源，创建进程，然后放入就绪队列。 进程调度中：从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或因等待某一事件而阻塞时才释放处理机。,设有4道作业，它们的提交时间及执行时间如下表，若按先来先服务调度算法进行调度，试计算4个作业的平均周转时间和平均带权周转时间。（

8、时间单位：小时，以十进制计算）。,先来先服务调度算法例,作业周转时间及带权周转时间的计算,平均周转时间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,作业,先来先服务算法特点,算法简单，易于实现， 但不利于短作业。,5.2.2 短作业（进程）优先调度算法,在作业调度中，从后备队列

9、中选择一个或多个估计运行时间最短的作业，将它们调入内存运行。 在进程调度中，从就绪队列中选择一个估计运行时间最短的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或因等待某一事件而阻塞时才释放处理机。,短作业优先调度算法例,平均周转时间 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,提交

10、时间,4,3,2,1,作业,短作业优先调度算法的特点,算法调度性能较好， 例如上例中， 先来先服务 短作业优先 平均周转时间 2.8 2.45 平均带权周转时间 5.25 3.85 但对长作业不利，未考虑作业的紧迫程度，运行时间为估计。,最短剩余时间优先调度算法,最短进程优先调度算法可以是非抢占式的，也可以是抢占式的。若无特别说明，通常是指非抢占式的算法。 抢占式的最短进程优先调度算法也称为最短剩余时间优先调度算法，即当一个新进程进入就绪队列时，若其需要的运行时间比当前运行进程的剩余时间短，则它将抢占CPU。,最短剩余时间优先算法例,时间：,1.4,2.67,1,2.125,带权周转时间,7,

11、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,作业,最短

12、平均周转时间,当一批作业同时到达时，最短作业优先调度算法才能获得最短平均周转时间。 设一组作业p1、p2、pn，其周转时间为t1、t2、 、tn，且假定t1t2 tn，则短作业优先调度算法的总周转时间为： t1+（t1+t2）+ +（t1+ +tn） =n*t1+（n-1）t2+ +tn,最短平均周转时间（续）,可以证明：若a1 a2 an且b1b2 bn，则 a1bn+a2bn-1 +anb1 a1bi1+a2bi2 +anbin a1b1+a2b2 +anbn 其中i1、i2、 、in 是1、2、 、n的一个排列。,5.2.3 时间片轮转调度算法,时间片轮转法：系统将所有就绪进程按到达时间

13、的先后次序排成一个队列，每次调度时把CPU分配给队首进程，并令其执行一个时间片。当时间片用完时，停止该进程的执行，将它送至就绪队列末尾等待下一次执行，然后再把处理机分配给就绪队列中的新队首进程。如此不断循环，直至完成为止。,时间片轮转算法例,设有A、B、C、D、E五个进程，其到达时间分别为0、1、2、3、4，要求运行时间依次为3、6、4、5、2，采用时间片轮转调度算法，当时间片大小为1和4时，试计算其平均周转时间和平均带权周转时间。,时间片大小为1,A、B、C、D、E要求运行时间依次为3、6、4、5、2，到达时间依次为0、1、2、3、4。,1：B运行，A等待；,2：A运行，CB等待；,3：C运

14、行，BDA等待；,4：B运行，DAEC等待；,5：D运行，AECB等待；,6：A运行，ECBD等待；,7：E运行，CBD等待；,8：C运行，BDE等待；,9：B运行，DEC等待；,10：D运行，ECB等待；,11：E运行，CBD等待；,12：C运行，BD等待；,13：B运行，DC等待；,14：D运行，CB等待；,15：C运行，BD等待；,16：B运行，D等待；,17：D运行，B等待；,18：B运行，D等待；,19：D运行，,0：A运行；,时间片为1的周转时间,平均周转时间 T=(7181417+8)/5=12.8 平均带权周转时间 W=(2.3333.53.4+4)/5=3.246,时间片大小

15、为4,A、B、C、D、E要求运行时间 依次为3、6、4、5、2 ，到达时间依次为0、1、2、3、4。,0：A运行，BCD依次到达；,3：B运行，CD等待，后E到达；,7：C运行，DEB等待；,11：D运行，EB等待；,15：E运行，BD等待；,17：B运行，D等待；,19：D运行,A、B、C、D、E开始时间依次为0、3、7、11、15；结束时间依次为3、19、11、20、17。,时间片为4的周转时间,平均周转时间 T=(318917+13)/5=12 平均带权周转时间 W=(132.253.4+6.5)/5=3.23,时间片大小的选择,若时间片太大，所有进程都能在一个时间片内完成，则时间片轮转

16、算法退化为先来先服务；若时间片太小，则进程调度频繁，系统开销增加。,确定时间片大小应考虑的因素,系统对响应时间的要求：响应时间=时间片*进程数。 就绪队列中的进程数目：时间片与就绪进程数成反比。 系统处理能力：人所能承受的响应时间一定，系统速度快则时间片可增长。,时间片轮转算法的特点及改进,对偏重I/O的进程不公平。为此改进为虚拟时间片轮转算法。 虚拟时间片轮转算法：新进程基于FCFS进入就绪队列，进程用完时间片后也进入就绪队列，进程因I/O阻塞进入I/O队列，I/O完成时进程进入附加队列，附加队列的优先级高于就绪队列，当进程从附加队列被调度时，其运行时间不超过上次发生中断时剩余的时间。,虚拟

17、时间片轮转调度示意图,CPU,新进程,就绪队列,调度,超时,优先级高,附加队列,I/O队列,请求I/O,I/O完成,5.2.4 优先权调度算法,在作业调度中，从后备作业队列中选择若干优先权高的作业调入内存。 在进程调度中，将处理机分配给就绪队列中优先权最高的进程。 优先权通常用优先数来衡量。在某些系统中，优先数越大优先权越高；而在另一些系统中，优先数越大优先权越小。,进程调度方式,进程调度有两种方式： 非抢占方式 抢占方式,非抢占方式,非抢占方式：又称非剥夺方式、不可剥夺方式、不可抢占方式。这种调度方式是指一旦将处理机分配给某进程后，便让该进程一直执行，直到该进程完成或发生某事件而进入阻塞状态

18、，才把处理机分配给其他进程。 非抢占方式中引起进程调度的因素有：进程结束、因某种原因而阻塞、执行同步原语等。 特点：简单，系统开销小，但无法处理紧急任务。,抢占方式,抢占方式：又称剥夺方式、可剥夺方式。这种调度方式是指允许调度程序根据某种原则去停止正在执行的进程，将已分配给该进程的处理机重新分配给其他进程。 抢占原则有：优先权、短作业优先、时间片。,按调度方式对优先权调度算法分类,非抢占式优先权算法：系统一旦将处理机分配给就绪队列中优先权最高的进程后，该进程便一直运行下去，直到完成或因发生某事件使该进程放弃处理机时，系统才将处理机分配给另一个更高优先权的进程。 抢占式优先权调度算法：将处理机分

19、配给优先权最高的进程，使之运行。在进程运行过程中，一旦出现了另一个优先权更高的进程时，进程调度程序就停止原运行进程，而将处理机分配给新出现的高优先权进程。,优先权的类型,优先权分为两种： 静态优先权 动态优先权,静态优先权,静态优先权是在创建进程时确定的，确定之后在整个进程运行期间不再改变。 确定依据有： 进程类型：系统，用户 进程对资源的需求：执行时间，资源数量 用户要求：紧迫程度 到达时间：先到则优先权高 特点：简单易行，系统开销小，但不精确。,动态优先权,动态优先权是指在创建进程时，根据进程的特点及相关情况确定一个优先权，在进程运行过程中再根据情况的变化调整优先权。 确定原则有：占用CP

20、U时间，等待时间。 例：优先数=CPU使用时间/2+基本优先数 CPU使用时间衰减函数: Decay(CPU)=CPU/2,响应比,响应比定义如下： 响应比作业响应时间/估计运行时间 由于响应时间为作业进入系统后的等待时间加上估计运行时间。因此 响应比1作业等待时间/估计运行时间,5.2.5 最高响应比优先调度算法,最高响应比优先调度算法是对短作业优先调度算法和先来先服务调度算法的一种综合。 在每次调度作业运行时，先计算后备作业队列中每个作业的响应比，然后挑选响应比最高者投入运行。 特点： 有利于短作业-等待时间相同，短作业优先， 考虑等待时间-运行时间相同，等待时间长的作业优先运行。,最高响

21、应比优先算法例,设有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：rB =1+2/6， rC =1+1/4， rD =1；B先运行。,9：rC =1+7/4， rD =1+6/5， rE =1+5/2；E先运行。,11：rC =1+9/4， rD =1+8/5；C先运行。,由此可知作业的运行顺序为A、B、E、C、D。,周转时间

22、的计算 顺序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,5.2.6 多级队列调度算法,实现思想：根据作业性质或类型不同，将进程就绪队列分为多个，每个队列采用不同的调度算法。 例如：终端型作业为前台作业，批处理作业为后台作业。前台采用时间片轮转

23、算法，后台采用先来先服务，前台作业的优先级高。,5.2.7 多级反馈队列调度算法,应设置多个就绪队列，并为每个队列赋予不同的优先级。第1个队列的优先级最高，第2队列次之，其余队列的优先级逐次降低。 每个队列中进程执行的时间片大小也各不相同，进程所在队列的优先级越高，其相应的时间片就越短。,多级反馈队列调度算法（2）,当一个新进程进入系统时，首先将它放入第1个队列的末尾，按先来先服务的原则排队等待调度。当轮到该进程执行时，如能在此时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第2队列的末尾，再同样地按先来先服务原则等待调度执行。如此下去，最后一个队列中使

24、用时间片轮转调度算法。,多级反馈队列调度算法（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

25、、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：

26、EEEE运行，B等待；,0：A运行；,26：B运行。,周转时间的计算,平均周转时间 T=(9261718+21)/5=18.25 平均带权周转时间 W=(33.254.253.6+3)/5=3.42,多级反馈队列调度算法的性能,多级反馈队列调度算法能较好满足各类用户的需求： 终端型用户：大多能在一个时间片内完成，响应时间较短； 短批处理作业用户：能在前几个队列完成，周转时间较短； 长批处理作业用户：依次在1n队列中运行，不会长时间得不到处理。,5.2.8 公平分享调度算法,公平分享调度算法基于进程组来分配CPU时间，其实现思想是对系统中的每个用户赋予某种权值，根据用户权值大小，按比例分配处理机

27、时间。 公平分享调度有许多实现方案，本节讲述UNIX中的一种实现方案。,UNIX中的公平分享调度,UNIX基于优先权调度，优先数越大优先权越低。对进程组k中进程j的优先数计算公式如下： CPUj（i）=CPUj（i-1）/2；进程j在时间段i使用的CPU时间 GCPUk（i）=GCPUk（i-1）/2；进程组k在时间段i使用的CPU时间 Pj（i）=Basej+ CPUj（i）/2+ GCPUk（i）/4Wk；进程j在时间段i的优先数， Basej 为进程j的基本优先数， Wk为进程组k的权值。,公平分享调度例,下例中Wk为0.5，Base为60。相应的优先数计算公式为： CPUj（i）=CP

28、Uj（i-1）/2； GCPUk（i）=GCPUk（i-1）/2； Pj（i）=60+ CPUj（i）/2+ GCPUk（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

29、 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,5.3 多处理机调度,多处理机系统上运行的操作系统广泛采用了线程机制，线程是处理机调度和运行的基本单位。 在多处理机环境中，线程可以用于开发应用程序中真正的并行性。 如果应用程序中的各个线程同时在各自独立的处理机中运行，其性能会得到显著提高

30、。,5.3.1 负载分配调度,基本思想：由系统建立一个全局共享的线程就绪队列，当某台处理机空闲时，便按某种调度算法从就绪队列中选择一个线程运行。 由于负载分配调度是由各个处理机自己进行调度的，而不考虑其他的处理机，因此也称为自调度(Self-scheduling) 。,负载分配调度算法,先来先服务(FCFS)算法。 最小优先数线程优先算法。 抢占式最小优先数优先算法。,负载分配调度优缺点,优点： 负载均衡。 不需要集中调度程序。 线程就绪队列组织灵活。 缺点： 瓶颈问题。 效率低。 线程切换频繁。 改进算法。,5.3.2 成组调度,成组调度是指将一组相关联的线程，同时分配到一组处理机上运行，线

31、程与处理机一一对应。 若某个线程因等待资源而阻塞时，其余正在运行的线程因此而同时中止运行，所以解决相关联线程因互斥和同步引起的线程等待而造成处理机空转问题，是提高系统效率的目的。,成组调度的思想,在成组调度时，如何为应用程序分配处理器时间， 1) 面向所有应用程序平均分配处理器时间 2) 面向所有线程平均分配处理器时间,图 两种分配处理器时间的方法,成组调度的优点,有利于改善系统性能。 减少调度开销。 节省资源分配时间。,5.3.3 专用处理器分配方式,专用处理机分配的思想是：当一个应用程序被调度时，专门为应用程序分配一组处理机，并且每个线程分配一个处理机，这个处理机专门运行该线程，直至应用程

32、序运行结束。,专用处理器分配方式,不足之处： 浪费处理机。 线程切换可能很频繁。 应用： 在高并行的多处理机系统中，有几十个甚至上百个处理机，每个处理机仅占整个系统很少一部分花费，处理机利用不再是效率的惟一标准。 在一个程序的整个运行过程中，如果能完全避免线程切换，这就大大提高了系统的效率。,UNIX的进程调度（P255）,UNIX的进程调度采用多级反馈队列调度算法，系统设置了多个就绪队列。进程调度程序执行时： 核心首先从处于“内存就绪”或“被剥夺”状态的进程中选择一个优先级最高的进程； 若系统中同时有多个进程都具有最高优先级，则核心将选择其中处于就绪状态最久的进程，将它从所在队列移出，恢复其上下文，使之执行； 仅当最高优先级队列中