Минимальная продолжительность потока

Ключевые слова и синонимы

Время отклика (Response time); длительность пребывания (Sojourn time)

Постановка задачи

Задача заключается в эффективном планировании заданий в системе с множеством ресурсов для обеспечения хорошего качества обслуживания. В литературе по планированию было рассмотрено несколько моделей для моделирования постановки задачи и изучено несколько различных метрик качества. В данной статье рассматривается следующая модель: имеется несколько одинаковых машин, и задания выпускаются с течением времени. Каждое задание характеризуется своим размером, то есть объемом требований по обработке, необходимым ему для выполнения, и временем выпуска, ранее которого оно не может быть спланировано. В этой модели Леонарди и Раз исследовали задачу минимизации средней продолжительности потока для заданий, где продолжительность потока – это длительность времени с момента выпуска задания до окончания выполнения требований по обработке. Продолжительность потока также называется временем отклика или длительностью пребывания и является очень естественной и часто используемой метрикой качества расписания.

Нотация

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

Основные результаты

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

Для случая, когда вытеснение не разрешено, Келлерер, Таутенхан и Вёгингер [6] предложили аппроксимационный алгоритм с коэффициентом [math]\displaystyle{ O(n^{1/2}) }[/math] для минимизации продолжительности потока на одной машине, а также показали, что ни один алгоритм с полиномиальным временем выполнения не может иметь коэффициента аппроксимации [math]\displaystyle{ n^{1/2 - \epsilon} }[/math] для любого [math]\displaystyle{ \epsilon \gt 0 }[/math], если только не выполняется соотношение P=NP.

Леонарди и Раз [8] представили первые нетривиальные результаты по минимизации средней продолжительности потока на нескольких машинах. Позже более простое представление этоих результатов было дано Леонарди в работе [7]. Основной результат [8] состоит в следующем.

Теорема 1 [8]. На нескольких машинах алгоритм SRPT является [math]\displaystyle{ O(min(log(n/m), \; log \; P)) }[/math]-конкурентным для минимизации средней продолжительности потока, где P – отношение максимального размера задания к минимальному.

Они также дали соответствующую нижнюю границу коэффициента конкурентоспособности (с точностью до постоянных коэффициентов).

Теорема 2 [8]. Для задачи минимизации продолжительности потока на нескольких машинах любой онлайновый алгоритм имеет коэффициент конкурентоспособности [math]\displaystyle{ \Omega(min(log(n/m), \; log \; P)) }[/math], даже если разрешена рандомизация.

Заметим, что минимизация средней продолжительности потока эквивалентна минимизации общей его продолжительности. Предположим, что каждое задание выплачивает 1 доллар за каждую единицу времени, когда оно живо (т. е. не завершено), тогда сумма полученных платежей равна общей продолжительности потока. Суммируя оплату за каждый временной шаг, общую продолжительность потока можно выразить как сумму по количеству незавершенных заданий в каждую единицу времени. Поскольку SRPT работает с заданиями, которые могут быть завершены как можно скорее, интуитивно кажется, что в любой момент времени он должен иметь наименьшее количество незавершенных заданий. Для одной машины это верно, однако для нескольких машин это не так (что показано в примере ниже). Основная идея работы [8] заключалась в том, чтобы показать, что в любой момент времени количество незавершенных заданий в рамках SRPT «по сути» не более чем в O(min(log P)) раз больше, чем при любом другом алгоритме. Для этого авторы разработали технику группировки заданий в логарифмическое число классов в соответствии с их оставшимися размерами и рассуждений о суммарном объеме незавершенной работы в этих классах. С тех пор эта техника нашла широкое применение для получения других результатов. Чтобы получить гарантию, выраженную относительно n, требуются некоторые дополнительные идеи.

Приведенный ниже пример показывает, как SRPT может отклоняться от оптимума при наличии нескольких машин. Этот пример также является ключевым компонентом в построении нижней границы в Теореме 2. Предположим, что у нас имеются две машины, и три задания размером 1, 1 и 2 поступают в момент времени t = 0. SRPT запланирует два задания размером 1 на момент времени t = 0, а затем будет работать над заданием размером 2 в момент времени t = 1. Таким образом, в момент t = 2 у него остается одна единица незавершенной работы. Однако оптимальный алгоритм может запланировать задание размера 2 на момент времени 0 и завершить все эти задания к моменту времени 2. Затем, в момент времени t = 2, поступают еще три задания с размерами 1/2, 1/2 и 1. Опять же, SRPT сначала будет работать над заданиями размера 1/2, и можно увидеть, что у него будет два незавершенных задания с оставшимся объемом работы 1/2 у каждого в момент t = 3, в то время как оптимальный алгоритм может закончить все эти задания к моменту 3. Эта схема продолжается, давая три задания размером 1/4, 1/4 и 1/2 при t = 3 и так далее. После k шагов у SRPT останется k заданий с размерами [math]\displaystyle{ 1/2, 1/4, 1/8, ... , 1/2^{k - 2}, 1/2^{k - 1}; 1/2^{k - 1} }[/math], тогда как у оптимального алгоритма не останется ни одного задания. При этом соперник может давать 2 задания размером [math]\displaystyle{ 1/2^k }[/math] каждые [math]\displaystyle{ 1/2^k }[/math] единиц времени в течение длительного времени, что означает, что SRPT может быть в [math]\displaystyle{ \Omega(log \; P) }[/math] раз хуже оптимального.

В своей работе Леонарди и Раз также рассмотрели оффлайновые алгоритмы для расписания без вытеснения.

Теорема 3 [8]. Существует полиномиальный по времени оффлайновый алгоритм, который достигает коэффициента аппроксимации [math]\displaystyle{ O(n^{1/2} \; log \; n/m) }[/math] при минимизации средней продолжительности потока на m машинах без вытеснения.

