操作系统概念-第六章：CPU调度.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Shandong University,操作系统概念,第六章：CPU调度,1,CPU,调度,要解决的问题,W,HAT：按什么原则分配CPU,进程调度算法,W,HEN：何时分配CPU,进程调度的时机,HO,W,：如何分配CPU,CPU调度过程（进程的上下文切换）,2,本章主要内容,基本概念,调度准则,调度算法,多处理器调度,实时调度,算法评估,进程调度模型,3,6.1 基本概念,利用多道程序最大化CPU使用率。,CPU I/O周期 进程执行由CPU执行和I/O等待周期组成。,CPU区间分布情况,4,CPU区间和I/O区间的交替序列,5,CPU区间时间直方图,6,CPU调度程序,调度程序从内存中就绪可执行的进程里选择一个，并为其中之一分配CPU。,CPU调度决策可以如下四种情况下发生,当一个进程从运行状态切换到等待状态,当一个进程从运行状态切换到就绪状态,当一个进程从等待状态切换到就绪状态,当一个进程终止时。,当调度只能发生在第一和第四两种情况时，称调度方法是非抢占的（,nonpreemptive,）,否则调度方案就是可抢占（,preemptive,）的。,7,分派程序（Dispatcher）,分派程序是一个模块，用来将CPU的控制交给由短期调度程序所选择的进程。其功能包括,切换上下文,切换到用户模式,跳转到用户程序的合适位置以重新启动这个程序,分派延迟（dispatch latency）分派程序停止一个进程而启动另一个进程执行所要花费的时间。,8,6.3 调度算法,先到先服务调度（First Come,First Served,FCFS）,最短作业优先调度（Shortest-Job-First,SJR）,优先权调度（Priority Scheduling）,轮转法调度（Round Robin,RR）,多级队列调度（multilevel queue-scheduling）,多级反馈队列调度（multilevel feedback queue scheduling）,11,Gantt Chart,12,先到先服务调度,（FCFS）,进程,区间时间,P1,24,P2,3,P3,3,假设进程按P1、P2、P3的顺序到达。则该调度的Gantt图如下：,等待时间：P1=0;P2=24;P3=27,平均等待时间：,(0+24+27)/3=17,13,假设进程按P2,P3,P1的顺序到来，则其调度的Gannt图如下,等待时间：P1=6;P2=0;P3=3,平均等待时间：,(6+0+3)/3=3,优于前一种情况,由于所有其他进程都等待一个大进程释放CPU，就会产生护航效应（convoy effect）。与可能允许较短进程先行相比，这种效果会导致CPU和设备的使用率变得更低,先到先服务调度,（FCFS）,14,先到先服务调度,（FCFS）,特点：,“公平”；,短作业等待时间长。,15,最短作业优先调度,(Shortest-Job-First,SJR),将每个进程与其下一个CPU区间段相关联。当CPU为可用时，它会赋给具有最短后续CPU区间的进程。如果两个进程具有同样长度的CPU区间，那么可以使用FCFS调度来处理。,16,最短作业优先调度,有以下的进程和其CPU区间时间,进程,区间时间,P1 6,P2 8,P3 7,P4 3,P4 P1 P3 P2,0 3 9 16 24,SJF,是最佳的：对于给定的一组进程，,SJF,算法的平均等待时间最小。,平均等待时间：7ms,17,确定下一CPU区间的长度,只能估计CPU区间的长度，无法精确计算,下一CPU区间的长度通常可预测为以前CPU区间的测量长度的指数平均,18,指数平均计算的实例,=0,n+1,=,n,Recent history does not count.,=1,n+1,=,t,n,Only the actual last CPU burst counts.,If we expand the formula,we get:,n+1,=t,n,+(1,-,)t,n-1,+,+,(1-),j,t,n-j,+,+,(1-,),n+1,0,Since both and(1-)are less than or equal to 1,each successive term has less weight than its predecessor.,19,下一个CPU区间长度的预测,20,最短作业优先调度,(Shortest-Job-First,SJR),两种方式,非抢占式：一旦进程获得CPU就一直占据CPU，直到其CPU区间完成为止,抢占式：如果一个新来的进程其CPU区间小于当前进程的CPU区间，则抢占之。这种调度方式称为最短剩余时间作业优先（Shortest Remaining Time First,SRTF）,21,抢占式调度,有以下的进程和其CPU区间时间,进程,到达时间,区间时间,P1 0 8,P2 1 4,P3 2 9,P4 3 5,P1 P2 P4 P1 P3,0 1 5 10 17 26,22,非抢占式SJF的实例,23,抢占式SJF的实例,24,最短作业优先调度,SJF调度算法也存在不容忽视的缺点：,该算法对长作业不利。如果有一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度，也就是说,长作业可能被饿死。,由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度,该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。,25,优先级调度,（Priority Scheduling）,每个进程被赋予一个优先级数字（优先权）,CPU分配给优先权高的进程（优先级数字越小，则优先权越大）,抢占式,非抢占式,SJF是一种特定的优先权调度方法,26,优先级调度,（Priority Scheduling）,有以下的进程和其CPU区间时间,进程 运行时间 优先权,P1 10 3,P2 1 1,P3 2 4,P4 1 5,P5 5 2,P2 P5 P1 P3 P4,0 1 6 16 18 29,27,优先级调度,（Priority Scheduling）,该算法存在的问题：无穷阻塞（indefinite blocking)或者称为饥饿（starvation）,低优先权的进程可能永远无法执行,解决办法：老化（aging）,随着时间的推进，进程的优先权逐渐提高,28,轮转法调度,（Round Robin）,轮转法是专门为分时系统而设计的。每个进程获得一小片CPU时间量（time quantum），通常为10-100毫秒。时间片结束后，进程被抢占并放入到就绪队列的最后重新参加调度。,如果就绪队列中有n个进程，具时间片为q，则每个进程会得到1/n的CPU时间，每个长度不超过q时间单元。每个进程必须等待CPU的时间不会超过(n-1)q个时间单元，直到它的下一个时间片为止。,29,轮转法调度,（Round Robin）,有以下的进程和其CPU区间时间,进程 运行时间,P1 24,P2 3,P3 3,时间片如果是4ms,P1 P2 P3 P1 P1 P1 P1 P1,0 4 7 10 14 18 22 26 30,30,时间片20时的RR实例,31,性能依赖于时间片的大小,如果时间片非常大（无限），那么RR策略与FCFS策略一样。,如果时间片很小，那么RR方法称处理器共享。n个进程对于用户来说都有它自己的处理器，速度各为真正处理器速度的1/n,32,时间片与上下文切换开销,q必须大于上下文切换所需时间,33,周转时间随时间片大小而改变,34,轮转法调度,时间片选择问题：,固定时间片,可变时间片,与时间片大小有关的因素：,系统响应时间,就绪进程个数,CPU能力,35,多级队列调度,根据进程的属性（内存、优先权和类型）将就绪队列分成几个相对独立的队列,前台（或交互式）,后台（或批处理）,每个队列有自己的调度算法,前台：RR,后台：FCFS,队列之间必须有调度,通常采用固定优先权可抢占调度来实现。,另一种可能是在队列之间划分时间片。每个队列都有一定的CPU时间，这可用于调度队列内的不同进程,20给后台，80给前台,36,多级队列调度示意图,37,多级队列调度,特点：,1、不够灵活,38,多级反馈队列调度,(Multilevel Feedback Queue Scheduling),通常，多级反馈队列调度程序可由下列参数来定义：,队列数量,每个队列的调度算法,用以确定进程何时升级到较高优先权队列的方法,用以确定进程何时降级到较低优先权队列的方法,用以确定进程在需要服务时应进入哪个队列的方法,39,多级反馈队列调度,(Multilevel Feedback Queue Scheduling),进程可以在不同队列间移动,*首先系统中设置多个就绪队列,*每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大,*各个队列按照先进先出调度算法,*一个新进程就绪后进入第一级队列,*进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列,*当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾,*当第一级队列空时，就去调度第二级队列，如此类推,*当时间片到后，进程放弃CPU，回到下一级队列,40,多级反馈队列调度的实例,三个队列,Q,0,：时间片为8毫秒,Q,1,：时间片为16毫秒,Q,2,：FCFS,41,多级反馈队列调度的实例,调度,进入就绪队列的进程被放在队列Q,0,内。队列0的每个进程都有8ms的时间片。如果一个进程不能在这一时间内完成，那么它就被移到队列1的尾部。,如果队列0为空，队列1头部进程会得到一个16ms的时间片。如果它不能完成，那么它将被抢占，并被放到队列2中。,只有当队0和队1为空时，队列2内的进程才可根据FCFS来运行。,42,多级反馈队列调度,调度效果：,资源利用率高,被调度的进程尽早投入运行；,响应速度快,交互式进程反应及时；,系统开销小,计算量大的进程落入底层队列。,实现复杂,43,6.4 多处理器调度,问题：,M,processes(threads),N,processors,SMP：all processors are identical(homogeneous),目标：load-sharing,separate ready queue for each processor,not really balanced;,common ready queue,Q,for all processors,each process accesses,Q,on its own,master/slave assignment.,44,自调度(self scheduling),均衡调度(balanced scheduling),一个就绪队列(多处理机访问互斥),优点,不需要专门的处理机从事任务分派工作,任务分配均衡,缺点,当CPU较多时,就绪队列成为瓶颈,线程两次调度可能处于不同处理机,不能保证同组线程同时调度,mach,45,自调度(self scheduling),就绪队列,进程(线程),进程(线程),进程(线程),CPU,CPU,CPU,46,主从调度（非对称多处理器）,就绪队列,进程(线程),进程(线程),进程(线程),CPU,CPU,CPU,CPU,47,6.5 实时调度,实时任务（实时计算）：,具有明确时间约束的计算任务。,实时调度：,合理安排就绪实时任务的执行次序，满足每个实时任务时间约束条件的调度。,48,6.5 实时调度,硬实时系统：,需要在保证的时间内完成关键任务,在提交进程时，同时有一条语句告诉系统用来完成或执行I/O所需要的时间。接着，调度程序或者允许进程并保证进程能按时完成，或者因不可能而拒绝请求。（资源预约）,软实时系统：,要保证关键进程拥有比其他进程更高的优先权,要求仔细设计调度程序和操作系统有关方面。,第一、系统必须有优先权调度，且实时进程必须有最高的优先权。实时进程的优先权不能随时间而下降，尽管非实时进程的优先权可以。,实时进程不应该老化,第二、分派延迟必须小。,内核抢占，在长时间系统调用内插入抢占点,49,分派延迟,1、抢占运行在内核中的进程。,2、低优先级进程释放其所需资源。,50,分派延迟,优先权倒置问题,高优先权进程需要等待低优先权进程的完成,优先权继承协议,所有的低优先权进程继承了高优先权，直到相关资源处理完毕。,51,6.6 算法评估,定义准则,CPU使用率,吞吐量,周转时间,等待时间,响应时间,最大化CPU使用率，同时规定最大响应时间,最大化吞吐量，要求周转时间与执行时间成线性关系,52,6.6 算法评估,分析评估法：,使用给定算法和系统负荷，产生一个公式或数字，以评估针对该负荷算法的性能。,确定性建模：采用特定预先确定的负荷，定义在给定负荷下每个算法的性能。,53,确定性建模,进程和其CPU区间时间,进程 运行时间,P1 10,P2 29,P3 3,P4 7,P5 12,P1 P2 P3 P4 P5,0 10 39 42 49 61,P3 P4 P1 P5 P2,0 3 10 20 32 61,P1 P2 P3 P4 P5 P2 P5 P2,0 10 20 23 30 40 50 52 61,FCFS,SJF,RR,54,确定性建模,简单快速，给出了确切数字，以允许算法被比较,但通常过分特殊且要求过多精确知识，故用处有限,55,排队模型,排队模型：,在许多系统上运行的进程每天都在变化，因此没有静态的进程集合和时间用于确定性建模。,CPU、I/O区间分布，到达率，服务率,n,为平均队列长度（不包括正在服务的进程）,为队列的平均等待时间,为新进程到达队列的平均到达率,n,=,W,(Little公式),可用于比较调度算法，但计算结果的精确性值得怀疑,56,通过模拟来评估CPU调度算法,57,实现,即使是模拟其精确度也是有限的。针对评估调度算法，惟一完全精确的方法是对它进行程序编码，将其放在操作系统内，并观测它如何工作。,主要困难是这种方法的代价,对算法编码、修改操作系统以支持该算法,另一困难是算法所使用的环境会变化,最为灵活的调度算法可以为系统管理员或用户所改变,58,进程调度模型,Solaris 2：基于优先级的进程调度,59,进程调度模型,Windows 2000：基于优先权、可抢占调度算法,可变类型115,实时类型1631,Linux：分时算法用于多个进程间公平可抢占式调度,为实时任务的算法、规定内核模式下运行的进程不能被抢占,60,Linux,调度,两种算法：分时与实时,分时,基于信用度的算法,信用度随着定时器中断的发生而降低,当所有进程的信用度都为0的时候，则重新计算信用度,这种算法似乎混合了两个因素：进程历史和它的优先级,实时,软实时,实现了两种POSIX.1b所要求的实时调度类型：FCFS 和 RR,高优先级的进程总是最先运行,61,