作业调度实例

1、2.6 批处理作业的管理与调度批处理作业的管理与调度主要内容主要内容2.6.1 作业和进程的关系作业和进程的关系2.6.2 批处理作业的管理批处理作业的管理2.6.3 批处理作业的调度批处理作业的调度2.6.4 作业调度算法作业调度算法2.6.1 作业和进程的关系作业和进程的关系1、作业的概念与特点、作业的概念与特点 作业作业(JOB)：是用户提交给是用户提交给OS计算的计算的一个独立任务一个独立任务 作业步作业步(Job Step)：一般作业须经过一般作业须经过若干个相对独立又相互关联的顺序加工若干个相对独立又相互关联的顺序加工步骤才能得到结果，其中每一步骤称为步骤才能得到结果，其中每一步骤

2、称为作业步。作业步。 作业的组织与作业步的确定，由用户作业的组织与作业步的确定，由用户做。做。 作业的四个阶段：作业的四个阶段：提交、收容、执行提交、收容、执行和完成。是一个动态的概念。和完成。是一个动态的概念。2.6.1 作业和进程的关系（作业和进程的关系（2）2、作业与进程的关系、作业与进程的关系 作业是任务实体作业是任务实体，进程是完成任务，进程是完成任务的执行实体；没有作业任务，进程无事的执行实体；没有作业任务，进程无事可干，没有进程，作业任务没法完成。可干，没有进程，作业任务没法完成。 作业概念更多地用在批处理操作系统，作业概念更多地用在批处理操作系统，而进程则可以用在各种多道程序设

3、计系而进程则可以用在各种多道程序设计系统。统。2.6.2 批处理作业的管理批处理作业的管理一、几个术语：一、几个术语： 脱机工作：脱机工作：批处理作业多采用脱机控制批处理作业多采用脱机控制方式工作方式工作 作业控制语言作业控制语言：用于写作业说明书用于写作业说明书 作业说明书作业说明书：主要有用户的各种请求、主要有用户的各种请求、作业的控制要求等。作业的控制要求等。 批处理作业的过程：批处理作业的过程：输入、调度、执输入、调度、执行和撤离。即作业的四个阶段行和撤离。即作业的四个阶段 二、二、作业控制块作业控制块(1) 作业控制块（作业控制块（JCB）：）：多道批处理操作多道批处理操作系统具有独

4、立的作业管理模块，必须像进程系统具有独立的作业管理模块，必须像进程管理一样为每一个作业建立作业控制块管理一样为每一个作业建立作业控制块。 JCB的创建与撤消：的创建与撤消：JCB通常是在批作业通常是在批作业进入系统时，由进入系统时，由Spooling系统系统(P428)建立的，建立的，它是作业存在于系统的标志，作业撤离时，它是作业存在于系统的标志，作业撤离时，JCB也被撤销。也被撤销。 Spooling技术：技术： Spooling技术是用技术是用一类物一类物理设备模拟另一类设备的技术。为了存放从输入理设备模拟另一类设备的技术。为了存放从输入设备输入的信息（程序、数据、作业说明书）及设备输入的

5、信息（程序、数据、作业说明书）及作业执行的结果，在辅助存储器上开辟了输入井作业执行的结果，在辅助存储器上开辟了输入井（缓冲区）和输出井，模拟输入和输出设备。（缓冲区）和输出井，模拟输入和输出设备。二、作业控制块二、作业控制块(2) JCB的主要内容：的主要内容： (1)作业情况：作业情况：用户名、作业名、语言名用户名、作业名、语言名 (2)资源需求：资源需求：估计估计CPU运行时间、最迟运行时间、最迟截止期、主存量、设备类型截止期、主存量、设备类型/台数、文件台数、文件数和数据量、函数库数和数据量、函数库/实用程序等。实用程序等。 (3)资源使用情况：资源使用情况：进入系统时间、开始运进入系统

6、时间、开始运行时间、己运行时间。行时间、己运行时间。 (4)作业控制：作业控制：优先数、控制方式、操作顺优先数、控制方式、操作顺序、出错处理等。序、出错处理等。 (5)作业类型：作业类型：CPU繁忙型、繁忙型、I/O繁忙型、繁忙型、批量型、终端型。批量型、终端型。三、作业的生命周期三、作业的生命周期作业生命周期有作业生命周期有4个状态个状态(4个阶段个阶段)： 输入状态：输入状态：此时作业的信息正在从输此时作业的信息正在从输入设备上预输入。入设备上预输入。 后备状态：后备状态：此时作业预输入结束但尚此时作业预输入结束但尚未被创建进程（不能执行）未被创建进程（不能执行） 执行状态：执行状态：作业

