作业调度实例ppt课件

2.6批处理作业的管理与调度,主要内容2.6.1作业和进程的关系2.6.2批处理作业的管理2.6.3批处理作业的调度2.6.4作业调度算法,1,2.6.1作业和进程的关系,1、作业的概念与特点作业(JOB)：是用户提交给OS计算的一个独立任务作业步(JobStep)：一般作业须经过若干个相对独立又相互关联的顺序加工步骤才能得到结果，其中每一步骤称为作业步。作业的组织与作业步的确定，由用户做。作业的四个阶段：提交、收容、执行和完成。是一个动态的概念。,2,2.6.1作业和进程的关系（2）,2、作业与进程的关系作业是任务实体，进程是完成任务的执行实体；没有作业任务，进程无事可干，没有进程，作业任务没法完成。作业概念更多地用在批处理操作系统，而进程则可以用在各种多道程序设计系统。,3,2.6.2批处理作业的管理,一、几个术语：脱机工作：批处理作业多采用脱机控制方式工作作业控制语言：用于写作业说明书作业说明书：主要有用户的各种请求、作业的控制要求等。批处理作业的过程：输入、调度、执行和撤离。即作业的四个阶段,4,二、作业控制块(1),作业控制块（JCB）：多道批处理操作系统具有独立的作业管理模块，必须像进程管理一样为每一个作业建立作业控制块。JCB的创建与撤消：JCB通常是在批作业进入系统时，由Spooling系统(P428)建立的，它是作业存在于系统的标志，作业撤离时，JCB也被撤销。Spooling技术：Spooling技术是用一类物理设备模拟另一类设备的技术。为了存放从输入设备输入的信息（程序、数据、作业说明书）及作业执行的结果，在辅助存储器上开辟了输入井（缓冲区）和输出井，模拟输入和输出设备。,5,二、作业控制块(2),JCB的主要内容：(1)作业情况：用户名、作业名、语言名(2)资源需求：估计CPU运行时间、最迟截止期、主存量、设备类型/台数、文件数和数据量、函数库/实用程序等。(3)资源使用情况：进入系统时间、开始运行时间、己运行时间。(4)作业控制：优先数、控制方式、操作顺序、出错处理等。(5)作业类型：CPU繁忙型、I/O繁忙型、批量型、终端型。,6,三、作业的生命周期,作业生命周期有4个状态(4个阶段)：输入状态：此时作业的信息正在从输入设备上预输入。后备状态：此时作业预输入结束但尚未被创建进程（不能执行）执行状态：作业已经被选中并构成进程去竞争处理器资源以获得运行。完成状态：作业已经运行结束，正在等待缓输出。,7,作业调度与进程调度的关系,缓输出,8,2.6.3批处理作业的调度,作业调度：对成批进入计算机系统的用户作业，根据作业控制块的信息，按一定的策略选取某些作业，使它们可以去获得处理器运行，这项工作称为作业调度。作业调度的基本目标：对任一作业的处理要尽可能快（Ti要小）对所有作业完成得快(T=Ti要小)整个系统的效率高,9,2.6.4作业调度算法,一、先来先服务算法FCFS(1)（FirstComeFirstServed）按照作业进入系统的先后次序来挑选作业，先进入系统的作业优先被挑选。FCFS算法的优缺点：算法容易实现。但效率不高，只顾及作业等候时间，没考虑作业要求服务时间的长短。因此优待了长作业而不利于短作业。,10,一、先来先服务算法FCFS(2),例如，三个作业同时到达系统并立即进入调度：作业名所需CPU时间作业128作业29作业33采用FCFS算法，三个作业的周转时间分别为：28、37和40，因此，平均作业周转时间T=(28+37+40)/3=35,11,二、先来先服务算法FCFS(3),若三个作业提交顺序改为作业2、1、3，平均作业周转时间约为29。(9+37+40)/329)若三个作业提交顺序改为作业3、2、1，平均作业周转时间约为18。(3+12+40)/318)FCFS调度算法的平均作业周转时间与作业提交的顺序有关。,12,二、最短作业优先算法SJF(1),SJF(ShortestJobFirst)SJF算法以进入系统的作业所要求的CPU时间为标准，总选取估计计算时间最短的作业投入运行。FJF算法的优缺点：算法易于实现。但效率不高，主要弱点是忽视了作业等待时间；会出现饥饿现象。,13,二、最短作业优先算法SJF(2),例如，四个作业同时到达系统并立即进入调度：作业名所需CPU时间作业19作业24作业310作业48假设系统中没有其他作业，现实施SJF调度算法，,14,二、最短作业优先算法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.98如果对它们施行FCFS调度算法，平均作业周转时间T=(9+13+23+31)/4=19平均带权作业周转时间W=(9/9+13/4+23/10+31/8)/4=2.51,15,二、最短作业优先算法SJF(4),SJF算法与FCFS算法的比较：SJF的平均作业周转时间比FCFS要小，故它的调度性能比FCFS好。SJF调度算法的问题：实现SJF调度算法需要知道作业所需运行时间，否则调度就没有依据，要精确知道一个作业的运行时间是办不到的。,16,SJF算法进一步讨论(1),最短剩余时间优先算法SRTF（ShortestRemainingTimeFirst）:把SJF算法改为抢占式的SJF算法一个新作业进入就绪状态，如果新作业需要的CPU时间比当前正在执行的作业剩余下来还需的CPU时间短，SRTF强占当前正在执行作业的CPU。此算法不但适用于作业JOB调度，同样也适用于进程调度。,17,SJF算法进一步讨论(2),例子：假如四个就绪作业其到达系统和所需CPU时间如下：作业名到达系统时间用CPU时间(毫秒)-Job108Job214Job329Job435JOB5101,18,SJF算法进一步讨论(3),采用SRTF算法各作业运行所需时间及运行的起止时间：,19,SJF算法进一步讨论(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毫秒。(0+(8-1)+(17-2)+(12-3)/4=31/4=7.75,20,三、响应比最高者优先(HRRF)算法,HRRF（HighestResponseRatioFirst）FCFS与SJF是片面的调度算法。FCFS只考虑作业等候时间而忽视了作业的计算时问，SJF只考虑用户估计的作业计算时间而忽视了作业等待时间。HRRF是介乎这两者之间的折衷算法，既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业又不使长作业的等待时间过长，改进了调度性能。,21,三、HRRF-响应比定义,作业进入系统后的等待时间与估计运行时间之比称作响应比，即响应比1+已等待时间/估计运行时间HRRF算法特点：短作业容易得到较高响应比长作业等待时间足够长后，也将获得足够高的响应比，饥饿现象不会发生。,22,三、HRRF-算法举例(1),例如，以下四个作业先后到达系统进入调度：作业名到达时间所需CPU时间作业1020作业2515作业3105作业41510,23,三、HRRF-算法举例(2),假设实施SJFSJF的作业调度顺序为作业1、3、4、2，平均作业周转时间T=(20+(25-19)+(35-15)+(50-5)(20+15+20+45)4=25平均带权作业周转时间W=(20/20+15/5+25/10+45/15)4=2.25,24,三、HRRF-算法举例(3)假设实施FCFS,如果对它们施行FCFS调度算法平均作业周转时间T=(20+30+30+35)4=28.75平均带权作业周转时间W=(20/20+30/15+30/5+35/10)4=3.13,25,三、HRRF-算法举例(4)对作业流执行HRRF调度算法,开始只有作业1，被选中执行时间20ms；作业1执行完毕，响应比依次为1+15/15、1+10/5、1+5/10，作业3被选中，执行时间5ms；作业3执行完毕，响应比依次为1+20/15、1+10/10，作业2被选中，执行时间15ms；作业2执行完毕，作业4被选中，执行时间10ms；平均作业周转时间T=(20+15+35+35)/4=26.25平均带权作业周转时间W=(20/20+15/5+35/15+35/10)/4=2.46,作业1324,26,四、优先数法,这种算法是根据确定的优先数来选取作业，每次总是选择优先数高的作业。规定用户作业优先数的方法：一种是由用户自己提出作业的优先数。另一种是由系统综合考虑有关因素来确定用户作业的优先数。,27,五、分类调度算法,思想：预先按一定原则把