题目

在一个单道批处理[1]系统中 一组作业的提交时刻和运行时间如下表所示：作业 提交时间 运行时间 (分钟)-|||-1 8:00 60-|||-2 8:50 50-|||-3 9:00 20-|||-4 9:10 10采用短作业优先的作业调度算法 请给出作业的调度次序并计算平均周转时间T。

在一个单道批处理[1]系统中 一组作业的提交时刻和运行时间如下表所示：

采用短作业优先的作业调度算法 请给出作业的调度次序并计算平均周转时间T。

题目解答

答案

8:00时刻作业1提交，进入CPU开始运行，

9:00时刻，作业1完成，内存中有作业2、作业3，采用短作业优先调度算法，作业3需要的时间20min比作业2所需50min更短，所以将作业3载入CPU运行。

9:20时刻，作业3完成，内存中有作业2、作业4，采用短作业优先调度算法，作业4需要的时间10min比作业2所需50min更短，所以将作业4载入CPU运行。

9:30时刻，作业3完成，内存中有作业2，将作业2载入CPU运行，作业2在10:20完成。

因此调度次序1、3、4、2。

作业1调度时间60min，作业2调度时间90min，作业3调度时间20min，作业4调度时间20min。

因此

解析

考查要点：本题主要考查短作业优先（SJF）调度算法的应用，以及平均周转时间的计算。
解题核心思路：

  1. 时间顺序分析：按作业到达时间顺序，动态维护就绪队列，每次选择剩余运行时间最短的作业运行。
  2. 周转时间计算：每个作业的周转时间 = 完成时间 - 提交时间，最终求平均值。
    破题关键点：
  • 注意作业到达时间，确保在每个时间点只调度已到达的作业。
  • 动态更新队列，每次作业完成时需检查是否有新作业到达，并重新选择最短作业。

调度过程分析

  1. 8:00时刻
    • 作业1到达，立即运行，运行时间为60分钟，完成时间9:00。
  2. 9:00时刻
    • 作业1完成，此时内存中有作业2（8:50到达，剩余50分钟）和作业3（9:00到达，剩余20分钟）。
    • SJF选择作业3运行，运行时间为20分钟，完成时间9:20。
  3. 9:20时刻
    • 作业3完成，此时内存中有作业2（剩余50分钟）和作业4（9:10到达，剩余10分钟）。
    • SJF选择作业4运行，运行时间为10分钟，完成时间9:30。
  4. 9:30时刻
    • 作业4完成，内存中仅剩作业2，作业2开始运行，运行时间为50分钟，完成时间10:20。

周转时间计算

  • 作业1：完成时间9:00 - 提交时间8:00 = 60分钟
  • 作业2：完成时间10:20 - 提交时间8:50 = 90分钟
  • 作业3：完成时间9:20 - 提交时间9:00 = 20分钟
  • 作业4：完成时间9:30 - 提交时间9:10 = 20分钟

平均周转时间：
$\text{平均周转时间} = \frac{60 + 90 + 20 + 20}{4} = \frac{190}{4} = 47.5 \text{分钟}$