Для доказательства этого результата авторы предложили общую технику преобразования расписания с вытеснением в расписание без вытеснения с потерей [math]\displaystyle{ O(n^{1/2}) }[/math] в коэффициенте аппроксимации. Они также показали почти совпадающую нижнюю границу. В частности,

Теорема 4 [8]. Ни один алгоритм с полиномиальным временем выполнения для минимизации общей продолжительности потока на нескольких машинах без вытеснения не может иметь коэффициент аппроксимации [math]\displaystyle{ O(n^{1/3 - \epsilon}) }[/math] для любого [math]\displaystyle{ \epsilon \gt 0 }[/math], если только не выполняется P=NP.

Расширения

С момента публикации этих результатов они были расширены по нескольким направлениям. Вспомним, что алгоритм SRPT является как вытесняющим, так и мигрирующим. Авербух, Азар, Леонарди и Регев [2] предложили онлайновый алгоритм планирования, который не является мигрирующим и при этом дает коэффициент конкурентоспособности [math]\displaystyle{ O(min(log(n/m), \; log \; P)) }[/math]. Авраами и Азар [1] представили онлайн-алгоритм с еще более ограниченным коэффициентом конкурентоспособности [math]\displaystyle{ O(min(log \; P, \; log(n/m))) }[/math]. Их алгоритм, помимо того, что не поддерживает миграцию, распределяет задание на машину сразу же по его поступлении. Недавно Гарг и Кумар [4, 5] распространили эти результаты на ситуацию, когда машины имеют неодинаковую скорость. Также были исследованы другие связанные проблемы и условия, такие как минимизация растяжения (определяемого как продолжительность потока, деленная на размер задания), минимизация взвешенной продолжительности потока, а также условие без предвидения, когда размер задания не известен в момент его поступления. Более подробную информацию можно найти в обзоре Прухса, Сгалла и Торнга [9].

Применение

Рассматриваемая здесь метрика продолжительности потока является одной из наиболее широко используемых метрик качества обслуживания, поскольку она соответствует количеству времени, которое приходится ждать до завершения задания. Рассматриваемая здесь модель планирования естественным образом возникает при наличии нескольких ресурсов и нескольких агентов, которые конкурируют за обслуживание этих ресурсов. Например, рассмотрим вычислительную систему с несколькими функционально однородными процессорами, где задания подаются пользователями произвольно с течением времени. Поддерживая низкое среднее время отклика, мы также поддерживаем низкий уровень разочарования пользователей. Эта модель не обязательно ограничивается компьютерными системами. В продуктовом магазине каждый кассир может рассматриваться как машина, а пользователи, стоящие в очереди на кассу, – как задания. Продолжительность потока пользователя – это время, потраченное на ожидание, пока он завершит свой расчет с кассиром. Конечно, во многих приложениях существуют дополнительные ограничения: например, вытеснение заданий может быть невыполнимым, или клиенты могут ожидать определенной справедливости – например, люди могут предпочесть, чтобы их обслуживали в продуктовом магазине в порядке очереди.

Открытые вопросы

Онлайновый алгоритм Леонарди и Раза также является самым известным оффлайновым аппроксимационным алгоритмом для этой задачи. В частности, неизвестно, существует ли аппроксимация с коэффициентом O(1) даже для случая двух машин. Решить этот вопрос было бы очень интересно. В смежной работе Бансал [3] рассмотрел задачу расчета немигрирующих расписаний для постоянного числа машин. Он предложил алгоритм, который выдает решение с коэффициентом аппроксимации [math]\displaystyle{ 1 + \epsilon }[/math] для любого [math]\displaystyle{ \epsilon \gt 0 }[/math] за время [math]\displaystyle{ n^{O(log \; n / \epsilon^2)} }[/math]. Это говорит о возможности создания для этой задачи схемы аппроксимации с полиномиальным временем выполнения – по крайней мере, для случая постоянного числа машин.

См. также

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

Литература

1. Avrahami, N., Azar, Y.: Minimizing total flow time and completion time with immediate dispacthing. In: Proceedings of 15th SPAA, pp. 11-18.(2003)

2. Awerbuch, B., Azar, Y., Leonardi, S., Regev, O.: Minimizing the flow time without migration. SIAM J. Comput. 31, 1370-1382 (2002)

3. Bansal, N.: Minimizing flow time on a constant number of machines with preemption. Oper. Res. Lett. 33, 267-273 (2005)

4. Garg, N., Kumar, A.: Better algorithms for minimizing average flow-time on related machines. In: Proceesings of ICALP, pp. 181-190(2006)

5. Garg, N., Kumar, A.: Minimizing average flow time on related machines. In: ACM Symposium on Theory of Compuring (STOC), pp. 730-738 (2006)

6. Kellerer, H., Tautenhahn, T., Woeginger, G.J.: Approximability and nonapproximability results for minimizing total flow time on a single machine. SIAM J. Comput. 28,1155-1166 (1999)

7. Leonardi, S.: A simpler proof of preemptive flow-time approximation. Approximation and On-line Algorithms. In: Bampis, E. (ed.) Lecture Notes in Computer Science. Springer, Berlin (2003)

8. Leonardi, S., Raz, D.: Approximating total flow time on parallel machines. In: ACM Symposium on Theory of Computing (STOC), pp. 110-119(1997)

9. Pruhs, K., Sgall, J., Torng, E.: Online scheduling. In: Handbook on Scheduling: Algorithms, Models and Performance Analysis, CRC press (2004). Symposium on Theory of Computing (STOC), pp. 110-119. (1997)