3处理器管理和调度.ppt

第三章 处理器调度,调度是系统将计算机资源分配给进程在单道程序环境下，没有资源竞争问题在多道程序环境下，多个进程并发运行，各进程之间存在资源的相互竞争，特别是对处理器资源的竞争，从而影响到系统性能处理器调度指在多道程序环境下将处理器分配给各进程在处理器调度中，合理的调度算法能够提高处理器的处理能力和系统性能，满足用户需求第三章 处理器调度,,3.1 作业的管理和调度3.2 处理器调度的层次3.3 选择调度算法的原则 3.4 处理器调度算法,第三章 处理器调度,,3.1 作业的管理和调度3.2 处理器调度的层次3.3 选择调度算法的原则 3.4 处理器调度算法,作业的概念,作业：作业由一组统一管理和操作的进程集合构成，是用户要求计算机系统完成的一项相对独立的工作分类：按需要处理工作的类型分计算型作业和I/O型作业；按作业提交的方式不同分为批处理作业和终端型作业,作业的概念,在多道程序环境下，用户的批处理作业被提交到系统的磁盘上，以批处理后备队列的形式进行组织，这样的作业为批处理作业批处理作业需要作业调度将后备队列上的作业调度到内存才能执行对终端型作业用户通过终端登录到系统，直接将作业置于内存中。

终端型作业不需要作业调度便能执行作业和进程的关系,进程：已提交完毕并选中运行的作业（程序）的执行实体，也是为完成作业任务向系统申请和分配资源的基本单位作业得到调度后必须为其生成相应的用户进程才能真正执行完成计算任务一个作业往往由多个父子关系的进程并发完成,作业和进程的关系,因此：,作业是任务实体，进程是完成任务的执行实体;没有作业任务，进程无事可干，没有进程，作业任务没法完成作业概念更多地用在批处理操作系统，而进程则可以用在各种多道程序设计系统批处理作业的相关概念,1、作业：用户在一次计算过程中，或者一次事务处理过程中，要求计算机系统所做工作的总称2、作业步：一个作业可划分成若干部分，称为一个作业步典型的作业控制过程：“编译”、“连接装配”、“运行”,,3、作业控制语言：用户用于描述批处理作业处理过程控制意图的一种特殊程序􀂄书写作业说明书的语言称为作业控制语言（JCL）4、作业说明书：表达用户对作业的控制意图内容，如作业的基本描述，作业控制描述，资源要求描述 作业=程序+数据+作业说明书,,5、作业控制块（JCB）作业控制块是批处理作业存在的标志保存有系统对于作业进行管理所需要的全部信息位于磁盘区域中JCB和作业一一对应,,（1）JCB的建立当作业开始由输入设备向磁盘的输入井传输时系统输入程序为其建立一个作业控制块进行初始化初始化的大部分信息取自作业说明书,,（2）JCB的使用需要访问作业控制块的程序系统输入程序作业调度程序作业控制程序系统输出程序等,,（3）JCB的撤消作业完成后，其作业控制块由系统输出程序撤消,作业控制块被撤消后其作业也不复存在,,（4）作业表每个作业有个作业控制块所有作业JCB构成一个作业表作业表存放在外存固定区域中，长度是固定限制了系统所能同时容纳的作业数量注意：系统输入程序、作业调度程序、系统输出程序都需要访问作业表，因而存在互斥问题,批处理作业的组织和管理,批处理作业的输入（输入井）批处理作业的建立（JCB）批处理作业的调度(按照某种调度算法从输入井的后备作业队列中选取作业，使其进入内存运行。

)(1)选择作业; (2) 分配资源(3)创建进程;(4)作业控制(5)后续处理,批处理作业的调度,作业调度——按照某种调度算法从输入井的后备作业队列中选取作业，使其进入内存运行作业调度程序的主要功能是审查系统是否能满足用户作业的资源要求以及按照一定的算法选取作业批处理作业的状态,提交状态:用户将作业提交给操作系统，等待输入程序和数据到磁盘 后备状态:系统接收输入的用户作业，并将其放入计算机磁盘作业在磁盘上以后备队列形式进行组织，等待作业调度程序将作业调度到内存 执行状态:作业被调度到内存，为作业分配资源并为其创建与之对应的进程，进程获得CPU，开始运行完成状态:从作业的第一个进程完成开始，直到作业所有的进程完成，释放作业所占用的资源，退出系统的整个进程批处理作业状态及其转换,终端型作业,为每个终端创建一个终端进程，接受用户的输入，执行命令解释程序，并把结果返回给用户 等待键盘中断，申请中断； CPU响应中断，将控制权交给命令解释程序 创建子进程，执行命令处理文件代码 处理结束，再次输出命令提示符例如分时操作系统命令解释程序的作用和JCL解释程序类似,总结,批处理作业需要作业调度，特别是在批处理操作系统中在分时操作系统和实时操作系统中，终端用户的作业直接送入到内存，不需要作业调度。

