日期:2014-05-17  浏览次数:20601 次

关于最短作业优先经典例题的思考
我是刚学计算机的,在看《现代操作系统(第2版)》机械工业出版社 2005.6
中的最短作业优先的例题是这样的:
……
现在考虑使用最短作业优先算法运行这4个作业,如图2-40b所示。目前周转时间分别为4、8、12和20分钟,平均为11分钟。可以证明最短作业优先是最优的。考虑有4个作业的情况,其运行时间分别为a、b、c、d。第一个作业在时间a结束,第二个在时间a + b结束,以此类推。平均周转时间为(4a + 3b + 2c + d)/4。显然a对平均值影响最大,所以它应是最短作业,其次是b,再次是c,最后的d只影响它自己的周转时间。对任意数目作业的情况,道理完全一样。
有必要指出,只有在所有的作业都可同时运行的情形下,最短作业优先算法才是最优化的。作为一个反例,考虑5个作业,从A到E,运行时间分别是2、4、1、1和1。它们的到达时间是0、0、3、3和3。开始,只能选择A或B,因为其他三个作业还没有到达。使用最短作业优先,将按照A、B、C、D、E的顺序运行作业,其平均等待时间是4.6。但是,按照B、C、D、E、A的顺序运行作业,其平均等待时间则是 4.4。
……
下面没有给出这种情况下的最短平均等待时间是多少,毕竟它只是作为一个例子出现已经达到了反证的目的,没有必要继续深入探讨在这种情况下的最短平均等待时间是多少。
而我刚好有兴趣研究了一下,发现这种情况的最短平均等待时间是3.6秒,而在网上找了下相关论述也没有找到有关于这个例题最短平均等待时间的结论,我就在这里发表一下,希望能够给予大家启发。当然很可能我说的方法早就存在了,但是我这个计算机菜鸟没有接触到,也希望大家不吝赐教。
我的算法是这样的:
先运行作业A,需要2秒,然后等待1秒,再依次运行CDEB,平均等待时间是3.6秒。
结合上文,我觉得这个平均等待时间似乎应该是平均周转时间。


------最佳解决方案--------------------
先运行作业A,需要2秒,然后等待1秒,再依次运行CDEB,平均等待时间是3.6秒。

我想说,有作业到来,不去运行,让系统等待本身就是不合理的,系统讨论的短作业优先,应该是对队列中的作业吧,没有排队,还考虑什么呢。
------其他解决方案--------------------
贼长,
------其他解决方案--------------------
增加了等待时间看起来是不对,问题是它确实达到了节省时间的目的,显然节省时间提高效率是我们的最终目标,如何实现、能否实现是另外的课题。
例题中说:按照B、C、D、E、A的顺序运行作业,其平均等待时间则是 4.4。
为什么不先运行A而先运行B呢,显然体重CDE的到达时间已经被系统知道了才进行的调优。
而我的方案显然比上述两种方案都更加优秀,如果能够实现的话显然是最优的方案。
------其他解决方案--------------------
没人给出有用的意见,看来这个东西没什么意义。