结构推理 短作业优先调度算法总能得到最小的平均周转时间吗?为什么?
【正确答案】短作业优先调度算法只有在所有作业同时到达后备作业队列时,才能得到最小的平均周转时间。如果各作业不是同时到达,这个结论是不成立的。可以用反例说明,例如,教材上举有如下例子:考虑有5个作业A到E,运行时间分别是2、4、1、1、1;到达时间分别是0、0、3、3、3。按照短作业优先的原则,最初只有A和B可以参与选择,因为其他3个还没有到达。于是,运行顺序应该是A、B、C、D、E。它们每个的周转时间分别是2、6、4、5、6,平均周转时间是4.6。但如果按照顺序B、C、D、E、A来调度,它们每一个的周转时间成为9、4、2、3、4,平均周转时间是4.4。结果比短作业优先调度算法好。之所以会这样,就是因为这5个作业并没有同时到达。
【答案解析】