1、第四讲 CPU调度,中国科学技术大学计算机系 陈香兰Fall 2013,内容提要,调度的类型调度的队列模型调度的准则调度的算法,内容提要,调度的类型调度的队列模型调度的准则调度的算法,调度的类型,按调度的层次：长期（长程、作业、高级）调度；中期（中级、中程）调度；短期（短程、进程、低级）调度按OS的类型：批处理调度分时调度实时调度多处理机调度等等,作业调度,在批处理系统中，一般需要进行作业调度；分时系统和实时系统大多不需要作业调度作业调度要考虑1）接纳多少个作业多道程序度2）接纳哪些作业调度算法,中期调度,与挂起状态相关目的：提高内存利用率和系统吞吐量对换,进程调度,在分时系统中，进程调度的运
2、行频率很高Linux中，常规经验值，时间片大小50ms左右进程调度要考虑1）什么时候 发生调度的时机2）哪个进程 调度原则和调度算法3）如何分派 进程上下文切换,调度的方式：抢占式非抢占式,可剥夺式（可抢占式Preemptive）： 当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用不可剥夺式（不可抢占式 Non-preemptive ）： 某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去,Scheduling time 调度的时机,When a processSwitches from running to wa
3、iting stateSwitches from running to ready stateSwitches from waiting to readyTerminatesSchedulingNonpreemptive: for 1 & 4Till 1 or 4Win 3.x, old versions of MacOS, Preemptive: for 2 & 3根据时间片抢占、根据优先关系抢占,与进程调度相关的进程运行规律分析,Process execution = n (CPU execution + I/O wait)Objective of multiprogrammingMaxi
4、mum CPU utilization Scheduling is a fundamental OS function for almost all resources,Alternating Sequence of CPU And I/O Bursts,A property of process：CPU-I/O burst cycleProcess Starts as a CPU burstEnds as a CPU burstCPU burst distributionCPU-bound VS. I/O-bound,Histogram of CPU-burst Times,内容提要,调度的
5、类型调度的队列模型调度的准则调度的算法,调度队列模型,按照系统中调度层次的数目，有3种模型仅有进程调度的具有高级和低级调度的同时具有三种调度的,仅具有进程调度的调度队列模型,具有高、低两级调度的调度队列模型,具有三级调度的调度队列模型,内容提要,调度的类型调度的队列模型调度的准则调度的算法,选择调度方式和算法的若干准则,面向用户的准则周转时间短响应时间快截止时间的保证优先权准则面向系统的准则系统吞吐率高处理机利用率好各类资源的平衡利用,面向用户的准则：1、周转时间短,定义：作业周转时间(Turnaround time)是指从作业提交给系统开始，到作业完成为止的这段时间间隔。包括：1）作业在外存
6、后备队列上等待作业调度的时间2）进程在就绪队列上等待进程调度的时间(waiting time)3）进程在CPU上执行的时间4）等待I/O操作完成的时间 其中，第2、3、4项在一个作业的处理过程中，可能发生多次用户和系统管理员对周转时间有不同的需求,定义：平均周转时间定义：带权周转时间：作业周转时间T与系统为它提供的实际服务时间Ts之比，即W=T/Ts定义：平均带权周转时间：通常将周转时间作为评价批处理系统的性能、选择作业调度方式和算法的准则,面向用户的准则：2、响应时间快,定义：响应时间(Response time)是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的的时间，或者说直到
7、在屏幕上显示出结果为止的一段时间间隔。包括：从键盘输入的请求信息传送到处理机的时间处理机对请求信息进行处理的时间将所形成的响应回送到终端显示器的时间响应时间常用于评价分时操作系统的性能，是选择分时系统中进程调度算法的重要准则之一,面向用户的准则：3、截止时间的保证,定义：截止时间(Deadline)是指某任务必须开始执行的最迟时间，或者必须完成的最迟时间。截止时间是用来评价实时系统性能的重要指标，因而是选择实时调度算法的重要准则实时系统软实时系统(soft real-time) vs 硬实时系统(hard real-time)非实时系统,面向用户的准则：4、优先权准则,引入优先权使用优先数表示
8、优先权优先权高者优先执行必要时，引入抢占,面向系统的准则：1、系统吞吐率高,定义：吞吐率(Throughput)是指系统在单位时间内完成的作业数是用于评价批处理系统性能的重要指标，也是用于选择批处理作业调度的重要准则吞吐率与作业的平均长度有关大型作业中、小型作业吞吐率与作业的调度算法也有关,面向系统的准则：2、处理机利用率好,CPU是稀缺资源定义：处理器利用率（CPU Utilization） =进程调度方式和算法对CPU利用率起着十分重要的作业对于大中型多用户系统，CPU利用率是衡量系统性能的重要指标40%90%,面向系统的准则：3、各类资源的平衡利用,除CPU之外的其他资源，例如内存、外存、I/O设备,