操作系统需要完成的功能是决定是否能够为作业创建进程分时操作系统和实时操作系统也支持批处理作业，在批处理作业存在时，也能够完成作业调度第三章 处理器调度,,3.1 作业的管理和调度3.2 处理器调度的层次3.3 选择调度算法的原则 3.4 处理器调度算法,,在多道程序环境下，进程的数目往往多于处理器的数目，多个进程共享处理器资源就必然引起对处理机的竞争 如需要考虑： 按照何种原则挑选批处理作业进入主存？ 能否继续接纳分时用户？ 如何在多进程之间分配处理器？等等,处理器调度的层次,按照层次分为三级： （1）高级调度 （作业调度、长程调度） （2）中级调度 （平衡负载调度、中程调度） （3）低级调度 （进程/线程调度、短程调度）,高级调度,高级调度（作业调度、长程调度、宏观调度）—— 按一定原则对外存输入井上的大量后备作业进行选择调入内存，并为它们创建进程、分配必要的资源，再将新创建的进程排在就绪队列上，准备执行􀂃 一般在批处理系统中有作业调度高级调度,执行作业调度时应决定： 接纳多少个作业？ 接纳哪些作业？ 取决于多道程序度。

取决于所采用的调度算法，如先来先服务调度算法、短作业优先调度算法、最高响应比法等中级调度,平衡负载调度，中程调度决定主存储器中所能容纳的进程数，这些进程将允许参与竞争处理器资源中级调度根据存储资源量和进程的当前状态来决定辅存和主存中进程的对换引入中级调度的目的是为了提高内存的利用率和系统吞吐量,低级调度,低级调度（进程调度、短程调度、微观调度）——用来决定就绪队列中的哪个进程应获得处理机，再由分派程序执行把处理机分配给该进程的具体操作低级调度是由每秒可操作许多次的处理机调度程序执行，处理机调度程序应常驻内存进程调度的方式： 非抢占方式，抢占方式 抢占原则： 1 时间片原则； 2优先级原则； 3 短进程优先原则处理器调度的层次,,处理器调度与进程状态转换,调度模型,注意：并不是每个操作系统都有三级调度，其中低级调度是每种操作系统必备的按照层次，处理器调度模型可分为： 三级调度模型（高，中，低） 两级调度模型（高，低） 一级调度模型（低）,一级调度模型,,两级调度模型,,处理器的三级调度模型,第三章 处理器调度,,3.1 作业的管理和调度3.2 处理器调度的层次3.3 选择调度算法的原则 3.4 处理器调度算法,调度算法的目标,单位时间内运行尽可能多的作业使处理机尽可能保持“忙碌”使各种I/O设备得以充分利用对所有的作业都是公平合理的,,调度算法需要考虑的因素,要设计一个理想的调度算法是一件十分困难的事，在实际系统中，调度算法往往折衷考虑，设计调度算法时应考虑的因素：􀂄 调度算法应与系统设计目标保持一致􀂄 注意系统资源均衡使用􀂄 保证提交的作业在截止时间内完成􀂄 设法缩短作业平均周转时间大多数操作系统都采用比较简单的调度算法,评价调度算法的性能指标,面向系统的： 1、资源利用率 2、吞吐率 3、公平性面向用户的 ： 4、响应时间 5、周转时间,1、资源利用率,CPU利用率=CPU有效工作时间/CPU总的运行时间 CPU总的运行时间=CPU有效工作时间 +CPU空闲等待时间,2、吞吐率,单位时间内处理的作业数处理的长作业多，吞吐率低 处理的短作业多，吞吐率高,3、公平性,确保每个用户每个进程获得合理的CPU份额或其他资源份额，不会出现饿死情况。

