SJF什么时候比FCFS差？

Question

在同时处理大量任务的超级计算机操作系统中，是否存在 SJF 策略比 FCFS 策略花费更长的等待时间指标的情况？

可以假定系统中存在一个以上的内核。

Answer 1

一开始觉得不可能，后来又折腾了一番，终于得出这样的结果：

可以。

假设就绪队列中充满了突发时间相等的进程(all = x):

Process    Burst time
 P1          x
 P2          x
 P3          x
 P4          x
 .           .
 .           .
 .           .
 Pn          x

现在在这种情况下 FCFS 会做什么，首先出现的进程将被分配 CPU 然后下一个首先出现的进程将被分配 CPU 等等没有浪费任何时间。

但是 SJF 会做的是：它会首先从就绪队列中的可用作业中找到突发时间最短的作业，在这种情况下这是浪费时间，因为所有突发时间都相等 并且 SJF 将最终遍历就绪队列而没有任何结果。