操作系统作业调度算法

第四组 朱志华 李磊 石燕 于洪波

作业的基本概念 作业是用户交给计算机的具有独立功能的 任务。 在联机系统中，从用户登录系统到用户退 出系统的整个过程，可以多次形成作业， 用户每输入一条命令或运行一段程序都代 表着一个作业步。 作业在系统中也是动态的，从作业产生到 作业消失的整个过程中，作业的状态跟随 系统的运作而发生变化。

作业调度算法 作业调度的主要任务、目标、计价作业调 度算法的优劣的性能指标、主要作业调度 算法及作业调度的时机是什么？ 作业调度的主要任务是：按照某种调度算法， 从后备作业中挑选一批合理搭配的作业进 入运动状态；同时为选中的作业分配内存 和外部设备资源，为其建立相关的进程， 当作业执行结束进入完成状态时，做好释 放资源等善后工作。

作业调度的目标： 1、响应时间快速2、周转时间或带权周转时间短3、均衡 的资源利用率；4、吞吐量大；5、系统反应时间短。

评价作业调度算法优劣的性能指标： 1、作业平均周转时间；2、作业平均带权周转时间

主要作业调度算法有： 1、先来先服务法；2、短作业优先算法；3、最高响应比 优先算法；4、资源搭配算法；5、多队列循环算法。

作业调度时机： 一般当输入井中有一道作业建立，或内存中的一道作业运 动结束时，系统启动统调度工作。

作业从进入系统到运行结束，一般要经历进入、 后备、运行、完成四个阶段。相应地，我们说此 作业处于进入、后备、执行、完成四个不同的状 态。 进入状态 即提交状态，作业从输入设备进入输入井。 后备状态 操作员把作业输入到直接存取的后援存取器后， 为进入系统的作业建立作业控制块， 并把它加入到后备 作业队列中，等候作业调度程序调度。这一过程也称为作 业注册。 运行状态 作业被作业调度程序选中，且分配了必要的资 源，建立一组相应的进程后，该作业就 进入了运行状态。 它分为三种状态：即就绪状态、执行状态、阻塞状态。 完成状态 当作业正常运行结束或因发生错误而终止时， 作业进入完成阶段。

作业中进程的状态转换图

作业调度程序作业调度程序 的主要功能是审 查系统能否满足 用户作业的资源 要求以及按照一 定的算法选取作 业。

调度算法性能的衡量作业平均周转时间 平均带权周转时间

常见的批处理作业调度算法(1)先来先服务算法 (FCFS:First Come First Serve) (2)最短作业优先算法 (SJF:Shortest Job First) (3)最高响应比优先算法 (HRN:Highest Response Ratio Next)响应比R = 作业周转

时间 / 作业处理时间=(作业处理时间 + 作业等待时间)/ 作业处理时间 = 1 +(作业等待时间 / 作业处理时间)

(4)基于优先数调度算法 (HPF:Highest Priority First) (5)均衡调度算法(分类排队算法)

先来先服务：FCFS算法是按作业到达的先 先来先服务： 后次序来进行调度。 最短作业优先的调度算法：SJF算法总是优 最短作业优先的调度算法： 先调度要求运行时间最短的作业，把它作 为 下一次服务的对象。 响应比高者优先调度算法：HRN算法就是 响应比高者优先调度算法： 在每调度一个作业投入执行时，计算后备 作业 中每个作业的响应比，挑选响应比高 者投入执行。

作业调度算法应用例子

假设以下有四个作业，已知它们进入系 统的时间、估计运行时间，应用先来先 服务、最短作业优先和最高响应比优先 作业调度算法，分别计算出作业的平均 周转时间和带权的平均周转时间。

先来先服务调度算法计算结果业 作 入 间 进 时 计 行 开 时 估 运 始 间 时 间 ( 钟 分 ) 120 8: 00 8: 00 : : 50 : : 8: 50 10: 00 10 : : 9: 00 10: 50 20 9: 50 11: 00 : : 业 均 转 间 作 平 周 时 T = 112.5 作 带 平 周 时 W= 4.975 业 权 均 转 间 束 间 结 时 转 间 周 时 ( 钟 分 ) 120 120 120 90 450 权 转 带 周 时 间 1 2.4 12 4.5 19.9

JOB1 JOB2 JOB3 JOB4

10: 00 : : 10: 50 : 11: 00 11: 20 :

最短作业优先作业算法计算结果业 作 入 间 进 时 计 行 开 时 始 间 估 运 时 间 ( 钟 分 ) 120 8: 8: 00 8: 8: 00 50 8: 50 10: 30 : : 10 : : 9: 00 10: 00 20 9: : 50 10: : 10 业 均 转 间 作 平 周 时 T = 95 作 带 平 周 时 W= 3.25 业 权 均 转 间 束 间 结 时 转 间 周 时 ( 钟 分 ) 120 150 70 40 380 权 转 带 周 时 间 1 3 7 2 13

JOB1 JOB2 JOB3 JOB4

10: 10: 00 11: 20 : : 10: 10 10: : 30

最高响应比优先作业算法计算结果

作业

进入时间

JOB1 JOB2 JOB3 JOB4

估计运行 开始时间 时间 分钟) (分钟) 120 : : 8:00 8:00 30 8:50 : 10:10 : 10 9:00 10:00 : : 20 9:50 : 11:00 : 作业平均周转时间 T = 87.5 作业带权平均周转时间 W = 4.075

结束时间

周转时间 分钟) (分钟) 120 70 70 90 350

带权周转 时间 1 1.4 7 4.5 16.3

: 10:00 11:00 : 10:10 : 11:20 :