单处理器调度

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算机科学系 操作系统课程组 李才伟,&,凌应标制作,2015,年,6,月,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,第四部分,调度,第,9,章 单处理器调度,第,10,章 多处理器和实时调度,主要内容：,处理器调度的类型,单处理器调度算法,传统,Unix,调度,多处理器调度,实时调度,Linux,调度,Unix FreeBSD,调度,Unix SVR4,调度,Windows,调度,Linux,虚拟机进程调度,2,9.1 处理器调度的类型,决定处理器要执行哪些进程,长程调度（,Long-term scheduling）,决定哪些新建进程可进入系统准备执行,控制多道程序系统的并发程度,进程越多则各进程对,CPU,的使用百分比越小,中程调度,(Medium-term scheduling),决定交换哪些主存辅存（内存,-,外存）进程,基于多道程序设计的管理需要,短程调度,(Short-term scheduling),决定下一个使用,CPU,的进程（,dispatcher,，分派程序）,I/O,调度（第,11,章,不是处理器调度）,决定可用的,I/O,设备处理哪个进程挂起的,I/O,请求,3,调度与进程状态转换,事件等待,事件发生,事件发生,超时,4,调度的层次,短程,运行,就绪,阻塞,阻塞/挂起,就绪/挂起,新建,退出,中程,长程,5,调度队列,6,短程调度时机,当前进程正常或异常终止（通过中断实现）,时钟或,I/O,中断,系统调用（通过软中断实现）,信号量操作（通过软中断实现）,7,短程调度模式,非剥夺式（,nonpreemptive）,让进程运行直到结束或阻塞的调度方式,容易实现,适合专用系统，不适合通用系统,剥夺式（,preemptive）,允许将逻辑上可继续运行的进程在运行过程中暂停的调度方式,可防止单一进程长时间独占,CPU,系统开销大（降低途径：硬件实现进程切换，或扩充主存以贮存大部分程序）,8,短程调度过程,进程上下文切换过程,基本过程,保存现场,根据某种调度算法选择下一个要运行的进程，如果没有就绪进程，系统会安排一个空闲进程(,idle)，,没有其他进程时该进程一直运行，在执行过程中可接收中断,恢复现场,9,短程调度目标,面向用户的目标与面向系统的目标,定量目标与定性目标,主要的目标,公平,确保每个进程都获得合理的,CPU,份额,效率,使,CPU,及其他系统资源尽量忙碌,响应时间（从提交到开始输出结果）,尽可能短,在交互式系统中尤为重要,周转时间,T,r,（,turnaround time,：从提交到结束）（也叫驻留时间，,residence time,）,尽可能短,吞吐量（单位时间内完成的进程数）,尽可能大,实时性,可以指定进程完成的最后期限,其他,10,9.2 进程调度算法,先来先服务,(First Come First Served,，,FCFS),最短进程优先,(Shortest Process Next,，,SPN),最短剩余优先,(Shortest Remaining Time,，,SRT),最高响应比优先,(Highest Response Ratio Next,，,HRRN),时间片（,time slicing,）轮转,(Round Robin,，,RR),最高优先级优先,(Highest Priority First,，,HPF),多级队列反馈,(Multilevel Feedback,，,MF/FB),11,各种调度策略的特点,类别,缩写,先来先服务,FCFS,轮转,RR,最短进程,优先,SPN,最短剩余优先,SRT,最高响应比,优先,HRRN,反馈,MF/FB,选择函数,max(w),常数,min(s),min(s-e),max(w+s)/s),e,优先级,决策模式,非抢占,抢占,(,时间片,),非抢占,抢占,(,到达时,),非抢占,抢占,(,时间片,),吞吐量,不强调,时间片太小时会低,高,高,高,不强调,响应时间,可能大,短进程小,短进程小,小,小,不强调,开销,最小,最小,可能高,可能高,可能高,可能高,对进程的影响,对短进程和,I/O,密集进程不利,公平对待,对长进程,不利,对长进程,不利,很好的平衡,可能对,I/O,密集进程有利,饥饿,无,无,可能,可能,无,可能,w,：已等待时间、,e,：已执行时间、,s,：进程所需总服务时间,12,进程调度例,进程,到达时间,服务时间,A,0,3,B,2,6,C,4,4,D,6,5,E,8,2,13,先来先服务（,FCFS）,当前进程结束后，选择最早到达就绪队列的那个进程（非剥夺式）,短进程等待执行的时间可能相当长,I/O,密集进程必须等待,CPU,密集进程结束,14,最短进程优先（,SPN）,每次调度选取估计运行时间最短的进程,不可剥夺式（不适合分时和事务处理系统）,“长”进程可能饿死,15,最短进程优先（,SPN）,难点：预知或估计进程的执行时间,生产环境：统计,交互式环境：估计,进程执行时间的估计：“指数平滑”技术,S,n,：,第,n,个实例执行时间的估计值,T,n,：,第,n,个实例执行时间的测量值,a,：,加权系数，,a,值越大，对变化反应越快,(,对老的运行时间忘记得越快,)(,0,a,q,qs,20,虚拟轮转,VRR,（,Virtual Round Robin,）,阻塞解除的进程进入辅助队列,辅助队列中的进程比就绪队列的优先获得处理器,可解决轮转对,I/O,密集型进程的不公平性问题,21,最高优先级优先（,HPF）,每个进程被赋予一个优先级（,priority,），每次调度选取就绪队列中优先级最高的进程投入运行,优先级确定方法：,静态：进程创建时指定优先级，在进程运行时优先级保持不变,动态：在进程创建时指定一个优先级，但在其生命周期内优先级可以动态变化（如等待时间长的优先级可提高，时间片过后的优先级可降低）,实现时可对应不同优先级采用多个就绪队列,22,优先级排队,23,多级队列反馈（,MF/FB）,剥夺式、时间片,关注进程已执行的时间，不用估计（剩余）执行时间,思想：采用动态优先级机制,设立多个优先级就绪队列，各个队列运行时间片可能不同（优先级越高,i,越小,时间片越小：2,i,）,新的就绪进程进入最高优先级队列,进程由于时间片用完被抢占而放弃,CPU，,下降一个优先级队列,（最高最低）,进程由于等待而放弃,CPU,后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列,在各优先级队列中采用,FCFS（,最低级队列中采用,RR）,24,多级队列反馈（,MF）,续,25,多级队列反馈（,MF）,续,调度：先按,FCFS,从最高优先级队列中选取，若最高优先级队列为空，按,FCFS,从次高优先级队列选取,26,9.2.4 性能比较,响应时间,短进程,(,高,优先级,),的标准化响应时间,归一化响应时间,=,周转时间,Tr,/,平均服务时间,Ts,=1/,（,1-,处理器利用率,）,27,性能比较,响应时间（续）,长进程,(,低,优先级,),的标准化响应时间,28,性能比较,周转时间,仿真建模,50,000,个仿真进程，按服务时间分成,100,组，,80,CPU,利用率（所需时间的百分点,进程服务时间长度）,归一化周转时间,=Tr/Ts,其中：,Tr=,周转时间,Ts=,服务时间,29,性能比较,等待时间,30,9.2.5,公平共享调度,用户应用或作业可以是一个进程（或线程）集合，而用户关心的是应用或作业的整体性能，因此应该基于进程集合进行调度决策,一个用户也可看成是一个用户组的成员，同一用户组的用户应只影响本用户组的调度而不影响其他用户组的调度，即应基于用户组进行调度决策,公平共享调度（,Fair-Share Scheduling,，,FSS,）：基于组调度，每个组公平共享处理器时间,每个用户被指定某种类型的权值，以定义其使用共享资源的份额,31,公平共享调度示例,进程,j,在时间段,i,开始处的,优先级：,P,j,(i)=Base,j,+CPU,j,(i)/2,+GCPU,j,(i)/4W,k,其中：,进程,j,的基础优先级,Base,j,=60,进程,j,在时间段,i,中处理器使用计数,CPU,j,(i)=CPU,j,(i-1)/2,组,j,在时间段,i,中处理器使用计数,GCPU,j,(i)=GCPU,j,(i-1)/2,分配给组,k,的权值,W,k,=0.5,32,9.3 传统,Unix,调度,Unix SVR3,、,4.3BSD Unix,分时交互系统,多级队列反馈，其中每个优先级队列采用,RR,优先级一秒重新计算一次,优先级基于进程类型和执行历史,P,j,(i)=Base,j,+CPU,j,(i)/2+nice,j,CPU,j,(i)=CPU,j,(i-1)/2,基本优先级,Base,取决于进程类型所属的优先级固定区间，以下区间优先级依次递减：,交换程序、块,I/O,设备控制、文件操作、字符,I/O,操作、用户进程,调整因子,nice,用于保证进程优先级不超出其区间范围,33,传统,Unix,的进程调度,调度由0号进程完成：始终在核心态执行，与其他进程并不完全一样。采用,时间片、多级反馈队列、核心优先级、用户优先级,时机：,进程由核心态转入用户态时：在每次执行核心代码之后返回用户态之前，检查各就绪进程的优先级并进行调度。如中断进程回到就绪队列,进程主动放弃处理机时：进程申请系统资源而未得到满足（如,read），,或进行进程间同步而暂停（如,wait,或,pause）,进程退出（如,exit）,进程进入阻塞队列或,exit,状态,34,用户优先级,进程在用户态和核心态的优先级是不同的，这里说的是用户态进程的优先级。它是基于执行时间的动态优先级，进程优先级可为0127之间的任一整数（共,128,个）。优先数越大，优先级越低,049之间的优先级（共,50,个）为系统内核保留,用户态下的进程优先级为50127之间（共,78,个）,在,Unix System V,中，进程优先数：,P_pri=P_CPU/2+PUSER+P_nice+NZERO,35,习题,必做：,9.2(P301),、,9.16(P303),选做：,9.1,、,9.14,、编程项目,2-,主机调度,shell,程序,