09单处理器调度.

计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月1第四部分调度第9章单处理器调度第10章多处理器和实时调度主要内容：处理器调度的类型单处理器调度算法传统Unix调度多处理器调度实时调度Linux调度UnixFreeBSD调度UnixSVR4调度Windows调度Linux虚拟机进程调度计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月29.1处理器调度的类型决定处理器要执行哪些进程长程调度（Long-termscheduling）决定哪些新建进程可进入系统准备执行控制多道程序系统的并发程度进程越多则各进程对CPU的使用百分比越小中程调度(Medium-termscheduling)决定交换哪些主存－辅存（内存-外存）进程基于多道程序设计的管理需要短程调度(Short-termscheduling)决定下一个使用CPU的进程（dispatcher，分派程序）I/O调度（第11章——不是处理器调度）决定可用的I/O设备处理哪个进程挂起的I/O请求计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月3调度与进程状态转换事件等待事件发生事件发生超时计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月4调度的层次短程运行就绪阻塞阻塞/挂起就绪/挂起新建退出中程长程计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月5调度队列计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月6短程调度时机当前进程正常或异常终止（通过中断实现）时钟或I/O中断系统调用（通过软中断实现）信号量操作（通过软中断实现）计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月7短程调度模式非剥夺式（nonpreemptive）让进程运行直到结束或阻塞的调度方式容易实现适合专用系统，不适合通用系统剥夺式（preemptive）允许将逻辑上可继续运行的进程在运行过程中暂停的调度方式可防止单一进程长时间独占CPU系统开销大（降低途径：硬件实现进程切换，或扩充主存以贮存大部分程序）计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月8短程调度过程进程上下文切换过程基本过程保存现场根据某种调度算法选择下一个要运行的进程，如果没有就绪进程，系统会安排一个空闲进程(idle)，没有其他进程时该进程一直运行，在执行过程中可接收中断恢复现场计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月9短程调度目标面向用户的目标与面向系统的目标定量目标与定性目标主要的目标公平——确保每个进程都获得合理的CPU份额效率——使CPU及其他系统资源尽量忙碌响应时间（从提交到开始输出结果）——尽可能短在交互式系统中尤为重要周转时间Tr（turnaroundtime：从提交到结束）（也叫驻留时间，residencetime）——尽可能短吞吐量（单位时间内完成的进程数）——尽可能大实时性——可以指定进程完成的最后期限其他计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月109.2进程调度算法先来先服务(FirstComeFirstServed，FCFS)最短进程优先(ShortestProcessNext，SPN)最短剩余优先(ShortestRemainingTime，SRT)最高响应比优先(HighestResponseRatioNext，HRRN)时间片（timeslicing）轮转(RoundRobin，RR)最高优先级优先(HighestPriorityFirst，HPF)多级队列反馈(MultilevelFeedback，MF/FB)计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月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：进程所需总服务时间计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月12进程调度例进程到达时间服务时间A03B26C44D65E82计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月13先来先服务（FCFS）当前进程结束后，选择最早到达就绪队列的那个进程（非剥夺式）短进程等待执行的时间可能相当长I/O密集进程必须等待CPU密集进程结束计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月14最短进程优先（SPN）每次调度选取估计运行时间最短的进程不可剥夺式（不适合分时和事务处理系统）“长”进程可能饿死计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月15最短进程优先（SPN）难点：预知或估计进程的执行时间生产环境：统计交互式环境：估计进程执行时间的估计：“指数平滑”技术Sn：第n个实例执行时间的估计值Tn：第n个实例执行时间的测量值a：加权系数，a值越大，对变化反应越快(对老的运行时间忘记得越快)(0a1)(P290图9.8)nnnSaaTS)1(1计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月16最短剩余优先（SRT）剥夺式的SPN新进程进入就绪队列时将引发重新调度选取估计剩余时间最短的那个进程需要估计进程剩余执行时间“长”进程可能饿死计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月17最高响应比优先（HRRN）非剥夺式每次调度选取响应比R最大的那个进程w：等待CPU的时间s：估计执行时间利短进程，但长进程也不会饿死同SPN、SRT，要估计执行时间sswRR计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月18时间片轮转（RR）剥夺式的FCFS把CPU划分成若干时间片,并且按顺序分配给就绪列队中的各个进程当时间片用完而当前进程尚未结束时，系统剥夺该进程的CPU，将该进程排列到就绪队列的末尾，同时选择就绪队列头的进程运行计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月19时间片轮转（RR）（续）时间片（timeslice/quantum）长度的选择问题：太短：切换开销大太长：响应时间变长一般比典型的一次交互过程时间略长分时系统和事务处理系统中常用时间片轮转法利CPU密集进程，不利I/O密集进程sqsq-ss：响应时间q：时间片sqqs计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月20虚拟轮转VRR（VirtualRoundRobin）阻塞解除的进程进入辅助队列辅助队列中的进程比就绪队列的优先获得处理器可解决轮转对I/O密集型进程的不公平性问题计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月21最高优先级优先（HPF）每个进程被赋予一个优先级（priority），每次调度选取就绪队列中优先级最高的进程投入运行优先级确定方法：静态：进程创建时指定优先级，在进程运行时优先级保持不变动态：在进程创建时指定一个优先级，但在其生命周期内优先级可以动态变化（如等待时间长的优先级可提高，时间片过后的优先级可降低）实现时可对应不同优先级采用多个就绪队列计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月22优先级排队计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月23多级队列反馈（MF/FB）剥夺式、时间片关注进程已执行的时间，不用估计（剩余）执行时间思想：采用动态优先级机制设立多个优先级就绪队列，各个队列运行时间片可能不同（优先级越高[i越小]时间片越小：2i）新的就绪进程进入最高优先级队列进程由于时间片用完被抢占而放弃CPU，下降一个优先级队列（最高－最低）进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列在各优先级队列中采用FCFS（最低级队列中采用RR）计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月24多级队列反馈（MF）续计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月25多级队列反馈（MF）续调度：先按FCFS从最高优先级队列中选取，若最高优先级队列为空，按FCFS从次高优先级队列选取……计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月269.2.4性能比较—响应时间短进程(高优先级)的标准化响应时间归一化响应时间=周转时间Tr/平均服务时间Ts=1/（1-处理器利用率ρ）计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月27性能比较—响应时间（续）长进程(低优先级)的标准化响应时间计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月28性能比较—周转时间仿真建模—50,000个仿真进程，按服务时间分成100组，80％CPU利用率（所需时间的百分点~进程服务时间长度）归一化周转时间=Tr/Ts其中：Tr=周转时间Ts=服务时间计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月29性能比较—等待时间计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月309.2.5公平共享调度用户应用或作业可以是一个进程（或线程）集合，而用户关心的是应用或作业的整体性能，因此应该基于进程集合进行调度决策一个用户也可看成是一个用户组的成员，同一用户组的用户应只影响本用户组的调度而不影响其他用户组的调度，即应基于用户组进行调度决策公平共享调度（Fair-ShareScheduling，FSS）：基于组调度，每个组公平共享处理器时间每个用户被指定某种类型的权值，以定义其使用共享资源的份额计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月31公平共享调度示例进程j在时间段i开始处的优先级：Pj(i)=Basej+CPUj(i)/2+GCPUj(i)/4Wk其中：•进程j的基础优先级Basej=60•进程j在时间段i中处理器使用计数CPUj(i)=CPUj(i-1)/2•组j在时间段i中处理器使用计数GCPUj(i)=GCPUj(i-1)/2•分配给组k的权值Wk=0.5计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月329.3传统Unix调度UnixSVR3、4.3BSDUnix分时交互系统多级队列反馈，其中每个优先级队列采用RR优先级一秒重新计算一次优先级基于进程类型和执行历史Pj(i)=Basej+CPUj(i)/2+nicejCPUj(i)=CPUj(i-1)/2基本优先级Base取决于进程类型所属的优先级固定区间，以下区间优先级依次递减：交换程序、块I/O设备控制、文件操作、字符I/O操作、用户进程调整因子nice用于保证进程优先级不超出其区间范围计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月33传统Unix的进程调度调度由0号进程完成：始终在核心态执行，与其他进程并不完全一样。采用时间片、多级反馈队列、核心优先级、用户优先级时机：进程由核心态转入用户态时：在每次执行核心代码之后返回用户态之前，检查各就绪进程的优先级并进行调度。如中断――进程回到就绪队列进程主动放弃处理机时：进程申请系统资源而未得到满足（如read），或进行进程间同步而暂停（如wait或pause）进程退出（如exit）――进程进入阻塞队列或exit状态计算机科学系操作系统课程组李才伟&凌应标制作@2015年6月34用户优先级进程在用户态和核心态的优先级是不同的，这