Когда SJF хуже, чем FCFS?

Question

В операционных системах суперкомпьютеров, которые одновременно выполняют большое количество задач, есть ли ситуация, когда политика SJF занимает больше времени, чем политика FCFS, если говорить о метрике времени ожидания?

Можно предположить, что в системе присутствует более одного ядра.

Answer 1

Сначала я думал, что это невозможно, потом я потратил некоторое время и, наконец, пришел к такому результату:

Да, это может быть.

Предположим, что готовая очередь заполнена процессами с равным временем пакетной обработки (all = x):

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

Теперь в этом случае, что будет делать FCFS, процесс, который будет первым, будет выделен ЦП, а затем следующий процесс, который будет первым, будет выделен ЦП и т. Д. Без потери времени.

Но то, что сделает SJF:сначала он найдет задание с наименьшим временем посылки из доступных заданий в очереди готовности, что в данном случае является пустой тратой времени, поскольку все имеют равные времена посылки, и SJF в конечном итоге будет обходить очередь готовности без любой плодотворный результат.