4、响应时间,交互式进程从提交一个请求(命令)到接收到响应之间的时间间隔称响应时间使交互式用户的响应时间尽可能短，或尽快处理实时任务这是分时系统和实时系统衡量调度性能的一个重要指标5、周转时间,从用户把作业提交给系统开始，到作业完成为止的时间间隔称作业周转时间，应使作业周转时间或平均作业周转时间尽可能短这是批处理系统衡量调度性能的一个重要指标调度性能指标重点看 ：平均作业周转时间和平均带权作业周转时间,作业周转与平均周转时间,如果作业i提交给系统的时刻是ts，完成时刻是tf，该作业的周转时间ti为： ti = tf - ts 平均作业周转时间 T = (Σti) / n,作业带权周转时间和平均作业带权周转时间,如果作业i的周转时间为ti，所需运行时间为tk，则称wi=ti /tk为该作业的带权周转时间ti是等待时间与运行时间之和，故带权周转时间总大于1 平均作业带权周转时间 W = (Σwi) / n,注意：为了提高系统的性能，要让若干个用户的平均作业周转时间和平均带权周转时间最小T：衡量不同调度算法对同一个作业流的性能􀂄W：同一调度算法对不同作业流的性能衡量,第三章 处理器调度,,3.1 作业的管理和调度3.2 处理器调度的层次3.3 选择调度算法的原则 3.4 处理器调度算法,低级调度的功能和类型,低级调度的对象:进程或内核级线程，而 用户级线程调度是用户自己的事低级调度需要解决的问题: WHAT:按什么原则分配CPU —调度算法 WHEN:何时分配CPU —调度的时机 HOW:如何分配CPU —调度过程（进程的上下文切换）,低级调度的功能,(1)调度:实现调度策略(2)分派:实现调度机制,什么时候出现低级调度？,进程正常终止或异常终止正在执行的进程因某种原因而阻塞 提出I/O请求 在调用P操作时因资源不足而阻塞在引入时间片的系统中,时间片用完在剥夺调度方式中,就绪队列中某进程的优先权变得比当前正在执行的进程高,或有优先权更高的进程进入就绪队列,调度机制的功能模块,（1）队列管理程序 根据要求在各等待队列和就绪队列中移动PCB/TCB指针（2）上下文切换程序 保存当前运行进程的上下文信息到PCB，恢复选中进程，使其运行 （3）分派程序 当前进程上下文－分派进程上下文－选中的进程上下文,低级调度的基本类型,非剥夺式(Non Non-preemptive Mode) Mode)：分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程。

剥夺方式(Preemptive Mode) Mode)：当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程作业调度和低级调度算法,在操作系统中，大多数调度算法对作业调度和低级调度都是适用的1、先来先服务算法（FCFS）2、最短作业优先算法（SJF）3、最短剩余时间优先算法（SRTF）4、响应比最高者优先算法（HRRF）5、优先级调度算法6、轮转调度算法7、多级反馈队列调度算法8、彩票调度算法,1、先来先服务算法,应用范围与含义– 作业调度：选择一个或多个最先进入后备队列的作业，将它们调入内存，为它们分配资源、创建进程，并放入就绪队列– 进程调度：按照进程就绪的先后次序来调度进程，为之分配处理机非剥夺式，最简单,。