Минимизация продолжительности потока: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Строка 22: Строка 22:
'''Оффлайновые и онлайновые конфигурации'''
'''Оффлайновые и онлайновые конфигурации'''


В оффлайновой конфигурации экземпляр входных данных полностью известен алгоритму. В частности, для любого значения j = 1... n алгоритму известны rj и pj.
В ''оффлайновой конфигурации'' экземпляр входных данных полностью известен алгоритму. В частности, для любого значения j = 1, ..., n алгоритму известны <math>r_j \;</math> и <math>p_j \;</math>.


Напротив, в ''онлайновой конфигурации'' в любой момент времени t алгоритму известно только множество задач, запущенных до времени t.


Напротив, в онлайновой конфигурации в любой момент времени t алгоритму известно только множество задач, запущенных до времени t.


Обозначим за A и OPT рассматриваемый алгоритм и оптимальный оффлайновый алгоритм для этой задачи, соответственно. Аналогичным образом A(I) и OPT(I) обозначают стоимость определенного экземпляра входных данных I.


Обозначим за A и OPT рассматриваемый алгоритм и оптимальный оффлайновый алгоритм для этой задачи, соответственно. Аналогичным образом A(I) и OPT(I) обозначают стоимость определенного экземпляра входных данных I.


'''Предположения для онлайнового случая'''


Предположения для онлайнового случая
Можно также сделать предположения о знании алгоритмом продолжительности обработки каждого задания. В частности, стоит иметь в виду важный случай, часто встречающийся в практических приложениях, в котором pj полностью неизвестно онлайновому алгоритму до того момента, как выполнение задания будет полностью завершено (''отсутствие предвидения'') [1, 3].


Можно также сделать предположения о знании алгоритмом продолжительности обработки каждого задания. В частности, стоит иметь в виду важный случай, часто встречающийся в практических приложениях, в котором pj полностью неизвестно онлайновому алгоритму до того момента, как выполнение задания будет полностью завершено (отсутствие предвидения) [1, 3].


'''Метрика эффективности'''


Метрика эффективности
Во всех случаях, как это часто происходит в задачах комбинаторной оптимизации, эффективность работы алгоритма измеряется в сравнении с его оптимальным оффлайновым аналогом. В задаче минимизации, аналогичной рассматриваемой, коэффициент конкурентоспособности <math>\rho_A \;</math> определяется следующим образом:


Во всех случаях, как это часто происходит в задачах комбинаторной оптимизации, эффективность работы алгоритма измеряется в сравнении с его оптимальным оффлайновым аналогом. В задаче минимизации, аналогичной рассматриваемой, коэффициент конкурентоспособности определяется следующим образом:
<math>\rho_A = max_{I \in \mathcal{I}} \frac{A(I)}{OPT(I)}</math>.


PA = max
I2I  OPT (I)


В оффлайновом случае <math>\rho_A \;</math> является коэффициентом ''аппроксимации алгоритма''. В онлайновом случае будем называть <math>\rho_A \;</math> ''коэффициентом конкурентоспособности'' A.


В оффлайновом случае p^ является коэффициентом аппроксимации алгоритма. В онлайновом случае будем называть p^ коэффициентом конкурентоспособности A.


Вытеснение
'''Вытеснение'''


Если вытеснение разрешено, обработка задания может быть прервана и возобновлена после завершения других заданий в промежутке. Как будет показано далее, вытеснение необходимо для разработки эффективных алгоритмов на базе рассматриваемой структуры [5,6].
Если ''вытеснение'' разрешено, обработка задания может быть прервана и возобновлена после завершения других заданий в промежутке. Как будет показано далее, вытеснение необходимо для разработки эффективных алгоритмов на базе рассматриваемой структуры [5,6].


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

Версия от 12:07, 6 августа 2018

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

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

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

Эвристики «сначала самое короткое задание» возникают в задачах упорядочения, целью которых является минимизация воспринимаемой задержки для пользователей в многопользовательской или многозадачной системе. В этой задаче алгоритм должен спланировать множество заданий для пула из 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.


