第6讲 处理机调度3ppt.ppt

《第6讲 处理机调度3ppt.ppt》由会员分享，可在线阅读，更多相关《第6讲 处理机调度3ppt.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、操作系统原理（六）处理机调度张玉宏张玉宏郑州大学升达经贸管理学院资讯系郑州大学升达经贸管理学院资讯系资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院26.1概述如何从作业中挑选作业进入主存运行、如何在进程之间分配处理器时间，无疑是操作系统资源管理中的一个重要问题。这一涉及处理器分配的问题，称之为处理器调度。资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院3第六章处理机调度6.1处理机的二级调度宏观上：作业调度微观上：进程调度资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院4第

2、六章处理机调度6.1处理机的二级调度作业调度又称为宏观调度。任务对存放在辅存设备上的大量作业，以一定的策略进行挑选，分配主存等必要的资源，建立作业对应的进程，使其投入运行资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院5第六章处理机调度6.1处理机的二级调度进程调度又称为微观调度。任务对进入主存的所有进程，确定哪个进程在什么时候获得处理机，使用多长时间。资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院66.1处理机的二级调度处理机的二级调度处理机的二级调度处理机的二级调度 6.1.1 作业调度1.处理的对象：作业2

3、.所使用的数据结构w作业控制块(JCB)w后备作业队列3.任务：n要选择一个作业，分配内存和必要的外设，建立一个进程。资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院71.处理的对象：处理的对象：w进程进程 2.所使用的数据结构所使用的数据结构wpcb w就绪队列就绪队列 3.任务：任务：n确定什么时间，将确定什么时间，将CPU给哪一个进程给哪一个进程并确定使用多长时间。并确定使用多长时间。6.1.2进程调度进程调度 资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院8作业和进程的关系小结作业和进程之间的主要关系：作

4、业和进程之间的主要关系：1.作业是作业是任务实体任务实体，进程是，进程是完成任务完成任务的的执执行实体行实体;2.没有作业任务，进程无事可干，没有进没有作业任务，进程无事可干，没有进程，作业任务没法完成。程，作业任务没法完成。3.作业概念更多地用在批处理操作系统，作业概念更多地用在批处理操作系统，而进程则可以用在各种多道程序设计系而进程则可以用在各种多道程序设计系统。统。资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院96.2作业调度6.2.1作业调度的功能作业调度的主主要要任任务务是：完成作业从后备状态到执行状态和从执行状态到完成状态的转变。资讯管理系

5、张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院10三、三、1.区别：w对象、数据结构和任务不同。2.关联：w作业调度是对使用CPU的顾客进行预分w进程调度是对使用CPU的顾客进行具体分配外存CPU内存6.1.3作业调度与进程的作业调度与进程的关联与区别关联与区别 资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院116.2作业调度作业调度 执行运行运行就绪就绪等待等待后备提交完成作业录入作业调度作业调度作业调度作业调度资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院126.2作业调度6

6、.2.2作业控制块（JCB，JobControlBlock）每个作业进入系统时由系统为其建立一个作业控制块JCB（Job Control Block)，它是存放作业控制和管理信息的数据结构，主要信息见右图。资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院136.2.1 作业调度的功能作业调度的功能1.记录进入系统的各作业情况1)建立相应JCB（作业控制块）2)组成后备作业队列3)作业完成时，撤消JCBwJCB的作用：作业调度和资源分配的依据。6.2作业调度作业调度 资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院1

7、4一道考研题对作业进行管理和调度的重要的数据结构是（）（2002年华中科技大学）作业控制块（JCB）资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院152.策略：按一定的策略，从后备作业队列中挑选一个或几个作业投入运行。3.为选中的作业分配资源（如：内存、外设）4.作业运行结束作善后处理5.模块功能实现：创建一个进程6.2.1 作业调度的功能作业调度的功能资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院161.目标1)公平性2)吞吐率高3)设备利用率4)快的周转时间2.如何衡量调度算法的好坏1)对批处理系统：周转时

8、间、带权周转时间2)对分时系统和实时系统：响应时间 6.2.2 作业调度的目标和调度性能的衡量作业调度的目标和调度性能的衡量 资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院176.2.3调度性能的衡量作业调度算法规定了从后备作业中选择作业进入系统内存的原则，这些原则的性能如何，就是本节所讨论的问题。一、确定调度算法时应考虑的因素1.应与系统的整体设计目标一致2.考虑系统中各种资源的负载均匀3.保证作业的执行4.对一些专用资源的使用特性的考虑资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院186.2.3调度性能的衡

9、量二、调度性能的衡量通常采用平均周转时间和带权平均周转时间作业的周转时间：ti=tci-tsiti:作业周转时间tci：作业完成时间tsi:作业提交时间周转时间包括等待时间和运行时间资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院19一道考研题（西安电子科技大学一道考研题（西安电子科技大学2000）设有4个作业同时到达，每个作业的执行时间均为2个小时，它们在一台处理机上按单道方式执行，则平均周转时间为（）A1小时，B5小时C2.5小时D8小时答案B（平均作业周转时间=（2+（2+2）+（2+2+2）+（2+2+2+2）/4=5小时资讯管理系张玉宏主讲资讯

