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

Вспомним, что онлайновый алгоритм 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>.