Предположения для онлайнового случая

Можно также сделать предположения о знании алгоритмом продолжительности обработки каждого задания. В частности, стоит иметь в виду важный случай, часто встречающийся в практических приложениях, в котором pj полностью неизвестно онлайновому алгоритму до того момента, как выполнение задания будет полностью завершено (отсутствие предвидения) [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 и обозначим за wj(t) количество времени, проведенного A над выполнением задания j до t. Обозначим за xj(t) = pj - wj(t) его оставшееся время обработки в момент t. Наилучшей известной эвристикой для минимизации средней продолжительности потока при разрешенном вытеснении является эвристика наименьшего оставшегося времени обработки (shortest remaining processing time, SRPT). В любое время t, эвристика SRPT выполняет «повисшее» задание j, для которого xj(t) минимально. Если вытеснение не разрешено, эта эвристика превращается в эвристику «сначала самое короткое задание» (shortest job first, SJF): в начале выполнения плана или при завершении задания алгоритм выбирает «повисшее» задание с наименьшим временем обработки и выполняет его до завершения.


Сложность

Рассматриваемая задача является полиномиально разрешимой на единичном компьютере с вытеснением [9,10]. Если вытеснение допускается, то оптимальным для одного компьютера является подход SRPT. На параллельных компьютерах наилучшая известная верхняя граница для случая с разрешенным вытеснением достигается алгоритмом SRPT, который является O(logmin n/m; P)-аппроксимируемым [6], где P – отношение между самым большим и самым малым временем обработки для данного экземпляра. Заметим, что алгоритм SRPT является онлайновым, так что предыдущий результат выполняется также и для онлайнового случая. Кроме того, в [ ] было доказано, что в онлайновом случае эта нижняя граница является строгой. Для оффлайнового случая с разрешенным вытеснением не найдено неконстантной нижней границы.


В случае с отсутствием вытеснения ни один оффлайновый алгоритм не способен улучшить Q (nll3~€)-аппроксимацию, для любого e > 0, а наилучшая верхняя граница составляет O(n/m log(n/m)) [6]. В случае с единственным компьютером верхняя и нижняя границы приобретают вид [5].


Расширения Для вышеописанных сценариев было предложено немало расширений, в частности, для онлайнового случая с разрешенным вытеснением. Большинство предположений касались мощности алгоритма или знания экземпляра входных данных. В первом случае представляет интерес вариант, в котором алгоритм выполняется на более быстрых компьютерах, нежели его оптимальный аналог. Этот аспект обсуждался в работе [4]. Ее авторы доказали, что даже небольшое повышение скорости приводит к тому, что некоторые простые эвристики могут продемонстрировать эффективность, близкую к оптимальной.


Что до знания алгоритмом экземпляра входных данных, любопытным вариантом онлайновой конфигурации, встречающимся во многих современных практических приложениях, является вышеупомянутый подход с отсутствием предвидения. Этот аспект рассматривался в [1,3]. В частности, авторы [ ] доказали, что рандомизированный вариант эвристики MLF, описанный выше, позволяет получить коэффициент конкурентоспособности, который в среднем отличается от оптимума не более чем на полилогарифмический коэффициент.

Применение

Первой и основной сферой приложения политик планирования является распределение ресурсов по процессам в многозадачных операционных системах [ ]. В частности, использование эвристик, подобных «сначала самое короткое задание», в особенности эвристики MLF, документировано в таких широко распространенных ОС, как UNIX и WINDOWS NT [8,11]. Впоследствии рассматривалось их применение в других областях – таких как доступ к веб-ресурсам [2].

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

Алгоритмы на основе эвристик типа «сначала самое короткое задание» в недавнем прошлом активно исследовались. Однако некоторые вопросы остаются нерешенными. В частности, для оффлайнового случая с параллельными компьютерами до сих пор не найдено неконстантной нижней границы аппроксимации. А для онлайнового случая с параллельными компьютерами не известно строгой нижней границы при отсутствии предвидения. Актуальная нижняя граница £?(logn) была получена для конфигурации с одним компьютером [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)