Минимизация продолжительности потока
Ключевые слова и синонимы
Продолжительность потока; время отклика
Постановка задачи
Эвристики «сначала самое короткое задание» возникают в задачах упорядочения, целью которых является минимизация воспринимаемой задержки для пользователей в многопользовательской или многозадачной системе. В этой задаче алгоритм должен спланировать множество заданий для пула из m идентичных компьютеров. Для каждого задания известны срок запуска и продолжительность обработки. Цель заключается в минимизации среднего времени, потраченного на выполнение задания системой. Это обычно считается подходящей метрикой для оценки качества услуги, предоставляемой системой интерактивным пользователям. Формальное определение задачи оптимизации выглядит следующим образом.
Дано:
Множество m идентичных компьютеров и множество n заданий 1, 2, ..., n. Каждому заданию j присвоены срок запуска [math]\displaystyle{ r_j \; }[/math] и продолжительность обработки [math]\displaystyle{ p_j \; }[/math]. Обозначим за [math]\displaystyle{ \mathcal{I} }[/math] множество допустимых экземпляров входных данных.
Цель:
Цель заключается в минимизации продолжительности среднего потока (или среднего времени отклика) заданий. Обозначим за [math]\displaystyle{ C_j \; }[/math] время завершения выполнения задания j системой. Продолжительность потока или время отклика [math]\displaystyle{ F_j \; }[/math] задания j определяется как [math]\displaystyle{ F_j = C_j - r_j \; }[/math]. Цель заключается в минимизации значения
[math]\displaystyle{ min \frac{1}{n} \sum_{j = 1}^n F_j }[/math].
Поскольку n является частью входных данных, задача эквивалентна минимизации общей продолжительности потока, т. е. [math]\displaystyle{ \sum_{j = 1}^n F_j }[/math].
Оффлайновые и онлайновые конфигурации
В оффлайновой конфигурации экземпляр входных данных полностью известен алгоритму. В частности, для любого значения j = 1, ..., n алгоритму известны [math]\displaystyle{ r_j \; }[/math] и [math]\displaystyle{ p_j \; }[/math].
Напротив, в онлайновой конфигурации в любой момент времени t алгоритму известно только множество задач, запущенных до времени t.
Обозначим за A и OPT рассматриваемый алгоритм и оптимальный оффлайновый алгоритм для этой задачи, соответственно. Аналогичным образом A(I) и OPT(I) обозначают стоимость определенного экземпляра входных данных I.
Предположения для онлайнового случая
Можно также сделать предположения о знании алгоритмом продолжительности обработки каждого задания. В частности, стоит иметь в виду важный случай, часто встречающийся в практических приложениях, в котором [math]\displaystyle{ p_j \; }[/math] полностью неизвестно онлайновому алгоритму до того момента, как выполнение задания будет полностью завершено (отсутствие предвидения) [1, 3].
Метрика эффективности
Во всех случаях, как это часто происходит в задачах комбинаторной оптимизации, эффективность работы алгоритма измеряется в сравнении с его оптимальным оффлайновым аналогом. В задаче минимизации, аналогичной рассматриваемой, коэффициент конкурентоспособности [math]\displaystyle{ \rho_A \; }[/math] определяется следующим образом:
[math]\displaystyle{ \rho_A = max_{I \in \mathcal{I}} \frac{A(I)}{OPT(I)} }[/math].
В оффлайновом случае [math]\displaystyle{ \rho_A \; }[/math] является коэффициентом аппроксимации алгоритма. В онлайновом случае будем называть [math]\displaystyle{ \rho_A \; }[/math] коэффициентом конкурентоспособности A.
Вытеснение
Если вытеснение разрешено, обработка задания может быть прервана и возобновлена после завершения других заданий в промежутке. Как будет показано далее, вытеснение необходимо для разработки эффективных алгоритмов на базе рассматриваемой структуры [5, 6].
Основные результаты
Алгоритмы
Рассмотрим любое задание j данного экземпляра и время t в плане A и обозначим за [math]\displaystyle{ w_j(t) \; }[/math] количество времени, проведенного A над выполнением задания j до наступления момента t. Обозначим за [math]\displaystyle{ x_j(t) = p_j - w_j(t) \; }[/math] его оставшееся время обработки в момент t.
Наилучшей известной эвристикой для минимизации средней продолжительности потока при разрешенном вытеснении является эвристика «наименьшее оставшееся время обработки» (shortest remaining processing time, SRPT). В любое время t эвристика SRPT выполняет «повисшее» задание j, для которого [math]\displaystyle{ x_j(t) \; }[/math] минимально. Если вытеснение не разрешено, эта эвристика превращается в эвристику «сначала самое короткое задание» (shortest job first, SJF): в начале выполнения плана или при завершении задания алгоритм выбирает «повисшее» задание с наименьшим временем обработки и выполняет его до завершения.
Сложность
Рассматриваемая задача является полиномиально разрешимой на единичном компьютере с разрешенным вытеснением [9, 10]. Если вытеснение допускается, то оптимальным для одного компьютера является подход SRPT. На параллельных компьютерах наилучшая известная верхняя граница для случая с вытеснением достигается алгоритмом SRPT, который является O(log min n/m, P)-аппроксимируемым [6], где P – отношение между самым большим и самым малым временем обработки для данного экземпляра. Заметим, что алгоритм SRPT является онлайновым, так что предыдущий результат выполняется также и для онлайнового случая. Кроме того, в [6] было доказано, что в онлайновом случае эта нижняя граница является строгой. Для оффлайнового случая с разрешенным вытеснением не найдено неконстантной нижней границы.
В случае с отсутствием вытеснения ни один оффлайновый алгоритм не способен улучшить [math]\displaystyle{ \Omega (n^{1/3 - \epsilon}) }[/math]-аппроксимацию, для любого [math]\displaystyle{ \epsilon \gt 0 \; }[/math], а наилучшая верхняя граница составляет [math]\displaystyle{ O(\sqrt{n/m} \; log(n/m)) }[/math] [6]. В случае с единственным компьютером верхняя и нижняя границы приобретают вид [math]\displaystyle{ O(\sqrt{n}) }[/math] и [math]\displaystyle{ \Omega (n^{1/2 - \epsilon}) }[/math], соответственно [5].
Расширения
Для вышеописанных сценариев было предложено немало расширений, в частности, для онлайнового случая с разрешенным вытеснением. Большинство предположений касались мощности алгоритма или знания экземпляра входных данных. В первом случае представляет интерес вариант, в котором алгоритм выполняется на более быстрых компьютерах, нежели его оптимальный аналог. Этот аспект обсуждался в работе [4]. Ее авторы доказали, что даже небольшое повышение скорости приводит к тому, что эффективность некоторых простых эвристик будет приближена к оптимальной.
Что до знания алгоритмом экземпляра входных данных, любопытным вариантом онлайновой конфигурации, встречающимся во многих современных практических приложениях, является вышеупомянутый подход с отсутствием предвидения. Этот аспект рассматривался в работах [1, 3]. В частности, авторы [1] доказали, что рандомизированный вариант эвристики MLF, описанной выше, позволяет получить коэффициент конкурентоспособности, который в среднем отличается от оптимума не более чем на полилогарифмический коэффициент.
Применение
Первой и основной сферой приложения политик планирования является распределение ресурсов по процессам в многозадачных операционных системах [11]. В частности, использование эвристик, подобных «сначала самое короткое задание», а именно эвристики MLF, документировано в таких широко распространенных ОС, как UNIX и WINDOWS NT [8, 11]. Впоследствии рассматривалось их применение в других областях – таких как доступ к веб-ресурсам [2].
Открытые вопросы
Алгоритмы на основе эвристик типа «сначала самое короткое задание» в недавнем прошлом активно исследовались. Однако некоторые вопросы остаются нерешенными. В частности, для оффлайнового случая с параллельными компьютерами до сих пор не найдено неконстантной нижней границы аппроксимации. А для онлайнового случая с параллельными компьютерами не известно строгой нижней границы при отсутствии предвидения. Актуальная нижняя граница [math]\displaystyle{ \Omega(log \; n) }[/math] была получена для конфигурации с одним компьютером [7], и есть причины предполагать, что она оказывается на логарифмический коэффициент ниже границы для параллельного случая.
См. также
Литература
1. Becchetti, L., Leonardi, S.: Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines. J. ACM 51 (4), 517-539 (2004)
2. Crovella, M.E., Frangioso, R., Harchal-Balter, M.: Connection scheduling in web servers. In: Proceedings of the 2nd USENIX Symposium on Internet Technologies and Systems (USITS-99), 1999 pp. 243-254
3. Kalyanasundaram, B., Pruhs, K.: Minimizing flow time nonclairvoyantly. J. ACM 50(4), 551 -567 (2003)
4. Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. J. ACM 47(4), 617-643 (2000)
5. Kellerer, H., Tautenhahn, T., Woeginger, G.J.: Approximability and nonapproximability results for minimizing total flow time on a single machine. In: Proceedings of 28th Annual ACM Symposium on the Theory of Computing (STOC '96), 1996, pp. 418-426
6. Leonardi, S., Raz, D.: Approximating total flow time on parallel machines. In: Proceedings of the Annual ACM Symposium on the Theory of Computing STOC, 1997, pp. 110-119
7. Motwani, R., Phillips, S., Torng, E.: Nonclairvoyant scheduling. Theor.Comput.Sci. 130(1), 17-47 (1994)
8. Nutt, G.: Operating System Projects Using Windows NT. Addison-Wesley, Reading (1999)
9. Schrage, L.: A proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 16(1), 687-690 (1968)
10. Smith, D.R.: A new proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 26(1), 197-199 (1976)
11. Tanenbaum, A.S.: Modern Operating Systems. Prentice-Hall, Englewood Cliffs (1992)
