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

Задача связана с планированием динамически поступающих заданий в сценарии, когда требования к обработке заданий неизвестны планировщику. Отсутствие знания о том, сколько времени займет выполнение задания, нередко встречается в реальных системах, где такую информацию может быть трудно или невозможно получить. Цель состоит в том, чтобы составить расписание заданий, обеспечивающего пользователям высокое качество обслуживания. В частности, целью является разработка алгоритмов, имеющих хорошую среднюю производительность и являющихся справедливыми в том смысле, что ни одно подмножество пользователей не получает существенно более низкой производительности по сравнению с другими.

Обозначим за <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].

Вспомним, что онлайновый алгоритм Shortest Remaining Processing Time (SRPT), который в любой момент времени работает над заданием с наименьшим оставшимся временем обработки, является оптимальным для минимизации средней продолжительности потока.

 

 

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 является (1 + <math>\epsilon</math>)-скоростными, 0(l/€2+2lt>)-конкурентным для минимизации <math>\ell_p</math>-норм продолжительности потока. Для минимизации <math>\ell_p</math>-нормы растяжимости SETF является (1 + <math>\epsilon</math>)-скоростным, O(l/e3+1/? - log1+1/p P)-конкурентным.

Наконец, Bansal и Pruhs также рассматривают алгоритм Round Robin (RR) или Processor Sharing, который в любой момент времени делит процессор поровну между незавершенными заданиями. Считается, что RR является идеальной справедливой стратегией, поскольку одинаково относится ко всем незавершенным заданиям. Тем не менее, они показали следующий результат:

Теорема 5. Для любого p > 1 существует e > 0, такое, что даже при наличии в (1 + e) раз более быстрого процессора алгоритм RR не является оптимальным для минимизации <math>\ell_p</math>-норм продолжительности потока. В частности, для e < 1/2p алгоритм RR является (1 + e)-скоростным, ^(п^-^РЩ-конкурентным. Для <math>\ell_p</math>-норм растяжимости RR является Q(n)-конкурентным, как и фактически любой рандомизированный алгоритм без предвидения.

Приведенные выше результаты были расширены по нескольким направлениям. Бансал и Прус [ ] распространили эти результаты на взвешенные <math>\ell_p</math>-нормы продолжительности потока и растяжимости. Чекури, Ханна, Кумар и Гель [4] распространили их результаты на случай нескольких машин. Их алгоритмы особенно элегантны: каждое задание назначается некоторой машине случайным образом, и все задания на определенной машине обрабатываются с помощью алгоритма SRPT или SETF (в зависимости от применимости).

Наиболее первоочередная задача заключается в том, можно ли сократить разрыв между O(log P) и J2(log P) для минимизации средней растяжимости в формулировке без предвидения.