7、已经被选中并构成进作业已经被选中并构成进程去竞争处理器资源以获得运行。程去竞争处理器资源以获得运行。 完成状态：完成状态：作业已经运行结束，正在作业已经运行结束，正在等待缓输出。等待缓输出。作业调度与进程调度的关系作业调度与进程调度的关系 缓输出缓输出执行状态执行状态运运行行就就绪绪等等待待输输入入状状态态后后备备状状态态完完成成状状态态进程调度进程调度中级调度中级调度作业调度作业调度预输入预输入完成完成撤消进程撤消进程创建进程创建进程2.6.3 批处理作业的调度批处理作业的调度 作业调度：作业调度：对成批进入计算机系统的对成批进入计算机系统的用户作业，根据作业控制块的信息，按用户作业，根据作

8、业控制块的信息，按一定的策略选取某些作业，使它们可以一定的策略选取某些作业，使它们可以去获得处理器运行，这项工作称为作业去获得处理器运行，这项工作称为作业调度。调度。 作业调度的基本目标：作业调度的基本目标： 对任一作业的处理要尽可能快对任一作业的处理要尽可能快（Ti要小）要小） 对所有作业完成得快对所有作业完成得快(T=Ti要小要小) 整个系统的效率高整个系统的效率高2.6.4 作业调度算法作业调度算法 一、先来先服务算法一、先来先服务算法FCFS(1)（First Come First Served） 按照作业进入系统的先后次序来挑选按照作业进入系统的先后次序来挑选作业，作业，先进入系统的

9、作业优先被挑选先进入系统的作业优先被挑选。 FCFS算法的优缺点：算法的优缺点： 算法容易实现。算法容易实现。但效率不高，只顾及但效率不高，只顾及作业等候时间，没考虑作业要求服务时作业等候时间，没考虑作业要求服务时间的长短。因此优待了长作业而不利于间的长短。因此优待了长作业而不利于短作业。短作业。 一、先来先服务算法一、先来先服务算法FCFS(2) 例如，三个作业同时到达系统并立即例如，三个作业同时到达系统并立即进入调度：作业名进入调度：作业名 所需所需CPU时间时间 作业作业1 28 作业作业2 9 作业作业3 3 采用采用FCFS算法，三个作业的周转时间算法，三个作业的周转时间分别为：分别

10、为：28、37和和40，因此，因此，平均作平均作业周转时间业周转时间T = (28+37+40)/3 = 35二、先来先服务算法二、先来先服务算法FCFS(3) 若三个作业提交顺序改为作业若三个作业提交顺序改为作业2、1、3，平均作业周转时间约为平均作业周转时间约为29。(9+37+40)/3 29) 若三个作业提交顺序改为作业若三个作业提交顺序改为作业3、2、1，平均作业周转时间约为平均作业周转时间约为18。(3+12+40)/3 18) FCFS调度算法的平均作业周转时间调度算法的平均作业周转时间与作业提交的顺序有关与作业提交的顺序有关。二、最短作业优先算法二、最短作业优先算法SJF(1)

11、SJF(Shortest Job First ) SJF算法以进入系统的作业所要算法以进入系统的作业所要求的求的CPU时间为标准，时间为标准，总选取估计总选取估计计算时间最短的作业投入运行计算时间最短的作业投入运行。FJF算法的优缺点：算法的优缺点： 算法易于实现。算法易于实现。但效率不高，主但效率不高，主要弱点是忽视了作业等待时间；要弱点是忽视了作业等待时间； 会出现饥饿现象。会出现饥饿现象。二、最短作业优先算法二、最短作业优先算法SJF(2) 例如，四个作业同时到达系统并立即进例如，四个作业同时到达系统并立即进入调度：入调度： 作业名作业名 所需所需CPU时间时间 作业作业1 9 作业作业

12、2 4 作业作业3 10 作业作业4 8 假设系统中没有其他作业，现实施假设系统中没有其他作业，现实施SJF调度算法，调度算法，二、最短作业优先算法二、最短作业优先算法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 平均带权作业周转时间平均带权

