《处理机的多级调度精选PPT.ppt》由会员分享，可在线阅读，更多相关《处理机的多级调度精选PPT.ppt（32页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、处理机的多级调度处理机的多级调度第1页，此课件共32页哦（一）（一）处理机的多级调度处理机的多级调度一一.处理机调度的功能处理机调度的功能n n 确定数据结构n n 制定调度策略（调度原则）n n 给出调度算法n n 具体的实施处理机分派不同类型的操作系统往往采用不同的处理机分配方法。第2页，此课件共32页哦二二二二.处理机调度的分层实现处理机调度的分层实现处理机调度的分层实现处理机调度的分层实现只有内存中的程序才能在CPU上运行。因此，处理机的调度通常分为两层：n n 宏观上：作业调度 对存放在辅存设备上的大量作业，以一定的策略进行挑选，分配主存等必要的资源，建立作业对应的进程，使其投入运行
2、。n n 微观上：进程调度 对进入注册的所有进程，确定哪个进程在什么时候获得处理机，使用多长时间。第3页，此课件共32页哦三三.批处理系统中的处理机调度批处理系统中的处理机调度第4页，此课件共32页哦四四.多任务操作系统中的处理机调度多任务操作系统中的处理机调度在分时系统或支持多任务并发执行个人计算机操作系在分时系统或支持多任务并发执行个人计算机操作系统中，系统将用户提交的任务处理为进程，一个进程又可统中，系统将用户提交的任务处理为进程，一个进程又可以创建多个子进程，形成可以并发执行的多进程。以创建多个子进程，形成可以并发执行的多进程。进程调度的任务任务是：当处理机空闲时，以某种策略是：当处理
3、机空闲时，以某种策略选择一个就绪进程去运行，并分配处理机的时间。选择一个就绪进程去运行，并分配处理机的时间。另外，由于分时系统中的作业调度功能很弱（甚至没有），因此有些分时系统会将进程在内、外存之间进行交换。由于进程仍然存在，也与处理机的分配无关，故称为中级调度。第5页，此课件共32页哦五五.多线程操作系统中的处理机调度多线程操作系统中的处理机调度在支持多线程运行的系统中，每个进程都创建一个线程，也可以创建多个线程。系统为进程分配它所需要的资源，而处理机的分配的对象则为线程。系统提供线程调度程序，其功能是当处理机空闲时，以某种策略选择一个就绪线程去运行，并分配处理机时间。第6页，此课件共32页
4、哦（二）（二）作业调度作业调度一一.作业的状态作业的状态作业的状态作业的状态 作业在整个活动期间一共有四种状态：提提交交状状态态：用户将自己的程序和数据提交给系统，等待输入。后后备备状状态态：作业已存放在磁盘上，等待调进主存。执行状态执行状态：作业在主存中运行。完成状态完成状态：作业计算完成，退出主存。第7页，此课件共32页哦作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转变。第8页，此课件共32页哦二二二二.作业调度的功能作业调度的功能作业调度的功能作业调度的功能n n确定数据结构建立作业控制块（JCBJCB，Job Control Block），记记录录已已进进入
5、入系系统统的的各各作作业业的的情情况况（类类型型、状状态态、资资源源请请求求与分配等）；与分配等）；n n确定调度策略与调度算法n n分配资源为被选中的作业创建进程，并且为其申请系统资源；n n善后处理收回作业占用的全部资源，撤销作业控制块以及与该作业有关的全部进程。第9页，此课件共32页哦三三.作业控制块（作业控制块（JCBJCBJCBJCB，Job Control BlockJob Control Block）n n每个作业进入系统时由系统为其建立一个作业控 制 块 JCB（Job Control Block)，它是存放作业控制和管理信息的数据结构，是作业存在的标志，主要信息见右图。第10
6、页，此课件共32页哦四四四四.作业调度算法性能的衡量作业调度算法性能的衡量作作业业调调度度算算法法规规定定了了从从后后备备作作业业中中选选择择作作业业进进入入系系统统内存的原则。内存的原则。1.1.1.1.确定调度算法时应考虑的因素确定调度算法时应考虑的因素(1)应与系统的整体设计目标一致应与系统的整体设计目标一致(2)考虑系统中各种资源的负载均匀(3)保证作业的执行保证作业的执行(4)对一些专用资源的使用特性的考虑对一些专用资源的使用特性的考虑第11页，此课件共32页哦2.2.2.2.调度性能的衡量调度性能的衡量调度性能的衡量调度性能的衡量通常采用平均周转时间和带权平均周转时间来衡量作业调度
7、算法性能的好坏。(1)周转时间周转时间：一个作业提交给计算机系统到该作业的结果返回给用户所需要的时间。n n定义定义：ti=tci-tsi si ti：作业周转时间tci：作业完成时间 tsi:作业提交时间n n意义意义：说明作业i i在系统中停留的时间长短n n平均周转时间平均周转时间：第12页，此课件共32页哦(2)(2)带权周转时间带权周转时间n n定义定义：一个作业的周转时间与其运行时间的比值比值n n意义意义：说明作业i i在系统中的相对相对等待时间。(3)(3)平均带权周转时间平均带权周转时间n n精确度精确度精确度精确度：高于周转时间和平均周转时间另外，还可以用CPU的利用率和吞
8、吐量来衡量。第13页，此课件共32页哦五五五五.作业调度算法作业调度算法1.1.1.1.先来先服务调度算法先来先服务调度算法(FCFS)(FCFS)n n策略策略：按照作业来到的先后次序来到的先后次序进行调度n n特点特点：每次选择的作业是等待时间最久的，而不管作业运行时间的长短。这种调度算法突出的优点是实实现现简简单单，但效效率率较较低低，在一些实际的系统和一般应用程序中采用这种算法的较多。第14页，此课件共32页哦2.2.短作业优先调度算法短作业优先调度算法短作业优先调度算法短作业优先调度算法n n策略策略：考虑作业的运行时间，每次总是选择一个请求运行时间最小运行时间最小的作业调入内存（系
9、统）。n n特点特点：易实现，系统吞吐量高。只考虑短作业，而没有考虑长作业的利益。相对先来先服务调度算法实现要困难些，如果作业的到来顺序及运行时间不合适，会出现饿死饿死现象。第15页，此课件共32页哦讨论在两种调度算法下的周转时间与带权周转时间讨论在两种调度算法下的周转时间与带权周转时间第16页，此课件共32页哦3.3.3.3.响应比高者优先调度算法响应比高者优先调度算法响应比高者优先调度算法是介于这两种算法之间的一种拆衷的算法。响应比响应比 响应时间响应时间 /执行时间执行时间 1 1 等待时间/执行时间每每调调度度一一个个作作业业时时，计计算算后后备备作作业业表表中中每每个个作作业业的响应
10、比，挑选响应比高者投入运行。的响应比，挑选响应比高者投入运行。第17页，此课件共32页哦这种算法从理论上讲是比较完备的，但作业调度程序要统计作业的等待时间，使用用户的估计的运行时间，并要作浮点运算，从而浪费大量的计算时间，这是系统程序所不允许的。第18页，此课件共32页哦4.4.4.4.优先数调度算法优先数调度算法优先数调度算法优先数调度算法优先数调度算法终合考虑各方面的因素（作业等待时间、运行时间、缓急程度，系统资源使用等），给每个作业设置一个优先数，调度程序总是选择一个优先数最大（或者最小）的作业调入（系统）内存。这种算法实现的困难在于如何终合考虑，这些因素之间的关系怎样处理。第19页，此
11、课件共32页哦5.5.均衡调度算法均衡调度算法均衡调度算法是一种更为理想化的调度算法，实现更困难，并且存在算法本身的开销有时会远远大于先来先服务和小作业优先调度算法的不足，这也是后两种算法被众多系统采用的最根本的原因。第20页，此课件共32页哦(三三)进程调度进程调度一一.调度调度/分派结构分派结构处理机分配由调度和分派两个功能组成。处理机分配由调度和分派两个功能组成。1.调度调度：组组织织和和维维护护就就绪绪进进程程队队列列。包包括括确确定定调调度度算算法法、按按调调度度算算法法组组织织和和维维护护就就绪绪进进程程队队列列。（按按调调度度原原则则选择进程）选择进程）2.2.分派分派：当当处处
12、理理机机空空闲闲时时，从从就就绪绪队队列列队队首首中中移移一一个个PCBPCB，并将该进程投入运行。并将该进程投入运行。（赋予使用处理机的权限）（赋予使用处理机的权限）第21页，此课件共32页哦二二二二.进程调度的功能进程调度的功能进程调度的功能进程调度的功能1.记录和保持系统中所有进程的有关情况和状态特征2.决定分配（处理机）策略决定分配（处理机）策略调度策略的不同，组织就绪进程队列的方式也不同。调度策略的不同，组织就绪进程队列的方式也不同。n n先来先服务调度：就绪进程按先来先服务调度：就绪进程按等待时间大小的顺序等待时间大小的顺序等待时间大小的顺序等待时间大小的顺序排队排队n n优先数调
13、度：就绪进程按优先数调度：就绪进程按优先数的先后次序优先数的先后次序优先数的先后次序优先数的先后次序排队排队3.3.实施处理机的分配和回收总而言之，进程调度包括：总而言之，进程调度包括：n n调度算法的选择（调度算法）调度算法的选择（调度算法）n n调度时机的选择（调度时机）调度时机的选择（调度时机）n n实施进程调度（调度程序）实施进程调度（调度程序）第22页，此课件共32页哦三三.进程调度方式进程调度方式进程调度方式进程调度方式n n什么是调度方式什么是调度方式在按进程在按进程优先级调度优先级调度优先级调度优先级调度的系统中，当一进程正在处理机上执的系统中，当一进程正在处理机上执行时，若有
14、某个更为行时，若有某个更为“重要而紧迫重要而紧迫”的进程需要运行时，系统的进程需要运行时，系统如何分配处理机。基本的方式有二种。如何分配处理机。基本的方式有二种。1.1.非剥夺方式非剥夺方式2.剥夺方式剥夺方式剥夺方式剥夺方式在实现中还可采用选择可抢占策略。第23页，此课件共32页哦四四四四.调度用的进程状态变迁图调度用的进程状态变迁图右右图图中中新新创创建建的的进进程程进进入入低低优优就就绪绪状状态态，一一个个运运行行进进程程因因时时间间片片到到（实实际际上上是是计计算算量量大大的的进进程程）而而转转换换成成低低优优就就绪绪；进进程程因因等等待待I/OI/O完完成而转换高优就绪成而转换高优就
15、绪.通过进程调度变迁图，可反映系统的进程调度的各种特征。通过进程调度变迁图，可反映系统的进程调度的各种特征。第24页，此课件共32页哦1.1.队列结构队列结构n nI/O等待对列一个进程如果请求I/O，则进入，则进入I/O等待队列；n n低优先就绪队列低优先就绪队列一个进程如果在运行中超过了分配给它的时间片，就进入低优先就绪n n高优先就绪队列当进程从等待状态变为就绪状态时，则进入高优先就绪队列。第25页，此课件共32页哦2.2.进程调度算法进程调度算法n n当当CPU空闲时，若高优先就绪队列非空，则从高优先空闲时，若高优先就绪队列非空，则从高优先就绪队列中选择一个进程运行，分配时间片为就绪队
16、列中选择一个进程运行，分配时间片为100ms。n n当当CPUCPU空闲时，若高优先就绪队列为空，则从低优先就绪队列中选择一个进程运行，分配时间片为500ms500ms。优先调度与时间片调度相结合的调度策略优先调度与时间片调度相结合的调度策略3.3.调度效果调度效果优先照顾了优先照顾了I/O量大的进程；适当照顾了计算量大的进程。适当照顾了计算量大的进程。第26页，此课件共32页哦五五五五.进程调度算法进程调度算法1.进程优先数调度算法进程优先数调度算法进程优先数调度算法进程优先数调度算法是是目目前前操操作作系系统统广广泛泛采采用用的的一一种种进进程程调调度度算算法法，这这种种算算法法按按照照某
17、某种种原原则则由由系系统统（或或用用户户、或或系系统统与与用用户户结结合合）赋赋予予每每个个进进程程一一个个优优先先数数，在在处处理理机机空空闲闲时时，进进程程调调度度程程序序就就从从就就绪绪进进程程中中选选择择一一个个优优先先数数最最大大（或或者者最最小小）的进程占用的进程占用CPUCPU（该进程就从就绪状态转换成运行状态）。（该进程就从就绪状态转换成运行状态）。采采用用这这种种调调度度算算法法的的关关键键是是如如何何确确定定进进程程的的优优先先数数、一一个个进进程程的的优优先先数数确确定定之之后后是是固固定定的的，还还是是随随着着该该进进程程运运行行的情况的变化而变化。的情况的变化而变化。
18、第27页，此课件共32页哦n n静态：n n进程的优先数在进程创建时确定后就不再变化进程的优先数在进程创建时确定后就不再变化n n确定进程优先数：确定进程优先数：系统确定系统确定系统确定系统确定：（运行时间、使用资源，进程的类型）：（运行时间、使用资源，进程的类型）用户确定用户确定用户确定用户确定：（紧迫程度，计费与进程优先数有关）：（紧迫程度，计费与进程优先数有关）系系统统与与用用户户结结合合（用用户户可可以以为为本本用用户户的的进进程程设设置置优优先先数数，但但不不是是作作调调度度用用，系系统统还还要要根根据据系系统统情情况况把把用用户户设设置置的进程优先数作为确定进程优先数的一个参数）的
19、进程优先数作为确定进程优先数的一个参数）n n动态动态动态动态：系系统统在在运运行行的的过过程程中中，根根据据系系统统的的设设计计目目标标，不不断断地地调调整整进进程程的的优优先先数数，这这种种方方法法的的优优点点是是能能比比较较客客观观地地反反映映进进程程的实际情况和保证达到系统设计目标的实际情况和保证达到系统设计目标。第28页，此课件共32页哦2.循环轮转调度算法循环轮转调度算法循循环环轮轮转转调调度度实实际际上上是是一一种种先先来来先先服服务务算算法法的的调调度度算算法法，它它把把系系统统的的响响应应时时间间分分成成大大小小相相等等（或或不不相相等等）的的时时间间单单位位，称称为为时时间
20、间片片。每每个个进进程程被被调调度度到到后后，占占用用一一个个时时间间片片，片片用用完完后后，该该进进程程让让出出CPU，由运行状态转换成就绪状态，排在就绪队列的队尾。多个进程循环轮转。第29页，此课件共32页哦n n 简单循环轮转调度简单循环轮转调度n n 实现简单、系统开销小。n n 不灵活，当系统中进程较多时，系统开销变大。n n 可变时间片轮转调度n n时间片的大小可变，系统可根据系统中当前的进程数来确定时间片的大小。例：Q=T/Nn nT T：系系统统响响应应时时间间，一一般般为为1 1秒秒，具具体体大大小小由由系系统统设设计计时时根根据系统设计目标确定。据系统设计目标确定。n nN
21、N：系系统统中中进进程程的的个个数数，也也由由系系统统设设计计时时确确定定，或或者者通通过过系系统统配配置文件，由系统管理员确定。置文件，由系统管理员确定。第30页，此课件共32页哦第六章第六章 小结小结一一.处理机的二级调度处理机的二级调度二二.作业调度作业调度 1.1.作业的状态作业的状态 2.2.作业控制块作业控制块 3.3.作业调度的功能 4.4.周转时间、带权周转时间：定义、物理意义 5.5.常用的作业调度算法先来先服务 短作业优先第31页，此课件共32页哦第六章第六章 小结（续）小结（续）三三.进程调度进程调度1.进程调度的功能2.调度方式：非剥夺方式剥夺方式3.常用的进程调度算法：优先数调度循环轮转调度 4.调度用的进程状态变迁图（多种进程状态及变迁）第32页，此课件共32页哦