操作系统06处理机调.pptx

第六章第六章 处理机调度处理机调度（一）（一）处理机的多级调度处理机的多级调度（二）（二）作业调度作业调度（三）（三）进程调度进程调度处理机调度的目标：处理机调度的目标：nCPU使用率使用率高高：使处理机尽可能忙n响应时间响应时间快：快：与用户交互快捷n周转时间周转时间短：短：用户等待输出的时间短n等待时间等待时间小：公平公平，确保每个进程都能公平地占有处理机n系统系统吞吐量吞吐量大大：相同时间内完成的作业（进程）尽可能多处理机的调度通常可分为两级调度：作业调度和进程调度。操作系统类型的不同，处理机的调度等级也是不同的：1、批处理系统中的处理机调度 2、多任务操作系统中的处理机调度 3、多线程操作系统中的处理机调度（一）（一）处理机的多级调度处理机的多级调度1、批处理系统中的处理机调度、批处理系统中的处理机调度处理机调度分两级：作业调度和进程调度。处理机调度分两级：作业调度和进程调度。n作业调度作业调度(又称宏观调度又称宏观调度)：对存放在辅存设：对存放在辅存设备上的大量作业，以一定的策略进行挑选，备上的大量作业，以一定的策略进行挑选，分配主存等必要的资源，建立作业对应的进分配主存等必要的资源，建立作业对应的进程，使其投入运行。程，使其投入运行。n进程调度进程调度(又称微观调度又称微观调度)：对进入主存的所：对进入主存的所有进程，确定哪个进程在什么时候获得处理有进程，确定哪个进程在什么时候获得处理机，使用多长时间。机，使用多长时间。42.多任务操作系统中的处理机调度多任务操作系统中的处理机调度u 在分时系统或支持多任务并发执行个人计在分时系统或支持多任务并发执行个人计算机操作系统中，系统将用户提交的任务处算机操作系统中，系统将用户提交的任务处理为进程，一个进程又可以创建多个子进程，理为进程，一个进程又可以创建多个子进程，形成可以并发执行的多进程。形成可以并发执行的多进程。u 进程调度的任务是：进程调度的任务是：当处理机空闲时，以当处理机空闲时，以某种策略选择一个就绪进程去运行，并分配某种策略选择一个就绪进程去运行，并分配处理机的时间。处理机的时间。63.多线程操作系统中的处理机调度多线程操作系统中的处理机调度n 在支持多线程运行的系统中，一个进程可在支持多线程运行的系统中，一个进程可以创建一个线程，也可以创建多个线程。系以创建一个线程，也可以创建多个线程。系统为进程分配它所需要的资源，而处理机的统为进程分配它所需要的资源，而处理机的分配单位则为线程。分配单位则为线程。n 系统提供线程调度程序，其功能是系统提供线程调度程序，其功能是当处理当处理机空闲时，以某种策略选择一个就绪线程去机空闲时，以某种策略选择一个就绪线程去运行，并分配处理机时间。运行，并分配处理机时间。7作作业业调调度度的的主主要要任任务务是是完完成成作作业业从从后后备备状状态态到到执行状态和从执行状态到完成状态的转变。执行状态和从执行状态到完成状态的转变。（二）（二）作业调度作业调度1 1、作业的状态、作业的状态作业在整个活动期间一共有三种状态：作业在整个活动期间一共有三种状态：后备状态：后备状态：作业已存放在磁盘上，等待掉进主存。作业已存放在磁盘上，等待掉进主存。执行状态：执行状态：作业在主存中运行。作业在主存中运行。完成状态：完成状态：作业计算完成开始，退出主存。作业计算完成开始，退出主存。2、作业调度功能：、作业调度功能：n确定数据结构：为作业分配控制块确定数据结构：为作业分配控制块JCB；n确确定定调调度度算算法法：按按一一定定的的调调度度算算法法，从从后后备备作作业业中中选择一个或几个作业进入系统内存；选择一个或几个作业进入系统内存；n分分配配资资源源：为为被被选选中中的的作作业业创创建建进进程程，并并且且为为其其申申请系统资源；请系统资源；n善后处理：作业结束后作善后处理工作。善后处理：作业结束后作善后处理工作。103 3、作业控制块、作业控制块 作作业业控控制制块块JCBJCB（Job Job Control Control Block)Block)，它它是是存存放放作作业业控控制制和和管管理理信信息息的的数数据据结结构构，是是作作业业存存在在的的唯唯一一标标识识，是是操操作系统调度的依据。作系统调度的依据。主要信息见右图。主要信息见右图。114 4、作业调度算法的性能衡量指标：、作业调度算法的性能衡量指标：平均周转时间平均周转时间和和带权平均周转时间带权平均周转时间u周转时间周转时间完成时间提交时间等待时完成时间提交时间等待时 间执行时间间执行时间u平均周转时间平均周转时间周转时间总和周转时间总和作业数作业数u带权周转时间带权周转时间周转时间周转时间执行时间执行时间u平均带权周转时间平均带权周转时间=带权周转总和带权周转总和作业数作业数 5 5、作业调度算法、作业调度算法先来先服务先来先服务FCFSFCFS短作业优先短作业优先SJFSJF响应比高优先响应比高优先优先优先调度调度13（1 1）作业调度算法（一）作业调度算法（一）先来先服务调度算先来先服务调度算 法法(FCFS)(FCFS)n策略：策略：作业作业来到的先后次序来到的先后次序进行调度进行调度n优点：优点：实现简单实现简单n缺点：缺点：效率较低效率较低（2 2）作业调度算法（二）作业调度算法（二）短作业优先调度短作业优先调度 算法（算法（SJFSJF）n策策略：略：考考虑虑作作业业的的运运行行时时间间，每每次次总总是是选选择择一一个个 运行时间最小运行时间最小的作业调入内存（系统）的作业调入内存（系统）。n优点：优点：易实现，系统吞吐量高易实现，系统吞吐量高 缺缺点点：只只考考虑虑短短作作业业，而而没没有有考考虑虑长长作作业业的的利利益益。如如果果作作业业的的到到来来顺顺序序及及运运行行时时间间不不合合适，会出现适，会出现饿死饿死现象。现象。讨论在两种调度算法下的周转时间与带权周转时间讨论在两种调度算法下的周转时间与带权周转时间讨论在两种调度算法下的周转时间与带权周转时间讨论在两种调度算法下的周转时间与带权周转时间（3 3）作业调度算法（三）：响应比高者优先调度算法）作业调度算法（三）：响应比高者优先调度算法响响应应比比高高者者优优先先调调度度算算法法是是介介于于前前两两种种算算法法之之间间的的一一种种折衷的算法。折衷的算法。响应比响应比 周转时间周转时间/执行时间执行时间 1 等待时间等待时间/执行时间执行时间（4 4）作业调度算法（四）：优先调度算法）作业调度算法（四）：优先调度算法优优先先数数调调度度算算法法综综合合考考虑虑各各方方面面的的因因素素（作作业业等等待待时时间间、运运行行时时间间、缓缓急急程程度度，系系统统资资源源使使用用等等），给给每每个个作作业业设设置置一一个个优优先先数数，调调度度程程序序总总是是选选择择一一个个优优先先数数最最大大（或或者者最最小小）的的作作业业调调入入（系系统统）内内存存。这这种种算算法法实实现现的的困困难难在在于于如如何何终终合合考考虑，这些因素之间的关系怎样处理。虑，这些因素之间的关系怎样处理。(三三)进程调度进程调度1 1、调度、调度/分派结构分派结构处理机分配由处理机分配由调度调度和和分派分派两个功能组成。两个功能组成。1）调度）调度组织和维护就绪进程队列。包括确定调度算法、按调度算法组织和维护就绪进程队列。（按调度原则选择进程）。2）分派）分派当处理机空闲时，从就绪队列队首中移一个PCB，并将该进程投入运行。（赋予使用处理机的权限）。20调度与分派结构图调度与分派结构图2 2、进程调度的功能进程调度的功能记录和保持系统中所有进程的有关情况和状态特征（记录和保持系统中所有进程的有关情况和状态特征（PCB）决定分配（处理机）策略决定分配（处理机）策略实施处理机的分配和回收实施处理机的分配和回收3 3、进程调度方式进程调度方式基本的方式有二种：基本的方式有二种：1）非剥夺方式）非剥夺方式2）剥夺方式）剥夺方式4 4、进程调度算法、进程调度算法 进程优先级调度算法进程优先级调度算法循环轮转调度（循环轮转调度（RRRR）多级反馈队列调度多级反馈队列调度231）进程优先数调度算法）进程优先数调度算法是是目目前前操操作作系系统统广广泛泛采采用用的的一一种种进进程程调调度度算算法法，这这种种算算法法按按照照某某种种原原则则由由系系统统（或或用用户户、或或系系统统与与用用户户结结合合）赋赋予予每每个个进进程程一一个个优优先先数数，在在处处理理机机空空闲闲时时，进进程程调调度度程程序序就就从从就就绪绪进进程程中中选选择择一一个个优优先先数数最最大大（或或者者最最小小）的的进进程程占占用用CPU（该该进进程程就就从从就就绪绪状状态态转转换换成运行状态）。成运行状态）。采采用用这这种种调调度度算算法法的的关关键键是是如如何何确确定定进进程程的的优优先先数数、一一个个进进程程的的优优先先数数确确定定之之后后是是固固定定的的，还还是是随随着着该该进进程运行的情况的变化而变化。程运行的情况的变化而变化。2）循环轮转调度算法）循环轮转调度算法循循环环轮轮转转调调度度实实际际上上是是一一种种特特殊殊的的先先来来先先服服务务算算法法的的调调度度算算法法，它它把把系系统统的的响响应应时时间间分分成成大大小小相相等等（或或不不相相等等）的的时时间间单单位位，称称为为时时间间片片。每每个个进进程程被被调调度度到到后后，占占用用一一个个时时间间片片，片片用用完完后后，该该进进程程让让出出CPUCPU，由由运运行行状状态态转转换换成成就就绪绪状状态态，排排在就绪队列的队尾。多个进程循环轮转。在就绪队列的队尾。多个进程循环轮转。【例例】有有5 5个进程（个进程（A A，B B，C C，D D，E E）几乎同时到进入就）几乎同时到进入就 绪队列，估计的运行时间分别为绪队列，估计的运行时间分别为2 2，4 4，6 6，8 8，1010分钟，分钟，分别计算作业的平均周转时间。分别计算作业的平均周转时间。时间片轮转（时间片为时间片轮转（时间片为2 2分钟）分钟）26 A B C D E B C D E C D E D E E t 0 2 4 6 8 1012 1416182022 242628 30 t=(2+12+20+26+30)/5=18 分钟分钟作业作业第第6章章 6题题28