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

Материал из WEGA
(Новая страница: «Ключевые слова и синонимы Продолжительность потока; время отклика Постановка задачи Эв…»)
 
 
(не показано 11 промежуточных версий 1 участника)
Строка 1: Строка 1:
Ключевые слова и синонимы
== Ключевые слова и синонимы ==
Продолжительность потока; время отклика
Продолжительность потока; время отклика


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


Дано:
Множество m идентичных компьютеров и множество n заданий 1, 2, …, n. Каждому заданию j присвоены дата запуска rj и продолжительность обработки pj. Обозначим за I множество допустимых экземпляров входных данных.


Цель:
'''Дано:'''
Цель заключается в минимизации продолжительности среднего потока (или среднего времени отклика) заданий. Обозначим за Cj время завершения выполнения задания j системой. Продолжительность потока или время отклика Fj задания j определяется как Fj = Cj — rj. Цель заключается в минимизации значения


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


Поскольку n является частью входных данных, задача эквивалентна минимизации общей продолжительности потока, т. е.


Оффлайновые и онлайновые конфигурации
'''Цель:'''
В оффлайновой конфигурации экземпляр входных данных полностью известен алгоритму. В частности, для любого значения j = 1... n алгоритму известны rj и pj.
 
Цель заключается в минимизации продолжительности ''среднего потока'' (или ''среднего времени отклика'') заданий. Обозначим за <math>C_j \;</math> время завершения выполнения задания j системой. Продолжительность потока или время отклика <math>F_j \;</math> задания j определяется как <math>F_j = C_j - r_j \;</math>. Цель заключается в минимизации значения
 
<math>min \frac{1}{n} \sum_{j = 1}^n F_j</math>.
 
 
Поскольку n является частью входных данных, задача эквивалентна минимизации ''общей'' продолжительности потока, т. е. <math>\sum_{j = 1}^n F_j</math>.
 
'''Оффлайновые и онлайновые конфигурации'''
 
В ''оффлайновой конфигурации'' экземпляр входных данных полностью известен алгоритму. В частности, для любого значения 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].


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


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


В оффлайновом случае p^ является коэффициентом аппроксимации алгоритма. В онлайновом случае будем называть p^ коэффициентом конкурентоспособности A.
<math>\rho_A = max_{I \in \mathcal{I}} \frac{A(I)}{OPT(I)}</math>.
Вытеснение
Если вытеснение разрешено, обработка задания может быть прервана и возобновлена после завершения других заданий в промежутке. Как будет показано далее, вытеснение необходимо для разработки эффективных алгоритмов на базе рассматриваемой структуры [5,6].


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


Алгоритмы
В оффлайновом случае <math>\rho_A \;</math> является ''коэффициентом аппроксимации'' алгоритма. В онлайновом случае будем называть <math>\rho_A \;</math> ''коэффициентом конкурентоспособности'' A.
Рассмотрим любое задание 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].
'''Вытеснение'''


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


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


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


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


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


Литература
Наилучшей известной эвристикой для минимизации средней продолжительности потока при разрешенном вытеснении является эвристика ''«наименьшее оставшееся время обработки»'' (shortest remaining processing time, SRPT). В любое время t эвристика SRPT выполняет «повисшее» задание j, для которого <math>x_j(t) \;</math> минимально. Если вытеснение не разрешено, эта эвристика превращается в эвристику ''«сначала самое короткое задание»'' (shortest job first, SJF): в начале выполнения плана или при завершении задания алгоритм выбирает «повисшее» задание с наименьшим временем обработки и выполняет его до завершения.
 
 
'''Сложность'''
 
Рассматриваемая задача является полиномиально разрешимой на единичном компьютере с разрешенным вытеснением [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].
 
 
'''Расширения'''
 
Для вышеописанных сценариев было предложено немало расширений, в частности, для онлайнового случая с разрешенным вытеснением. Большинство предположений касались мощности алгоритма или знания экземпляра входных данных. В первом случае представляет интерес вариант, в котором алгоритм выполняется на более быстрых компьютерах, нежели его оптимальный аналог. Этот аспект обсуждался в работе [4]. Ее авторы доказали, что даже небольшое повышение скорости приводит к тому, что эффективность некоторых простых эвристик будет приближена к оптимальной.
 
 
Что до знания алгоритмом экземпляра входных данных, любопытным вариантом онлайновой конфигурации, встречающимся во многих современных практических приложениях, является вышеупомянутый подход с отсутствием предвидения. Этот аспект рассматривался в работах [1, 3]. В частности, авторы [1] доказали, что рандомизированный вариант эвристики MLF, описанной выше, позволяет получить коэффициент конкурентоспособности, который в среднем отличается от оптимума не более чем на полилогарифмический коэффициент.
 
== Применение ==
Первой и основной сферой приложения политик планирования является распределение ресурсов по процессам в многозадачных операционных системах [11]. В частности, использование эвристик, подобных «сначала самое короткое задание», а именно эвристики MLF, документировано в таких широко распространенных ОС, как UNIX и WINDOWS NT [8, 11]. Впоследствии рассматривалось их применение в других областях – таких как доступ к веб-ресурсам [2].
 
== Открытые вопросы ==
Алгоритмы на основе эвристик типа «сначала самое короткое задание» в недавнем прошлом активно исследовались. Однако некоторые вопросы остаются нерешенными. В частности, для оффлайнового случая с параллельными компьютерами до сих пор не найдено неконстантной нижней границы аппроксимации. А для онлайнового случая с параллельными компьютерами не известно строгой нижней границы при отсутствии предвидения. Актуальная нижняя граница <math>\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)
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
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)
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)
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
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
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)
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)
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)
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)
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)
11. Tanenbaum, A.S.: Modern Operating Systems. Prentice-Hall, Englewood Cliffs (1992)
[[Категория: Совместное определение связанных терминов]]

Текущая версия от 11:23, 7 декабря 2024

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

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

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

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