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

Обозначим за <math>\mathcal{J} = \{ 1, 2, ..., n \}</math> множество заданий во входном экземпляре задачи. Каждое задание j характеризуется временем освобождения <math>r_j</math> и требованием к обработке <math>p_j</math>. В онлайновом режиме задание j сообщается планировщику только в момент времени <math>r_j</math>. Еще одним ограничением является режим с отсутствием предвидения, в котором в момент <math>r_j</math> раскрывается только существование задания j; в частности, <math>p_j</math> планировщику неизвестно до тех пор, пока задание не выполнит свое требование к обработке и не покинет систему. Пусть имеется расписание, тогда время завершения <math>c_j</math> задания – это самое раннее время, в которое задание j получает объем обслуживания <math>p_j</math>. Продолжительность потока <math>f_j</math> задания j определяется как <math>c_j - r_j</math>. Протяженность задания определяется как отношение времени потока к его объему. Протяженностью также называют нормализованную продолжительность потока или замедление, и она является естественной мерой справедливости, поскольку измеряет время ожидания задания на единицу полученного обслуживания. Расписание называется вытесняющим, если задание может быть прервано произвольно, и его выполнение может быть возобновлено позже с момента прерывания без каких-либо штрафов. Хорошо известно, что вытеснение необходимо для получения разумных гарантий времени потока даже в оффлайновом режиме [5].

Однако алгоритм SRPT часто критикуют за то, что он может привести к «зависанию» заданий, в случае которого некоторые задания могут откладываться на неопределенное время. Например, рассмотрим последовательность, в которой задание размера 3 поступает в момент времени t = 0, а затем в течение длительного времени одно задание размера 1 поступает каждую единицу времени, начиная с t = 1. При использовании алгоритма SRPT задание размера 3 будет отложено до тех пор, пока не перестанут поступать задания размера 1. С другой стороны, если целью является минимизация максимальной продолжительности потока, то легко увидеть, что оптимальным алгоритмом является алгоритм First in First Out (FIFO). Однако FIFO может работать очень плохо с точки зрения средней продолжительности потока (например, множество маленьких заданий может застрять из-за очень большого задания, которое прибыло чуть раньше). Естественным способом сбалансировать среднюю и наихудшую производительность является рассмотрение lp-норм продолжительности потока и протяженности, где lp-норма последовательности x 1 ; xn ; xi )1/p. xi )1/p. определяется как

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