new_ch2-25处理器调度26批处理的管理与调度27低级调度

2.5处理机调度2.5.1处理机调度的层次2.5.3高级调度2.5.3中级调度2.5.4低级调度2.5.5选择调度算法的原则2.5.1处理机调度的层次高级调度(1)•作业调度、长程调度•高级调度的任务•批处理操作系统中的高级调度高级调度(2)分时操作系统中，高级调度任务：1）是否接受一个终端用户的连接；2）一个程序能否被计算机系统接纳并构成进程；3）一个新建态的进程是否能够加入就绪进程队列。中级调度(1)•平衡负载调度，中程调度。•决定主存储器中所能容纳的进程数，这些进程将允许参与竞争处理器资源。•中级调度根据存储资源量和进程的当前状态来决定辅存和主存中进程的对换。中级调度(2)•中级调度决定那些进程被允许参与竞争处理器资源，使用的方法是通过把一些进程换出主存，使之进入“挂起”状态，不参与进程调度，起到平滑和调整系统负荷的作用。低级调度(1)•进程调度、短程调度。•主要功能是按照某种原则决定就绪队列中的哪个进程或内核级线程能获得处理器,并将处理机出让给它进行工作。•短程调度程序是操作系统最为核心的部分，短程调度策略的优劣直接影响到整个系统的性能。低级调度(2)有两类低级调度方式：•第一类称剥夺方式：高优先级剥夺原则时间片剥夺原则•第二类称非剥夺方式：处理器调度的层次中级调度新建态挂起就绪态挂起等待态高级调度低级调度运行态就绪态等待态终止态处理器调度与进程状态转换高级调度中级调度低级调度运行态就绪态终止态新建态挂起就绪态中级调度挂起等待态等待态高级调度高级调度中级调度处理器的调度模型中级调度处理器低级调度高级调度完成超时挂起就绪队列挂起等待队列等待队列就绪队列等待事件交互式用户事件出现后备作业队列中级调度2.5.5选择调度算法的原则(1)l资源利用率CPU利用率=CPU有效工作时间/CPU总的运行时间，CPU总的运行时间=CPU有效工作时间+CPU空闲等待时间。选择调度算法的原则(2)2响应时间•交互式进程从提交一个请求(命令)到接收到响应之间的时间间隔称响应时间。•使交互式用户的响应时间尽可能短，或尽快处理实时任务。•这是分时系统和实时系统衡量调度性能的一个重要指标。选择调度算法的原则(3)3周转时间•批处理用户从作业提交给系统开始，到作业完成为止的时间间隔称作业周转时间，应使作业周转时间或平均作业周转时间尽可能短。•这是批处理系统衡量调度性能的一个重要指标。选择调度算法的原则(4)4吞吐率单位时间内处理的作业数。5公平性确保每个用户每个进程获得合理的CPU份额或其他资源份额，不会出现饿死情况。作业周转时间•如果作业i提交给系统的时刻是ts，完成时刻是tf，该作业的周转时间ti为：ti=tf-ts实际上，它是作业在系统里的等待时间与运行时间之和。平均作业周转时间•为了提高系统的性能，要让若干个用户的平均作业周转时间和平均带权周转时间最小。平均作业周转时间T=(Σti)/n作业带权周转时间和平均作业带权周转时间•如果作业i的周转时间为ti，所需运行时间为tk，则称wi=ti/tk为该作业的带权周转时间。•ti是等待时间与运行时间之和，故带权周转时间总大于1。平均作业带权周转时间W=(Σwi)/n衡量调度算法的调度性能•用平均作业周转时间来衡量对同一作业流施行不同作业调度算法时，它们呈现的调度性能；•用平均作业带权周转时间来衡量对不同作业流施行同一作业调度算法时，它们呈现的调度性能。这两个数值均2.6批处理作业的管理与调度2.6.1作业和进程的关系2.6.2批处理作业的管理2.6.3批处理作业的调度2.6.4作业调度算法2.6.1作业和进程的关系(1)•作业(JOB)，•作业步(JobStep)，•作业组织，•作业的提交、收容、执行和完成。作业和进程的关系(2)•作业是任务实体，进程是完成任务的执行实体;没有作业任务，进程无事可干，没有进程，作业任务没法完成。•作业概念更多地用在批处理操作系统，而进程则可以用在各种多道程序设计系统。2.6.2批处理作业的管理•批处理作业的脱机控制方式，•作业控制语言，•作业说明书，•批处理作业的输入，调度、执行和撤离。作业控制块(1)•多道批处理操作系统具有独立的作业管理模块，必须像进程管理一样为每一个作业建立作业控制块（JCB）。•JCB通常是在批作业进入系统时，由Spooling系统建立的，它是作业存在于系统的标志，作业撤离时，JCB也被撤销。作业控制块(2)JCB的主要内容包括：(1)作业情况(用户名、作业名、语言名),(2)资源需求(估计CPU运行时间、最迟截止期、主存量、设备类型/台数、文件数和数据量、函数库/实用程序等),(3)资源使用情况(进入系统时间、开始运行时间、己运行时间),作业控制(优先数、控制方式、操作顺序、出错处理等)。作业生命周期状态•输入状态：此时作业的信息正在从输入设备上预输入。•后备状态：此时作业预输入结束但尚未被选中执行。•执行状态：作业已经被选中并构成进程去竞争处理器资源以获得运行。•完成状态：作业已经运行结束，正在等待缓输出。2.6.3批处理作业的调度(1)•处于后备状态的作业在系统资源满足的前提下可以被作业调度选中进入内存计算。而只有处于执行状态的作业才真正构成进程获得计算的机会。批处理作业的调度(2)•作业调度选中一个作业且把它装入主存储器时就为该作业创建一个用户进程。这些进程将在进程调度的控制下占有处理器运行。•为了充分利用处理器，可以把多个作业同时装入主存储器，这样就会同时有多个用户进程，这些进程都要竞争处理器。批处理作业的调度(3)•进入计算机系统的作业只有经过两级调度后才能占用处理器。第一级是作业调度，使作业进入主存储器；第二级是处理器调度，使作业进程占用处理器。•作业调度与处理器调度的配合能实现多道作业的同时执行。作业调度与进程调度的关系执行状态运行就绪等待输入状态后备状态完成状态进程调度中级调度缓输出作业调度预输入完成2.6.4作业调度算法1先来先服务算法(1)•按照作业进入系统的先后次序来挑选作业，先进入系统的作业优先被挑选。•算法容易实现，效率不高，只顾及作业等候时间，没考虑作业要求服务时间的长短，•不利于短作业而优待了长作业。先来先服务算法(2)•例如，三个作业同时到达系统并立即进入调度：作业名所需CPU时间作业128作业29作业33•采用FCFS算法，三个作业的周转时间分别为：28、37和40，因此，平均作业周转时间T=(28+37+40)/3=35先来先服务算法(3)•若三个作业提交顺序改为作业2、1、3，平均作业周转时间约为29。•若三个作业提交顺序改为作业3、2、1，平均作业周转时间约为18。FCFS调度算法的平均作业周转时间与作业提交的顺序有关。2最短作业优先算法(1)•SJF算法以进入系统的作业所要求的CPU时间为标准，总选取估计计算时间最短的作业投入运行。•算法易于实现，效率不高，主要弱点是忽视了作业等待时间。•会出现饥饿现象。最短作业优先算法(2)•例如，四个作业同时到达系统并立即进入调度：作业名所需CPU时间作业19作业24作业310作业48假设系统中没有其他作业，现实施SJF调度算法，最短作业优先算法(3)•SJF的作业调度顺序为作业2、4、1、3，平均作业周转时间T=(4+12+21+31)/4=17平均带权作业周转时间W=(4/4+12/8+21/9+31/10)/4=1.98J2J4J1J34122131最短作业优先算法(4)•如果对它们施行FCFS调度算法，平均作业周转时间T=(9+13+23+31)/4=19平均带权作业周转时间W=(9/9+13/4+23/10+31/8)/4=2.51J1J2J3J49132331最短作业优先算法(5)•SJF的平均作业周转时间比FCFS要小，故它的调度性能比FCFS好。•实现SJF调度算法需要知道作业所需运行时间，否则调度就没有依据，要精确知道一个作业的运行时间是办不到的。最短作业优先算法(6)•可根据每个进程的执行历史来预测它的下一个CPU长度，令tn是第n个实际的执行长度，τn是其预测值，那么，下一个CPU执行长度的预测公式：τn+1=αtn+(1-α)τn其中，α(0α1)用于控制最近的tn和其预测值τn在预测中的作用，其值常为0.5。SJF算法进一步讨论(1)•SRTF把SJF算法改为抢占式的。一个新作业进入就绪状态，如果新作业需要的CPU时间比当前正在执行的作业剩余下来还需的CPU时间短，SRTF强行赶走当前正在执行作业,•此算法不但适用于JOB调度，同样也适用于进程调度。SJF算法进一步讨论(2)•一个例子,假如四个就绪作业其到达系统和所需CPU时间如下：作业名到达系统时间CPU时间(毫秒)---------------------------------------Job108Job214Job329Job435SJF算法进一步讨论(3)J1J2J4J1J3015101726SJF算法进一步讨论(4)•Job1从0开始执行，就绪队列仅一个作业。•Job2在时间1到达，Job1剩余时间（7毫秒）大于JOB2所需时间（4毫秒），Job1被剥夺，Job2被调度执行。•平均等待时间是（（10-1）+（1-1）+（17-2）+（5-3））/4=26/4=6.5毫秒。•采用非抢占式SJF调度，那么，平均等待时间是7.75毫秒。3响应比最高者优先(HRRF)算法•FCFS与SJF是片面的调度算法。FCFS只考虑作业等候时间而忽视了作业的计算时问，SJF只考虑用户估计的作业计算时间而忽视了作业等待时间。•HRRF是介乎这两者之间的折衷算法，既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业又不使长作业的等待时间过长，改进了调度性能。响应比定义作业进入系统后的等待时间与估计运行时间之比称作响应比，现定义；响应比＝1+已等待时间/估计运行时间•短作业容易得到较高响应比，•长作业等待时间足够长后，也将获得足够高的响应比，•饥饿现象不会发生。HRRF算法举例(1)例如，以下四个作业先后到达系统进入调度：作业名到达时间所需CPU时间作业1020作业2515作业3105作业41510HRRF算法举例(2)假设实施SJF•SJF的作业调度顺序为作业1、3、4、2，平均作业周转时间T=（20+25-10+35-15+50-5）/4=25平均带权作业周转时间W=（20/20+15/5+20/10+45/15）/4=2.25HRRF算法举例(3)假设实施FCFS•如果对它们施行FCFS调度算法，作业调度顺序为作业1、2、3、4，平均作业周转时间T=（20+35-5+40-10+50-15）/4=28.75平均带权作业周转时间W=（20/20+30/15+30/5+35/10）/4=3.125HRRF算法举例(4)对作业流执行HRRF调度算法•开始只有作业1，被选中执行时间20；•作业1执行完毕，响应比依次为1+15/15、1+10/5、1+5/10，作业3被选中，执行时间5；•作业3执行完毕，响应比依次为1+20/15、1+10/10，作业2被选中，执行时间15；•作业2执行完毕，作业4被选中，执行时间10；HRRF算法举例(5)对作业流执行HRRF调度算法平均作业周转时间T=（20+25-10+40-5+50-15）/4=26.25平均带权作业周转时间W=（20/20+15/5+35/15+35/10）/4=2.464优先数法(1)•这种算法是根据确定的优先数来选取作业，每次总是选择优先数高的作业。优先数法(2)规定用户作业优先数的方法：•一种是由用户自己提出作业的优先数。•另一种是由系统综合考虑有关因素来确定用户作业的优先数。5分类调度算法•预先按一定原则把作业划分成若干类，以达到均衡使用系统资源和兼顾大小作业的目的。•分类原则包括作业计算时间、对内存的需求、对外围设备的需求等。作业调度时还可为每类作业设置优先级，从而照顾到同类作业中的轻重缓急。6用与不用磁带的作业搭配•作业调度时，把使用磁带机和不使用磁带机的作业搭配挑选。•可使要用磁带机的作业在执行时省去等待