操作系统第六章处理机调度

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2016/10/21 Friday,#,第六章 处理机调度,为,了提高处理机的效率，处理机采用多级调度。,用户作业从进入系统成为后备作业开始，直到运行结束退出系统为止，需要经过不同级别的调度。,批处理,OS,可能经历作业调度、进程调度、线程调度,分时,OS,可能经历进程调度、线程调度,6.2,作业调度,作业可以是一次计算，一个控制过程。,作业的状态：,后备状态：作业在辅存上，并建立,JCB,，等待调度；,执行状态：作业进入主存，到作业计算完成为止；,完成状态：从作业计算完成开始，到善后处理完毕并退出系统为止。,例如：,后备状态：,在家拿到大学录取通知书,执行状态：,到大学报道注册,完成状态：,完成答辩后，归还资源到毕业离校,6.2,作业调度,作,业调度的功能主要是完成作业从后备执行和执行完成状态的转变。,其中主要的是按一定的调度算法，从后备作业队列中选,出,一个,作,业投入运行,。,执行,就绪,等待,后备,完成,作业调度,作业调度,执行状态,当作业处于执行状态时，其对应的进程不一定处于执行状态。,进程调度,6.2.4,调度算法性能的衡量,调度目标主要有一下,四,点：,对所有作业应该是公平合理的；,应使设备有高的利用率；,系统吞吐量大；,有较快的响应时间；,但这些目标本身有些是相互冲突的。,6.2.4,调度算法性能的衡量,通常用平均周转时间和平均带权周转时间,衡量作业调度算法的好坏。,1,、,平均周转时间,t=,其中：,ti=tcitsi,ti,是作业的周转时间,;,tci,是作业,i,的完成时间,(closure);,tsi,是,作,业,i,进入系统的时间,;,i=1,n,ti,1,n,6.2.4,调度算法性能的衡量,通常用平均周转时间和平均带权周转时间,衡量作业调度算法的好坏。,2,、,平均带权周转时间,w=,其中：,wi=ti/tri,ti,是作业,i,的周转时间,tri,是作业,i,的执行时间,i=1,n,wi,1,n,6.2.5,作业调度算法,1.,先来先服务调度算法（,FCFS,算法）,思想：作业按来到的先后次序进行调,度,例,如：下列作业序列采用,FCFS,算法（为方便计算采用十进制），分别计算平均周转时间和平均带权周转时间。,作业,进入系统时间,tsi,执行时间,tri,开始时间,完成时间,tci,周转时间,ti=tci-tsi,带权周转时间,Wi=ti/tri,1,8.00,2.00,8.00,10.00,2.00,1.00,2,8.50,0.50,10.00,10.50,2.00,4.00,3,9.00,0.10,10.50,10.60,1.60,16,4,9.50,0.20,10.60,10.80,1.30,6.6,调度次序,1,2,3,4,t=1.725 w=6.875,特,点：对短作业不利,6.2.5,作业调度算法,2.,短作业优先调度算法（,SJF,算法）,思想：从后备作业中选择执行时间最短的作业作为下一次服务的对象。,例如：下列作业序列采用,SJF,算法（为方便计算采用十进制），分别计算平均周转时间和平均带权周转时间。,作业,进入系统时间,tsi,执行时间,tri,开始时间,完成时间,tci,周转时间,ti=tci-tsi,带权周转时间,Wi=ti/tri,1,8.00,2.00,8.00,10.00,2.00,1.00,2,8.50,0.50,10.30,10.80,2.3,4.60,3,9.00,0.10,10.00,10.10,1.10,11,4,9.50,0.20,10.10,10.30,0.8,4,调度次序,1,3,4,2 t=1.55,w=5.15,缺点：只照顾短作业的利益，而不考虑长作业的利益。,6.2.5,作业调度算法,3,、,响,应比高者优先调度算法（介于二者之间的一种折中算法）,响应比,rp=,响应时间,/,执行时间,响,应时间,=,等待时间,+,执行时间,rp=1+,等待时间,/,执行时间 或,rp=,等待时间,/,执行时,间,当调度时，需计算后备作业的响应比，然后选择响应比最高者投入运行,。,作业,进入系统时间,tsi,执行时间,tri,开始时间,完成时间,tci,周转时间,ti=tci-tsi,带权周转时间,Wi=ti/tri,1,8.00,2.00,8.00,10.00,2.00,1.00,2,8.50,0.50,3,9.00,0.10,4,9.50,0.20,开始时，调度作业,1,投入运行。,当作业,1,结束时，需要计算后备队列作业的响应比。,当作业,1,结束时,：,rp2,=(10.00-8.50)/0.5=3,rp3,=(10.00-9.00)/0.1=10,rp4,=(10.00-9.50)/0.2=2.5,作业,3,投入运行,作业,进入系统时间,tsi,执行时间,tri,开始时间,完成时间,tci,周转时间,ti=tci-tsi,带权周转时间,Wi=ti/tri,1,8.00,2.00,8.00,10.00,2.00,1.00,2,8.50,0.50,3,9.00,0.10,10.00,10.10,1.1,11,4,9.50,0.20,当作,业,3,结,束时,：,rp2,=(10.10-8.50)/0.5=3.2,rp4,=(10.10-9.50)/0.2=3,作业,2,投入运行,，,最,后作业,4,运行,作业,进入系统时间,tsi,执行时间,tri,开始时间,完成时间,tci,周转时间,ti=tci-tsi,带权周转时间,Wi=ti/tri,1,8.00,2.00,8.00,10.00,2.00,1.00,2,8.50,0.50,10.10,10.60,2.1,4.2,3,9.00,0.10,10.00,10.10,1.1,11,4,9.50,0.20,10.60,10.80,1.3,6.5,调,度次序,1,3,2,4,t=1.625 w=5.675,缺点：每次需要调度时都要计算响应比，较复杂。,2,、,在一个多道程序设计系统中，有,3,个作业,A,B,C,，到达输入井的时间如下：,进程,到达时间,运行时间（小时）,开始执行时间,完成时间,周转时间（分）,A,7,：,50,1.5,（,(90,分,),B,8,：,00,0.4,（,24,分）,C,8,：,30,1,（,60,分）,系统在,9:00,开始按响应比高者优先算法对它们进行调度，请计算该作业序列的平均响应时间。,3,、有,j1,j2,j3,三个作业同时到达，执行时间分别为,a,b,c,且,abc,试证明,SJF,算法能够获得最小的平均周转时间。,课堂练习,1,、,P 157 6.6,FCFS,算法：,t=2.025 w=4.225,SJF,算法：,t=1.8375 w=3.2875,2.,在一个多道程序设计系统中，有,3,个作业,A,B,C,，到达输入井的时间如下：,进程,到达时间,运行时间（小时）,开始执行时间,完成时间,周转时间（分）,A,7,：,50,1.5,（,(90,分,),9:24,10:54,3:04,（,184,分,),B,8,：,00,0.4,（,24,分）,9:00,9:24,1:24,（,84,分）,C,8,：,30,1,（,60,分）,10:54,11:54,3:24,（,204,分）,系统在,9:00,开始按响应比高者优先算法对它们进程调度，请计算该作业序列的平均响应时间。,分析：,响应比,=,等待时间,/,执行时间,9:00,时，,rpA=70/90=7/9,，,rpB=60/24=5/2,，,rpC=30/60=1/2,，作业,B,执行,9:24,时，,rpA=94/90=47/45,，,rpC=54/60=9/10,，作业,A,执行,周转时间,=,完成时间到达时间，,t=,（,184+84+204,）,/3=157,分。,6.3,进程调度,一,：进程调度的功能,将进程按一定的策略从就绪队列中移出并建立,它,执,行的机器状态。,二、进程调度的时机可能有以下几种情况,1.,正在执行的进程执行完毕；,2.,执行的进程因中断调用、自陷、请求,I/O,服务等而阻塞；,3.,在分时系统中，进程分配的时间片用完；,4.,在可剥夺方式中，有优先级更高的进程要求处理；,6.3,进程调度,三：进程调度方式,当有优先级更高的进程进入就绪队列时，如何分配处理机？,1,、,非,剥夺方式：让正在执行的进程继续执行，直到该进程完成或因,某,事,件而进入“等待,”时,，才把处理机分配给优先级更高的进程。,2,、,可,剥夺方式：当优先级更高的进程一到，便暂停正在执行的进程，立即把处理机分配给它。,3,、,选,择可抢占策略：,每个进程不仅有优先级，而且还有一对标志（,U,、,V,）,U=1,，表示该进程可以抢占另一进程,U=0,，表示该进程不可抢占另一进程,V=1,，表示该进程可以被另一进程抢占,V=0,，表示该进程不可被另一进程抢占,U,、,V,的值可根据进程的动态特征由系统临时提交，这样，就使,抢,占,方式具有一定的灵活性,。,例,如：,:,表示该进程可以抢占另一进程，但不,能被其它的进程抢占。,U,V,1,0,6.3.4,进程优先数调度算法,思想：把处理机分配给就绪队列中优先权最高的进程。,不可抢占优先权算法,可抢占优先权算法,优先权的处理较为关键,静态优先权,在进程建立时确定，且规定它在进程的整个运行期间保,持,不,变,。确,定优先权的依据有：,进程所需资源的要求。如进程的执行时间及内存需要量少的应赋予较高的优先权。,进,程类型。如系统进程的优先权应高于用户进程。,根,据用户类型。如按用户付费用的多少来确定优先权。,6.3.4,进程优先数调度算法,二,.,动,态优先权,在进程创建时所赋予的优先权，可以随着,进,程,的推进而改变，以便获得更好的调度性能。,P155 UNIX,系统中优先数的计算,优先数,P_pri=min127,P_cpu/16-P_nice+PUSER,优先数,P_pri,越大，则优先级越小。,PUSER,是固定偏置常数，定为,100,P_nice,的值默认为,20,，可以用命令,nice,设置,P_cpu,的值可变，当时钟信号到来时，当前进程的,P_cpu+1,直到,255,，而每过,1S,，内核中计算优先数的程序又将所有进程的,P_cpu-10,，当,P_cpu10,时，,P_cpu,置,0,。,这样的负反馈过程使系统中在用户态下运行的各个进程都能比较均衡地享用处理机。,P_cpu ,P_pri ,进程优先级 进程被调度的机会,进程被调度的机会 进程优先级,P_pri P_cpu,6.3.5,循环轮转调度,在分时系统中，系统规定,1,个时间片，每个进程被调度时分得,1,个时间片，当这一时间片用完时，该进程就转为就绪态并进入就绪队列的末端。,6.3.5,循环轮转调度,简单循环轮转调度,时间片,q,固定,，,q=t/n,t,为用户可接受的响应时间,n,为进入系统的最大进程数,如,t=3s,n=100,则,q=30ms,如果,q,太大，则退化为,FIFO,算法,如果,q,太小，则会导致系统开销的增加。切换占,时间片,10%,。,q,的值通常为几百,ms,6.3.5,循环轮转调度,2,、,可变时间片轮转调度,例如：,t=3s,n=6,如图所示,此时,q1=3s/6=500ms,在轮转过程中，如果有新的进程到达，都暂时不进入就绪队列。,如果此时到达,24,个进程，经过一轮后，,n=24+6=30,此时,q2=3/30=100ms,。,可以减少系统开销,。,CPU,PCB1,PCB2,PCB6,就绪队列,6.3.6,多级反馈队列调度,1.,当上一个队列空时，才调度下一个队列；,2.,当,1,个进程的时间片用完时，进入下一个就绪队列；,3.,当进程由等待变成就绪时，进入第,1,个队列；,这种算法可以先用较小的时间片处理,完,那些需时间较短的进程，,而,给那些需时间较长的进程分配较大的时间片，以