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

Вспомним, что онлайновый алгоритм Shortest Remaining Processing Time (SRPT), который в любой момент времени работает над заданием с наименьшим оставшимся временем обработки, является оптимальным для минимизации средней продолжительности потока. Однако алгоритм SRPT часто критикуют за то, что он может привести к «зависанию» заданий, в случае которого некоторые задания могут откладываться на неопределенное время. Например, рассмотрим последовательность, в которой задание размера 3 поступает в момент времени t = 0, а затем в течение длительного времени одно задание размера 1 поступает каждую единицу времени, начиная с t = 1. При использовании алгоритма SRPT задание размера 3 будет отложено до тех пор, пока не перестанут поступать задания размера 1. С другой стороны, если целью является минимизация максимальной продолжительности потока, то легко увидеть, что оптимальным алгоритмом является алгоритм First in First Out (FIFO). Однако FIFO может работать очень плохо с точки зрения средней продолжительности потока (например, множество маленьких заданий может застрять из-за очень большого задания, которое прибыло чуть раньше). Естественным способом сбалансировать среднюю и наихудшую производительность является рассмотрение <math>\ell_p</math>-норм продолжительности потока и протяженности, где <math>\ell_p</math>-норма последовательности <math>\chi_1, ..., \chi_n</math> определяется как <math>(\sum_i \chi^p_i)^{1/p}</math>.

Shortest Elapsed Time First (SETF) – это алгоритм без предвидения, который в любой момент времени работает над заданием, получившим на текущий момент наименьший объем обслуживания. Это естественный способ отдать предпочтение коротким заданиям, учитывая отсутствие знания о размерах заданий. Фактически SETF представляет собой непрерывную версию алгоритма многоуровневой обратной связи (Multi-Level Feedback, MLF). К сожалению, SETF (или любой другой детерминированный алгоритм без предвидения) плохо работает в рамках конкурентного анализа, где алгоритм называется c-конкурентным, если для каждого входного экземпляра его производительность не более чем в c раз ниже, чем у оптимального автономного (обладающего предвидением) решения для этого экземпляра [7]. Однако конкурентный анализ может быть слишком пессимистичным в своих гарантиях. Способ обойти эту проблему был предложен Кальянасундарамом и Прусом [6], которые позволили онлайн-планировщику использовать немного более быстрый процессор, чтобы компенсировать отсутствие знаний о будущих поступлениях и размерах заданий. Алгоритм <math>Alg</math> является s-скоростным, c-конкурентным по скорости, где c – отношение наихудшего случая для всех экземпляров I, <math>Alg_s(I)/Opt_1(I)</math>, где <math>Alg_s</math> – значение решения, полученного <math>Alg</math> при использовании s-скоростного процессора, а <math>Opt_1</math> – оптимальное значение при использовании процессора с единичной скоростью. Как правило, наиболее интересные результаты получаются в случаях, когда c мало и s = (1 + <math>\epsilon</math>) для любого произвольного <math>\epsilon > 0</math>.

'''Теорема 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 для времени потока.

'''Теорема 4 [2]. В постановке задачи без предвидения алгоритм SETF является <math>(1 + \epsilon)</math>-скоростным, <math>O(1 / \epsilon^{2 + 2/p})</math>-конкурентным для минимизации <math>\ell_p</math>-норм продолжительности потока. Для минимизации <math>\ell_p</math>-нормы растяжимости SETF является <math>(1 + \epsilon)</math>-скоростным, <math>O(1 / \epsilon^{3 + 1/p} \cdot log^{1 + 1/p} P)</math>-конкурентным.'''