13、作业周转时间 W = (9/9+13/4+23/10+31/8)/4 = 2.51二、最短作业优先算法二、最短作业优先算法SJF(4)SJF算法与算法与FCFS算法的比较：算法的比较： SJF的平均作业周转时间比的平均作业周转时间比FCFS要小，故它的调度性能比要小，故它的调度性能比FCFS好。好。SJF调度算法的问题：调度算法的问题： 实现实现SJF调度算法需要知道作业调度算法需要知道作业所需运行时间，否则调度就没有依所需运行时间，否则调度就没有依据，要精确知道一个作业的运行时据，要精确知道一个作业的运行时间是办不到的。间是办不到的。SJF算法进一步讨论算法进一步讨论(1) 最短剩余时间优先

14、算法最短剩余时间优先算法SRTF（Shortest Remaining Time First）: 把把SJF算法改为抢占式的算法改为抢占式的SJF算法算法 一个新作业进入就绪状态，如果新一个新作业进入就绪状态，如果新作业需要的作业需要的CPU时间比当前正在执行时间比当前正在执行的作业剩余下来还需的的作业剩余下来还需的CPU时间短，时间短，SRTF强占当前正在执行作业的强占当前正在执行作业的CPU。 此算法不但适用于作业此算法不但适用于作业JOB调度，调度，同样也适用于进程调度。同样也适用于进程调度。SJF算法进一步讨论算法进一步讨论(2) 例子：假如四个就绪作业其到达系统例子：假如四个就绪作业

15、其到达系统和所需和所需CPU时间如下：时间如下： 作业名作业名 到达系统时间到达系统时间 用用CPU时间时间(毫秒毫秒) - Job1 0 8 Job2 1 4 Job3 2 9 Job4 3 5JOB5101 SJF算法进一步讨论算法进一步讨论(3) 采用采用SRTF算法算法 各作业运行所需时间及运行的各作业运行所需时间及运行的起止时间：起止时间： J1 J2 J4 J1 J30151017268 4 5 7 90 1 3 0 2到达时间到达时间SJF算法进一步讨论算法进一步讨论(4) Job1从从0开始执行，就绪队列仅一个作业。开始执行，就绪队列仅一个作业。 Job2在时间在时间1到达，到

16、达，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三、响应比最高者优先三、响应比最高者优先(HRRF)算法算法HRRF（Highest Response Ratio First） FCFS与与SJF是片面的

17、调度算法是片面的调度算法。FCFS只考虑作业等候时间而忽视了作业的计只考虑作业等候时间而忽视了作业的计算时问，算时问，SJF只考虑用户估计的作业计只考虑用户估计的作业计算时间而忽视了作业等待时间。算时间而忽视了作业等待时间。 HRRF是介乎这两者之间的折衷算法是介乎这两者之间的折衷算法，既考虑作业等待时间，又考虑作业的运既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业又不使长作业的行时间，既照顾短作业又不使长作业的等待时间过长，改进了调度性能。等待时间过长，改进了调度性能。三、三、HRRF-响应比定义响应比定义 作业进入系统后的等待时间与估计作业进入系统后的等待时间与估计运行时间之比称作

18、响应比运行时间之比称作响应比，即，即 响应比响应比 1+已等待时间已等待时间/估计运行时间估计运行时间 HRRF算法特点：算法特点： 短作业容易得到较高响应比短作业容易得到较高响应比 长作业等待时间足够长后，也将获得足长作业等待时间足够长后，也将获得足够高的响应比，够高的响应比， 饥饿现象不会发生。饥饿现象不会发生。三、三、HRRF-算法举例算法举例(1) 例如，以下四个作业先后到达系统进入例如，以下四个作业先后到达系统进入调度：调度： 作业名作业名 到达时间到达时间 所需所需CPU时间时间 作业作业1 0 20 作业作业2 5 15 作业作业3 10 5 作业作业4 15 10三、三、HRR

19、F-算法举例算法举例(2)假设实施假设实施SJF SJF的作业调度顺序为作业的作业调度顺序为作业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三、三、HRRF-算法举例算法举例(3)假设实施假设实施FCFS 如果对它们施行如果对它们施行FCFS调度算法调度算法 平均作业周转时间平均作业周转时间T = (20+30+30+35)4 = 28.75 平均带权作业周转时间平均带权作业周转

20、时间W = (20/20+30/15+30/5+35/10)4 = 3.13三、三、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 平均带