10、管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院206.2.3调度性能的衡量 t i r iw i=1+等待等待+运行运行 运行运行等待等待 运行运行资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院216.2.4先来先服务调度算法和短作业优先调度算法1.先来先服务调度算法（FCFS）：先来先服务算法是按作业来到的先后次序进行调度的这种调度算法突出的优点是实现简单，效率较低，在一些实际的系统和一般应用程序中采用这种算法的较多。资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院226.2.4先来先服务调度

11、算法和短作业优先调度算法短作业优先调度算法(SJFShortestJobFirst)：短作业优先调度算法考虑作业的运行时间，每次总是从就绪队列中选择一个运行时间最小的作业调入内存（系统）.资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院23一道考研题华中科技大学2001年资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院246.2.3作业调度算法作业调度算法 先来先服务调度算法和短作业优先调度算法340.8010.3010.100.209.50446.51.3010.8010.600.209.5042111.1010

12、.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资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院25一道考

13、研题华中科技大学2001填空题：在作业调度算法中，（）调度算法的调度性能要好些答案：短作业优先（SJF）资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院26一道考研题（华中科技大学一道考研题（华中科技大学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答案B资讯管理系张

14、玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院276.2.5其它几种调度算法先来先服务和短作业优先算法都有其片面性：先来先服务调度算法只考虑作业的等待时间，而忽视了作业的运行时间短作业优先算法则相反，只考虑了作业的运行时间，而忽视了作业的等待时间。响应比高者优先调度算法是介于这两种算法之间的一种拆衷的算法。资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院286.2.5其它几种调度算法响应比高者优先调度算法：资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院29响应比高者优先调度算法该算法

15、，就是每调度一个作业投入运行时，计算后备作业表中每个作业的响应比，然后挑选响应比最高的投入运行。资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院30响应比高者优先调度算法本算法优待了短作业但如果一个作业等待的时间足够长的话，其响应比也会增加，不至于无休止的运行下去。资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院31响应比高者优先调度算法（单位：小时，并以10进制算46.51.3010.8010.600.209.5042111.6010.1010.000.109.00334.22.1010.6010.100.508

16、.502112.0010.008.002.008.001执行顺序带权周转时间周转时间完成时间开始时间运行时间提交时间作业响应比高者优先调度算法平均周转时间 t=1.625平均带权周转时间 w=5.675资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院329.5049.0038.5028.001执行顺序带权周转时间周转时间完成时间开始时间运行时间提交时间作业2.000.50.10.2资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院336.2.5其它几种调度算法优先数调度算法优先数调度算法是终合考虑各方面的因素（作业等

17、待时间、运行时间、缓急程度，系统资源使用等），给每个作业设置一个优先数，调度程序总是选择一个优先数最大（或者最小）的作业调入（系统）内存。这种算法实现的困难在于如何综合考虑，这些因素之间的关系怎样处理。资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院34 6.3进程调度进程调度6.3.1 进程调度进程调度 又称为又称为cpu调度，其根本任务是按照某调度，其根本任务是按照某种原则为处于就绪状态的进程分配种原则为处于就绪状态的进程分配cpu资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院351.调度：n在众多就绪状态进

18、程中，按一定的原则选一个进程。w进程控制：对系统中的全部进程实施有效的管理2.分派n当CPU空闲时，移出n就绪队列元素，将CPUn控制权赋予它。运行运行就绪就绪等待等待控制调度控制6.3.1 进程调度进程调度资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院363.调度/分派结构 ready-qschedulersuspwakeupreceive.pcb1pcb2pcb3pcb4pcb5dispatcherCPU6.3.1 进程调度进程调度调度分派资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院371.记录进程的动态

19、变化wPCBw队列2.确定调度策略w先来先服务w紧迫程度3.进程之间切换6.3.2 进程调度功能进程调度功能资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院381.什么是调度方式当一进程正在处理机上执行，若有更高优先级的进程进入就绪队列时,如何分配处理机。2.调度方式1)非剥夺方式2)可剥夺方式 6.3.3调度方式调度方式资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院39调度方式所谓“非剥夺型调度”是指：一旦某个进程被调度执行，则该进程一直执行下去直至该进程结束，或由于某种原因自行放弃cpu进入等待状态，这时才将

20、cpu重新分配给其他进程。所谓剥夺型调度是指：一旦就绪状态中出现优先权更高的进程，或者运行的进程已用满了规定的时间片时，便立即剥夺当前进程的运行(将其放回就绪状态)，把cpu分配给其他进程。资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院40一道考研题（南京大学1999）资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院41分析：本题是一个多道系统兼有作业调度和进程调度的计算机体。其执行过程可以借助图示的方法加以描述：资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院42J30t

