作业调度之最短作业优先算法5例题解析

作业调度之最短作业优先算法5例题解析

例题一、某系统采用不能移动已在主存储器中作业的可变分区方式管理主存储器，现有供用户使用的主存空间100K，系统配有4台磁带机，有一批作业见下表：

作业序号 进输入井时间 要求计算时间 需要主存容量 申请磁带机数 1 10：00 25分钟 15K 2台 2 10：20 30分钟 60K 1台 3 10：30 10分钟 50K 3台 4 10：35 20分钟 10K 2台 5 10：40 15分钟 30K 2台 按计算时间最短者优先算法如下表：

我的解释：系统首先装入1、2、4，但1结束时4沿未到达，因此先执行2；2执行完毕后，资源可以分配给3或5，考虑5的时间短优先分配5并执行，执行完5后，主存中只有4已就绪并等待执行，因此开始执行4，执行4的同时系统会将作业3装入主存，最后自然执行作业3；因此最后的顺序是： 1\\2\\5\\4\\3

作业序号 进输入井时间 进入主存时间 开始计算时间 结束计算时间 周转时间 解释

1 10：00 10：10 10：00 10：25 25

此时输入井中只有一个作业且满足资源要求，因此被选中运行。 2 10：20 10：20 10：25 10：55 35

作业2到达输入井，满足资源要求，装入主存，等到作业1运行完毕进入运行。 5 10：40 10：55 10：55 11：10 30

由于作业3要求主存空间无法满足，因此作业4先行一步装入主存，当作业2让出处理器的同时，作业5满足资源要求进入主存就绪。根据算法作业5先进入处理器运行。 4 10：35 10：35 11：10 11：30 55 3 10：30 11：30 11：30 11：40 70

最后作业3装入主存并运行 平均周转时间：（25+35+30+55+70）/5＝43 分钟 ［分析］解答本题时应注意如下几个问题：

1

第一，系统采用的是多道程序设计技术，但没有限定并行工作的道数，因此，只要当前尚未分配的资源可以满足在输入井中等待的某些作业的要求时，作业调度可以按照给定的算法从中选择一个或多个作业装人主存储器；

第二，采用可变分区方式管理主存储器，但没给出主存空间的分配算法，因而，只要有合适的空间就可分配，题中还规定可用移动技术来合并分散的空闲区； 第三，对磁带机采用静态分配；

第四，进程调度采用可抢占的最高优先级调度算法，即对已被装人主存储器的作业而言优先级高的作业可抢占处理器执行；

第五，虽然作业需要使用磁带机，但题意中已提示忽略磁带机和调度所花的时间，所以，解题时不必考虑外围设备的启动二八D中断等复杂情况，只需把它们当作纯计算型的作业；

第六，由于没有规定什么时候开始进行作业调度，故在一般情况下只要输入井中有等待处理的作业就可按选定的算法去选择满足必要条件的作业。 根据本题的要求列表分析如下：

在10：3O时，作业（3）进人输入井，但因主存空闲空间虽然有40K却因被分成各为15K和25K的两个区域而不能用来装人作业（3）。当移动作业（2）后可把作业（3）装人主存储器，由于作业（3）的计算时间比作业（2）短，按规定的进程调度算法作业（3）可抢占处理器，致使作业（2）暂停运行。当作业（3）结束时已有作业（4）和（5）在输人井等待处理，它们都满足作业调度的必要条件，但由于作业（5）的计算时间短于作业（4），故先把作业（5）装人主存储器。现主存储器中有作业（2）和作业（5）两个作业，因作业（5）的优先级高于作业（2），故作业（2）的运行仍将被推迟。当作业（5）结束后作业调度又可选作业（4）进人主存储器，同样地，作业（4）抢先于作业（2）

2

运行。

可见，作业调度选中作业的次序为：（1）、（2）、（3）、（5）、（4），作业（2）是最后一个结束的作业且被移动过。

「题解］(1）作业调度选中作业的次序依次为作业（1）、（2）、（3）、（5）、（4），最后一个执行结束的是作业（2）。

（2）为了把作业（3）装人主存储器而移动了作业（2）。 （3）每个作业的周转时间可列表于下：

五个作业的平均周转时间为：

（25＋80＋10＋40＋15）／5＝170／5=34（分钟）

例题二、2005.4.42.在一个多道程序系统，用户空间为100K，有四台打印机；采用在主存的作业不能移动的可变分区方式管理主存。主存空间采用最先适应分配算法，静态分配打印机；对作业采用计算时间短的作业优先调度算法管理。 今有如下所示的作业序列，请分别列出各个作业的执行时间和周转时间。注意：忽略系统开销。 作业名 进入输入井时需计算时间 需打印机台数 主存需求间 量 JOB1 8.0时 1小时 2台 20K JOB2 8.2时 0.6小时 1台 60K JOB3 8.4时 0.5小时 1台 25K JOB4 8.6时 1小时 3台 20K JOB5 9.0时 0.5小时 2台 20K

标准答案：JOB1 \\JOB2 \\JOB5 \\JOB3 \\JOB4

解析：首批装入JOB1\\JOB2\\JOB4，由于JOB1首先到达先执行它，执行完后的时间是9，JOB2和JOB4按时间短算法，先执行JOB2，JOB2执行完后，正在主存就绪等待的是：“JOB4和JOB5” ， 再根据时间短算法我们优先执行JOB5，JOB5执行完后，正在主存就绪等待的是“JOB4和JOB3”，再根据时间短算法我们优先执行JOB3，最后执行JOB4，因此最终的作业序列是：“1-2-5-3-4”

3

例题三、2008.4.46、在一个多道程序系统，供用户使用的主存空间有100K，采用计算时间短的作业优先算法。今有如下所示的作业序列，它们的提交时间、运行时间和对主存需求的数量在下表中所列，当第一个作业进入系统后开始调度，假定作业都是仅作计算，请列出各个作业的开始时间、完成时间和周转时间。注意：忽略系统开销。

作业 进入输人井时间 需计算时间 主存需求 开始时间 完成时间 周转时间

1 8．0时 0．5小时 15K 2 8．2时 0．4小时 60K 3 8．3时 0．3小时 40K 4 8．5时 0．2小时 10K 5 8．6时 0．1小时 15K

标准答案：

解析：内存空间有100K，首先装入1\\2\\4\\5，根据时间顺序优先执行1，执行完1之后的时间是8.5，此时按短时间算法应该先执行5，但5沿未到达，因此我优先执行4，执行完4之后的时间点是8.6；此时按短时间算法我们继续执行5，执行完5之后虽剩余内存可分配给3，但作业2早已在主存就绪等待，我们优先执行作业2，最后再执行作业3；因此最终的作业序列是：1-4-5-2-3

4