第6讲处理机调度课件

操作系统原理（六）处理机调度6.1概述如何从作业中挑选作业进入主存运行、如何在进程之间分配处理器时间，无疑是操作系统资源管理中的一个重要问题。这一涉及处理器分配的问题，称之为处理器调度。第六章处理机调度6.1处理机的二级调度w宏观上：作业调度w微观上：进程调度第六章处理机调度6.1处理机的二级调度w作业调度又称为宏观调度。w任务对存放在辅存设备上的大量作业，以一定的策略进行挑选，分配主存等必要的资源，建立作业对应的进程，使其投入运行第六章处理机调度6.1处理机的二级调度w进程调度又称为微观调度。任务对进入主存的所有进程，确定哪个进程在什么时候获得处理机，使用多长时间。6.1处理机的二级调度处理机的二级调度处理机的二级调度处理机的二级调度 6.1.1 作业调度1.处理的对象：作业2.所使用的数据结构w作业控制块(JCB)w后备作业队列3.任务：n要选择一个作业，分配内存和必要的外设，建立一个进程。1.处理的对象：处理的对象：w进程进程 2.所使用的数据结构所使用的数据结构wpcb w就绪队列就绪队列 3.任务：任务：n确定什么时间，将确定什么时间，将CPU给哪一个进程给哪一个进程并确定使用多长时间。并确定使用多长时间。6.1.2进程调度进程调度 作业和进程的关系小结作业和进程之间的主要关系：作业和进程之间的主要关系：1.作业是作业是任务实体任务实体，进程是，进程是完成任务完成任务的的执执行实体行实体;2.没有作业任务，进程无事可干，没有进没有作业任务，进程无事可干，没有进程，作业任务没法完成。程，作业任务没法完成。3.作业概念更多地用在批处理操作系统，作业概念更多地用在批处理操作系统，而进程则可以用在各种多道程序设计系而进程则可以用在各种多道程序设计系统。统。6.2作业调度6.2.1作业调度的功能作业调度的主主要要任任务务是：完成作业从后备状态到执行状态和从执行状态到完成状态的转变。三、三、1.区别：w对象、数据结构和任务不同。2.关联：w作业调度是对使用CPU的顾客进行预分w进程调度是对使用CPU的顾客进行具体分配外存CPU内存6.1.3作业调度与进程的作业调度与进程的关联与区别关联与区别 6.2作业调度作业调度 执行运行运行就绪就绪等待等待后备提交完成作业录入作业调度作业调度作业调度作业调度6.2作业调度6.2.2作业控制块（JCB，JobControlBlock）w每个作业进入系统时由系统为其建立一个作业控制块JCB（Job Control Block)，它是存放作业控制和管理信息的数据结构，主要信息见右图。6.2.1 作业调度的功能作业调度的功能1.记录进入系统的各作业情况1)建立相应JCB（作业控制块）2)组成后备作业队列3)作业完成时，撤消JCBwJCB的作用：作业调度和资源分配的依据。6.2作业调度作业调度 一道考研题对作业进行管理和调度的重要的数据结构是（）（2002年华中科技大学）作业控制块（JCB）2.策略：按一定的策略，从后备作业队列中挑选一个或几个作业投入运行。3.为选中的作业分配资源（如：内存、外设）4.作业运行结束作善后处理5.模块功能实现：创建一个进程6.2.1 作业调度的功能作业调度的功能1.目标1)公平性2)吞吐率高3)设备利用率4)快的周转时间2.如何衡量调度算法的好坏1)对批处理系统：周转时间、带权周转时间2)对分时系统和实时系统：响应时间 6.2.2 作业调度的目标和调度性能的衡量作业调度的目标和调度性能的衡量 6.2.3调度性能的衡量作业调度算法规定了从后备作业中选择作业进入系统内存的原则，这些原则的性能如何，就是本节所讨论的问题。一、确定调度算法时应考虑的因素1.应与系统的整体设计目标一致2.考虑系统中各种资源的负载均匀3.保证作业的执行4.对一些专用资源的使用特性的考虑6.2.3调度性能的衡量w二、调度性能的衡量w通常采用平均周转时间和带权平均周转时间w作业的周转时间：wti=tci-tsiwti:作业周转时间wtci：作业完成时间wtsi:作业提交时间w周转时间包括等待时间和运行时间一道考研题（西安电子科技大学一道考研题（西安电子科技大学2000）设有4个作业同时到达，每个作业的执行时间均为2个小时，它们在一台处理机上按单道方式执行，则平均周转时间为（）A1小时，B5小时C2.5小时D8小时答案B（平均作业周转时间=（2+（2+2）+（2+2+2）+（2+2+2+2）/4=5小时6.2.3调度性能的衡量 t i r iw i=1+等待等待+运行运行 运行运行等待等待 运行运行6.2.4先来先服务调度算法和短作业优先调度算法1.先来先服务调度算法（FCFS）：先来先服务算法是按作业来到的先后次序进行调度的这种调度算法突出的优点是实现简单，效率较低，在一些实际的系统和一般应用程序中采用这种算法的较多。6.2.4先来先服务调度算法和短作业优先调度算法短作业优先调度算法(SJFShortestJobFirst)：短作业优先调度算法考虑作业的运行时间，每次总是从就绪队列中选择一个运行时间最小的作业调入内存（系统）.一道考研题华中科技大学2001年6.2.3作业调度算法作业调度算法 先来先服务调度算法和短作业优先调度算法340.8010.3010.100.209.50446.51.3010.8010.600.209.5042111.1010.1010.000.109.0033161.6010.6010.500.109.00344.62.3010.8010.300.508.502242.0010.5010.000.508.502112.0010.008.002.008.001112.0010.008.002.008.001执行顺序带权周转时间周转时间完成时间开始时间运行时间提交时间作业先来先服务调度算法平均周转时间 t=1.725平均带权周转时间 w=6.875短作业优先调度算法平均周转时间 t=1.55平均带权周转时间 w=5.15一道考研题华中科技大学2001填空题：在作业调度算法中，（）调度算法的调度性能要好些答案：短作业优先（SJF）一道考研题（华中科技大学一道考研题（华中科技大学2000）某系统采用短作业优先的调度策略，现有作业序列：作业1（提交时间：8:00,运行时间1.50），作业2（提交时间：8:30,运行时间0.80）作业3（提交时间：9:00,运行时间0.10），作业4（提交时间：9:30,运行时间0.30），单位：小时，以十进制计。其平均带权周转时间为：（）A4.65B3.00C5.52D12.23答案B6.2.5其它几种调度算法w先来先服务和短作业优先算法都有其片面性：w先来先服务调度算法只考虑作业的等待时间，而忽视了作业的运行时间w短作业优先算法则相反，只考虑了作业的运行时间，而忽视了作业的等待时间。w响应比高者优先调度算法是介于这两种算法之间的一种拆衷的算法。6.2.5其它几种调度算法w响应比高者优先调度算法：响应比高者优先调度算法该算法，就是每调度一个作业投入运行时，计算后备作业表中每个作业的响应比，然后挑选响应比最高的投入运行。响应比高者优先调度算法本算法优待了短作业但如果一个作业等待的时间足够长的话，其响应比也会增加，不至于无休止的运行下去。响应比高者优先调度算法（单位：小时，并以10进制算46.51.3010.8010.600.209.5042111.6010.1010.000.109.00334.22.1010.6010.100.508.502112.0010.008.002.008.001执行顺序带权周转时间周转时间完成时间开始时间运行时间提交时间作业响应比高者优先调度算法平均周转时间 t=1.625平均带权周转时间 w=5.6759.5049.0038.5028.001执行顺序带权周转时间周转时间完成时间开始时间运行时间提交时间作业2.000.50.10.26.2.5其它几种调度算法优先数调度算法优先数调度算法是终合考虑各方面的因素（作业等待时间、运行时间、缓急程度，系统资源使用等），给每个作业设置一个优先数，调度程序总是选择一个优先数最大（或者最小）的作业调入（系统）内存。这种算法实现的困难在于如何综合考虑，这些因素之间的关系怎样处理。6.3进程调度进程调度6.3.1 进程调度进程调度 又称为又称为cpu调度，其根本任务是按照某调度，其根本任务是按照某种原则为处于就绪状态的进程分配种原则为处于就绪状态的进程分配cpu1.调度：n在众多就绪状态进程中，按一定的原则选一个进程。w进程控制：对系统中的全部进程实施有效的管理2.分派n当CPU空闲时，移出n就绪队列元素，将CPUn控制权赋予它。运行运行就绪就绪等待等待控制调度控制6.3.1 进程调度进程调度3.调度/分派结构 ready-qschedulersuspwakeupreceive.pcb1pcb2pcb3pcb4pcb5dispatcherCPU6.3.1 进程调度进程调度调度分派1.记录进程的动态变化wPCBw队列2.确定调度策略w先来先服务w紧迫程度3.进程之间切换6.3.2 进程调度功能进程调度功能1.什么是调度方式当一进程正在处理机上执行，若有更高优先级的进程进入就绪队列时,如何分配处理机。2.调度方式1)非剥夺方式2)可剥夺方式 6.3.3调度方式调度方式调度方式所谓“非剥夺型调度”是指：一旦某个进程被调度执行，则该进程一直执行下去直至该进程结束，或由于某种原因自行放弃cpu进入等待状态，这时才将cpu重新分配给其他进程。所谓剥夺型调度是指：一旦就绪状态中出现优先权更高的进程，或者运行的进程已用满了规定的时间片时，便立即剥夺当前进程的运行(将其放回就绪状态)，把cpu分配给其他进程。一道考研题（南京大学1999）分析：本题是一个多道系统兼有作业调度和进程调度的计算机体。其执行过程可以借助图示的方法加以描述：J30tJ2J1102030405060708090I02 30msCPU 10msI01 30msCPU 10msCPU 10msI01 20msCPU 10msI02 40msCPU 20msCPU 10msI01 20ms进程运行示意图解答（1）由上图可以看出，J1从开始到完成的时间为080ms，J2从开始到完成的时间为090ms，J3从开始到完成的时间为090ms（2）3个作业共需时间为90s，CPU总共时间为：20+10+10+10+10+10=70s所以CPU利用率为：70/90=77.8%（3）3个作业全部完成是IO1的利用率是（20+30+20）/90=70/90=77.8%调度用的进程状态变迁图 CPU为空时，首先从 高优先就绪中选择。高优先就绪为空时，则从低优先就绪中选 择。调度策略调度策略 照顾了I/O量大的 进程。调度效果调度效果因果关系因果关系？6.3.4 调度用的进程状态变迁图调度用的进程状态变迁图运行高优先就绪低优先就绪因I/O而阻塞运行I/O完成时间片到其次选择500ms首先选择 100ms请求 I/O.1.队列结构I/O等待队列一个进程如果请求I/O，则进入I/O等待队列；低优先就绪队一个进程如果在运行中超过了它的时间量就进入低优先就绪；高优先就绪队列当进程从等待状态变为就绪状态时则进入高优先就绪队列。调度用的进程状态变迁图调度用的进程状态变迁图2.进程调度算法优先调度与时间片调度相结合的调度策略(1)当CPU空闲时，若高优先就绪队列非空，则从高优先就绪队列中选择一个进程运行，分配时间片为100ms。(2)当CPU空闲时，若高优先就绪队列为空，则从低优先就绪队列中选择一个进程运行，分配时间片为500ms。3.调度效果优先照顾了I/O量大的进程；适当照顾了计算量大的进程。1、进程优先数调度算法2、循环轮转调度常用的进程调度算法常用的进程调度算法常用的进程调度算法常用的进程调度算法6.3.5进程优先数调度算法优先数调度算法是目前操作系统广泛采用的一种进程调度算法，这种算法按照某种原则由系统（或用户、或系统与用户结合）赋予每个进程一个优先数，在处理机空闲时，进程调度程序就从就绪进程中选择一个优先数最大（或者最小）的进程占用CPU（该进程就从就绪状态转换成运行状态）。采用这种调度算法的关键是：如何确定进程的优先数一个进程的优先数确定之后是固定的，还是随着该进程运行的情况的变化而变化。6.3.5进程优先数调度算法静态：进程的优先数在进程创建时确定后就不再变化确定进程优先数：系统确定：（运行时间、使用资源，进程的类型）用户确定：（紧迫程度，计费与进程优先数有关）系统与用户结合（用户可以为本用户的进程设置优先数，但不是作调度用，系统还要根据系统情况把用户设置的进程优先数作为确定进程优先数的一个参数）6.3.5进程优先数调度算法动态进程优先数：系统在运行的过程中，根据系统的设计目标，不断地调整进程的优先数，这种方法的优点是能比较客观地反映进程的实际情况和保证达到系统设计目标。6.3.6循环轮转调度循环轮转调度实际上是一种先来先服务算法的调度算法，它把系统的响应时间分成大小相等（或不相等）的时间单位，称为时间片。每个进程被调度到后，占用一个时间片，片用完后，该进程让出CPU，由运行状态转换成就绪状态，排在就绪队列的队尾。多个进程循环轮转。6.3.6循环轮转调度6.3.6循环轮转调度系统按进程转换成就绪状态的时间的降序排队，调度程序每次调度，总是从队首移出一程的PCB，然后，将此进程投入运行（由就绪状态转换成运行状态）。一个运行时间片到的进程从运行状态转换成就绪状态后，排在就绪队列的队尾。6.3.6循环轮转调度评价：优点是实现简单、系统开销小缺点是不灵活，当系统中进程较少时，系统开销变大为什么？由于该算法简单易于实现，且系统开销较小，早期的分时操作系统和目前一些应用系统中广泛采用了这种调度算法。6.3.6循环轮转调度二、可变时间片轮转调度为了克服前种调度算法的缺点，人们设计出一种可变时间片的调度算法，其思想是：时间片的大小是可变的，系统可根据系统中当前的进程数来确定时间片的大小。6.3.6循环轮转调度这种算法从理论上克服了系统中进程数很少时系统开销大的缺点，但修改时间片的大小，统计系统进程的数量也需要消耗系统时间，还有一个调整时间片大小的周期，太大，等于是固定时间片，太小，系统开销很大，得不尝失。一、处理机的二级调度一、处理机的二级调度作业调度与进程调度的联系与区别二、作业调度二、作业调度1.功能2.调度性能评价1)周转时间2)平均周转时间定义3.常用策略调度算法小结小结三、进程调度三、进程调度1.调度/分派结构2.功能3.调度方式4.调度用的进程状态变迁图给定图进行分析给定原则画出图5.进程调度算法小结小结作业：p1326-2，6-4，6-7