Планирование с учетом наименьшего прошедшего времени обработки: различия между версиями

'''Теорема 2 [1]. SETF является <math>(1 + \epsilon)</math>-скоростным, <math>O(log^2 P)</math>-конкурентным алгоритмом для минимизации средней растяжимости, где P – отношение максимального размера задания к минимальному. С другой стороны, даже при скорости O(1) любой алгоритм без предвидения, по меньшей мере, <math>\Omega(log \; P)</math>-конкурентен. Любопытно, что с точки зрения n любой алгоритм без предвидения должен быть <math>\Omega(n)</math>-конкурентным даже при ускорении O(1). Более того, SETF является O(n)-конкурентным (даже без дополнительного ускорения).'''

'''Для специального случая, когда все задания поступают в момент времени 0, алгоритм SETF является оптимальным вплоть до константных коэффициентов. Он O(logP)-конкурентен (без дополнительного ускорения). Более того, любой алгоритм без предвидения должен быть <math>\Omega(log \; P)</math>-конкурентным даже при ускорении порядка O(1).'''

Ключевой идеей вышеприведенного результата является связь между алгоритмами SETF и SRPT. Во-первых, за счет (1 + <math>\epsilon</math>)-ускорения можно показать, что SETF не хуже MLF в случае, когда пороги имеют степень (1 + <math>\epsilon</math>). Во-вторых, поведение MLF на экземпляре I может быть связано с поведением алгоритма Shortest Job First (SJF) на другом экземпляре I0, полученном из I путем разделения каждого задания на логарифмическое число заданий с геометрически возрастающими размерами. Наконец, производительность SJF связана с SRPT при помощи еще одного ускорения с коэффициентом (1 + <math>\epsilon</math>).

Вышеприведенные нижние границы несколько удивительны, поскольку SRPT и FIFO оптимальны для случая p = 1 и p = 1 для времени потока.