1

问题 ：

五个批处理作业 A 到 E 几乎同时到达计算机中心。他们估计运行时间为 10、6、2、4 和 8 分钟。它们的（外部确定的）优先级分别为 3、5、2、1 和 4，其中 5 是最高优先级。确定平均过程周转时间。忽略进程切换开销。对于 Round Robin Scheduling，假设系统是多道程序，并且每个作业都获得了 CPU 的公平份额。所有作业都完全受 CPU 限制。

解决方案 #1以下解决方案来自此页面：

对于循环，在前 10 分钟内，每个作业获得 1/5 的 CPU。在 10 分钟结束时，C 结束。在接下来的 8 分钟内，每个作业获得 1/4 的 CPU，之后 D 完成。然后剩下的三个作业中的每一个都在 6 分钟内获得 1/3 的 CPU，直到 B 完成，依此类推。五项作业的完成时间分别为 10、18、24、28、30，平均为 22 分钟。

解决方案 #2以下解决方案来自康奈尔大学，可以在此处找到，并且与前一个解决方案明显不同，即使问题以完全相同的形式给出（顺便说一下，这个解决方案对我来说更有意义）：

请记住，周转时间是作业到达和作业完成之间经过的时间量。由于我们假设所有作业都在时间 0 到达，因此周转时间将只是它们完成的时间。(a) 循环：下表列出了在每个时间段内将处理哪些作业。* 表示作业在该时间段内完成。

1 2 3 4 5  6 7 8  9 10  11 12 13 14  15 16 17 18  19 20 21  22 23 24  25 26  27 28  29 30  
A B C D E  A B C* D E   A  B  D  E   A  B  D* E   A  B  E   A  B* E   A  E   A  E*  A  A*

结果是不同的：例如，在第一个中，C 在 10 分钟后完成，而在第二个中，C 在 8 分钟后完成。

哪一个是正确的，为什么？我很困惑..提前谢谢！

4

2 回答 2

1

问题是不同的。第一个问题没有指定时间量，因此您必须假设时间量与一分钟相比非常小。第二个问题清楚地指定了一分钟的调度程序量。

第二种解决方案的奥秘在于为什么它假定任务按字母顺序运行。我只能假设这是在整个课程中做出的假设，因此学生应该知道在这里做。

于 2012-03-28T23:47:34.650 回答
0

事实上，不存在所谓的“正确”RR 算法。RR 只是一系列算法，基于以循环顺序调度多个任务的通用概念。实现可能会有所不同（例如，您可能会考虑任务优先级，或者您可能会丢弃它们，或者您可以手动将优先级设置为任务长度或其他任何函数）。

所以答案是——两种算法似乎都是正确的，它们只是不同而已。

于 2012-03-28T23:46:01.607 回答