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

Материал из WEGA
Перейти к навигации Перейти к поиску
 
(не показано 5 промежуточных версий этого же участника)
Строка 3: Строка 3:


== Постановка задачи ==
== Постановка задачи ==
Эвристики «сначала самое короткое задание» возникают в задачах упорядочения, целью которых является минимизация воспринимаемой задержки для пользователей в многопользовательской или многозадачной системе. В этой задаче алгоритм должен спланировать множество заданий для пула из m идентичных компьютеров. Для каждого задания известны дата запуска и продолжительность обработки. Цель заключается в минимизации среднего времени, потраченного на выполнение задания системой. Это обычно считается подходящей метрикой качества услуги, предоставляемой системой интерактивным пользователям. Формальное определение задачи оптимизации выглядит следующим образом.
Эвристики «сначала самое короткое задание» возникают в задачах упорядочения, целью которых является минимизация воспринимаемой задержки для пользователей в многопользовательской или многозадачной системе. В этой задаче алгоритм должен спланировать множество заданий для пула из m идентичных компьютеров. Для каждого задания известны срок запуска и продолжительность обработки. Цель заключается в минимизации среднего времени, потраченного на выполнение задания системой. Это обычно считается подходящей метрикой для оценки качества услуги, предоставляемой системой интерактивным пользователям. Формальное определение задачи оптимизации выглядит следующим образом.




'''Дано:'''
'''Дано:'''


Множество m идентичных компьютеров и множество n заданий 1, 2, ..., n. Каждому заданию j присвоены дата запуска <math>r_j \;</math> и продолжительность обработки <math>p_j \;</math>. Обозначим за <math>\mathcal{I}</math> множество допустимых экземпляров входных данных.
Множество m идентичных компьютеров и множество n заданий 1, 2, ..., n. Каждому заданию j присвоены срок запуска <math>r_j \;</math> и продолжительность обработки <math>p_j \;</math>. Обозначим за <math>\mathcal{I}</math> множество допустимых экземпляров входных данных.




Строка 32: Строка 32:
'''Предположения для онлайнового случая'''
'''Предположения для онлайнового случая'''


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




Строка 42: Строка 42:




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




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


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


== Основные результаты ==
== Основные результаты ==
Строка 53: Строка 53:
'''Алгоритмы'''
'''Алгоритмы'''


Рассмотрим любое задание j данного экземпляра и время t в плане A и обозначим за <math>w_j(t) \;</math> количество времени, проведенного A над выполнением задания j до t. Обозначим за <math>x_j(t) = p_j - w_j(t) \;</math> его ''оставшееся время обработки'' в момент t.
Рассмотрим любое задание j данного экземпляра и время t в плане A и обозначим за <math>w_j(t) \;</math> количество времени, проведенного A над выполнением задания j до наступления момента t. Обозначим за <math>x_j(t) = p_j - w_j(t) \;</math> его ''оставшееся время обработки'' в момент t.




Наилучшей известной эвристикой для минимизации средней продолжительности потока при разрешенном вытеснении является эвристика ''«наименьшее оставшееся время обработки»'' (shortest remaining processing time, SRPT). В любое время t, эвристика SRPT выполняет «повисшее» задание j, для которого <math>x_j(t) \;</math> минимально. Если вытеснение не разрешено, эта эвристика превращается в эвристику ''«сначала самое короткое задание»'' (shortest job first, SJF): в начале выполнения плана или при завершении задания алгоритм выбирает «повисшее» задание с наименьшим временем обработки и выполняет его до завершения.
Наилучшей известной эвристикой для минимизации средней продолжительности потока при разрешенном вытеснении является эвристика ''«наименьшее оставшееся время обработки»'' (shortest remaining processing time, SRPT). В любое время t эвристика SRPT выполняет «повисшее» задание j, для которого <math>x_j(t) \;</math> минимально. Если вытеснение не разрешено, эта эвристика превращается в эвристику ''«сначала самое короткое задание»'' (shortest job first, SJF): в начале выполнения плана или при завершении задания алгоритм выбирает «повисшее» задание с наименьшим временем обработки и выполняет его до завершения.




'''Сложность'''
'''Сложность'''


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




В случае с отсутствием вытеснения ни один оффлайновый алгоритм не способен улучшить <math>\Omega (n^{1/3 - \epsilon})</math>-аппроксимацию, для любого <math>\epsilon > 0 \;</math>, а наилучшая верхняя граница составляет <math>O(\sqrt{n/m} \; log(n/m))</math> [6]. В случае с единственным компьютером верхняя и нижняя границы приобретают вид <math>O(\sqrt{n})</math> и <math>\Omega (n^{1/2 - \epsilon})</math> [5].
В случае с отсутствием вытеснения ни один оффлайновый алгоритм не способен улучшить <math>\Omega (n^{1/3 - \epsilon})</math>-аппроксимацию, для любого <math>\epsilon > 0 \;</math>, а наилучшая верхняя граница составляет <math>O(\sqrt{n/m} \; log(n/m))</math> [6]. В случае с единственным компьютером верхняя и нижняя границы приобретают вид <math>O(\sqrt{n})</math> и <math>\Omega (n^{1/2 - \epsilon})</math>, соответственно [5].




'''Расширения'''
'''Расширения'''


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




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


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


== Открытые вопросы ==
== Открытые вопросы ==
Алгоритмы на основе эвристик типа «сначала самое короткое задание» в недавнем прошлом активно исследовались. Однако некоторые вопросы остаются нерешенными. В частности, для оффлайнового случая с параллельными компьютерами до сих пор не найдено неконстантной нижней границы аппроксимации. А для онлайнового случая с параллельными компьютерами не известно строгой нижней границы при отсутствии предвидения. Актуальная нижняя граница £?(logn) была получена для конфигурации с одним компьютером [7], и есть причины предполагать, что она оказывается на логарифмический коэффициент ниже границы для параллельного случая.
Алгоритмы на основе эвристик типа «сначала самое короткое задание» в недавнем прошлом активно исследовались. Однако некоторые вопросы остаются нерешенными. В частности, для оффлайнового случая с параллельными компьютерами до сих пор не найдено неконстантной нижней границы аппроксимации. А для онлайнового случая с параллельными компьютерами не известно строгой нижней границы при отсутствии предвидения. Актуальная нижняя граница <math>\Omega(log \; n)</math> была получена для конфигурации с одним компьютером [7], и есть причины предполагать, что она оказывается на логарифмический коэффициент ниже границы для параллельного случая.


== См. также ==
== См. также ==

Текущая версия от 15:47, 15 августа 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.


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

Можно также сделать предположения о знании алгоритмом продолжительности обработки каждого задания. В частности, стоит иметь в виду важный случай, часто встречающийся в практических приложениях, в котором [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)