如何证明按短作业优先算法调度时其平均周转时间最短

答案:2 悬赏:0 手机版

解决时间 2021-03-07 10:18

提问者网友：箛茗
2021-03-06 12:46

最佳答案

五星知识达人网友：西风乍起
2021-03-06 13:46

假设有n个作业，按照运行时间排序t1 < t2 t1 + t2 + ... + t(i-1) + ti = a(i+1)
依次类推之后bx > ax 其中i < x < j+1.之后b与a又相等。
所以任意交换后，等待时间变大。所以最小作业优先的等待时间最小。所以平均周转时间最短。

全部回答

1楼网友：山河有幸埋战骨
2021-03-06 14:37

假设有n个作业，按照运行时间排序t1 < t2 <... < tn 平均周转时间 = （总的运行时间 + 总的等待时间）/n 其中总的运行时间是定值，n为定值，因此要平均周转时间最短既要求总的等待时间最短。按照最短作业优先，设第i个作业的等待时间为ai.则 a1 = 0 a2 = t1 a3 = t1 + t2 .... an = t1 + t2 + ... + t(i-1) 总的等待时间为a1 + a2 + a3 + ... + an 现在只需要证明这个是最小就可以了。任意取2个作业i 和 j。且ti < tj。交换ti和tj的顺序。则新等待时间变成b0 b1 b2 .... b(i-1) bi b(i+1) ..... b(j-1) bj b(j+1) ... bn 其中b0 + b1 + ... + b(i-1) + bi与原来的a相等。 b(i+1) = t1 + t2 + ... + t(i-1) + tj > t1 + t2 + ... + t(i-1) + ti = a(i+1) 依次类推之后bx > ax 其中i < x < j+1.之后b与a又相等。所以任意交换后，等待时间变大。所以最小作业优先的等待时间最小。所以平均周转时间最短。

我要举报

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息