21、J2J1102030405060708090I02 30msCPU 10msI01 30msCPU 10msCPU 10msI01 20msCPU 10msI02 40msCPU 20msCPU 10msI01 20ms进程运行示意图资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院43解答（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

22、个作业全部完成是IO1的利用率是（20+30+20）/90=70/90=77.8%资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院44调度用的进程状态变迁图 CPU为空时，首先从 高优先就绪中选择。高优先就绪为空时，则从低优先就绪中选 择。调度策略调度策略 照顾了I/O量大的 进程。调度效果调度效果因果关系因果关系？6.3.4 调度用的进程状态变迁图调度用的进程状态变迁图运行高优先就绪低优先就绪因I/O而阻塞运行I/O完成时间片到其次选择500ms首先选择 100ms请求 I/O资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达

23、经贸管理学院45.1.队列结构I/O等待队列一个进程如果请求I/O，则进入I/O等待队列；低优先就绪队一个进程如果在运行中超过了它的时间量就进入低优先就绪；高优先就绪队列当进程从等待状态变为就绪状态时则进入高优先就绪队列。资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院46调度用的进程状态变迁图调度用的进程状态变迁图2.进程调度算法优先调度与时间片调度相结合的调度策略(1)当CPU空闲时，若高优先就绪队列非空，则从高优先就绪队列中选择一个进程运行，分配时间片为100ms。(2)当CPU空闲时，若高优先就绪队列为空，则从低优先就绪队列中选择一个进程运行，分

24、配时间片为500ms。3.调度效果优先照顾了I/O量大的进程；适当照顾了计算量大的进程。资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院471、进程优先数调度算法2、循环轮转调度常用的进程调度算法常用的进程调度算法常用的进程调度算法常用的进程调度算法资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院486.3.5进程优先数调度算法优先数调度算法是目前操作系统广泛采用的一种进程调度算法，这种算法按照某种原则由系统（或用户、或系统与用户结合）赋予每个进程一个优先数，在处理机空闲时，进程调度程序就从就绪进程中选择一个优先数

25、最大（或者最小）的进程占用CPU（该进程就从就绪状态转换成运行状态）。采用这种调度算法的关键是：如何确定进程的优先数一个进程的优先数确定之后是固定的，还是随着该进程运行的情况的变化而变化。资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院496.3.5进程优先数调度算法静态：进程的优先数在进程创建时确定后就不再变化确定进程优先数：系统确定：（运行时间、使用资源，进程的类型）用户确定：（紧迫程度，计费与进程优先数有关）系统与用户结合（用户可以为本用户的进程设置优先数，但不是作调度用，系统还要根据系统情况把用户设置的进程优先数作为确定进程优先数的一个参数）资讯

26、管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院506.3.5进程优先数调度算法动态进程优先数：系统在运行的过程中，根据系统的设计目标，不断地调整进程的优先数，这种方法的优点是能比较客观地反映进程的实际情况和保证达到系统设计目标。资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院516.3.6循环轮转调度循环轮转调度实际上是一种先来先服务算法的调度算法，它把系统的响应时间分成大小相等（或不相等）的时间单位，称为时间片。每个进程被调度到后，占用一个时间片，片用完后，该进程让出CPU，由运行状态转换成就绪状态，排在就绪队列的

27、队尾。多个进程循环轮转。资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院526.3.6循环轮转调度资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院536.3.6循环轮转调度系统按进程转换成就绪状态的时间的降序排队，调度程序每次调度，总是从队首移出一程的PCB，然后，将此进程投入运行（由就绪状态转换成运行状态）。一个运行时间片到的进程从运行状态转换成就绪状态后，排在就绪队列的队尾。资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院546.3.6循环轮转调度评价：优点是实现简单、系

28、统开销小缺点是不灵活，当系统中进程较少时，系统开销变大为什么？由于该算法简单易于实现，且系统开销较小，早期的分时操作系统和目前一些应用系统中广泛采用了这种调度算法。资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院556.3.6循环轮转调度二、可变时间片轮转调度为了克服前种调度算法的缺点，人们设计出一种可变时间片的调度算法，其思想是：时间片的大小是可变的，系统可根据系统中当前的进程数来确定时间片的大小。资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院566.3.6循环轮转调度这种算法从理论上克服了系统中进程数很少时系

29、统开销大的缺点，但修改时间片的大小，统计系统进程的数量也需要消耗系统时间，还有一个调整时间片大小的周期，太大，等于是固定时间片，太小，系统开销很大，得不尝失。资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院57一、处理机的二级调度一、处理机的二级调度作业调度与进程调度的联系与区别二、作业调度二、作业调度1.功能2.调度性能评价1)周转时间2)平均周转时间定义3.常用策略调度算法小结小结资讯管理系张玉宏主讲资讯管理系张玉宏主讲郑州大学升达经贸管理学院郑州大学升达经贸管理学院58三、进程调度三、进程调度1.调度/分派结构2.功能3.调度方式4.调度用的进程状态变迁图给定图进行分析给定原则画出图5.进程调度算法小结小结作业：p1326-2，6-4，6-7