作业调度算法.ppt

作业调度算法 先来先服务FCFS 进程名 到达 时间 服务 时间 开始执行时间 结束 时间 周转 时间 带权周转时间 A 0 4 0 4 4 1 B 1 3 4 7 6 2 C 2 5 7 12 10 2 D 3 2 12 14 11 5.5 E 4 4 14 18 14 3.5 平均周转时间：9，平均带权周转时间：2.8 短作业优先调度算法(SJF) 进程名 到达 时间 服务 时间 开始执行时间 结束 时间 周转 时间 带权周转时间 A 0 4 4 4 4 1 B 1 3 6 9 8 2.67 C 2 5 13 18 16 3.1 D 3 2 4 6 3 1.5 E 4 4 9 13 9 2.25 平均周转时间：8，平均带权周转时间：2.1 高响应比优先调度算法 Rp=（等待时间+要求服务时间）/要求服务时间=1+等待时间/要求服务时间 进程名 到达 时间 服务 时间 开始执行时间 结束 时间 周转 时间 带权周转时间 A 0 4 4 4 4 1 B 1 3 4 7 6 2 C 2 5 9 14 12 2.4 D 3 2 7 9 6 3 E 4 4 14 18 14 3.5 平均周转时间：8.4，平均带权周转时间：2.38 1、设有4道作业，他们的提交时间及执行时间如下： 试计算在单道程序环境下，分别采用先来先服务和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并分别指出它们的调度顺序。 作业号 提交时间 执行时间 1 10.0 2.0 2 10.2 1.0 3 10.4 0.5 4 10.5 0.3 (1)FCFS 顺序：1、2、3、4 平均周转时间：T=（2.0+2.8+3.1+3.3）/4=2.8 平均带权周转时间：W=（1+2.8+6.2+11）4=5.25 (2)短作业优先：1、4、3、2 平均周转时间：T=（2.0+1.8+2.4+3.6）/4=2.45 平均带权周转时间：W=（1+6+4.8+3.6）4=3.85 2、有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法，在下表所示的作业序列，作业优先数即为进程优先数，优先数越小优先级越高。 （1） 列出所有作业进入内存时间及结束时间 （2）计算平均周转时间 作业名 到达时间 估计运行时间 优先数 A 10:00 40分 5 B 10:20 30分 3 C 10:30 50分 4 D 10:50 20分 6 （1）所有作业的进入内存时间和结束时间： 作业的平均周转时间为：（70+30+90+90）/4=70分。 作业名 到达时间 估计运 行时间 优先数 进入内 存时间 开始执 行时间 结束 时间 周转时间 A 10:00 40分 5 10:00 10:00 11:10 70 B 10:20 30分 3 10:20 10:20 10:50 30 C 10:30 50分 4 11:10 11:10 12:00 90 D 10:50 20分 6 10:50 12:00 12:20 90 3、有一多道程序设计系统，采用不允许移动的可变分区方式管理主存空间，设主存空间为100K，采用最先适应算法分配主存，作业调度和进程调度均采用先来先服务算法，今有如下作业序列： 试完成下表： 作业 提交时间 预计运行时间 主存要求 1 10.1 0.3小时 15K 2 10.3 0.5小时 60K 3 10.5 0.4小时 50K 4 10.6 0.4小时 10K 5 10.7 0.2小时 20K 作业 提交时间 预计运 行时间 主存要求 开始执 行时间 完成时间 周转时间 1 10.1 0.3小时 15K 2 10.3 0.5小时 60K 3 10.5 0.4小时 50K 4 10.6 0.4小时 10K 5 10.7 0.2小时 20K 平均周转时间： 作业 提交时间 预计运 行时间 主存要求 开始执 行时间 完成时间 周转时间 1 10.1 0.3小时 15K 10.1 10.4 0.3 2 10.3 0.5小时 60K 10.4 10.9 0.6 3 10.5 0.4小时 50K 11.5 11.9 1.4 4 10.6 0.4小时 10K 10.9 11.3 0.7 5 10.7 0.2小时 20K 11.3 11.5 0.8 平均周转时间：0.76 4、某系统采用不能移动已在主存中作业的可变分区方式管理主存，现在有供用户使用的主存空间100K，系统配有4台磁带机，现有一作业序列： 该系统采用多道程序设计技术，对磁带机采用静态分配，请分别写出采用先来先服务和短作业优先算法选中作业执行的次序和平均周转时间。 作业号 提